Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Подобные свойства сохраняются и для произвольного кода Vna, если В частности, такой код исправляет
любые одиночные ошибки вида 0 -*¦ 1; при этом алгоритм их исправления чрезвычайно прост. Действительно, пусть в кодовом слове V=X1 х2. . .хп произошло не более одной ошибки и получилось слово и. Если ошибка произошла в /-m символе, то понятно, что S(U) = S(V)jT]. Поскольку 5 (и)=0 (mod І), то вычет числа 5 (и) по модулю / равен /, т. е. номеру позиции, в которой произошла ошибка. Если же ошибки не произошло, то вычет 5 (и) по модулю / равен нулю.
Проиллюстрируем исправление одиночной ошибки на примере рассмотренного выше кода V4 6. Пусть принято слово W=Olll. Тогда 5(м)=2+3+4=9І4 (mod Б). Следовательно, ошибка произошла в четвертой позиции, т. е. передавалось кодовое слово 0110.
,66 Наиболее употребимы коды Vn,і при минимально возможном I : t=n-f 1. Именно они впервые были предложены советскими специалистами по кодированию Р. Р. Варша-мовым и Г. М. Тененгольцем.
Коды Vnii обладают способностью исправлять еще один тип искажений кодовых слов, характерный для несимметричных каналов. Это так называемые выпадения и вставки символов.
Предположим, что в некотором слове V = X1Xi- . .Xn произошло выпадение одного символа, в результате чего получилось слово и=у1у2. . .уп_1 длины п—1. Пусть H1 — число единиц, а п0 — число нулей, расположенных правее выпавшего символа. Оказывается, числа пг и п0 могут быть определены с помощью суммы
п- 1
5 (и) = Ц Iyi.
1 = 1
В самом деле, если выпал символ 0, то S (v)—S(U)=H1, а если выпал символ 1, то S(v)—S(u)=n—п0. Если w(u) — вес слова и, то, очевидно,
H1^JSU (и)<.п—п0^ri. (3)
Так как S(u)=0 (mod І), то вычет числа — S (и) по модулю I равен либо пх (в случае выпадения нуля), либо п—п0 (в случае выпадения единицы). Неравенства (3) показывают, что если этот вычет не превосходит W(и), то выпал символ 0, если же это не так, то символ 1. В первом случае выпавший символ 0 надо вставить в слово и так, чтобы правее него было число единиц, равное вычету числа — S (и) по модулю I. Если же этот вычет больше, чем W (и), то вставляем в слово и единицу так, чтобы правее нее было число нулей, равное разности п и вычета числа — S (и). Если, например, при использовании кода V4 5 принято слово и= = 101, то S (и)=4, a W (и)=2, вычет числа — S (и) по модулю 5 равен 1, и, следовательно, выпал символ 0. Вставить его надо так, чтобы правее него была одна единица. Получается кодовое слово 1001.
Аналогично исследуется случай одиночной вставки символа. Читателю предлагается обосновать следующий алгоритм восстановления кодового слова, отвечающий этому случаю.
Пусть принято словом=уjt/a- • -Уп+ї длины тг+1 и k — вычет числа S (и) по модулю I. Тогда
1) если k=0, то отбрасывается последний символ слова и;
,67 2) если 0<k<w(u), то отбрасывается любой нулевой символ, правее которого в слове и ровно k единиц;
.3) если k = W (и), отбрасывается первый символ слова и;
*4) если k>w(u), отбрасывается любой единичный символ, правее которого имеется n+1—k нулей.
Задачи и дополнения
1. Сравнить коды V66 и V510, а также коды V6i7l V6 8> • • ¦> ^e іг 110 их способности исправлять двойные замещения вида 0-І-1.
2. Для кода V„s n+i сформулировать признак исправимое™ замещения двух или большего числа символов. Каким будет этот признак для кода Vn, гп?
3. Найти алгоритм исправления (исправимого) двойного замещения для кодов Vfli „+1 и Vfij 2п.
4. Коды Vni ft можно использовать для исправления одиночных замещений вида I—>-0. Каково в этом случае правило декодирования?
5. Построив код V7i8l убедиться, что на местах с номерами 3, 5, 6, 7 встречаются всевозможные наборы из нулей и единиц и, значит, символы с этими номерами играют роль информационных.
6. Утверждение задачи 5 можно обобщить на случай любого кода Vn, н + 1, для которого п=2т—1.
Рассмотрим т позиций с номерами 1,2,.. ., 2т~1. Выберем произвольную комбинацию из нулей и единиц в оставшихся п—т позициях. Тогда существует единственное заполнение позиций 1,2, . . .,Im, для которого получившееся слово удовлетворяет условию (2), т. е. является кодовым. Отсюда вытекает, что число слов кода Vtii „+1 равно 2п~т, т. е. совпадает с числом слов в коде Хемминга длины п=2т—1.
7." Пусть /г^я+1 есть простое число. Через Vn, ft обозначим код, СОСТОЯЩИЙ ИЗ всех СЛОВ D=jc1' X2 ... хп, для которых выполняются дез соотношения:
П
У| /IpO (mod к), >j Pxi » С (mod к). і'= і (=1
Построить код Убедиться, что он исправляет любые одиночные н двойные замещения вида 0—>-1.
8. Показать, что всякий код Vfii k (см. задачу 7) исправляет любые одиночные и двойные замещения вида 0->1. Сохранится ли это свойство для составного k?
14. HliKvTHHECKHE КОДЫ
Среди линейных кодов особо важную роль играют так называемые циклические коды. По ряду причин они являются наиболее ценным достоянием теории кодирования. Во-первых, они допускают еще более компактное описание, чем произвольные линейные коды. Во-вторых, имеющиеся для линейных кодов алгоритмы кодирования й декодирования могут быть в применении к циклическим
