Контрольная работа: Построение порождающего полинома циклического кода по его корням (степеням корней)

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

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

1.4.3 Построение конечного поля

Определение: Многочленом над конечным полем называют многочлен, коэффициенты которого лежат в .

Построение порождающего полинома циклического кода напрямую связано с расширением конечного поля, рассмотрим построение расширения поля. Так как в рамках данной работы рассматриваются двоичные циклические коды, то не трудно догадаться, что основное поле Галуа будет состоять из двух элементов – нуля и единицы - GF(2). Построим расширение поля GF(2⁴ ), это поле пригодно для построения циклического кода длины 15, так как 2⁴ -1 = 15. Для построения расширения поля нужно выбрать полином по модулю которого оно будет построено, исходя из того, что m = 4 необходим полином четвертой степени. Из таблицы в книге [1] или таблицы из приложения выберем полином . Примитивный элемент поля – x. Напомним, что расширение поля является мультипликативной группой примитивного элемента , в нашем случае это x, а также умножение будет проводиться по модулю неприводимого полинома . Начнем со степени элемента x равной 0.

Умножим на по модулю полинома : , разделим х на , остаток от деления равен х. Не будем рассматривать формирование элементов соответствующих 1-3 степеням, рассмотрим формирование элементов для степеней 4 и 5:

Рассмотрим вычисление элемента

Рассмотрим вычисление элемента

И так далее, пока не будет получено 2⁴ = 16 элементов. Ниже представлено представление поля GF(2⁴ ), полученного способом, изложенным выше.

Таблица 1. Представление поля GF(2⁴ ).

1.4.4 О корнях полиномов и минимальных полиномах

Минимальным полиномом или функцией минимума элемента поля GF(p^m ) называется полином m_i (x) наименьшей степени с коэффициентами из GF(p), для которого является корнем, иначе говоря, m_i ()=0.

Рассмотрим теорему, которая является ключевой для построения порождающего полинома кода по последовательности корней, ее доказательство можно найти в книгах [1] и [2].

Теорема. 1 . Предположим, что f_i (x) над GF(p) является минимальным полиномом элемента из GF(p^m ). Тогда f(x) является также минимальным полиномом элемента.

Определение. Два элемента из GF(p^m ) называются сопряженными, если они являются корнями одного и того же минимального полинома над GF(p) (это означает, что коэффициенты полинома лежат в GF(p)).

Следствие 1 теоремы 1:

Можно сделать вывод, что у элемента может быть не один сопряженный элемент, таких элементов может быть m или меньше. Используя теорему 1 можно составить последовательность сопряженных элементов, такую последовательность в литературе еще называют циклотомическим классом. Множество элементов, входящие в циклотомический класс (сопряженные элементы) можно найти по следующей формуле:

(1)

Где, С – циклотомический класс, s – степень элемента для которого находятся сопряженные элементы, p – показатель основного поля, m – число элементов расширения поля.

Рассмотрим пример нахождения циклотомического класса для элемента из GF(2⁴ ). Здесь и далее будем представлять элемент, как его степень.

Итак, s = 1, p = 2, m = 4.

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

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

Следствие 2 из теоремы 1: