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

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

К этому типу кодов обычно относят систематические коды с расстоянием d=3, которые, согласно (4.77), позволяют исправить все одиночные ошибки. Рассмотрим код Хэмминга, каждая комбинация которого содержит четыре информационных и три контрольных символа (обозначается как (7,4)); он соот­ветствует неравенству (4.83) и имеет избыточность χ = r/(k + r) = 3/7.

Если информационные символы с занимают в комбинации (в групповом коде) первые четыре места, то последующие три контрольных символа образуют­ся, согласно (4.81), как   

Декодирование осуществляется путем трех проверок на четность согласно

где

Так как в (4.87) x может принимать значения 0 или 1, то всего может быть семь (2^r= 8) контрольных чисел X: 000, 100, 010, 001, 011, 101, 110 и 111. Первое из них имеет место в случае правильного приема, а остальные семь формируются и искажении информационных и контрольных символов. Если искажен один из контрольных символов е_j, то, как следует из (4.87), контрольное число примет одно из трех значений: 100, 010 или 001. Остальные четыре контрольных числа используются для выявления ошибок к информационных символах. Порядок присвоения контрольных чисел ошибочным информационным символам может устанавливаться в любой последовательности. Если для с₁– с₄ выбрать соответственно комбинации 011, 101, 110 и 111, то контрольные числа будут определяться формулам

При искажении одного из информационных символов становятся равными единице те суммы х_j, в которые входит этот символ.

Возможен и другой метод отыскания одиночных ошибок, предложенный впервые самим Хэммингом. При этом методе код строится так, что контрольное число в двоичной системе счисления сразу указывает номер искаженного символа. Для этого контрольные символы располагаются на месте первого (младшего а1, второго а2 и четвертого а4 разрядов комбинации группового кода, как это казано на схеме кодирующего и декодирующего устройства (рис. 4.9). В качестве источника информационных символов аЗ, а5, а6, а7 в схеме используется генератор слова, который совместно с элементами И 1, 2 выполняет также функции формирователя тактирующих сигналов для записи в триггеры ТЗ, Т5—Т7 информационных символов и в триггеры Tl, T2, ТЗ — контрольных символов, формируемых элементами ИСКЛЮЧАЮЩЕЕ ИЛИ С1—СЗ. Единичные выходы треп ров Q подключены к индикаторам кода на логических пробниках а1—а7 и опознавателей на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ S1—S3 с индикаторами номера ошибочного разряда 2^0—2^2 в двоичном коде и М — в десятичном. Заметим, что элементы ИСКЛЮЧАЮЩЕЕ ИЛИ выполняют роль сумматоров по модулю 2.

Контрольные символы формируются по правилам:

(4.88)

которые, как видно из схемы, реализуются элементами С1-С3 соответственно.

Рис. 4.9. Кодирующее и декодирующее устройства кода Хэмминга

При первой (нулевой) комбинации (их номера показаны слева от дисплея) на

выходе генератора формируется информационный код 0000, который обнуляет все триггеры под действием тактового сигнала с выхода Clk кодового генератора, поступающего на их тактовые V-входы через элементы И 1, 2 при разрешающих сигналах I на выходах 6 и 8 генератора. При комбинации № 1 информационный код 1010 записывается в триггеры ТЗ, Т5 – Т7 и в соответствии с правилами (4.88) через С1—С2, в виде контрольных символов – в триггеры Т1, Т2 и Т4, в результа­те чего формируется групповой код 1011010, который можно наблюдать на инди­каторах а1—а7. Этот код поступает далее через линию связи в декодер приемника, который также содержит 7 триггеров и опознаватель, работающий по правилам:

которые реализуются элементами SI—S3.

Поскольку в нашей демонстрационной схеме роль приемных триггеров деко­дера играют триггеры кодера, т. е. Т1—Т7, то при комбинации № 2, когда на деко­дер посылается тот же (безошибочный) информационный код 1010, индикатор ошибки М будет показывать нуль.

При комбинации № 3 вводится информационный код 1110, т. е. с ошибкой в разряде а5. В декодере этот код анализируется с помощью опознавателя и сигнал об ошибке в 5-м разряде через дешифратор может быть подан на счетный вход 5-го триггера декодера и переведет его в противоположное (исправленное) состояние. В нашем случае дешифратор находится внутри индикатора М, который про­сто показывает номер разряда, в котором произошла ошибка.

При комбинации № 4 триггеры обнуляются, затем с генератора выдается код 1010 (комбинация № 5), вводится ошибка 1011 (комбинация № 6), которая будет индицироваться цифрой 7 (ошибка в разряде а7 группового кода). Аналогичным образом определяются ошибки в других разрядах (комбинации № 9, 12, 15).