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

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

Оглавление


Предисловие

1. Краткие теоретические сведения

1.1 Полиномиальное представление двоичных чисел

1.2 Циклический код

1.3 Поле

1.4 Поля Галуа

1.4.1 Примитивный элемент поля и циклическая группа

1.4.2 Модульная арифметика и деление полиномов

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

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

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

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

Заключение

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

Приложения


Предисловие


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


1. Краткие теоретические сведения


1.1 Полиномиальное представление двоичных чисел


Весьма удобным является представление двоичных чисел в виде полиномов степени n -1, где n – количество разрядов числа.

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

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


1.2 Циклический код


Циклические коды относят к классу линейных кодов. Для обеспечения коррекции ошибок к блоку информационных разрядов добавляется блок контрольных разрядов. Значения контрольных разрядов формируются путем некоторых линейных операций над информационными разрядами, поэтому такие коды называются линейными. Линейный код называется циклическим, если слово Построение порождающего полинома циклического кода по его корням (степеням корней) принадлежит данному коду, и слово Построение порождающего полинома циклического кода по его корням (степеням корней) также принадлежит этому коду. Проще говоря, если циклически сдвинуть кодовую комбинацию, то в результате также получится кодовая комбинация, принадлежащая данному коду. Это самое важное свойство циклических кодов. Циклический код задается при помощи порождающего полинома g(x). На сегодняшний день существуют таблицы с параметрами кода - длина, мощность корректирующая способность и корни порождающего полинома. Порождающий полином, как правило, представлен в виде степеней его корней. Обозначим за n длину кода, если длину n можно представить в виде Построение порождающего полинома циклического кода по его корням (степеням корней), где m – целое положительное число, то такой код называют кодом с тривиальной длиной.


1.3 Поле


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

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

Результатом умножения и сложения элементов поля является элемент также из этого поля.

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

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

Для умножения и сложения выполняются правила ассоциативности, коммутативности и дистрибутивности.


1.4 Поля Галуа


Конечное поле или поле Галуа – это поле (далее конечное поле обозначено, как GF(p)), содержащее конечное число элементов. Нужно отметить, что аксиомы 1 – 5, справедливы, как для поля с конечным числом элементов, так и с бесконечным, но главное отличие конечных полей от бесконечных определяет аксиома 2. Из этого вытекает, что на понятие «умножение» и «сложение» накладывается ряд ограничений. Выполнение аксиомы 2 осуществляется выполнением по модулю некоторого числа p, называемым характеристикой поля.

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

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


1.4.1 Примитивный элемент поля и циклическая группа

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

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

Выше было сказано, что полином Построение порождающего полинома циклического кода по его корням (степеням корней) должен быть специальным, это означает, что любые операции, выполняемые по модулю Построение порождающего полинома циклического кода по его корням (степеням корней)должны оставаться обратимыми, иначе система не образует поле. Таким образом, полином Построение порождающего полинома циклического кода по его корням (степеням корней)должен быть неприводимым в поле GF(p), т.е. его нельзя разложить на множители, используя только многочлены с коэффициентами из поля GF(p). Аналогом неприводимого полинома является простое число. На сегодняшний день не существует систематического способа поиска неприводимых полиномов. Наиболее обширная таблица неприводимых полиномов представлена в книге [1].

Резюме: Расширение поля содержит полиномы степени m-1 и меньше, с коэффициентами из основного поля. Любой элемент расширения поля можно получить, как степень примитивного элемента Построение порождающего полинома циклического кода по его корням (степеням корней). Умножение проводится по модулю неприводимого над полем GF(p) полиномом. Описанная выше теория может показаться запутанной, но ниже будет дан пример, который поможет понять изложенные теоретические сведения.


1.4.2 Модульная арифметика и деление полиномов

Рассмотрим, сложение и умножение по модулю некоторого числа p, это означает проведение операции по обычным правилам, а затем деление результата на число p. Например, умножим 7 на 3 по модулю 10. Обозначим проведение операции по модулю, как «mod» Построение порождающего полинома циклического кода по его корням (степеням корней). Построение порождающего полинома циклического кода по его корням (степеням корней) Теперь получившийся результат, разделим на 10 и возьмем остаток, остаток равен единице, следовательно Построение порождающего полинома циклического кода по его корням (степеням корней). Но так как, для работы с двоичными циклическими кодами нам понадобится конечное поле GF(2), которое содержит два элемента – нуль и единицу, то рассмотрим сложение по модулю два. Сумма по модулю два обозначается знаком Построение порождающего полинома циклического кода по его корням (степеням корней).

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

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

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

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

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

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

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


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


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


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


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


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


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


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


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

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

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

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

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

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

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

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

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

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

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


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


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

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


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


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

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


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

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

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

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

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

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