Помехозащитное кодирование
Простейший код для борьбы с шумом—это контроль четности, он, в частности, широко используется в модемах. Кодирование заключается в добавлении к каждому байту девятого бита таким образом, чтобы дополнить количество единиц в байте до заранее выбранного для кода четного (even) или нечетного (odd) значения. Используя этот код, можно лишь обнаруживать большинство ошибок.
Простейший код, исправляющий ошибки, — это тройное повторение каждого бита. Если с ошибкой произойдет передача одного бита из трех, то ошибка будет исправлена, но если случится двойная или тройная ошибка, то будут получены неправильные данные. Часто коды для исправления ошибок используют совместно с кодами для обнаружения ошибок. При тройном повторении для повышения надежности три бита располагают не подряд, а на фиксированном расстоянии друг от друга.
Использование тройного повторения естественно значительно снижает скорость передачи данных.
рис. 12 Двоичный симметричный канал,
где p — это вероятность безошибочной передачи бита, а q — вероятность передачи бита с ошибкой. Предполагается, что в таком канале ошибки происходят независимо. Далее рассматриваются только такие каналы.
Двоичный симметричный канал реализует схему Бернулли, поэтому вероятность передачи n бит по двоичному симметричному каналу с k ошибками равна Pn(k) = Cnkpn−kqk.
Пример. Вероятность передачи одного бита информации с ошибкой равна q = 0.01 и нас интересует вероятность безошибочной передачи 1000 бит (125 байт). Искомую вероятность можно подсчитать по формуле P1000(0) = C01000 p1000 q0 = 0.991000 ≈ 4.32 * 10-5, т.е. она ничтожно мала.
Добиться минимальности вероятности ошибки при передаче данных можно используя специальные коды. Обычно используют систематические помехозащитные коды. Идея систематических кодов состоит в добавлении к символам исходных кодов, предназначенных для передачи в канале, нескольких контрольных символов по определенной схеме кодирования. Принятая такая удлиненная последовательность кодов декодируется по схеме декодирования в первоначально переданную.
Приемник способен распознавать и/или исправлять ошибки, вызванные шумом, анализируя дополнительную информацию, содержащуюся в удлиненных кодах.
Двоичным (m, n)-кодом называется пара, состоящая из схемы кодирования E : Z2m → Z2n и схемы декодирования D : Z2n → Z2m, где Z2n — множество всех двоичных последовательностей длины n, m < n (случай m = n рассматривается в криптографии).
Функции D и E выбираются так, чтобы функция H = D○T ○E, где T — функция ошибок, с вероятностью, близкой к единице, была тождественной. Функции D и E считаются безошибочными, т. е. функция D ○ E — тождественная (см. рис. 13).
Рис. 13