Xreferat.com » Рефераты по математике » Построение порождающего полинома циклического кода по его корням (степеням корней)

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

/>)=0.

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

Теорема. 1. Предположим, что fi(x) над GF(p) является минимальным полиномом элемента Построение порождающего полинома циклического кода по его корням (степеням корней) из GF(pm). Тогда f(x) является также минимальным полиномом элементаПостроение порождающего полинома циклического кода по его корням (степеням корней).

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

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

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


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


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

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

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

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

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

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

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

Два сопряженных между собой элемента будут иметь один и тот же минимальный полином.

Теорема 2. Минимальный полином элемента Построение порождающего полинома циклического кода по его корням (степеням корней) равен


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


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

Следствие из теоремы 2: Все элементы GF(pm) являются корнями полиномов.

Построим минимальный полином для элемента Построение порождающего полинома циклического кода по его корням (степеням корней)из GF(24). Сопряженные элементы для Построение порождающего полинома циклического кода по его корням (степеням корней) найдены выше.

Используя теорему 2, запишем минимальный полином в общем виде:


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


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


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


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

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

Резюме: Для нахождения минимального полинома для элемента Построение порождающего полинома циклического кода по его корням (степеням корней) из GF(pm) необходимо:

Построить расширение поля по модулю некоторого неприводимого над GF(p) полинома.

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

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

Раскрыть скобки разложения, не приводя подобные.

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

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

Раскрыть скобки, привести подобные, учитывая тот факт, что суммирование ведется по модулю p.

Рассмотрим подробнее следствие 2 из теоремы 1:

Циклотомический класс для элемента Построение порождающего полинома циклического кода по его корням (степеням корней): {1, 2, 4 ,8} для этих четырех элементов будут одинаковые минимальные полиномы.

Рассмотрим более подробно пример нахождения минимальных полиномов для GF(24).

Построение GF(24) рассмотрено выше, будем пользоваться готовым результатом.


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

Таблица 2. Представление GF(24).


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


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


Так как все элементы получились одинаковыми, то циклотомический класс будет состоять из одного элемента – {0}.


При помощи теоремы 2 запишем: m0(a0) = (x - a0 ), заменим a0 на элемент поля.

Минимальная функция для элемента a0: m0(a0) = (x + 1)

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

Используя формулу 1, получим циклотомический класс. {1, 2, 4, 8}.

Используя теорему 2, запишем разложение минимального полинома.


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


Теперь заменим a на элементы поля, после раскрытия скобок и приведения подобных получим минимальный полином для элементов со степенями 1, 2, 4, 8.

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

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

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

Используя формулу 1, запишем циклотомический класс: C = {3,6,12,24}, как видно элемент со степенью 24 отсутствует в представлении поля GF(24). Если разделить Построение порождающего полинома циклического кода по его корням (степеням корней)на полином, по модулю которого производилось построение GF(24), то получим остаток Построение порождающего полинома циклического кода по его корням (степеням корней). Построение порождающего полинома циклического кода по его корням (степеням корней)

Используя теорему 2, запишем разложение минимального полинома:


m3(x) = (x – a3 ) (x – a6 ) (x – a9 ) (x – a12 ).


Теперь, раскрыв скобки и приведя подобные, получим полином m3(x) = x4 + x3+ x2 + x1+1.

Следовательно, это полином для элементов со степенями 3,6,12,9.

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

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

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

Используя формулу 1, запишем циклотомический класс: C = {5,10,5,10}. Так как элементы класса совпали, то в классе останется два элемента C = {5,10}.

Используя теорему 2, запишем разложение минимального полинома:


m5(x) = (x – a5 ) (x – a10 ) = x2 + x+1


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

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

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

Используя формулу 1, запишем циклотомический класс: C = {7,14,28,56}. Так как Построение порождающего полинома циклического кода по его корням (степеням корней), то C = {7,14,11,13}

Используя теорему 2, запишем разложение минимального полинома:


m7(x) = (x – a7 ) (x – a14 ) (x – a11 ) (x – a13 ) = x4 + x3+1


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


2. О циклических кодах и корнях порождающего полинома с точки зрения конечных полей


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

Теорема 3. Циклический код длины n с порождающим полиномом g(x) существует тогда и только тогда, когда g(x) делит Построение порождающего полинома циклического кода по его корням (степеням корней).

Следствие из теоремы 3. Порождающий полином циклического кода длины n можно найти, разложив полином Построение порождающего полинома циклического кода по его корням (степеням корней) на простые множители:


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


где s – число простых множителей. Произведение произвольного подмножества этих множителей дает порождающей многочлен g(x). Если g(x) – порождающий полином, то он делит Построение порождающего полинома циклического кода по его корням (степеням корней), и, следовательно, Построение порождающего полинома циклического кода по его корням (степеням корней). Полином g(x) можно найти, найдя все его простые делители.

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

Резюме:

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

Пусть Построение порождающего полинома циклического кода по его корням (степеням корней) - корень полиномаПостроение порождающего полинома циклического кода по его корням (степеням корней). Тогда Построение порождающего полинома циклического кода по его корням (степеням корней) не что иное, как функция минимума для Построение порождающего полинома циклического кода по его корням (степеням корней).

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

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

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


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


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


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


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

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

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

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

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

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

Рассмотрим каждый шаг более подробно на примере кода (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: m3(x) = (x – a3 ) (x – a6 ) (x – a9 ) (x – a12 ) = x4 + x3+ x2 + x1+1.

Для корня со степенью 5: m5(x) = (x – a5 ) (x – a10 ) = x2 + x+1

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

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


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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: