13. О кодах, исправляющих несимметричные ошибки

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

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

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

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

Как обычно, постараемся найти простое условие, выделяющее кодовые слова среди прочих. Будем искать это условие в виде сравнения по некоторому модулю l. Представим себе, что число l уже выбрано, и рассмотрим код, состоящий из всех таких слов υ = x₁ х₂ ... х_n, для которых

т. е. из слов, для которых сумма номеров единичных позиций делится на l без остатка. Обозначим указанный код через V_{n, l}. Так, при n = 4, l = 5 получим следующее множество кодовых слов:

Нетрудно убедиться, хотя бы перебором всех возможных случаев, что данный код исправляет любые одиночные ошибки вида 0 → 1. Например, ошибка в третьем символе слова 1001 переводит его в слово 1011. При этом никакое другое кодовое слово не могло преобразоваться в результате одиночной ошибки в слово 1011. Поэтому получатель декодирует слово 1011 однозначно, считая, что было послано слово 1001. Аналогично обстоит дело с другими двоичными наборами, содержащими одиночные замещения нуля на единицу. Отметим, что в некоторых случаях (но не всегда!) возможно исправление также и двойных замещений нуля на единицу. Один из таких случаев - ошибка в двух первых символах слова 0000. Получающееся при этом слово 1100 не является кодовым и не могло получиться ни из какого кодового слова в результате одиночной ошибки. К тому же имеется единственный вариант двойного замещения, переводящего кодовое слово в слово 1100, - именно тот, который был указан выше.

Подобные свойства сохраняются и для произвольного кода V_n,l, если l ≥ n + 1. В частности, такой код исправляет любые одиночные ошибки вида 0 → 1; при этом алгоритм их исправления чрезвычайно прост. Действительно, пусть в кодовом слове υ = x₁ x₂ ... x_n произошло не более одной ошибки и получилось слово u. Если ошибка произошла в j-м символе, то понятно, что S(u) = S(υ) + j. Поскольку S(υ) ≡ 0 (mod l), то вычет числа S (и) по модулю l равен j, т. е. номеру позиции, в которой произошла ошибка. Если же ошибки не произошло, то вычет S(u) по модулю l равен нулю.

Проиллюстрируем исправление одиночной ошибки на примере рассмотренного выше кода V_4,5. Пусть принято слово u = 0111. Тогда S(u) = 2 + 3 + 4 = 9 ≡ 4 (mod 5). Следовательно, ошибка произошла в четвертой позиции, т. е. передавалось кодовое слово 0110.

Наиболее употребимы коды V_n,l при минимально возможном l : l = n + 1. Именно они впервые были предложены советскими специалистами по кодированию Р. Р. Варшамовым и Г. М. Тененгольцем.

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

Предположим, что в некотором слове υ = x₁x₂ ... х_n произошло выпадение одного символа, в результате чего получилось слово u = у₁у₂ ... y_n-1 длины n-1. Пусть n₁ - число единиц, а n₀ - число нулей, расположенных правее выпавшего символа. Оказывается, числа n₁ и n₀ могут быть определены с помощью суммы

В самом деле, если выпал символ 0, то S(υ) - S(u) = n₁, а если выпал символ 1, то S(υ) - S(u) = n - n₀. Если ω(u) - вес слова u, то, очевидно,

Так как S(u) ≡ 0 (mod l), то вычет числа - S(u) по модулю l равен либо n₁ (в случае выпадения нуля), либо n - n₀ (в случае выпадения единицы). Неравенства (3) показывают, что если этот вычет не превосходит ω(u), то выпал символ 0, если же это не так, то символ 1. В первом случае выпавший символ 0 надо вставить в слово и так, чтобы правее него было число единиц, равное вычету числа - S(u) по модулю l. Если же этот вычет больше, чем ω(u), то вставляем в слово и единицу так, чтобы правее нее было число нулей, равное разности п и вычета числа - S(u). Если, например, при использовании кода V_4,5 принято слово u = 101, то S(u) = 4, a ω(u) = 2, вычет числа - S(u) по модулю 5 равен 1, и, следовательно, выпал символ 0. Вставить его надо так, чтобы правее него была одна единица. Получается кодовое слово 1001.

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

Пусть принято слово u = y₁y₂ ... y_n+1 длины n + 1 и k - вычет числа S(u) по модулю l. Тогда

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

2) если 0 < k < ω(u), то отбрасывается любой нулевой символ, правее которого в слове u ровно k единиц;

3) если k = ω(u), отбрасывается первый символ слова u;

4) если k > ω(u), отбрасывается любой единичный символ, правее которого имеется n + 1 - k нулей.