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

3. Имея корни полиномов – делителей g(x) можно найти их функции минимума, и следовательно найти g(x) .

4.

содержит корни g(x).

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

,

где

минимальный полином.

2.1 Нахождение порождающего полинома по последовательности степеней корней

В таблице из приложения Г книги [1] содержатся параметры циклических кодов и последовательности степеней корней. Мы рассматриваем только коды тривиальной длины. Часть этой таблицы указана в приложении А данной работы. В таблице из приложения В книги [1] указаны неприводимые полиномы над GF(2). Укороченное представление такой таблицы также есть в приложении Б данной работы.

Алгоритм нахождения порождающего полинома:

1. Исходя из длины выбранного кода, построить расширение

поля по модулю неприводимого полинома над степень которого равна m. Где m находится из следующего соотношения: .

2. Для каждого корня построить циклотомический класс.

3. Для каждого корня найти минимальный полином.

4. Перемножить полученные минимальные полиномы по правилам для

.

Рассмотрим каждый шаг более подробно на примере кода (15,5,7) . Для такого кода в таблице циклических кодов указаны следующие степени корней {1,3,5}.

Шаг 1. Построение

.

Длина n заданного кода равна 15. Так как

, m = 4. Будем строить . Так как m = 4, то из таблицы неприводимых полиномов выберем полином четвертой степени , по модулю которого будет построено . Как построить расширение поля, было рассмотрено в 1.4.3.

Таблица 3.

.

Шаг 2. Построение циклотомических классов.

Последовательность степеней корней для данного кода - {1,3,5}. Для каждого элемента последовательности построим циклотомический класс, при помощи формулы

. Подробно построение циклотомических классов описано в 1.4.4

Для корня со степенью 1 это {1,2,4,8}.

Для корня со степенью 3 это {3,6,9,12}.

Для корня со степенью 5 это {5,10}.

Шаг 3. Нахождение минимальных полиномов.

Исходя из теоремы 2, для каждого корня найдем его минимальный полином, подробно нахождение минимальных полиномов описано выше.

Для корня со степенью 1:

Для корня со степенью 3: m₃(x) = (x – a³ ) (x – a⁶ ) (x – a⁹ ) (x – a¹² ) = x⁴ + x³+ x² + x¹+1.

Для корня со степенью 5: m₅(x) = (x – a⁵ ) (x – a¹⁰ ) = x² + x+1

Шаг 4. Нахождение порождающего полинома.

Из 1.5

, где это минимальные полиномы для заданных корней, то было получено, что

Заключение

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

Список литературы

1. У. Питерсон, Э. Уэлдон. «Коды, исправляющие ошибки»: Москва: Мир, 1976.

2. Р. Блейхут. «Теория и практика кодов исправляющих ошибки»: Москва: Мир, 1986. - 576с.

3. Жуков А.Б. , Каменский С.В. Передача сообщений. – НГТУ, 2003.

Приложения

Приложение А. Таблица неприводимых полиномов над GF(2).

Приложение Б. Таблица двоичных некоторых циклических кодов тривиальной длины