Коды Хэмминга

 

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

Такие коды имеют несколько контрольных разрядов (КР), каждый из которых контролирует по чётности свою группу разрядов в слове. Эти группы формируются так, чтобы исследовательный опрос КР указал место сбоя. В КР записывается такая цифра, чтобы количество “1” в контролируемых разрядах было нечётным.

Представим кодовую комбинацию с числом разрядов n=15. Тогда схема формирования КР в коде Хэмминга имеет вид:

Контрольные разряды Номера разрядов
A x   x   x   x   x   x   x   x
B   x x     x x     x x     x x
C       x x x x         x x x x
D               x x x x x x x x

 

КР А контролирует по чётности все нечётные разряды кода. В КРА записывается такая цифра, чтобы количество “1” в нечётных разрядах было нечётным. Таким образом КРА контролирует по чётности все разряды в номерах которых есть “1” в первом разряде (в двоичном представлении).

КР В контролирует по чётности разряды в номерах которых есть “1” во втором разряде.

КР С контролирует по чётности разряды в номерах которых есть в третьем разряде.

КР Д контролирует по чётности разряды в номерах которых есть в четвёртом разряде.

Контрольные разряды могут быть размещены среди информационных различными способами. Наиболее удобно их размещать на 1,2,4,…позициях, так как в этом случае каждый КР принадлежит только одной, соответствующей ему группе разрядов.

Если число КР=К, то длина кодовой комбинации n определяется таким образом:

,

при k=4 . Отсюда можно найти k , так как при работе кода возможны n+1 результатов: ошибки нет, ошибка в 1-м разряде, во 2-м разряде и так долее.

Пример 1. сформируем КР для слова х=01110100101. Длина слова m=11, k=4, n=15. следовательно код Хэмминга должен иметь вид:

АВ0С111D0100101

Для определения значений А, В, С, D решим уравнения:

А+0+1+1+0+0+1+1=1 (mod 2)=1 А=1

В+0+1+1+1+0+0+1=1 (mod 2)=1 В=1

С+1+1+1+0+1+0+1=1 (mod 2)=1 С=0

D+0+1+0+0+1+0+1=1 (mod 2)=1 D=0

Таким образом, слово х в коде Хэмминга примет вид: 110011100100101.

Пример 2. найти ошибку в слове х=110011100101101. для этого сформируем суммы по mod 2 разрядов, контролируемых разрядами А, В, С,D.

A=1+0+1+1+0+0+1+1 (mod 2)=1

B=1+0+1+1+1+0+0+1 (mod 2)=1

C=0+1+1+1+1+1+0+1 (mod 2)=0

D=0+0+1+0+1+1+0+1 (mod 2)=0

Следовательно, ошибка в разряде с номером 1100. Если ошибки нет, то проверка по всем КР даёт номер разряда 0000, которой нет.

Пример 3. Сформируем при наличии ошибок во 2-м и 5-м разрядах слова х=1110001, то есть принято слово x`=1010101.

A=1+1+1+1 (mod 2)=0

B=0+1+0+1 (mod 2)=0

C=0+1+0+1 (mod 2)=0

Таким образом, при двукратной ошибке декодирование даёт номер разряда 111, что неверно.

Незначительное увеличение избыточности кода путём введения дополнительного КР1, осуществляющего проверку на чётность всего кода, позволяет обнаружить все двукратные ошибки. Располагает КР1 на месте “0”–го разряда кода. Признаком наличия двукратной ошибки является равенство нулю функции x` при проверке всех разрядов кода на нечётность и равенство “1” хотя бы одной функции .

Пример 4. Найдём КР1 для слова х=1110001.

A=1+1+0+1=1

B=1+1+0+1=1

C=0+0+0+1=1

I+1+0+0+1 (mod 2)=1 I=1

Таким образом, слово примет вид 11110001.

Пусть принято слово x`=11010101 ошибки во 2-м и 5-м разрядам. Сформируем функции .

A=1+1+1+1 (mod 2)=0

B=0+1+0+1 (mod 2)=0

C=0+1+0+1 (mod 2)=0

I=1+1+0+1+0+1+0+1=1 x`=0

Таким образом, в коде присутствуют 2 ошибки.

Общий недостаток избыточных кодов – они не приспособлены для выполнения арифметической операции.

 

 


 

Глава 14