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

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

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

.( 1 )

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

.( 2 )

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

.( 3 )

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

;( 4 )

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

где .

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

;

;

;( 5 )

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

.( 6 )

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

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

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

Разработка автоматизированного рабочего места помощника бухгалтера ООО Торговый дом Алдан
рабочий место автоматизированный информационный Развитие экономики и других сфер человеческой деятельности в наше время связано с применением вычислительной техники, созданием информационных систем различного назначения. Сегодня обработка экономической информации стала само ...

Разработка преобразователя разности фаз в постоянное напряжение
Разработка преобразователя разности фаз двух сигналов в постоянное напряжение со следующими параметрами: · Частота входных сигналов 10кГц - 100 кГц; · Входное напряжение 50мВ - 5В; · Диапазон измерения ∆φ 0 - 180о ...