5.3. МИНИМАЛЬНЫЕ МНОГОЧЛЕНЫ И СОПРЯЖЕНИЯ

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

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

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

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

Мы начнем с одного предпочитаемого значения называемого примитивной длиной кода.

Определение 5.3.1. Для кода над длина вида называется примитивной Циклический код примитивной длины над называется примитивным циклическим кодом.

Поле является расширением поля Согласно теореме об однозначном разложении, разложение

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

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

Теперь мы можем связать данное определение циклического кода с использованной в § 5.1 его трактовкой.

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

где с вычисляется в поле

Доказательство. -сли с то имеем с Обратно, предположим, что с и запишем

где степень меньше стененн минимальный многочлен элемента Но тогда из равенства

следует, что Следовательно, с должен делиться на Для всех а поэтому и на

Чтобы проиллюстрировать эти идеи, выберем Можно найти все циклические коды длины 15, разложив на простые многочлены:

Справедливость такого разложения можно проверить перемножением, а простоту множителей — методом проб и ошибок. Всего имеется подмножества множества этих простых множителей и, следовательно, 32 порождающих многочлена циклических длины 15. Два из них являются тривиальными, а 30 приводят к нетривиальным циклическим кодам. В качестве примера рассмотрим один из них, положив

Так как степень равна 8, то а так как вес многочлена равен 5, то минимальное расстояние не превосходит 5. В гл. 7 мы увидим, что минимальное расстояние равно 5. Следовательно, рассматриваемый код является -кодом и позволяет исправлять две ошибки. Проверочные соотношения могут быть записаны в виде

где — некоторые корни многочленов соответственно из расширения В частности, с следовательно, это рассмотренный в § 5.1 пример. (Многочлен имеет, конечно, и другие корни, но этих двух корней достаточно, чтобы определить и нет необходимости проверять остальные.)

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

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

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

Теорема 5.3.3. Пусть характеристика поля равна Тогда для любого многочлена над и произвольного целого выполняется равенство

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

Доказательство. Начнем и будем рассуждать так же, как при доказательстве теоремы 4.6.10. Чтобы сократить число шагов, определим многочлен равенством тогда

Но

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

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

Далее,

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

Доказательство. Так как равно степени характеристики поля, то теорема 5.3.3 дает

Но коэффициенты принадлежат полю а все элементы этого поля удовлетворяют условию Следовательно,

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

Определение 5.3.5. Два элемента из поля являющиеся корнями одного и того же минимального многочлена над называются сопряженными (относительно поля

В общем случае у элемента может быть больше, чем один, сопряженный элемент — на самом деле Необходимо также отметить, что отношение сопряженности зависит от основного поля.

Два элемента из могут быть сопряжены относительно поля и не сопряжены относительно поля

Используя теорему 5.3.4, легко выписать все сопряженные с элементы. Если многочлен является минимальным для элемента то он минимален и для элемента для Следовательно, сопряжены все элементы множества

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

Теорема 5.3.6. Минимальный многочлен элемента равен

Доказательство. Согласно теореме 5.3.4, все эти элементы действительно должны быть корнями минимального многочлена

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

где второе равенство вытекаег из теоремы 5.3.3 и того факта, что Таким образом,

в то время как теорема 5.3.3 утверждает, что

Следовательно, Для каждого I, и принадлежит подполю что и требовалось доказать.

Например, выберем а равным примитивному элементу поля Тогда множество

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

все коэффициенты которого (после раскрытия скобок) будут элементами поля GF (2). Аналогично множеством сопряженных элементов, содержащих элемент будет

а минимальный многочлен элемента равен

все коэффициенты которого (после раскрытия скобок) будут элементами поля GF (2).

Теперь вместо выберем в качестве основного поля которое также является подполем поля ; тогда множеством сопряженных элементов, содержащим «7, будет

и минимальный многочлен элемента а над полем равен

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

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

Теорема 5.3.7. Пусть конечное поле. Если взаимно просты, то многочлен делит многочлен при некотором и многочлен имеет различных корней в расширении поля

Доказательство. Необходимо доказать только, что делит некотором так как в этом случае можно воспользоваться общим разложением

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

Таким образом, делит и, следовательно, имеет различных корней в так как имеет различных корней в этом поле.

Чтобы доказать, что делнт для некоторого воспользуемся алгоритмом деления и выпишем следующих равенств:

Все остатки расположены между Так как их всего то по меньшей мере два из них равны между собой, скажем при I, меньшем Тогда

или

Так как взаимно просты, то должно делить Полагая завершаем доказательство.

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

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