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

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

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

.( 1 )

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

.( 2 )

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

.( 3 )

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

;( 4 )

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

где .

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

;

;

;( 5 )

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

.( 6 )

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

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

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

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

Разработка схемы приоритетов прерываний
Для обеспечения перехода от одной программы к другой в мультипрограммной ЭВМ вводится так называемый режим прерывания программ. Прерывание программы - способность процессора прекращать выполнение текущей программы и её управление при возникновении определенных условий. Сигналы, вызы ...