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

Для построения кода Хэмминга используется информационная часть в виде двоичного кода на все сочетания с числом информационных символов k, к которой добавляют контрольные символы т. Таким образом, общая длина полной кодовой комбинации n =k + m.

Рассмотрим последовательность кодирования и декодирования по Хэммингу.

Кодирование кодом Хэмминга предусматривает выполнение следующих этапов.

1. Определение числа контрольных символов. Для этого можно воспользоваться следующими рассуждениями. При передаче по каналу с помехами при единичном искажении может быть искажен любой из п символов кода, всего будет n вариантов искажённых комбинаций. Код может быть передан и без искажений. Таким образом, при единичном искажении может быть n + 1 вариантов передачи, включая передачу без искажений. Используя контрольные символы, необходимо различить все п + 1 вариантов. С помощью контрольных символов m можно описать 2^m событий. Значит, должно быть выполнено условие

2^m ≥ n + 1=k + m + 1. (4.3)

В неравенстве (4.3) по известной величине k находится число контрольных разрядов m, необходимых для построения кода, способного обнаружить и исправить заданное число ошибок.

В табл. 4.13 представлена зависимость между k и т, полученная из неравенства (4.3).

Таблица 4.13

Число контрольных символов в зависимости от числа информационных разрядов для исправления одной ошибки

k	1	2	3	4	5	6	7	8	9	10	11	12	13
m	2	3	3	3	4	4	4	4	4	4	4	5	5

Число искажённых кодовых комбинаций зависит от кратности искажения и в общем случае определяется по формуле

, (4.4)

где n – число разрядов полной кодовой комбинации,

l – кратность искажения.

Неравенство (4.3) в общем случае записывается в виде

2^m ≥ Е+1, (4.5)

где величина Е определяется (4.4).

Формулы (4.4) и (4.5) позволяют определить число контрольных разрядов для искажений произвольной кратности.

2. Размещение контрольных символов. Для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т.е. на позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для семиэлементной полной кодовой комбинации можно записать

m₁, m₂, k₄, m₃, k₃, k₂, k₁, (4.6)

где k₄ – старший (четвертый) разряд информационной кодовой комбинации двоичного кода, подлежащий кодированию; k₁ – младший (первый) разряд.

3. Определение состава контрольных символов. Какой из символов должен стоять на контрольной позиции (1 или 0), выявляют с помощью проверочной таблицы. Рассмотрим это на примере комбинации (4.6).

Вначале составляется предварительная таблица (табл. 4.14), в которой записаны все кодовые комбинации (исключая нулевую) для трехразрядного двоичного кода на все сочетания и в правом столбце сверху вниз проставлены символы комбинации кода Хэмминга, записанные в последовательности (4.6).

Таблица 4.14

Пример предварительной таблицы кода Хэмминга

Разряды двоичных чисел			Символы кода
3(k3)	2(k2)	1(k1)
0	0	1	m1
0	1	0	m2
0	1	1	k4
1	0	0	m3
1	0	1	k5
1	1	0	k2
1	1	1	k1

По предварительной таблице составляется проверочная таблица, в которой выписаны символы кодовой комбинации (4.6) в трех строках, формируемые по следующим правилам.

В первую строку записываются символы, против которых проставлены единицы в младшем (первом) разряде комбинации двоичного кода табл. 4.12. Так, в комбинациях 001, 011, 101 и 111 единицы находятся в младших разрядах, поэтому в первой строке проверочной таблицы (см. табл. 4.14) записывается символ т₁, против которого стоит единица в комбинации двоичных чисел 001. Далее в первую строку записывается символы k₄, k₃ и k_1.

Во вторую строку проверочной таблицы записываются символы, против которых проставлены единицы во втором разряде двоичного кода. Так, комбинации 010, 011, 110 и 111 содержат во втором разряде 1, поэтому вторая строка проверочных коэффициентов состоит из символов m₂, k₃, k₂ и k₁.

В третью строку записываются символы, против которых проставлены единицы в третьем разряде двоичного кода, это символы т₃, k₃, k₂ и k₁.

Таблица 4.15