Построение групповых кодов, исправляющих одиночные ошибки

Вырабатываемое источником информации единичное сообщение формируется в безызбыточную комбинацию, причем все комбинации должны иметь одинаковую длительность (разрядность n).

Рассмотрим пример кодирования и исправления однократных ошибок групповым кодом Хемминга для n = 4 разрядных информационных блоков. Из условия (3.3.) следует, что m = 7, код (7,4) имеет семь разрядов, из них 4 информационных.

Построим "матрицу ошибок", т.е. переберем все возможные однократные ошибки (место ошибки определим вектором с одной единицей):

. (3.4)

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

В качестве примера закодируем информационный блок 1010.

В выбранном 7 элементном блоке 1, 2, 4 разряды заняты под проверочные, а в 3, 5, 6, 7 разрядах запишем передаваемую информацию.

Найдем проверочные символы из уравнения (3.5,б)

а₁ = а₃ Å а₅ Å а₇ = 0 Å 1 Å1 = 0 а₁ = 0

а₂ = а₃ Å а₆ Å а₇ = 0 Å 0 Å 1 = 1 а₂ = 1

а₄ = а₅ Å а₆ Å а₇ = 1 Å 0 Å 1 = 0 а₄ = 0

Теперь запишем закодированный блок

число 1010010.

Допустим, что при приеме этого блока произошла ошибка в третьем разряде (т.е. мы приняли блок вида 1010110), тогда проверочные равенства (3.5,а) в приемнике дадут синдром ошибки:

а₁ Å а₃ Å а₅ Å а₇ = 0 Å 1 Å 1 Å 1 = 1

а₂ Å а₃ Å а₆ Å а₇ = 1 Å 1 Å 0 Å 1 = 1

а₄ Å а₅ Å а₆ Å а₇ = 0 Å 1 Å 0 Å 1 = 0.

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