8.6. МНОГОЧЛЕН МЭТТСОНА—СОЛОМОНА

В гл. 7 каждому вектору был сопоставлен многочлен Сейчас будет введен другой многочлен, связанный с вектором а, а именно многочлен Мэттсона-Соломона . Пусть примитивный корень степени из единицы.

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

где

не берется по модулю Другой формой записи многочлена является:

Например, МС-многочлены, соответствующие кодовым словам симплексного -кода равны соответственно где (использовано задание поля, приведенное на рис. 4.5).

Замечания. (1). Коэффициенты определяются равенствами:

Поэтому многочлен иногда называют дискретным преобразованием Фурье вектора а; мы, однако, всегда будем называть его многочленом Мэттсона — Соломона.

(2). Заметим, что для всех (индексы берутся по модулю

(3). Код БЧХ в узком смысле с конструктивным расстоянием может быть теперь определен как множество всех таких векторов, для которых

(4). Мы просим прощения за использование символа для обозначения числа кодовых слов веса и для коэффициентов МС-многочлена, надеемся, что смысл будет ясен из контекста.

Теорема 20. (Формула обращения.) Вектор а восстанавливается по многочлену в соответствии с формулами:

Доказательство. Воспользоваться формулами (7.16) и (8.5).

Определение. Покомпонентное произведение двух многочленов

определим равенством

Обозначим через остаток от деления произвольного многочлена на .

Лемма 21. Если а — двоичный вектор, то его МС-многочлен является идемпотентом кольца многочленов над по модулю многочлена т. е.

Доказательство. Согласно теореме 20 равно 0 или 1. Тогда утверждение следует из леммы 2.

Теорема 22. (Другие свойства.)

тогда и только тогда, когда

(iii). Аналогично тогда и только тогда, когда

(iv). МС-многочлен циклического сдвига вектора а равен .

(v). МС-многочлен векторов 0 и 1 равен соответственно

Общая проверка на четность на векторе а задается равенством

Доказательство, Если то следовательно, Наоборот, предположим, что для всех Тогда нам надо показать, что

Согласно (7.16) правая часть в (8.11) равна многочлену

приведенному по модулю Коэффициент при в этом произведении равен:

Согласно лемме 6 гл. 7 внутренняя сумма равна нулю, за исключением случая так что выражение становится равным

что согласно теореме 20 равно коэффициенту при в левой части равенства (8.11).

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

Проанализируем теперь более тщательно соответствие и его многочлена Мэттсона — Соломона (см. рис. 8.6).

Пусть обозначает множество всех многочленов от с коэффициентами из степень которых менее Множество может быть превращено в кольцо (см. § 7.2) двумя способами. В обоих кольцах сложение определяется обычным образом. Умножение двух многочленов в кольце осуществляется по модулю т. е. . В кольце произведение многочленов есть определенное выше покомпонентное произведение

Тогда отображение, которое ставит в соответствие многочлену его МС-многочлен является согласно теореме 22 изоморфизмом колец Обратное отображение определяется равенством (8.9). (Отображение кольца А в кольцо В, сохраняющее операции сложения и умножения: называется гомоморфизмом этих колец. Если взаимно однозначно и является отображением «на», то называется изоморфизмом колец

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

в идемпотент из Заметим, что идемпотенты кольца сами образуют кольцо так как в поле характеристики 2 сумма двух идемпотентов опять является идемпотентом. На самом деле кольцо является образом кольца при МС-отображении, так как согласно лемме 2 и теореме 20 прообраз идемпотента из лежит в Таким образом, отображение является кольцевым изоморфизмом.

Рис. 8.6. Отображение Мэттсона-Соломона

Пусть кольцо, состоящее из всех многочленов кольца но с покомпонентным умножением. (Отметим, что относительно покомпонентного умножения элементы кольца идемпотентами не являются.) Тогда отображение также является кольцевым изоморфизмом (см. рис. 8.6).

Двоичные линейные коды являются линейными подпространствами в (или в S(x) и, следовательно, в (или в ). Как мы видели в теореме 1, идеал в состоит из всех кратных некоторого фиксированного многочлена. Идеалы в также имеют простую структуру.

Лемма 23. Идеал в состоит из множества всех многочленов таких, что для некоторого фиксированного подмножества индексов

Доказательство. Пусть образ рассматриваемого идеала в Так как также идеал, то в поле у него имеется определенное множество нулей, а именно корни порождающего многочлена, так что

Например, код БЧХ в узком смысле с конструктивным расстоянием является идеалом в

В гл. 12 показано, что коды Гоппы могут быть описаны как кратные некоторого фиксированного многочлена в Однако идеалы в представляют специального интереса (см. упражнение (50)).

Упражнения. (48). Показать, что при кольцо состоит из многочленов:

(49). Пусть «циклический код» в т. е. такое подпространство в что Показать, что или

(50). Пусть — идеал в Показать, что соответствующий ему в код состоит из всех векторов, у которых в некоторых фиксированных координатах стоят нули. Таким образом, такие коды неинтересны. [Указание. Работать в кольце

Многочлен локаторов. Предположим, что ненулевыми координатами вектора являются и только они (здесь Сопоставим вектору а элементы поля вида называемые локаторами вектора а, и элементы поля вида задающие значения ненулевых координат. Таким образом, вектор а полностью определяется набором . В случае двоичного вектора а все естественно, равны 1.

Заметим, что

Определение. Многочлен локаторов вектора а равен

(Корни многочлена являются величинами, обратными локаторам.) Таким образом, коэффициенты а, представляют собой элементарные симметрические функции от

Обобщенные тождества Ньютона. Величины связаны системой однородных линейных уравнений.

Теорема 24. Для всех величины удовлетворяют рекуррентному соотношению

В частности, выбирая , получаем:

Доказательство. В уравнении

положим и умножим его на

Суммируя по , получаем (8.12).

Упражнения. (51). Пусть а — вектор веса да. Показать, что матрица

невырождена при и вырождена, если

(52). Обычная форма тождеств Ньютона. Пусть переменные и

где элементарные симметрические функции от причем для всех Для всех определим степенные суммы равенством

(a). Показать, что если то

(b). Приравнивая коэффициенты при одинаковых степенях переменной, показать, что

Заметим, что в случае, когда все равны 1 (т. е. в случае, когда вектор а двоичный), формула (8.15) совпадает с (8.12).

(53). Предположим, что принимают значения в поле характеристики Показать, что если при фиксированном имеет место равенство для всех в диапазоне не делящихся на то для

(54). Показать, что в двоичном случае из уравнений (8.14) и (8.15) вытекает равенство

(55). (Чень.) Используя уравнение (8.12), дать другое доказательство границы БЧХ.

(56). (Чень и Показать, что в двоичном случае МС-многочлен для может быть получен из многочлена локаторов для по формуле

где

Следовательно,

Применение к декодированию кодов БЧХ. Как мы увидим в следующей главе, уравнения (8.12) — (8.16) играют важную роль при декодировании кода БЧХ с конструктивным расстоянием 5. В этом приложении роль а играет вектор ошибок, по которому декодер легко находит Затем на основании уравнений (8.12) — (8.16) определяется многочлен Для определения значений введем многочлен значений для

Если многочлен известен, то определяются равенствами

Теорема 25.

где

Заметим, что так как то для определения многочлена по формуле (8.19) необходимо только знание величин Доказательство.

Вес вектора. Теорема 26. Вес вектора а равен где число корней степени из единицы, являющихся корнями его многочлена Мэттсона-Соломона .

Доказательство. Вытекает из (8.9).

Следствие 27. Если -многочлен вектора а, то

Воспользуемся теоремой 26 для того, чтобы дать другое доказательство границы БЧХ.

Теорема 28. (Граница БЧХ.) Пусть — циклический код с порождающим многочленом где множество К содержит отрезок последовательных целых чисел для некоторого Тогда минимальный вес любого ненулевого кодового слова а из равен по меньшей мере

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

Пусть

Ясно, что число корней степени из единицы, являющихся корнями многочлена равно числу корней степени из единицы, являющихся корнями многочлена Это число не превосходит Таким образом, согласно теореме 26 вес вектора а не меньше

Многочлены Мэттсона — Соломона для минимальных идеалов. В остальной части параграфа мы ограничимся рассмотрением только двоичных кодов.

МС-многочлены элементов соответственно равны:

Из этих формул видно, что легче работать с идемпотентами чем с идемпотентами При условии достаточной внимательности

можно упростить обозначения, используя функцию следа. Пусть

причем показатели, большие чем немедленно приводятся по модулю Например, если то и не равно Игнорирование этого соглашения приведет к ошибке.

Упражнение. (57). Для показать, что если со-—примитивный кубический корень из единицы, то при

Таким образом, МС-многочленами элементов соответственно являются:

Нам придется встречаться также с минимальными идеалами, которые не являются циклическими сдвигами идемпотентов. Пусть произвольный минимальный идеал. Согласно теореме 9 элементы образуют подполе поля изоморфное полю Следовательно, МС-преобразование многочлена равно

где элемент из . В последнем выражении показатель должен быть редуцирован по модулю показатель модулю

Многочлены Мэттсона — Соломона для кодовых слов. Согласно пункту (iii) теоремы 7 каждый многочлен может быть записан в виде

Его МС-преобразование равно:

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

Заметим, что равенство (8.21) может быть переписано в виде

где — множество представителей с возможными повторениями. Тогда МС-преобразование многочлена равно:

Пусть циклический код, ненули которого лежат в циклотомических классах Кодовое слово из тогда записывается в виде

а его МС-многочлен

Кодовое слово из имеет вид

а его МС-многочлен

Пример. Коды длины 15. (см. упражнение (7)). [15, 4, 8] симплексный код состоит из векторов, МС-многочлен которых

В общем случае симплексный код задается условием:

[15, 2, 10] симплексный код состоит из векторов Их МС-многочлены равны:

т. е.

[15, 4, 6]-код имеет МС-многочлены

[15, 11, 3]-код Хэмминга состоит из векторов вида

где Соответствующие МС-многочлены:

Аналогичные формулы имеют место для любого кода Хэмминга.

Упражнение. (58). Показать, что [23, 12, 7]-код Голея состоит из векторов, МС-многочлен которых имеет вид:

Другая формула для веса вектора. Теорема 31 дает формулу, которая иногда позволяет найти точное распределение весов кода. Доказательство этой формулы основано на одном тождестве (теорема 29) для МС-многочлена.

Пусть производная от многочлена Заметим, что в поле характеристики 2 многочлен состоит только из тех членов многочлена в которых нечетно.

Теорема 29. МС-многочлен произвольного вектора а удовлетворяет равенству

Доказательство. Согласно (8.24) утверждение теоремы достаточно доказать для где Пусть означает остаток от делении на Тогда

Отметим, что степени переменной в многочлене могут быть больше чем Если четно, то

и в выражении члены со степенями входящие в многочлен аннулируются членами со степенями входящими в многочлен Если нечетно, то

Объединяя члены со степенями многочлена и члены со степенями многочлена получаем:

(напомним, что Таким образом, окончательно получаем произведение многочлена на нечетные степени многочлена т. е.

Упражнение. (59). Проверить теорему для

Следствие 30. Если корень многочлена или многочлена то равно нулю или единице.

Определим:

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

Теорема 31. Вес вектора с МС-многочленом равен:

Упражнение (60). Пусть двоичное представление веса вектора имеет вид

где равно нулю или единице. Доказать, что:

[Указание. Воспользоваться теоремой Лукаса-—теоремой 28 гл. 13.]

(iii). Таким образом, если вес да четен, то