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?