Оглавление
Предисловие
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. Операцияумножения обозначается как />,сложение, как />.
2. Результатомумножения и сложения элементов поля является элемент также из этого поля.
3. Для любогоэлемента поля не равного нулю, существует обратный элемент по сложению иумножению, так что /> и />
4. Поле всегдасодержит мультипликативную единицу 1, так что />иаддитивную единицу 0, так что />.
5. Для умножения исложения выполняются правила ассоциативности, коммутативности идистрибутивности.
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 (/>)=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) необходимо:
1. Построить расширениеполя по модулю некоторого неприводимого над GF(p) полинома.
2. Построить циклотомическийкласс для элемента />, учитывая то,что одинаковые элементы в классе учитываются только один раз и то, что степеньэлемента класса может превышать максимальную степень элементов расширения поля.
3. При помощитеоремы 2 записать разложение минимального полинома, используя в качествекорней элементы циклотомического класса.
4. Раскрыть скобкиразложения, не приводя подобные.
5. Проверить, непревышает ли степень /> максимальнуюстепень элементов GF(pm) (см. выше).
6. Заменить элементы/> на элементы поля.
7. Раскрыть скобки,привести подобные, учитывая тот факт, что суммирование ведется по модулю 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) можно найти, найдя все его простые делители.
Простые делители есть нечто иное, как функции минимума или минимальные полиномы. Таким образом, знаякорни минимальных полиномов, можно легко найти порождающий полином кода. Исходяиз сказанного в предыдущих разделах, можно сделать вывод, что поле /> как раз содержит корниминимальных полиномов, а следовательно содержит корни порождающего полинома.
Резюме:
1. Порождающийполином не что иное, как произведение его простых делителей />.
2. Пусть /> - корень полинома/>. Тогда /> не что иное, как функцияминимума для />.
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: 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 />, где /> это минимальные полиномыдля заданных корней, то было получено, что
/>
Заключение
В данной работерассмотрено краткое математической описание циклических кодов с точки зрения алгебрыконечных полей, которого вполне достаточно для решения задачи нахожденияпорождающего полинома кода, используя его корни. Безусловно, материал изложен вочень сжатой форме и многое нужно принять, как аксиому. Изначально даннаяработа задумывалась, как описание алгоритма нахождения полинома с некоторымикомментариями к каждому шагу, но в процессе описания алгоритма, оказалось, чтобез краткой теории конечных полей это сделать невозможно.
Список литературы
1. У. Питерсон, Э.Уэлдон. «Коды, исправляющие ошибки»: Москва: Мир, 1976.
2. Р. Блейхут.«Теория и практика кодов исправляющих ошибки»: Москва: Мир, 1986. — 576с.
3. Жуков А.Б.,Каменский С.В. Передача сообщений. – НГТУ, 2003.
Приложения
Приложение А. Таблицанеприводимых полиномов над GF(2).
/>
Приложение Б. Таблица двоичных некоторых циклических кодов тривиальнойдлины
/>
/>/>