12.3. КОДЫ ГОППЫ

Коды Гоппы являются наиболее интересным подклассом альтернантных кодов. Так же как циклические коды определяются в терминах порождающих многочленов (теорема 1 гл. 7), так и коды Гоппы определяются в терминах многочленов Гоппы G(z). В противоположность циклическим кодам, для которых трудно по порождающему многочлену определить их минимальное расстояние, коды Гоппы обладают тем свойством, что Мы дадим сначала определение этих кодов в терминах

многочленов Гоппы, а затем покажем, что они являются альтернантными.

Определение кода Гоппы длины с символами из поля GF(q) опирается на два объекта: многочлен с коэффициентами из поля для некоторого фиксированного называемого многочленом Гоппы, и подмножество элементов из таких, что для всех Обычно в качестве выбирается подмножество всех элементов поля которые не являются корнями многочлена

С каждым вектором а над GF(q) свяжем рациональную функцию

Определение. Код Гоппы (или состоит из всех векторов а таких, что

или, что эквивалентно, таких, что в кольце многочленов

Если неприводим, то называется неприводимым кодом Гоппы.

На рис. 12.3 приведены основные свойства этих кодов. Примеры приведены после теоремы 6.

Рис. 12.3. Свойства кодов Гоппы

Проверочная матрица Г. Очевидно, что линейный код. Его проверочная матрица может быть найдена из (12.9). Многочлен в кольце многочленов по модулю имеет обратный многочлен (так как он не делит Этот обратный многочлен равен:

действительно,

Следовательно, вектор а лежит в коде тогда и только тогда, когда

как многочлен (а не по модулю

Если

Приравнивая согласно (12.10) нулю коэффициенты при видим, что а принадлежит коду тогда и только тогда, когда где

— проверочная матрица кода

Так как матрица обратима, то согласно упражнению (31) гл. 7 проверочная матрица может быть записана в иной форме:

Эта форма обычно проще.

Проверочная матрица с элементами из GF(q) получается из (или ) заменой каждого элемента матрицы соответствующим вектором-столбцом длины над

Сравнивая (12.11) с (12.13), видим, является альтернантным кодом

Следовательно, размерность кода не меньше чем а минимальное расстояние не меньше чем

На самом деле легко указать обобщенный код Рида — Соломона, который задает код

Теорема представляет собой ограничение на подполе GF(q) кода где

Доказательство (i). Выберем Тогда

где многочлен, степень которого меньше чем Таким образом,

Пусть

Тогда для всех Кроме того, Так как многочлен определяется своими значениями в точках, то Таким образом,

и, следовательно, Итак,

(ii). Обратное включение доказывается аналогичным образом, и мы оставляем это доказательство читателю.

Из теоремы 2 получаем следующую теорему.

Теорема 5. Код, дуальный коду Гоппы, равен:

где

Упражнение. (2). Доказать непосредственно, что коды при при

дуальны.

Двоичные коды Гоппы. Как и для двоичных кодов БЧХ, в двоичном случае для кодов Гоппы исследования продвинуты несколько дальше (ср. § 7.6). Предположим, что двоичный код Гоппы Пусть -слово кода веса причем положим

Тогда

и согласно (12.8)

По определению кода все а, различны, так что многочлены не имеют общих делителей и дробь (12.15) несократима. Так как то многочлены взаимно просты, и, следовательно, из (12.15) вытекает, что

Так как все операции выполняются по модулю 2, то содержит четные степени и является полным квадратом. Пусть - полный квадрат наименьшей степени, делящийся на Тогда

Отсюда заключаем, что

В частности, если то Следовательно, для минимального расстояния кода выполняется неравенство

Важнейшим частным случаем является следующий.

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

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

Примеры двоичных кодов Гоппы. (1). Выберем где примитивный элемент поля, Для всех выполняется условие так как корни многочлена лежат в полях и не лежат в поле (см. теорему 8 гл. 4). Получаем неприводимый код Гоппы для размерности с минимальным расстоянием Согласно (12.12) проверочная матрица этого кода равна:

Из рис. 4.5 находим:

Кодовыми словами являются они образуют -код Гоппы. Добавляя общую проверку на четность и переупорядочивая столбцы, получаем следующий -код:

Этот код оказывается циклическим. Объяснение этого явления дано в § 12.5

Этот пример может быть также использован для иллюстрации теоремы 4. Здесь так как для всех Таким образом, теорема 4 утверждает, что [8, 2, 5]-код Гоппы является ограничением на подполе кода с порождающей матрицей

Легко проверить, что:

(2) Выберем Опять Для всех (на основании теоремы 8 гл. 4). Тогда является [32, 17, 7] неприводимым кодом Гоппы, проверочная матрица которого согласно (12.12) имеет вид (здесь а — примитивный элемент поля

(см. скан)

Здесь мы воспользовались таблицей поля приведенной на рис. 4.5. Весовой спектр кода найденный на имеет вид:

(3). Конечно, совсем не обязательно ограничивать возможные значения коэффициентов многочлена нулем и единицей. Например, можно выбрать где примитивный элемент поля GF(24). По теореме 19 гл. 9 этот многочлен неприводим в поле GF(24), так как Следовательно, в качестве можно выбрать все поле GF(24). Это приводит к неприводимому -коду Гоппы.

Упражнение. (3). Найти проверочную матрицу этого кода.

(4). Неприводимые коды Гоппы. Рассмотрим неприводимый в многочлен Корни этого многочлена лежат в поле следовательно, по теореме 8 гл. 4 в полях Предполагая не делящимся на 3 и выбирая получаем неприводимый код Гоппы с параметрами

Как мы видели в примере (2), при границы для являются точными.

С другой стороны, выбирая в качестве неприводимый многочлен третьей степени над получаем код с параметрами (12.20) для произвольного

В общем случае, выбирая в качестве произвольный неприводимый многочлен над степени получаем неприводимый код Гоппы с параметрами

для произвольных целых чисел Сопоставимые примитивные коды БЧХ имеют параметры

т. е. при одинаковых они имеют на один информационный символ меньше.

Упражнения (4). Пусть Многочлен степени с коэффициентами из поля и пусть наименьшее поле, содержащее все корни многочлена Доказать, что для построения кода Гоппы с параметрами (12.21) можно выбирать для любого такого, что и

(5). Коды БЧХ. Примитивные коды БЧХ в узком смысле являются частным случаем кодов Гоппы. Выберем

где примитивный элемент поля Тогда из (12.12) получаем:

что дает проверочную матрицу кода если заменить на

Для построения двоичных кодов БЧХ, исправляющих ошибок, надо выбрать

В примерах (1) и получилось, что значения совпадают с граничными значениями, приведенными на рис. 12.3. Однако, как показывает пример" кодов БЧХ, это не всегда так.

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

Упражнение. (5). Другая форма проверочной матрицы. Предположим, что не имеет кратных корней, скажем, где различные элементы поля Показать, что если и только если для матрицы где для

Замечание. Заметим, что в этом упражнении матрица является матрицей Коши (см. упражнение (7) гл. 11). Если проверочная матрица кода, исправляющего ошибок, то согласно теореме 10 гл. 1 любые столбцов матрицы должны быть линейно независимыми. В классической теории матриц известны два вида комплексных матриц, обладающих тем свойством, что любая их квадратная подматрица является невырожденной: матрицы Вандермонда и матрицы Коши—(см. лемму 17 гл. 4 и упражнение (7) гл. 11). Матрицы Вандермонда лежат в основе определения кодов БЧХ (§ 7.6), и, как мы только что увидели, матрицы Коши лежат в основе сепарабельных кодов Гоппы.

Упражнения. (6). Коды Гоппы с для некоторых называются комулятивными. Доказать, что между кодом и кодом существует взаимно однозначное соответствие, сохраняющее вес.

Пример (1) подсказывает следующее упражнение.

(7). (Кордаро и Вагнер.) Пусть — двоичный -код с наибольшим возможным исправляющий большинство ошибок веса Положим Доказать, что если сравнимо с 0 или 1 по модулю 3, и если ; показать также, что порождающая матрица, кода может быть выбрана в виде матрицы, содержащей столбцов, равных равных и остальных столбцов, равных