Код Хемминга

Рассмотрим код Хемминга, исправляющий одиночные ошибки.

Код Хемминга, как и любой код содержит комбинацию m информационных и r = n-m избыточных символов. Избыточная часть кода строится так, чтобы при декодировании можно было установить не только наличие ошибки, но и ее положение. Это достигается путем многократной проверки принятой комбинации на четность, количество проверок равно значению избыточных символов r. При каждой проверке охватывается часть информационных символов и один из избыточных, при этом получают один контрольный символ. Если результат проверки дает четное число, то контрольному символу присваивается значение 0, если нечетное - 1. В результате всех проверок получается r - разрядное двоичное число, указывающее номер искаженного символа. Для исправления ошибки значение этого символа (бита) изменяется на обратное.

Необходимое количество проверочных символов r или значность кода для кодов Хемминга, исправляющих одиночные ошибки определяется из ранее полученного соотношения:

2^m £ 2ⁿ/(1+ n). (2.7)

Значения проверочных символов и номера их позиций по методу Хемминга устанавливается одновременно с выбором контролируемых групп кодовых комбинаций. При этом исходят из следующего: в результате первой проверки получают контрольное число, если оно равно 1, то один из символов первой проверенной группы искажен. Для выяснения вопроса, какой из символов может быть искажен, рассмотрим таблицу 2.4, в которой представлен натуральный ряд четырехразрядных контрольных чисел в двоичной системе счисления.

Таблица 2.4

Как видно из таблицы 2.4, если младший разряд контрольного числа содержит 1, то искажение должно быть в одной из нечетных позиций кодовой комбинации. Следовательно, первой проверкой должны быть охвачены символы с нечетными номерами. Если результат второй проверки даст 1, то получим 1 во втором разряде контрольного числа. Следовательно, второй проверкой должны быть охвачены символы с номерами, содержащими 1 во втором разряде двоичной записи этого номера: 2, 3, 6, 7, 10 и т.д. Аналогично при третьей проверке проверяться символы, номера которых в двоичной записи содержат 1 в третьем разряде: 4, 5, 6, 7, 12 и т.д.

Такие рассуждения позволяют образовать таблицу 2.5 проведения проверок.

Таблица 2.5

Если символы проверяемой кодовой комбинации обозначить через a_i, то проверочные суммы S_i можно записать следующим образом:

S₁ = а₁ а₃ а₅ а₇ а₉ .....

S₂ = а₂ а₃ а₆ а₇ а₁₀ .....

S₃ = а₄ а₅ а₆ а₇ а₁₂ .....

S₄ = а₈ а₉ а₁₀ а₁₁ а₁₂ .....

Номер позиции символа, в котором произошла ошибка в процессе приема-передачи комбинации, определяется следующим двоичным числом: N₂=....S_i....S₄ S₃ S₂ S₁.

С целью упрощения операций кодирования и декодирования целесообразно выбирать такое размещение проверочных символов в кодовой комбинации, при котором каждый из них включается в минимальное число проверяемых групп (лучше в одну группу). Нетрудно отметить из таблицы 2.4, что символы 1, 2, 4, 8......2ⁿ встречаются в каждой группе только один раз. Это связано с тем, что они являются степенью числа 2 и их двоичный код в таблице 4 содержит только одну единицу. Эти символы стоят на первом месте в правой части выражений для S_i. Таким образом, в коде Хемминга символы а₁, а₂, а₄, а₈.... должны быть проверочными, а символы а₃, а₅, а₇, а₉.... - информационными.

При передаче значения проверочных символов устанавливаются в кодовой комбинации такими, чтобы суммы S равнялись нулю (т.е. были бы четными числами), т.е. значения проверочных символов а₁, а₂, а₄.... выбираются из условия равенства S_i нулю.

Представим в качестве примера в коде Хемминга двоичную комбинацию 10010. Для нее число информационных символов m=5, при этом максимальное число передаваемых кодов равно 32. Разрядность кода Хемминга для m=5 должна быть равной 9 (n=9). Для девятиразрядного кода символы а₁, а₂, а₄ и а₈ являются проверочными, а символы а₃, а₅, а₆, а₇ и а₉ - информационными. Для заданного кода а₃=0, а₅=1, а₆=0, а₇=0 и а₉=1, тогда:

S₁ = а₁ 0 1 0 1 = а₁ 0=0, откуда следует, что а₁=0;

S₂ = а₂ 0 0 0 = а₂ 0=0, т.е. а₂ =0;

S₃ = а₄ 1 0 0 = а₄ 1=0, т.е. а₄ = 1.

Аналогично: а₈ = 1.

Следовательно, код Хемминга для кода 10010 будет равен 110011000.

Если при приеме-передаче произошла однократная ошибка в пятом символе, т.е. код при приеме принял значение 110001000, то в результате первой проверки будет получено число 1, в результате второй - 0, третьей - 1 и четвертой - 0. Таким образом, в результате проверок будет получено контрольное число 0101, указывающее на искажение пятого символа, принятой кодовой комбинации.

Если произойдет однократная ошибка приема-передачи первого символа кодовой комбинации, то сумма S₁ будет равна 1, а остальные суммы будут равны 0. Полученное контрольное число N будет равно 0001, что указывает на искажение первого символа принятого кода. Аналогичные контрольные числа будут получены при искажениях 2-го, 3-го и т.д. символов кода. Отметим, что для исправления ошибки принятой кодовой комбинации необходимо лишь изменить значение искаженного символа на противоположное.