Построение порождающего полинома циклического кода по его корням (степеням корней) (стр. 2 из 4)

1

1 = 0

1

0 = 1

0

0 = 0

0

1 = 1

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

Деление полиномов.

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

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

Рассмотрим деление пошагово:

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

: . Теперь если сложить и по модулю два, то так как присутствует в обоих операндах, то эти элементы сокращаются, так как они одинаковые. Итак, результат первого шага деления:

Далее нужно взять делитель один раз, т.е. умножить его на

и сложить результат по модулю два с результатом предыдущего шага. Таким образом, получим:

Итак,

- частное от деления, а - остаток.

Умножение полиномов.

Умножим полином

на полином .

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

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

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.

Таким образом, для элемента

будут сопряженными элементы

Следует иметь ввиду, что при построении циклотомического класса, степень элемента

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