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