6. Обнаружение и исправление ошибок. Код Хэмминга

При передаче информации всегда существует некоторая вероятность искажения кода. Поэтому необходимо выявлять эти ситуации и исправлять их. Наиболее простая задача - обнаружение одиночной ошибки. При этом предполагается, что наличие более одной ошибки в сообщении маловероятно.

Для обнаружения одиночной ошибки вводят дополнительный разряд, в который заносят 0 или 1, чтобы число единиц было четным или нечетным (последнее предпочтительнее, т.к. в этом случае отсутствует нулевой символ).

Например:

контроль по четности - 10010010 1, 00000000 0;

контроль по нечетности - 10010010 0, 00000000 1.

По сути дела, такая проверка соответствует логической операции XOR (см. выше). Т.е., например: 1011 XOR 1100 = 0111.

При приеме контрольный разряд проверяется и при нарушении четности (нечетности) байт бракуется. При определении контрольного разряда используют сложение по модулю «2».

При передаче блоков информации можно формировать дополнительную строку и заносить туда контрольную сумму блока (или ее дополнение до кода FF - этот метод называют проверкой контрольной суммы). Контрольная сумма выделена жирным шрифтом:

Исходное сообщение		Полученное сообщение
01000110 1	F	01000110 1	F
01001001 1	I	01000001 0	A
01001100 1	L	01001100 1	L
01000101 1	E	01000101 1	E
00000110 0		00001110 1

Рис.4. Получение контрольной суммы

Если контрольные суммы не совпадают при передаче и приеме файла, то он бракуется. При определении контрольной суммы выполняют сложение каждого столбца по модулю «2». Проверка по контрольным суммам (а не по каждому байту) производится для экономии машинных ресурсов, ведь гораздо проще и быстрее сравнить одну пару байтов, чем, например, 4 пары.

Код называется кодом с исправлением ошибок, если всегда из неправильного кодового набора можно получить правильный. Главное для исправления ошибок является то, что необходимо иметь возможность обнаруживать и выделять местоположение ошибочных разрядов. Если местоположение ошибки определено, то ее исправление производится путем замены ошибочного разряда на его инверсию. Код, в котором возможно обнаружить и исправить ошибки, называют помехозащищенным или корректирующим.

Одним из первых корректирующих кодов, для которого одиночная ошибка не только обнаруживается, но и исправляется, является код Хэмминга. Рассмотрим основные принципы его построения.

Пусть сообщение имеет m информативных разрядов и k контрольных разрядов p1p2...pk для проверки на четность. Присвоим десятичное значение позиции каждого из (m+k) разрядов кодового набора, начиная со значения 1 для старшего разряда и заканчивая значением (m+k) для младшего. Контрольные разряды размещаются в позициях:

N=1,2, ...,2^(k-1). (2)

Проведем проверку на четность в k подгруппах кодового набора. Результат каждой проверки на четность записывается как 1 или 0 в зависимости от того, обнаружена ошибка или нет. По результатам этих проверок строится двоичное число ck…с1, равное номеру ошибочного разряда (при значении ноль ошибка отсутствует).

Код Хэмминга содержит информативную часть из m разрядов и контрольную из k разрядов. Получить код Хэмминга - это сформировать контрольные разряды и расставить их в нужные позиции.

Минимальное кодовое расстояние (число несовпадающих разрядов) для кода Хэмминга = 3, т.е. в любых двух кодовых наборах одинаковой длины не может быть меньше трех несовпадающих разрядов (см. рис.5).

Чтобы в код из k разрядов можно было записать значение для (m+k) позиций, должно выполняться условие

2^k>=m+k+1. (3)

Так, например, если m=4, то k=3, а кодовый набор будет иметь семь разрядов (номера контрольных разрядов 1,2,4 по формуле (2)); при m=8 k=4, а номера контрольных разрядов: 1,2,4,8; при m=16 k=5, номера контрольных разрядов: 1,2,4,8,16 и т.д.

Опишем, например, способ построения кода Хэмминга при m=4 и k=3.

На рис.5 приведен перечень кодовых обозначений позиций (c3c2c1) и их номера в десятичной системе счисления (N). Исходя из этого перечня, необходимо проверять на четность те номера битов, в позиции которых стоят 1 (смотри столбцы), т.е. ненулевые позиции:

В частности, в столбце с3 - номера (4,5,6,7); в столбце c2 - (2,3,6,7); и в столбце c1 - (1,3,5,7). Обратите внимание, что в позициях 1,2,4 стоят контрольные разряды р1,р2,р3 (см. формулу (2)), они выделены зеленым. Непосредственно сама информация закодирована только в позициях 3,5,6,7, что соответствует значимым разрядам m1,m2,m3,m4, (выделены желтым).

с3 c2 c1 N

0 0 0 0 (ошибка отсутствует)

0 0 1 1 р1

0 1 0 2 р2

0 1 1 3 m1

1 0 0 4 р3

1 0 1 5 m2

1 1 0 6 m3

1 1 1 7 m4

Рис.5. Номера позиций

с3 - (4,5,6,7); c2 - (2,3,6,7); c1 - (1,3,5,7).

Как уже указывалось, исправление заключается в замене ошибочного разряда на его инверсию.

Если m=6, то с учетом (3) k=4: p1=(1,3,5,7,9); p2=(2,3,6,7,10); p3=(4,5,6,7); p4=(8,9,10).

Опишем, например, способ построения кода Хэмминга при m=4 и k=3.

Дано исходное сообщение: 0 1 0 1

1). пронумеруем номера столбцов от 1 до 7, а ниже – значимые (m) и контрольные разряды (р)

2). Запишем исходное сообщение в позиции значимых разрядов. Это будет строка с1.

3). Ниже выписываем в столбик номера позиций с ненулевыми битами в строке с1 и сразу переводим их в двоичную форму. Под чертой записываем контрольную сумму 1, вычисленную с помощью операцииXOR.

4). В строке с2 повторим исходное сообщение, а в контрольные позиции (1,2,4) вставим биты из полученной контрольной суммы по следующему принципу:

последний (правый) бит вставляем в поз. 1;

предпоследний бит – в поз. 2;

второй бит – в поз. 4. Полученная строка будет являться кодом Хэмминга.

5). Сделаем проверку полученного кода и убедимся, что ошибки нет. Для этого снова выписываем все номера позиций с ненулевыми битами в строке с2 и находим контрольную сумму  2.

6). В строке с3 повторим строку с2, но искусственно введем в один из значимых разрядов (например, в m3 – шестая позиция) ошибочный бит «1» вместо «0».

7). Снова выписываем номера ненулевых элементов из строки с3 и находим контрольную сумму  3. Переводим полученную контрольную сумму в десятичный вид и получаем, что ошибочна 6-я позиция, поэтому для исправления в ней нужно сделать инверсию.

1 2 3 4 5 6 7

p1 p2 m1 p3 m2 m3 m4

передаваемое (исходное) сообщение с1 0 1 0 1

кодовое сообщение (код Хэмминга) с201001 0 1

полученное сообщение с3 0 1 0 0 1 11

по строке с1: 5=0101

7=0111

 1=0010

Проверка правильности кода Хэмминга (по строке с2):

2=0010

5=0101

7=0111

 2=0000 – значит ошибки в коде Хэмминга нет

Проверяем полученное сообщение (строка с3):

2=0010

5=0101

6=0110

7=0111

 3=0110₂=6₁₀

Заметим, что существуют коды, которые обнаруживают и исправляют и более одной ошибки.