Некоторые помехоустойчивые коды
Метод контроля четности
Простейшим кодом, создающим условия обнаружения ошибок, является код с проверкой четности. При этом кодировании, для формирования кодового слова каждые k информационных бит дополняются одним контрольным битом. Этот контрольный бит таков, что общее число «1» в кодовом слове всегда четное. (Контрольный бит в этом случае называют битом четности). Приемник проверяет число «1» в пришедшем слове и, если оно оказывается нечетным, фиксирует наличие ошибки. Таким образом, этот метод позволяет обнаружить ошибочные слова, если они сформировались в результате искажения нечетного числа битов. Уровень избыточности кода составляет 1/(k+1).
Эффективность такого кодирования, в смысле вероятности пропуска ошибочных слов, будет существенно зависеть от статистических характеристик ошибок, которые вносит канал. Рассмотрим две модели этих ошибок.
Модель 1 – случайная групповая ошибка.
Пусть длина кодового слова равна n бит. Определим вектор ошибки 
, где
В предельном варианте плохой помеховой обстановки можно считать, что любой из 
векторов ошибок равновероятен. В этих условиях, вероятность реализации любого вектора 
одинакова, т.е. векторы ошибок с четным и нечетным числом 1 равновероятны. Код с контролем четности не обнаруживает ошибки при четном числе единиц в векторе . Следовательно,
Р[необнаружения ошибки] 
= 0,5. (3.1)
Т.е., вероятность «неудачи» обнаружения указанных групповых ошибок для этого кода оказывается очень высокой.
Модель 2 – случайная битовая ошибка
Будем считать, что ошибки в битах кодового слова являются взаимно независимыми. Пусть p – вероятность ошибки передачи одного бита. Тогда, вероятность искажения j произвольных битов из последовательности n бит будет равна
.
Представим это выражение в виде
. (3.2)
Если учесть, что j – это число искаженных бит и p < ½, то из (3.2) хорошо видно, что вероятность появления на выходе канала слов далеко «отстоящих» от исходного кодового слова, быстро уменьшается с ростом этого «расстояния» (с ростом j). Таким образом, слова на выходе такого канала группируются вблизи исходных кодовых слов.
Рассматриваемый метод терпит неудачу при четном числе искаженных бит, (т.е. при j = 2k, k = 1,2,…, 
). Следовательно, для рассматриваемой модели, вероятность пропуска ошибки может быть представлена в виде
Р[пропуска ошибки] = 
, (3.3)
где 
.
Поскольку обычно p << 1, то в выражении (3.3) можно учитывать лишь первое слагаемое уже при 
.
Так, при n = 32 и p = 
, P[пропуска ошибки] 
. Если бы проверочного бита не было, то P[пропуска ошибки] была бы равна вероятности искажения кадра, которая не меньше вероятности искажения в нем одного произвольного бита. Последняя равна, примерно, 
. Таким образом, добавление бита четности позволило в 1000 раз уменьшить вероятность пропуска ошибки.
3.2.2.2 Обнаружение ошибок в протокольных блоках стека TCP/IP
Функция вычисления контрольного признака (контрольной суммы), добавляемого в блоки данных протоколами стека TCP/IP, весьма проста, что снижает требования к вычислительным ресурсам сетевых узлов.
Предполагается, что защищаемый блок всегда содержит L+1 16-битных слов bi (i=0,1,…L), одно из которых, пусть bL, контрольное. Алгоритм его вычисления действительно прост:
т.е. контрольное слово является 16-битным поразрядным дополнением числа x. Нетрудно убедиться, что сумма b0 + b1 + …. +bL всегдакратна 216-1.
Приемник вычисляет дополнение до 1 суммы всех 16-разрядных слов полученного блока (содержащего и контрольную сумму). Если хотя бы один из разрядов результата равен 0, то фиксируется ошибка.
Приведем, в качестве примера, кодовые комбинации, вычисленные по приведенному выше алгоритму, для двухразрядных слов; при этом защищаемый блок должен содержать три таких слова (L=2). В таблице ниже – информационные слова b0 и b1, а вычисляемое контрольное слово - b2.
| b0 | b1 | b2 |
Нетрудно видеть, что сумма b0 + b1 + b2 всегдакратна значению 22-1=3.
Как контроль по четности, так и способ обнаружения ошибок в блоках стека протоколов ТСР/IP, хорошо «работают» при статистически независимых ошибках. Вместе с тем, при возникновении групповых ошибок в длинных последовательностях бит защищаемого блока данных они теряют свою эффективность. В таких ситуациях более надежны циклические избыточные коды.