Контроль по четности, нечетности, по Хеммингу.

Если в математическом коде выделен один контрольный разряд (k=1), то к каждому двоичному числу добавляется один избыточный разряд и в него записывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе была по модулю 2 равна 0 для случая нечетности. Появление ошибки в кодировании обнаружится по нарушению четности (нечетности). При этом допускается, что может возникнуть только одна ошибка. В самом деле, для случая четности правильным будет только половина возможных комбинаций. Чтобы одна допустимая комбинация превратилась в другую, должно возникнуть, по крайней мере, два нарушения или четное число нарушений. Пример реализации метода четности представлен в таблице.

Такое кодирование имеет минимальное кодовое расстояние, равное 2.
Можно представить и несколько видоизмененный способ контроля по методу четности – нечетности. Длинное число разбивается на группы. Контрольные разряды выделяются всем группам по строкам и по столбцам согласно следующей схеме:

Увеличение избыточности информации приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить её. В самом деле, пусть произошла неисправность в каком-то из разрядов этого числа (представим, что разряд а18 изменил состояние, т.е. а18=1). Это приводит к тому, что при проверке на четность сумма по соответствующим строка изменится для значений, которые содержат элемент а18, т.е. это будет четвертая сверху строка и третий слева столбец. Следовательно, нарушение четности по этой строке и столбцу можно зафиксировать, что в конечном счете означает обнаружение не только самой ошибки, но и места, где возникла ошибка. Изменив содержимое отмеченного разряда (в данном случае а18) на противоположное, можно исправить ошибку.
Контроль по методу четности-нечетности широко используют в ЭВМ для контроля записи, считывания информации в запоминающих устройствах на магнитных носителях.

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

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

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

Свойство кодов Хэмминга таково, что контрольное число указывает номер позиции, где произошла ошибка. При отсутствии ошибок в данной позиции последовательность будет содержать только нули. Полученное число таким образом описывает n=(m+k+1) событий.

Следовательно, справедливо неравенство

(4.1.)

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

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

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

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

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

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