1.4. Конструктивное введение в теорию БЧХ-кодов, исправляющих двойные ошибки

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

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

Эта идея векторной нумерации оказывается очень плодотворной, и в дальнейшем мы предположим, что

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

Разумно выбирать столбцы матрицы по возможности различными. Выберем в качестве первых строк проверочную матрицу

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

На этом пути нам надо отыскать функцию отображающую -мерные векторы в -мерные векторы.

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

Для исследования возможных выборов функции нам необходимо разработать некоторый аппарат для операций над двоичными -мерными векторами. Мы должны уметь в каком-то смысле складывать, вычитать, умножать и делить -мерные векторы. Для этого удобно интерпретировать каждый двоичный -мерный вектор как некоторый двоичный многочлен степени 4. Например,

Как мы и хотели, сложение двух таких двоичных многочленов соответствует сложению векторов. Однако умножение в общем случае приводит к многочленам степени, большей 4. Например,

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

Тогда (двоичное) деление дает

так что

или

Символ читается «сравнимо с». В общем случае говорят, что

тогда и только тогда, когда существует такой многочлен , что

Напомним, что операции умножения и сложения многочленов выполняются по модулю два. Некоторые авторы отмечают этот факт, используя запись . Заметим, что редукции по модулю 2 и по модулю перестановочны. Следующие свойства показывают, насколько плодотворно понятие сравнения многочленов.

1.42. Свойства сравнений. Если

и

то

и

Доказательства.

Более того, если степени многочленов и меньше степени то из формулы следует, что [Доказательство: и если с то степень правой части больше степени левой.]

Следовательно, различные многочлены, степени которых меньше степени лежат в различных классах вычетов по модулю Это определяет 2 различных классов вычетов. Имеются ли еще какие-нибудь классы вычетов? Нет, как вытекает из следующего алгоритма.

1.43. Алгоритм деления.

(см. скан)

Рассмотрев сложение, вычитание и умножение по модулю естественно исследовать возможность деления. Ответ на этот вопрос дает алгоритм Евклида.

1.44. Алгоритм Евклида.

(см. скан)

Детальное доказательство методом последовательного применения алгоритма деления приводится в разд. 2.1.

Покажем, что если и имеют общий делитель то деление на по модулю не всегда возможно.

Действительно, если и то Если бы всегда было выполнимо деление на то мы пришли бы к неправильному выводу, что

Однако, если то, согласно алгоритму Евклида, существуют такие и что

так что

Очевидно, что деление на эквивалентно умножению на

Если, в частности, является неприводимым многочленом, т. е. не имеет делителей, отличных от скаляров и скалярных кратных самого себя, то для каждого возможно деление на Как будет показано в разд. 2.1, многочлены с коэффициентами из поля однозначно разлагаются в произведение неприводимых многочленов, подобно однозначному разложению чисел в произведение простых сомножителей.

Покажем теперь, что двоичный многочлен

неприводим. Ясно, что не является его делителем.

Проверим, будет ли делителем

Так как остаток равен 1, то не будет. Исчерпав все линейные делители, проверим квадратные. Ясно, что не подходит, так же как и Остается проверить еще один делитель:

Следовательно, возможные делители должны иметь степень 3. Но все произведения таких делителей имеют степень 6, Значит, многочлен неприводим.

Таким образом, многочлены можно складывать, умножать и делить (не на нуль) по модулю Интерпретируя все двоичные -мерные векторы как классы вычетов по модулю мы получаем значительно более удобный аппарат для выбора функции определяющей вторую пятерку строк искомой проверочной матрицы, задающей код с исправлением двойных ошибок с блоковой длиной 31 и скоростью 21/31.

Предположим, что номера искаженных символов. Используя двоичную запись чисел и можно представить эти номера в виде классов вычетов по модулю т. е. установить соответствие где двоичные многочлены степени

Первые пять проверочных уравнений определяют второе множество проверочных уравнений должно определить

Декодер должен определить и по заданным

и

Рассмотрим теперь несколько возможных выборов функции Простейшей возможностью является умножение на константу:

Ясно, что эта идея себя не оправдывает, так как в этом случае следовательно, два уравнения зависимы. Вторые пять проверок (определяющих не дают декодеру ничего нового.

Ничего не дает также функция а при любом а. В этом случае

Испытаем теперь степенные функции. Сначала положим

Двумя уравнениями для декодера при этом являются

Читателю, не знакомому с полями характеристики 2 (которые мы изучаем в гл. 4), эти уравнения могут показаться независимыми. Но это не так, ибо

Таким образом, второе уравнение является квадратом первого, и дополнительные пять проверочных уравнении не дают нам ничего нового.

Не отчаиваясь, попробуем, однако,

Уравнения для декодера имеют вид

откуда

так что при

Значит, удовлетворяют уравнению

или, иначе,

или

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

Если произошла только одна ошибка, то

Следовательно, в этом случае единственная ошибка удовлетворяет уравнению

Наконец, декодер всегда декодирует, если ошибок не произошло, так как в этом случае

По причинам, которые станут ясными позже (разд. 7.2), более удобно оперировать не непосредственно с многочленом, корнями которого являются локаторы ошибок, а с многочленом, корни которого взаимны к локаторам, т. е. являются к ним мультипликативными

обратными. Это так называемый многочлен локаторов ошибок, который обозначается через и определяется равенством

Удобно также использовать символ для обозначения сумм степеней локаторов ошибок. В рассматриваемом примере

Выражения для многочлена локаторов ошибок в этих обозначениях принимают вид:

Так как эти случаи отличаются друг от друга равенствами или то ясно, что при не более чем двух ошибках декодер может определить номера ошибок. Если же искажаются три или более символов, то произойдет ошибка декодирования или отказ от декодирования. В гл. 16 на этом принципе будет построен алгоритм декодирования 16.481.

Таким образом, функция подходит для построения нижних пяти строк проверочной матрицы двоичного кода с блоковой длиной 31 и 10 проверочными символами, исправляющего все двойные ошибки. Первые пять проверок задают сумму номеров ошибок; вторые пять проверок задают сумму кубов номеров ошибок. Процедура декодирования состоит из трех основных шагов: (1) производится проверка и вычисляются и 53; (2) находится многочлен локаторов ошибок вычисляются взаимные величины для корней и изменяются символы в соответствующих позициях полученного слова.

Для первого шага процедуры декодирования требуется 10 отдельных множеств сумматоров по модулю 2. Входами каждого из них являются соответствующие подмножества из 31 полученных символов. Так как этот шаг является сравнительно простым, то мы откладываем рассмотрение нескольких известных способов вычисления проверок до разд. 5.2.

Второй шаг декодирования связан с операциями сложения, умножения, деления и возведения в квадрат в поле классов вычетов по модулю Более детальное исследование и реализация этих операций дается в гл. 2.

Третий шаг требует, чтобы декодер определил взаимные к корням алгебраического уравнения над полем классов вычетов по модулю двоичного многочлена Этот шаг рассматривается подробно в разд. 5.4.

Задачи

(см. скан)

(см. скан)