4.4. Многочлены Матсона — Соломона

Некоторые способы задания циклических кодов основаны на использовании многочленов Матсона — Соломона (МС-многочленов) [3, 4, 32]. Пусть число, являющееся степенью некоторого простого числа целое положительное число, целое положительное число, которое делит элемент порядка поля Обозначим через векторное пространство размерности над Сопоставим вектору многочлен МС-многочлен вектора обозначаемый ниже через определяется следующим образом:

где

Так как

(индексы у 5; вычисляются по модулю Таким образом,

Ниже нам понадобится следующая лемма.

Лемма 4.6. Пусть элемент порядка поля и пусть целое число. Тогда

1) если

2) если

Доказательство. Справедливость части 2 леммы очевидна. Для доказательства части 1 достаточно заметить, что в этом случае и

Из леммы 4.5 и равенства следует, что

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

Пусть -ичный циклический -код с порождающим многочленом

где Как было показано в разд. 3.6, множество замкнуто относительно перестановки множества Пусть минимальное целое число, не принадлежащее Если произвольный кодовый

вектор кода С, то

поскольку Следовательно, степень не больше чем Если ненулевой вектор веса то из формулы (4.30) получаем

Таким образом, йвчх является не чем иным, как нижней БЧХ-границей для минимального расстояния.

Обратно, выберем произвольным образом совокупность элементов удовлетворяющую следующим условиям:

Пусть

Тогда из леммы 4.5 для всех имеем

т. e. . Отсюда и из равенств (4.27) и (4.28) следует, что

Пусть множество всех многочленов над вида удовлетворяющих соотношениям (4.32). Из вышеизложенного следует справедливость следующей теоремы. Теорема 4.4. Отображение С в

и обратное отображение

устанавливают взаимно однозначное соответствие между элементами Число корней многочлена равно

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

Пример 4.11 [32]. Рассмотрим двоичный (23, 13)-код Голея из примера 4.2. В этом случае —элемент порядка 23. Множество состоит из следующих -циклов: В последнем цикле целое число сравнимо с —2-1 по модулю 23 [это связано с тем, что все (2, 23)-циклы — это цикл длины 11, содержащий 1, и цикл той же длины, содержащий Следовательно, полагая получаем Согласно (4.32), Как следует из вышеизложенного, для любого кодового вектора

Так как то при четном при нечетном Ниже будем считать, что Поскольку степень не больше 18, то не меньше Предположим, что Тогда и все корни -это корни уравнения вида Произведение этих 18 корней, согласно 4.33, равно так что Следовательно, также является корнем и показатель следует вычислять по модулю 23. Равенство (4.33) перепишем в виде

Тогда, поскольку многочлен над то, если корень, — также корень. Так как длина (2, 23)-циклов, отличных от равна 11, то число корней вида не больше 12. В то же время многочлен также имеет не более 12 корней вида Получили противоречие. Следовательно, Предположим, что Тогда и все корни многочлена должны иметь вид Произведение этих корней равно Элемент а следовательно, и являются корнями уравнения Так как числа взаимно

простые, то сам элемент 5 также имеет вид Вновь получили противоречие. Следовательно, Поскольку кодовый вектор для которого многочлен является порождающим многочленом имеет вес 7, то минимальное расстояние -кода Голея равно семи.

Утверждение 4.10. Рассмотрим код Рида — Соломона, определенный в примере 4.4. Множество представляет собой множество всех многочленов над степени и менее. Следовательно, многочлены над степени и менее).

Краткое доказательство. Так как то доказательство непосредственно следует из определений и теоремы 4.4.