12.4. ДАЛЬНЕЙШИЕ СВОЙСТВА КОДОВ ГОППЫ

Добавление общей проверки на четность. Пусть код Гоппы над GF(q) длины и многочленом степени ни один из корней которого не лежит в поле Согласно (12.12) вектор принадлежит коду тогда и толькотогда, когда для всех

Код можно расширить, добавив общую проверку на четность а задаваемую равенством

или

Условившись, что область суммирования в равенстве (12.23) можно изменить на область Наконец, объединяя (12.23) и (12.24), получаем, что вектор а принадлежит расширенному коду Гоппы тогда и только тогда, когда

Расширенный код будем обозначать через Упражнение. Пусть я; — подстановка на множестве задаваемая формулой

где удовлетворяют условию Проверить сначала, что это действительно подстановка на множестве Затем доказать, что переводит расширенный код Гоппы в эквивалентный код , где

(b). Предположим, что многочлен таков, что для некоторого выполняется условие

Показать, что код инвариантен относительно подстановки .

Коды Гоппы и многочлены Мэттсона — Соломона. В частном случае, когда состоит из всех корней степени из ениницы, коды Гоппы хорошо описываются в терминах многочленов Мэттсона-Соломона (см. следствие 8). Мы рассмотрим только двоичный случай.

Напомним, что в § 8.6 многочлен Мэттсона — Соломона для многочлена был определен равенством

где и -примитивный корень степени из единицы.

Обратная операция задается равенством

Если то между рациональной функцией

задаваемой равенством (12.8), и многочленом существует взаимосвязь. Эта взаимосвязь описывается следующей теоремой. Мы будем использовать запись для обозначения остатка от деления многочлена на Теорема 7.

Доказательство. Запишем

где

Тогда

Кроме того,

Следовательно, для доказательства (12.29) достаточно показать, что

т. е. что

Для того чтобы убедиться в справедливости этого равенства, достаточно умножить обе его части на Наконец, равенство (12.30) вытекает непосредственно из (12.28).

Следствие 8. Пусть -двоичный код Гоппы с где - примитивный корень степени из единицы. Тогда

Доказательство. Как и в доказательстве теоремы, запишем Так как многочлены взаимно просты, тогда и только тогда, когда Согласно следовательно,

Заметим, что если вес четен, то Таким образом, в этом случае многочлен делит

Пример. Рассмотрим двоичный код Гоппы где примитивный элемент поля GF(24). Проверочная матрица (12.12) равна:

Тогда код представляет собой -код с порождающей матрицей

Этот код является плохим, но служит хорошей иллюстрацией к следствию. Многочлены Мэттсона — Соломона для кодовых слов соответственно равны:

где через обозначен элемент

Применяя следствие к первому из этих многочленов, получаем многочлен

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

Следствие 9. Пусть двоичный код Гоппы где примитивный корень степени из единицы. Если код цикличен, то он является кодом БЧХ и для некоторого целого

Доказательство. Предположим, что ни для какого целого числа Тогда многочлен имеет некоторый корень лежащий в некотором поле Пусть ненулевое слово кода четного веса. Согласно следствию 8 многочлен кратен многочлену следовательно, Так как — циклический код, то по теоремы 22 гл. 8 равенство выполняется для всех Таким образом, многочлен имеет по меньшей мере различных корней и, следовательно, что невозможно.

Длинные коды Гоппы являются хорошими. В § 12.2 было доказано, что альтернантные коды лежат на границе Варшамова-Гилберта. На самом деле, как показывает следующее упражнение, это утверждение справедливо для значительно более узкого класса кодов.

Упражнение. (9). (а). Доказать, что если неприводимый многочлен степени над то существует код Гоппы над GF(q) с параметрами удовлетворяющий условию

[Указание. Опираясь на теорему 15 гл. 4, показать, что всего имеется неприводимых многочленов степени над полем

Вывести отсюда существование длинных неприводимых кодов Гоппы, лежащих на границе Варшамова — Гилберта.

Но это не дает способа отыскания наилучшего многочлена

Задача (нерешенная). (12.2). Какой из многочленов Гоппы обеспечивает наибольшее минимальное расстояние (или наименьшую избыточность)?