Файл: Шляпоберский В.И. Основы техники передачи дискретных сообщений.pdf

При декодировании с исправлением ошибок необхо­ димо учитывать, какие из уравнений не удовлетворены. Так, если не удовлетворяется одно из трех ур-ний (6.25), то ошибочно принятым является один из проверочных элементов. Когда не удовлетворяются первые два урав­ нения, то следует исправлять (заменять 0 на 1 или 1 на

.элемента. При ошибочном приеме двух и более элемен­ тов правильное декодирование невозможно, так как ко-

.довое расстояние кода d—3.

Предположим, что передаче подлежит информацион­ ная последовательность 1011. Тогда согласно (6.25) на выходе кодирующего устройства она примет вид 1011000. Пусть под действием помех эта комбинация будет при­ нята как 1111000. При декодировании в соответствии с (6.25) получим следующие результаты:

лучается из канонической формы М( „, ^ вычеркиванием i первых столбцов. Поскольку при этом число линейнозависимых столбцов матрицы проверок не может умень­ шиться, то и d M m i нового код а будет то же, что у исход­ ного. Коды, построенные таким образом, принято назы­

325

левые г-разрядные двоичные 'последовательности, назы­ вается кодом Хэмминга. Минимальное расстояние та­ кого кода d = 3 , т. е. кодом исправляются все одиночные ошибки. Таким образом, код Хэмминга полностью за­ дается количеством проверочных элементов г в кодовой комбинации. Порядок формирования г проверочных эле­ ментов определяется задаваемым алгоритмом обнаруже­ ния и исправления искаженного элемента, т. е. требо­

то согласно изложенному должно соблюдаться неравен­ ство

Единица в правой части учитывает случай отсутствия искажений. Сопоставляя выражение (6.26) с аналогич­ ным выражением табл. 6.3 для случая r—Ъ, видим, что они совпадают. Подставляя в (6.26) г—п—k, получим

где п и k могут принимать только целые значения. Не­ равенство (6.27) является исходным при определении длины кодовой комбинации по заданному числу инфор­ мационных элементов.

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

Пусть /7, = 1. Это значит, что один из элементов ко­ довой комбинации, охватываемых первой проверкой, ис­

326 . , -

ряд синдрома. Из табл. 1.1 находим все числа, имеющие

Теперь определим, какие позиции кодовых комбина­ ций занимают проверочные разряды, а какие—информа­ ционные. При этом необходимо помнить, что в каждую последовательность элементов, охватываемых провер­ кой, должен входить только одни проверочный элемент.

каждый первый элемент является проверочным, так как он входит только в соответствующую проверку. Эти эле­ менты формируются на передаче.

В качестве примера рассмотрим преобразование семиэлементного простого кода (К—7) в код Хэмминга, исправляющий одиночную ошибку. Согласно. (6.27) по­ лучим п— 11; г = 4 . Для такого кода четыре проверочных

327

b% = а 2 = а3 © а 6 © а, © а 1 о © а 1 1 ( 63 = 04 = ай © а в © а7 ,

К = а 8 = а 9 © а 1 0 © an.

Пусть передаваемая информационная последователь­ ность имеет вид 1011010. Тогда согласно изложенному принципу кодирования в канал связибудет передана кодовая комбинация 00100111010.

Теперь предположим, что в принятой комбинации ис­ кажен 9-й разряд — 00100111110. В результате четырех проверок на четность при декодировании получим:

есть двоичная запись цифры 9, то, следовательно, в при­ нятой комбинации искажен 9-й элемент, который необ­ ходимо исправить.

Если к передаваемым в канал связи «-элементным ко­

равна единице, а первые г проверок указывают номер искаженного разряда;

328