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

Рис. 6. Выделение контрольных разрядов по строкам и столбцам

Увеличение избыточности информации приводит к тому, что появля­ется возможность не только обнаружить ошибку, но и исправить ее. Пусть произошла неисправность в каком-то из разрядов этого числа (представим, что разряд а₁₈ изменил состояние, т. е. а₁₈ = 1). Это приведет к тому, что при проверке на четность сумма S_i(a_i+k_i) по соответствующим строкам и столбцам изменится для значений, которые содержат элемент а₁₈, т. е. это будет четвертая сверху строка и третий слева столбец. Следовательно, на­рушение четности по этой строке и столбцу можно зафиксировать, что в конечном счете означает обнаружение не только самой ошибки, но и места, где возникла ошибка. Изменив содержимое отмеченного разряда (в данном случае а₁₈) на противоположное, можно исправить ошибку.

Коды, предложенные американским ученым Р. Хэммингом, способны не только обнаружить, но и исправить одиночные ошибки. Эти коды - систематические.

Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибки, то запишем 0, если есть ошибка, то за­пишем 1 . Запись полученной последовательности символов образует двоичное, контрольное число, указывающее номер позиции, где произошла ошибка. При отсутствии ошибки в данной позиции последовательность будет содержать только нули. Полученное таким образом число описывает n = (m + + k + 1) событий. Следовательно, справедливо неравенство

2^k ³ (m + k + 1).

Определить максимальное значение m для данного k можно из следующего:

n… 1 2 3 4… 8…15 16…31 32…63 64

m…0 0 1 1… 4…11 11…26 26…57 57

k… 1 2 2 3… 4…4 5…5 6…6 7

Определим теперь позиции, которые надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, то контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, то, значит, в результате первой проверки обнаружена ошибка. Имея табли­цу двоичных эквивалентов для десятичных чисел, можно сказать, что, например, первая проверка охватывает позиции 1, 3, 5, 7, 9 и т. д., вторая проверка — позиции 2, 3, 6, 7, 10.

Проверка Проверяемые разряды

1... 1,3,5,7,9,11,13,15...

2... 2,3,6,7, 10, 11, 14, 15, 18, 19,22,23...

3... 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23...

4... 8,9,10,11,12,13,14,15,24...

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

В таблице 6 представлены примеры кодирования информации по методу Хэмминга для семиразрядного кода.

Как видно из таблицы 6, в этом случае n=7, m=4, k=3 и контроль­ными будут разряды 1, 2, 4.

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

Таблица 6

Кодирование информации по методу Хэмминга для 7-миразрядного кода