4.5.2. Полиномиальные коды и двойственные к ним коды

Множество всех кодовых слов кода С над все компоненты которых являются элементами подполя называется -подкодом кода С или подкодом над подполем. Если С — линейный код, то также является линейным кодом; если С — циклический код, то циклическим является также и код

Теорема 4.9. Пусть элемент порядка поля и пусть С — циклический код длины над с порождающим

многочленом Тогда порождающий многочлен кода С имеет следующий вид:

где минимальное множество, содержащее и замкнутое относительно перестановки

Доказательство. Если произвольный вектор над принадлежащий С, то так что Следовательно,

Обратно, пусть произвольный вектор длины над и пусть Тогда, так как то а следовательно,

Например, БЧХ-коды с являются подкодами над подполем кода Рида — Соломона.

Подкоды над подполем ОРМ-кодов) называются полиномиальными кодами [37]. БЧХ-коды при и укороченные циклические коды Рида — Маллера являются полиномиальными кодами. Кроме того, как будет показано ниже, евклидово-геометрические коды [27, 35] и проективно-геометрические коды [27, 39, 40] являются кодами, двойственными к полиномиальным кодам [4, 37, 41]. Основные свойства полиномиальных кодов можно вывести из теорем 4.6-4.9 [4, 37].

Утверждение 4.19. Множеством корней порождающего многочлена ОРМ-кода длины делитель порядка является множество

Идея доказательства. Это утверждение легко доказать, используя утверждение 4.16 и теорему 4.9.

Утверждение 4.20. Пусть

— 1, и пусть минимальный вес -ичного БЧХ-кода длины с конструктивным расстоянием совпадает с его конструктивным расстоянием. Тогда

1) минимальный вес ОРМ-кода длины порядка равен ;

2) минимальный вес -ичного БЧХ-кода длины с конструктивным расстоянием равен его конструктивному расстоянию.

Идея доказательства. Доказательство теоремы 4.7, за исключением того, что вектор должен быть вектором над

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

то о будет вектором над Доказательство части 2 утверждения 4.20 аналогично доказательству утверждения 4.14.

Пример 4.12. Пусть простое число и Код, двойственный -подкоду -ичного кода длины и порядка называется расширенным евклидово-геометрическим кодом размерности (сокращенно Эти коды являются расширениями евклидово-геометрических кодов (-кодов), введенных Уэлдоном [38]. Как следует из теоремы 4.5, в случае является кодом Рида — Маллера порядка Поле является векторным пространством размерности над но характеристический вектор произвольного аффинного подпространства размерности этого пространства, согласно теореме 4.8, принадлежит р-ОРМ-коду порядка Так как вектор и является вектором над то он также принадлежит подкоду над подполем. Рассмотрим произвольное аффинное подпространство размерности над пространства Из утверждения 2.76 следует, что число аффинных подпространств размерности содержащих и не имеющих других общих точек, кроме точек равно Пусть векторы этих подпространств. Проверочные суммы, коэффициентами которых являются компоненты этих характеристических векторов, ортогональны относительно линейной -суммы, коэффициентами которой являются компоненты характеристического вектора аффинного подпространства Аналогичными свойствами обладают и аффинные подпространства меньшей размерности. Так как то размерности допускает исправление ошибок веса до с помощью порогового декодирования за шагов.

Утверждение 4.21. Множеством корней порождающего многочлена -ичного -кода длины и размерности

является множество

Краткое доказательство. Как следует из примера 3.1, ЕГ-код размерности является кодом, двойственным четному подкоду подкода над подполем ОРМ-кода размерности Множеством корней порождающего многочлена кода С, согласно утверждению 4.19, является множество

Чтобы элемент был корнем порождающего многочлена двойственного кода, необходимо, чтобы элемент не принадлежал этому множеству; соответствующее условие на заключается в том, что Кроме того, заметим, что Отсюда следует справедливость утверждения 4.21.

Утверждение 4.22. ЕГ-код может быть декодирован точно так же, как и р-ЕГ-код.

Идея доказательства. В примере 4.12 следует рассмотреть только такие аффинные подпространства которые не содержат 0. При этом ошибки веса до могут быть исправлены с помощью порогового декодирования за шагов.

По определению двойственный к нему код содержит характеристические векторы всех аффинных подпространств размерности однако совсем не очевидно, что он может быть натянут только на эти векторы. В действительности же это так [42, 43]. Это означает, что из всех кодов, допускающих пороговое декодирование, основанное на описанных выше свойствах аффинных подпространств, ЕГ-коды имеют максимальное число информационных символов.

Утверждение 4.23. Примитивный БЧХ-код с параметрами из примера 4.1 является укороченным циклическим кодом Рида — Маллера первого порядка и допускает исправление ошибок веса 3 и менее с помощью порогового декодирования в 2 шага.

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

двоичным ЕГ-кодом размерности (1, 1). Полагая в утверждении получаем, что корнями порождающего многочлена этого кода являются элементы множества Следовательно, оба кода совпадают и, согласно примеру 4.12, допускают исправление ошибок веса 3 и менее с помощью порогового декодирования в 2 шага.

Пример 4.13. Пусть простое число и Код, двойственный -подкоду -ичного ОРМ-кода С длины и порядка называется проек-тивно-геометрическим кодом размерности (или сокращенно ПГ-кодом). Согласно утверждению 4.18, характеристические векторы и проективных подпространств размерности проективного пространства принадлежат С. Так как и — вектор над то он принадлежит также и Рассмотрим произвольное проективное подпространство размерности проективного пространства Существует проектных подпространств размерности содержащих и не имеющих других общих точек, кроме точек из Проверочные суммы, коэффициентами которых являются компоненты этих характеристических векторов, ортогональны относительно линейной -суммы, коэффициентами которой являются компоненты характеристического вектора подпространства Аналогичными свойствами обладают и проектные подпространства меньшей размерности. Это означает, что ПГ-код размерности допускает исправление ошибок веса до с помощью порогового декодирования в шагов.

В случае проективно-геометрические коды являются четными подкодами укороченных циклических кодов Рида — Маллера.

Утверждение 4.24. Корнями порождающего многочлена -ичного проективно-геометрического кода размерности и длины являются элементы множества

где элемент порядка

Идея доказательства. Вывод этого утверждения из утверждения 4.16 почти аналогичен доказательству утверждения 4.21.

Утверждение 4.25. Код максимальной длины с блоковой длиной является двоичным проективно-геометрическим кодом размерности (1,1) и, следовательно, допускает исправление

ошибок веса до с помощью порогового декодирования в один шаг. Код из примера 4.9 является одним из таких кодов.

Идея доказательства. Следует воспользоваться примером 4.13 и утверждением 4.24.

Циклические разностные коды [44] также являются кодами, двойственными полиномиальным кодам [37]. Изучены расширения кодов, основанных на конечных геометриях [45, 46], и методы порогового декодирования кодов, двойственных произвольным полиномиальным кодам [43]. Нахождение числа информационных символов полиномиальных кодов в общем случае является трудной задачей, а полученные формулы являются очень сложными [47, 48].

Задача 4.26. Пусть Найти для многочлен Матсона — Соломона

Краткое решение. По определению компонента вектора равна где . С другой стороны, из свойств и формулы (4.30) имеем

Пусть базис, двойственный базису (см. утверждение 2.81). Тогда

где Если положить то из формул (4.34) и (4.38) будет следовать, что

Многочлен, удовлетворяющий равенству (4.37), определяется однозначно (теорема 4.4), так что