9.2. Коды, исправляющие две ошибки

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

В качестве кодовых слов выбираются векторы, удовлетворяющие этим четырем проверочным соотношениям. К переданному кодовому слову прибавляется шум. Используя первые два проверочных уравнения, декодер получает сумму локаторов ошибок, а используя два нижних уравнения, он получает сумму кубов локаторов ошибок, Если произошло не более двух ошибок, то

Таким образом, код позволяет исправлять две ошибки. Для декодирования необходимо из проверочных уравнений вычислить и и затем выполнить необходимые для определения многочлена локаторов ошибок операции в поле Если взаимный корень этого многочлена то в позиции полученного слова произошла ошибка +1. Если -взаимный корень многочлена локаторов ошибок и то в позиции полученного слова произошла ошибка —1. Двойные ошибки в любой позиции кодового слова соответствуют взаимным корням многочлена локаторов ошибок кратности два. Для рассматриваемого кода, исправляющего двойные ошибки, квадратный многочлен локаторов ошибок

имеет кратные корни тогда и только тогда, когда

Это же условие вытекает из уравнений Аналогично, легко увидеть, что в случае одной единичной ошибки и ошибки отсутствуют только тогда, когда . У читателя может возникнуть вопрос, почему две нижние строки проверочной матрицы были построены в виде кубов двух первых строк, а не в виде их квадратов. Если вместо кубов взять квадраты, то нужные уравнения не получаются:

что можно привести к внешне более громоздкому (но более удобному для анализа) виду

Здесь соответствии с тем, в каком интервале лежит между или между Осложнение возникает потому, что Аналогичная трудность возникает при включении в проверочную матрицу любой четной степени локаторов. Хотя такой выбор и не обязательно должен быть плохим, однако он всегда приводит к уравнениям типа (9.23), которых мы предпочитаем избегать.

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

удовлетворяет этим проверочным соотношениям тогда и только тогда, когда Это возможно тогда и только тогда, когда многочлен кратен минимальному многочлену элемента а. Аналогично, кодовый многочлен удовлетворяет последним двум проверочным соотношениям тогда и только тогда, когда что возможно тогда и только тогда, когда кратен минимальному многочлену элемента Ясно, что многочлен степени представляет кодовое слово тогда и только тогда, когда кратен произведению Так как а — примитивный элемент поля то но при Так как и квадратные корни из единицы исчерпываются числами то очевидно, что Аналогично заключаем что для любого нечетного включая Таким образом, и минимальный многочлен элемента а, и минимальный многочлен элемента должны быть делителями многочлена Следовательно, если

— кодовое слово, то кратен многочлену также кратен этому многочлену. По этой причине мы назовем этот код негациклическим.