Кодирование информации

Код Хэмминга

Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например 11,7.

Такая запись определяет, что комбинация двоичного кода имеет 11 разрядов, из которых 7- информационных и 4 контрольных (7+4=11). Код Хэмминга ориентирован на исправление наиболее вероятных одиночных ошибок в кодовой комбинации. Считается, что ошибка в двух или более битах существенно менее вероятна.

С учетом этого исправление ошибки осуществляется с определенной вероятностью. Для анализа возможности кода исправлять отдельные ошибки введено определение кодового расстояния. Кодовое расстояние (расстояние Хэмминга) между двумя кодовыми комбинациями равно количеству несовпадающих разрядов.

 

V1=0 1 0 1 0 1 0 1

V2=1 1 1 1 0 0 0 0

---------------------------------

d= 1+0+1+0+0+1+0+1=4

Рассмотрим 4 разрешенные кодовые комбинации некоторого кода.

V0=0 0 0 0 0 0 0 0
V1=1 1 1 1 0 0 0 0
V2=0 0 0 0 1 1 1 1
V3=1 1 1 1 1 1 1 1

Кодовое расстояние между комбинациями зависит от выбора пар. Возможны варианты: d=4,8.

Минимальное кодовое расстояние (dmin) определяет способность кода исправлять ошибки. В данном примере dmin=4.

Например, при приеме кода V2 с ошибкой (0 0 0 0 0 1 1 1) нетрудно найти в таблице ту комбинацию, которая меньше других отличается от принятой.

Очевидно правильное значение переданного кода: 0 0 0 0 1 1 1 1. Принятая комбинация отличается от переданной на один кодовый переход. Другие кодовые комбинации отличаются от принятой на большее расстояние.

Если будет принята, например комбинация 0 0 0 0 0 0 1 1 с ошибками в двух разрядах, то в такой ситуации возникает неопределенность в нахождении варианта переданной, которая меньше других отличалается от принятой.

 

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

Например, для кода 7,4 проверочная матрица H имеет вид:

 

0 0 1