Принципы построения корректирующего кода Хемминга

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

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

.( 1 )

Единица во втором разряде контрольного числа свидетельствует о наличии ошибки на одной из позиций, двоичные номера которых имеют единицу во втором разряде. Такими позициями являются 2, 3, 6, 7, 10, 11 и т. д. Символы с перечисленными номерами войдут во вторую проверку:

.( 2 )

Аналогично в третью проверку должны войти символы, стоящие на тех позициях, двоичные номера которых имеют единицу в третьем разряде, т. е.:

.( 3 )

Для последней проверки с номером легко получить, что:

;( 4 )

код хемминг моделирование массив

где .

Поскольку контрольные символы должны обеспечивать четность проверочных сумм, они включаются лишь в одну проверку. Только в одну проверку входят символы, двоичные номера позиций которых являются целыми степенями двойки, т. е. 1, 2, 4, 8, 16 и т. д. На этих позициях и размещаются контрольные символы. Значения контрольных символов находятся как результат суммирования всех символов, входящих в данную проверку. Из выражений (1) - (4) можно определить значения контрольных символов:

;

;

;( 5 )

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

.( 6 )

что обеспечивает четность последней проверки.

При декодировании вначале производится проверок на четность в соответствии с выражениями (1) - (4). Затем производится проверка. При этом возможен случай, когда все проверки дают нулевой результат. Это соответствует отсутствию ошибки. Если некоторые из проверок и проверка дают результат, отличный от нуля, то это свидетельствует об однократной ошибке. Номер искаженной позиции указывает контрольное число. При наличии двукратной ошибки некоторые из проверок дадут результат, отличный от нуля, а последняя проверка даст нуль.

Другие стьтьи в тему

Разработка учебно-лабораторного стенда для изучения волоконно-оптического канала утечки акустической информации
Ранее считалось, что каналы оптической связи в силу особенностей распространения электромагнитной энергии в оптическом волокне (ОВ), а также ввиду применения узконаправленных передающих антенн в атмосферных каналах оптической связи обладают повышенной скрытностью. Известно, ...

Разработка регулятора для системы автоматического управления
Управление каким-либо объектом - это процесс воздействия на него с целью обеспечения требуемого течения процессов в объекте или требуемого изменения его состояния. Основой управления является переработка информации о состоянии объекта в соответствии с целью управления. Объект упр ...