7.5. ДЕЛИТЕЛИ МНОГОЧЛЕНА x^n-1

Так как порождающий многочлен циклического кода длины над GF(q) является делителем многочлена то в данном параграфе мы изучаем эти делители и вводим поле разложения многочлена

Мы всюду предполагаем, что взаимно просты. (Таким образом, в двоичном случае нечетно.) Согласно упражнению (8) гл. 4 существует такое наименьшее положительное целое число что делит Это число называется мультипликативным порядком по модулю . В соответствии с упражнением (11) гл. 4 многочлен делит и не делит —1 ни для какого

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

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

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

Поле называется поэтому полем разложения многочлена

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

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

(13). Доказать, что корни многочлена образуют мультипликативную группу поля тогда и только тогда, когда

Разложение многочлена x^n-1 над GF(q). Циклотомические классы по модулю были определены в § 4.3. В более общем случае циклотомический класс по модулю над GF(q) определяется как множество:

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

где пробегает множество представителей классов по модулю Отметим, что равно числу элементов в классе С Например, для имеем:

Таким образом, и многочлен разлагается на линейные множители в

Как и в гл. 4 (см., в частности, упражнение (14)), минимальный многочлен элемента равен:

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

где пробегает все множество представителей по модулю Это дает разложение многочлена на неприводимые многочлены над полем GF(q).

Например, для имеем:

где

На рис. 7.1 приведено разложение многочлена над на неприводимые множители для Так как (лемма 5 гл. 4), то в таблицу включены только нечетные значения

Рис. 7.1. Разложение многочлена над

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

Упражнения. (14). Доказать, что если взаимно просты, то содержит элементов.

(15). Пусть где К—подмножество чисел Доказать, что коэффициенты лежат в GF(q) тогда и только тогда, когда

(16). Доказать, что если делит над

(17). Доказать, что свойства выведенные в гл. 4, имеют место и для данного выше общего определения минимальных многочленов над произвольным полем.

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

где, по упражнению (15),

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

Ясно, что если то принадлежит тогда и только тогда, когда для всех Это дает определение циклического кода в терминах корней многочлена Согласно упражнению (16) нули дуального кода обратны ненулям исходного кода. Иными словами, если нули кода где пробегает классы то ненули кода это элементы где пробегает циклотомические классы

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

Лемма 5. Если не вводит никаких новых нулей, т. е. если для всех то многочлены порождают один и тот же код. (В частности, порождает тот же код, что

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

Отсюда

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

Упражнение. (18). Пусть Доказать, что где

Лемма 6. Пусть произвольный корень многочлена Тогда

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

Лемма 7. (Формула обращения). Вектор можно найти по многочлену по формуле

Доказательство.

Упражнения. (19). Обозначим через А следующую матрицу Вандермонда над (см, лемму 17 гл. 4):

где корень степени из единицы.

Доказать, что и

(20). Пусть

Доказать, что упражнение (7) гл. 16). Это дает другое доказательство того, что

(21). Показать, что вектор 1 принадлежит циклическому коду тогда и только тогда, когда Показать, что двоичный циклический код содержит вектор нечетного веса в том и только в том случае, когда он содержит вектор 1.