Некоторые помехоустойчивые коды

Метод контроля четности

Простейшим кодом, создающим условия обнаружения ошибок, является код с проверкой четности. При этом кодировании, для формирования кодового слова каждые 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-битных слов b_i (i =0,1,… L), одно из которых, пусть b_L, контрольное. Алгоритм его вычисления действительно прост:

т.е. контрольное слово является 16-битным поразрядным дополнением числа x. Нетрудно убедиться, что сумма b₀ + b₁ + …. +b_L всегдакратна 2 ¹⁶-1.

Приемник вычисляет дополнение до 1 суммы всех 16-разрядных слов полученного блока (содержащего и контрольную сумму). Если хотя бы один из разрядов результата равен 0, то фиксируется ошибка.

Приведем, в качестве примера, кодовые комбинации, вычисленные по приведенному выше алгоритму, для двухразрядных слов; при этом защищаемый блок должен содержать три таких слова (L=2). В таблице ниже – информационные слова b₀ и b₁ _,а вычисляемое контрольное слово - b₂.

b₀	b₁	b₂

Нетрудно видеть, что сумма b₀ + b₁ + b₂ всегдакратна значению 2²-1=3.

Как контроль по четности, так и способ обнаружения ошибок в блоках стека протоколов ТСР/IP, хорошо «работают» при статистически независимых ошибках. Вместе с тем, при возникновении групповых ошибок в длинных последовательностях бит защищаемого блока данных они теряют свою эффективность. В таких ситуациях более надежны циклические избыточные коды.