13. О КОДАХ, ИСПРАВЛЯЮЩИХ НЕСИММЕТРИЧНЫЕ ОШИБКИ

На практике нередко встречаются каналы, отличающиеся асимметричным характером ошибок, скажем, такие, в которых преобладают замещения вида 0 -> 1 (т. е. вместо нуля принимается единица), а замещения 1 -V О крайне редки.

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

Исходное соображение здесь очень простое: если в ка­нале невозможны ошибки вида 1 -> 0, то в принятом двоич­ном слове нет нужды проверять позиции с нулевыми сим­волами — они наверняка переданы без искажений. Будем поэтому производить проверку таким образом, чтобы ее результат зависел только от позиций с единичными симво­лами, точнее, от номеров этих позиций. С этой целью для произвольного двоичного слова и=х1хг...хп составим сумму

 

 

В сумме (1) ненулевые слагаемые соответствуют только еди­ничным символам и каждое из них совпадает с номером этого символа, т. е. число 8 (и) равно сумме номеров еди­ничных позиций слова и.

Как обычно, постараемся найти простое условие, выде­ляющее кодовые слова среди прочих. Будем искать это условие в виде сравнения по некоторому модулю I. Предста­вим себе, что число I уже выбрано, и рассмотрим код, состоящий из всех таких слов ь=хг х2 ... хп, для которых

 

Проиллюстрируем исправление одиночной ошибки на примере рассмотренного выше кода У4 6. Пусть принято слово ы=0111. Тогда 5 (м)=2+3+4=9=4 (той 5). Сле­довательно, ошибка произошла в четвертой позиции, т. е. передавалось кодовое слово ОНО.

Наиболее употребимы коды УпЛ при минимально воз­можном I : 1—п+1. Именно они впервые были предложены советскими специалистами по кодированию Р. Р. Варша- мовым и Г. М. Тененгольцем.

Коды Упл обладают способностью исправлять еще один тип искажений кодовых слов, характерный для не­симметричных каналов. Это так называемые выпадения и вставки символов.

 

В самом деле, если выпал символ 0, то 5 (V)—8(и)=П1, а если выпал символ 1, то 5 (V)—8(и)=п—п0. Если до (и) — вес слова и, то, очевидно,

 

Предположим, что в некотором слове ь=хлх2. . ,хп произошло выпадение одного символа, в результате чего получилось слово и~у1у2- ■ ■уп-1 длины п—1. Пусть п* — число единиц, а пе — число нулей, расположенных правее выпавшего символа. Оказывается, числа пг и п0 могут быть определены с помощью суммы

Так как 5(с/)=0 (той I), то вычет числа — 5 (и) по модулю I равен либо щ (в случае выпадения нуля), либо п—п0 (в случае выпадения единицы). Неравенства (3) пока­зывают, что если этот вычет не превосходит ш(и), то выпал символ 0, если же это не так, то символ 1. В первом случае выпавший символ 0 надо вставить в слово и так, чтобы пра­вее него было число единиц, равное вычету числа — 8 (и) по модулю I. Если же этот вычет больше, чем до (и), то встав­ляем в слово и единицу так, чтобы правее нее было число нулей, равное разности п и вычета числа — 5 (и). Если, например, при использовании кода Уя^ принято слово и= = 101, то 5(ы)=4, а ш(ы)=2, вычет числа — 8 (и) по моду­лю 5 равен 1, и, следовательно, выпал символ 0. Вставить его надо так, чтобы правее него была одна единица. Полу­чается кодовое слово 1001.

Аналогично исследуется случай одиночной вставки сим­вола. Читателю предлагается обосновать следующий алго­ритм восстановления кодового слова, отвечающий этому случаю.

Пусть принято СЛОВОН=1/1//2- • •Уп + 1 длины п+1 и к — вычет числа 5 (и) по модулю I. Тогда

1) если к=0, то отбрасывается последний символ сло­ва и;

2) если 0 < /е -< ш (ы), то отбрасывается любой нулевой символ, правее которого в слове и ровно к единиц; „3) если к = гю (и), отбрасывается первый символ слова и\ 4) если к>т(и), отбрасывается любой единичный сим­вол, правее которого имеется п-\-1—к нулей.

Задачи и дополнения

1. Сравнить коды У5 в и У.^ю. а также коды Т) 8> • • •> ^б 12 по их способности исправлять двойные замещения ьида 04-1.

Для кода Уп< „+х сформулировать признак исправимости заме­щения двух или большего числа символов. Каким будет этот признак для кода УПу 2„?

Найти алгоритм исправления (исправимого) двойного замеще­ния для кодов п+, и ]/п< !п.

Коды % можно использовать для исправления одиночных замещений вида 1->0. Каково в этом случае правило декодирования?

Построив код убедиться, что на местах с номерами 3, 5, 6, 7 встречаются всевозможные наборы из нулей и единиц и, значит, символы с этими номерами играют роль информационных.

Утверждение задачи 5 можно обобщить на случай любого кода Уп, п+1. Для которого п=2т—1.

Рассмотрим т позиций с номерами 1,2,.. ., 1т~х. Выберем про­извольную комбинацию из нулей и единиц в оставшихся п—т позициях.

Тогда существует единственное заполнение позиций 1,2  2т, для

которого элучившееся слово удовлетворяет условию (2), т. е. является кодовым. Отсюда вытекает, что число слов кода Уп> „+1 равно 2п~т, т. е. совпадает с числом слов в коде Хемминга длины п— 2т—1.

7/Пусть к ^ п+1 есть простое число. Через % обозначим код, состоящий из всех слов           х2 . . . хп, для которых выполняются

Построить кс<; Убедиться, что он исправляет любые одиночные и дбойнь.. замещения вида 0—>1.

8. Показать, что всякий код & (см. задачу 7) исправляет лю­бые одиночные и двойные замещения вида 0->1. Сохранится ли это свс.хчво для составного 6?