Пример 4.2. Принята кодовая комбинация 1010111

Принята кодовая комбинация 1010111. Известно, что она закодирована кодом Хэмминга, исправляющим одну ошибку. Определить, есть ли в ней искажение, и если есть, то исправить его.

Принятая кодовая комбинация имеет 7 разрядов, поэтому согласно табл. 4.11 в ней имеется 4 информационных символа и 3 контрольных. Структура такой комбинации имеет вид (4.6):

т 1	m 2	k 4	m 3	k 3	k 2	k 1

Проверочная таблица семиразрядного кода Хэмминга имеет вид табл. 4.15. Подстановка в неё символов принятой комбинации даёт табл. 4.17.

Таблица 4.17

Проверочная таблица принятой кодовой комбинации примера 4.2

Результат суммирования по модулю 2 строк этой таблицы приведен в правом столбце: первая строка даёт нулевой результат, вторая и третья строки дают единичный результат. Такой результат свидетельствует о наличии искажения.

Для исправления ошибки результат суммирования читается по вертикали снизу вверх. Это даёт двоичное число 110, ему соответствует десятичное число 6. Полученный результат означает, что искажён шестой разряд принятой кодовой комбинации, считая слева направо. Искажён разряд k ₂.Поэтому принятый символ этого разряда, равный 1, заменяется на символ 0, получена исправленная (неискажённая) кодовая комбинация 1010101. Отбрасываются контрольные символы первой, второй и четвёртой позиций полной кодовой комбинации, неискажённая информационная комбинация имеет вид 1101 (см. пример 4.1).

Итак, для повышения помехоустойчивости кода необходимы дополнительные контрольные символы, которые увеличивают длину кодовой комбинации. Например, семиразрядный код обеспечивает передачу 2⁷=128 кодовых комбинаций, однако количество информационных символов в семиразрядном коде Хэмминга k = 4, т.е. полезных информационных посылок всего N_k = 2⁴ = 16. Остальные 112 кодовых комбинаций из 128 предназначены для обеспечения помехоустойчивости кода, являются запрещенными и не используются.

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

Для построения такого кода число контрольных символов определяется не по табл. 4.13, а по формулам (4.3), (4.4), (4.5).

Имеются и частные приёмы построения кодов Хэмминга с повышенными корректирующими способностями. Например, код Хэмминга, позволяющий исправить единичные ошибки, если была только одиночная ошибка, и, обнаружить двойные ошибки, если были две ошибки, строится на базе кода, исправляющего единичные ошибки. Для этого к полной кодовой комбинации кода Хэмминга добавляется контрольный символ, дополняющий до чётности всю комбинацию, включая этот символ. Контрольный символ должен быть равен единице, если число единиц в закодированной комбинации (4.6) нечетное, и нулю, если число единиц четное.

В табл. 4.18 приводится несколько комбинаций четырехразрядного двоичного кода, закодированных для исправления одиночной ошибки, с добавлением дополнительного контрольного разряда m_доп, с целью проверки этих комбинаций на четность.

При декодировании принятой комбинации возможны следующие варианты.

1. Ошибок нет (прием верен). В таком случае как проверка на чётность расширенной кодовой комбинации, так и проверка по проверочной таблице дают нулевые суммы. Все контрольные разряды, включая m_доп, отбрасываются.

Таблица 4.18

Дата добавления: 2014-01-20