3.2.1. Арифметика gf(q)

Множество А образует поле, если для любых элементов a_i, a_j, a_k  А определены операции сложения «+» и умножения «» и выполня­ются следующие аксиомы:

Сложение «+»

(А1) Замкнутость a_i + a_j  А

(А2) Ассоциативность (a_i + a_j) + a_k = a_i + (a_j + a_k)

(A3) Существование единственного нулевого элемента 0  А, тако­го, что 0 + a_i = a_i

(А4) Обратный элемент (-a_i)  А такой, что (-а) + a_i = 0

(А5) Коммутативность a_i + a_j = a_j + a_i

Умножение «х»

(M1) Замкнутость a_i  a_j  А

(М2) Ассоциативность (a_i  a_j)  a_k = a_i  (a_j  a_k)

(М3) Существование единственного единичного элемента 1  А такого, что 1  a_i = a_i

(М4) Обратный элемент

(М5) Коммутативность a_i  a_j = a_j  a_i

Сложение и умножение

(D) Дистрибутивность a_i  (a_j + a_k) = a_i  a_j + a_i  a_k

Из перечисленных выше аксиом следуют важнейшие правила ариф­метики, справедливые в любом поле:

Для 0,1, а, b, с  А имеет место

1. а + 0 = 0  а = 0

2. a, b 0  a b  0

3. a = 0 и a  b = =  b= 0

4. -(a  b) = (-a)  b = a  -b)

5. a  0 и a  b = a  c/

Отметим также, что операции сложения и умножения имеют об­ратные операции: вычитания и деления, причем, вычитание опреде­ляется как а — b = а + (—b), а деление - как а  b = а  b^-1.

Неподготовленного читателя может смутить и даже испугать столь громоздкое аксиоматическое построение алгебраической струк­туры, называемой полем. Однако, эти страхи должны довольно быстро исчезнуть после того, как мы убедимся, что множество ра­циональных чисел образует поле. Напомним, что множество рацио­нальных чисел содержит все положительные и отрицательные целые числа (включая ноль), а также все числа вида п/т, где п, т - целые и т  0. Операциями сложения, вычитания, умножения и деле­ния в поле рациональных чисел являются обычные арифметические операции, которые мы изучали еще в начальной школе. Нетрудно заметить, что эти операции удовлетворяют всем перечисленным выше аксиомам.

Расширениями поля рациональных чисел являются поля веще­ственных и комплексных чисел, они также содержат бесконечное множество элементов.

Так как в каналах связи множество передаваемых сигналов все­гда конечно, основой теории кодирования являются поля, содержа­щие конечное число элементов (поля Галуа). Простейшим полем Галуа является двоичное поле GF(2), операции в котором (сложение и умножение) выполняются по правилам арифметики «по модулю 2». Нетрудно заметить, что правила арифметики по mod 2 удовле­творяют всем вышеперечисленным аксиомам (с учетом того, что об­ратным элементом к «1» по сложению и умножению является сама "1").

В высшей алгебре доказывается, что число элементов q конечного поля GF(q) всегда удовлетворяет условию

q = p^m, (2.55)

где р – простое число, а т = 1,2, …

Другими словами, если число элементов q некоторого множества не удовлетворяет условию (2.55), то для этого множества невозмож­но определить операции сложения и умножения, удовлетворяющие аксиомам поля. Так, например, невозможно образовать поле с чис­лом элементов, равным 6, 10, 12, 14 и т.д., но можно построить поле, с числом элементов, равным 2, 3, 4, 5, 7, 8, 9, 11 и т.д.

Таблица 2.4. Операции сложения и умножения в GF(5).

+	0	1	2	3	4			0	1	2	3	4
0	0	1	2	3	4		0	0	0	0	0	0
1	1	2	3	4	0		1	0	1	2	3	4
2	2	3	4	0	1		2	0	2	4	1	3
3	3	4	0	1	2		3	0	3	1	4	2
4	4	0	1	2	3		4	0	4	3	2	1

Наиболее просто операции сложения и умножения выполняются в поле с числом элементов, равным простому числу (т = 1). Здесь они определены как операции сложения и умножения по mod р, а сами элементы образуют последовательность чисел

{0,1,2,...,р-1}. (2.56)

Для примера, в таблице 2.4. приведены результаты сложения и умножения всех пар элементов a_i, b_j{0,1,2,3,4}, т.е сумма a_i + b_j ( mod 5) и произведение a_i  b_j ( mod 5). Непосредственной провер­кой можно убедиться в выполнении аксиом (Al) - (А5), (Ml) - (М5) и (D) для операций сложения и умножения. Таким образом, множе­ство элементов a  {0,1,2,3,4} с операциями сложения и умноже­ния, заданными табл. 2.4, образуют поле GF(5).

В теории полей Галуа доказывается следующая, очень важная теорема.

Теорема 2.5.1. В поле Галуа GF(p¹), содержащем q элементов, су­ществует по крайней мере один примитивный элемент  такой, что каждый ненулевой элемент из GF(p) может быть представлен как некоторая степень .

Так, в поле GF(5) существует два примитивных элемента = 2 и ₂ = 3, так как 2⁰ = 1, 2¹ = 2, 2² = 4, 2³( mod 5) = 3 и 3⁰ = 1, 3¹ = 3, 3²( mod 5) = 4, 3³( mod 5) = 2.

Сложнее обстоит дело с построением полей Галуа GF(p^m), где т > 1 (простое число р называется характеристикой поля).

Так как теория кодирования имеет дело, в основном, с полями характеристики 2, рассмотрим основные методы построения полей GF(2^m).

Прежде всего, заметим, что каждый элемент GF(2^m) можно пред­ставить в виде слова длины m над GF(2) или многочлена с двоичны­ми коэффициентами, степень которого меньше, чем m. Так, напри­мер, любой элемент a  GF(2³) можно записать как двоичное слово a₂a₁a₀ или как многочлен a₂X² + a₁X + a₀, где {a₂, a₁, a₀}  {0,1}. В этом случае, сложение элементов из GF(2^m) выполняется по правилу сложения представляющих их многочленов в поле GF(2). Если при этом умножение элементов мы определим как умножение представ­ляющих эти элементы многочленов по модулю некоторого заданного неприводимого многочлена над GF(2) степени m, то тем самым мы построим поле Галуа GF(2^m).

Неприводимым называется многочлен, неразложимый на произ­ведение многочленов с коэффициентами из GF(2).

Проводя аналогию с полем GF(p), можно сказать, что роль эле­ментов GF(p) в поле GF(2^m) играют двоичные слова или многочле­ны степени, меньшей m, а роль простого числа р - неприводимый многочлен степени m.

Для реализации операций в поле GF(2^m) в качестве неприводи­мого многочлена степени m удобнее выбирать примитивный много­член.

Примитивным многочленом р(Х) над GF(2) называется непри­водимый многочлен степени m, такой, что в поле GF(2^m), построен­ного по его модулю, элемент поля X является примитивным.

В теории чисел и теории полей примитивный многочлен над конечным полем GF(p) —это минимальный многочлен примитивного элемента поля GF(p^m) для положительного целого числа m.

Примитивный многочлен является неприводимым.

В теории полей Галуа доказывается следующая теорема.

Теорема 2.5.2. Для каждого поля Галуа существуют примитивные многочлены всех степеней.

Таблица 2.5. Представление поля GF(2⁴) (Таблица антилогарифмов).

В качестве примера приведем поле Галуа GF(2⁴) (табл. 2.5). Для его построения был выбран примитивный многочлен четвертой сте­пени X⁴ + X + 1. Из таблицы видно, что степени примитивного эле­мента  = X образуют все множество ненулевых элементов GF(2⁴). В таком представлении операция умножения в поле GF(2⁴) реализу­ется очень просто. Пусть, например, нам требуется найти произведе­ние элементов (1011)  (1010). Из таблицы 2.5 находим, что элемент (1011) можно представить в виде ⁷, а (1010) в виде ⁹. Из этого следует, что (1011)  (1010) = ⁷  ⁹ = ^{(7+9) mod 15} = ¹. Используя табл. 2.5 еще раз, определяем, что ¹ соответствует элементу (0010). Окончательно получаем (1011)  (1010) = (0010).

При программной реализации умножения в полях Галуа, как пра­вило, используют так называемые таблицы логарифмов и антилога­рифмов. Таблица антилогарифмов ноля GF(2⁴) совпадает с табл. 2.5. Используя эту таблицу, очень легко определить двоичный экви­валент элемента ⁱ по заданному i, 0  i  14. Таблица логарифмов (табл. 2.6), наоборот, позволяет быстро найти степень примитивного элемента  по его двоичному представлению.

Так как операция деления в полях Галуа эквивалентна умноже­нию на обратный элемент, весьма полезной при вычислениях ока­зывается таблица обратных элементов (табл. 2.7), которая для поля GF(2⁴) строится следующим образом. Пусть, например, нам нуж­но найти обратный элемент к (1010). По таблице логарифмов нахо­дим, что (1010) соответствует ⁹. Обратным элементом к ⁹ являет­ся ^15-9 = ⁶. По таблице антилогарифмов находим, что двоичным эквивалентом ⁶ является (1100). Таким образом, окончательно по­лучаем (1010)^-1 = (1100).

Таблица 2.6. Таблица логарифмов элементов GF(2⁴).

0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
0	1	4	2	8	5	10	3	14	9	7	6	13	11	12

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

Реализация операции сложения (и совпадающей с ней операции вычитания) элементов в поле GF(2^m) не представляет проблем. Сло­жение элементов из GF(2^m) сводится к покомпонентному сложению их двоичных представлений по модулю 2. Так, например, в поле GF(2⁴) (0011) + (1101) = (1110).

Таблица 2.7. Таблица обратных элементов поля GF(24).

i	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
	0001	1001	1110	1101	1011	0111	0110	1111	0010	1100	0101	1010	0100	0011	1000

С подробным обоснованием построения полей GF(2^m) и исследо­ванием их алгебраической структуры читатель может ознакомиться в [5].

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

Используя методы абстрактной алгебры, можно показать, что в двоичном поле любой многочлен степени m раскладывается над GF(2^m). Для данного пособия достаточно ознакомиться с основами вычислений в конечных полях. Серьезным читателям настоятельно рекомендуется изучение абстрактной алгебры по хорошему учебнику.

Использование арифметики GF(2^m) в процедурах декодирования позволяет заменить сложные комбинационные схемы практичными процессорными архитектурами, пригодными для решения уравнения (3.8). Ниже приводятся инструменты, необходимые для решения систем уравнений, которые возникают при декодировании циклических кодов.

Важные свойства GF(2^m)

Поле Галуа GF(2^m) изоморфно (с точностью до знака «+») линейному пространству {0, 1}^m. Другими словами, каждому элементу β GF(2^m) соответствует единственный m-мерный вектор .

В конечном поле имеется примитивный элемент GF(2^m), степени которого порождают все ненулевые элементы поля, т.еЭлемент является корнем неприводимого двоичного полинома р(х), р(α) = 0. Наименьшее положительное целое n, для которого αⁿ = 1, равно 2^m-1. Все элементы поля удовлетворяют уравнению βⁿ = 1, n = 2^m -1 (Другими словами, все ненулевые элементы поля совпадают с корнями степени n из единицы).

Наименьшее положительное целое z, для которого β^z = 1, равно одному из делителей 2^m-1. Это число z называют порядком элемента. Примитивными элементами поля являются все такие элементы β = αⁱ, 0 ≤i≤ 2^m- 2, для которых i взаимно просто с числом 2^m-1.

Неприводимый многочлен называют примитивным, если его корни имеют максимальный порядок, т.е. 2^m — 1. Все корни неприводимого многочлена имеют одинаковый порядок. Периодом многочлена называют наименьшее число z, при котором р(х) делит бином x^z— 1, z|(2^m - 1). Период неприводимого многочлена совпадает с порядком его корней.

Пример 27. Примитивный полином р(х) =х³ + х + 1 порождает поле GF(2³). Примитивный элемент поля обозначим α, р(α) = α³+ α + 1 = α + 1+ α + 1 = 0. В таблице показаны три способа представления элементов поля GF(2³).

Степень	Полином	Вектор	Степень	Полином	Вектор
-	0	000	α 3	1+ α	011
1	1	001	α 4	α + α 2	110
α	α	010	α 5	1+ α + α 2	111
α 2	α 2	100	α 6	1+ α 2	101

Для сложения элементов в GF(2^m) наиболее удобно векторное представление. При этом используются поразрядное сложение по модулю два. Однако для умножения в поле наиболее удобно степенное представление. В этом случае умножение сводится к сложению показателей степени элементов по модулю 2^m-1. Действительно, так как равенство αⁿ= 1, n= 2^m— 1, выполняется для всех элементов поля, то αⁿ⁺¹ = α, αⁿ⁺² = α², и т.д. Таким же способом находим, что α^-1= α^-1+n= α^n-1.

В Примере 27 α^-1 = α⁶. В общем случае, обратный элемент β^-1 = α^b элемента β = α^k определяется из сравнения b + k ≡ 0 mod(2^m — 1). Таким образом, b = 2^m - 1-k. Наконец, для реализации сложений в степенном представлении полезно использовать равенство р(α) = 0. Например, в Примере 27 имеем α³ = α³ + (α³ + α + 1) = α + 1.

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

Примечание: На самом деле, наиболее естественным представлением элементов конечного поля являются вычеты, т.е. остатки от деления по модулю неприводимого многочлена. В этом случае арифметика поля определяется как сложение, умножение и деление многочленов по неприводимому модулю. Если р(х) примитивный многочлен, то примитивным элементом поля вычетов по модулю р(х) является многочлен х. Иначе, все ненулевые элементы поля могут быть записаны как вычеты xⁱ mod p(x), где i=0,1,...,2^m-2.

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

Решение этого сравнения можно найти с помощью алгоритма Евклида для вычисления наибольшего общего делителя многочленов или вычисления подходящей дроби для отношения [р(х) /f(x)J.

Таблицы логарифмов и антилогарифмов (степеней)

Удобным способом реализации умножений и сложений в конечном поле является применение таблиц с различной интерпретацией их входного адреса. Эти таблицы позволяют легко переходить от полиномиального к степенному представлению элементов поля и наоборот.

Таблица антилогарифмов (точнее, степеней) A(i) удобна для реализации сложения. Выходом таблицы является двоичный вектор, записанный как целое число, A(i) , соответствующее элементу αⁱ. Таблица логарифмов (или индексов) L(i) удобна для реализации умножения в конечном поле. Эта таблица выдает значение показателя степени примитивного элемента альфа, α^L(i) соответствующего двоичному вектору, представленному целым числом i. Справедливо следующее равенство

Рассмотрим пример использования таблиц для реализации арифметики конечного поля.

Пример 28. Рассмотрим поле GF(2³) с порождающим многочленом р(α)= α³ + α + 1 и α⁷ = 1. Таблицы логарифмов и антилогарифмов имеют вид:

Адрес входа i	Анти - логарифм A(i)	Логарифм L(i)
0	1	-1
1	2	0
2	4	1
3	3	3
4	6	2
5	7	6
6	5	4
7	0	5

Примечание. В приведенной таблице имеются две особых точки. Нулевой элемент конечного поля не может быть представлен степенью примитивного элемента. Так что в столбце «Антилогарифм» не должно быть нулевого элемента поля, а в столбце «Логарифм» нулевому элементу поля не должно быть сопоставлено какое-либо число. Таким образом, при работе с этими таблицами требуется специальная проверка на нулевой элемент поля в результате вычислений или в исходных данных.

Рассмотрим вычисление элемента γ = α (α³ + α⁵)³ в векторной форме. Учитывая свойства поля GF(2³), находим последовательно:

С использованием таблиц эти вычисления выглядят следующим образом:

Таблицы логарифмов и степеней (антилогарифмов) используются для реализации арифметики конечного поля и GF(2^m). Соответствующие компьютерные программы доступны на ЕСС веб сайте для моделирования алгоритмов кодирования и декодирования кодов БЧХ и PC с арифметикой в GF(2^m). Сами алгоритмы рассматриваются в следующих ниже разделах.

Дополнительные свойства GF(2^m)

Минимальным многочленом ф_i(х) элемента αⁱ называется многочлен минимальной степени, корнем которого является данный элемент поля. Следующие свойства минимальных многочленов легко могут быть доказаны. Минимальный многочлен ф_i(х) элемента αⁱ имеет двоичные коэффициенты и является неприводимым над GF(2) = {0,1}. Более того, корнями этого многочлена являются αⁱ, α²ⁱ, α⁴ⁱ, ..., α^τ, где τ = 2^к и k делит m. Эти элементы называются сопряженными с αⁱ элементами поля. Степени сопряженных элементов поля образуют циклотомический смежный класс

Очевидно, что степень минимального многочлена равна числу элементов (мощности) соответствующего циклотомического смежного класса, т.е.

Циклотомические смежные классы (называемые также циклическими множествами ) обладают свойством расщепления множества вычетов целых чисел Z_n по модулю п = 2^т - 1. Таким образом, циклотомические смежные классы не пересекаются. Иначе, их пересечение , является пустым множеством, а их объединение равно всему множеству, т.е..

Пример 29. Циклотомическими множествами по модулю 7 являются:

Примитивный элемент α поля GF(2^m) (как и все другие) удовлетворяет уравнению α^п = 1. Все ненулевые элементы поля являются некоторой степенью примитивного элемента. Таким образом, бином степени п = 2^т - 1 имеет следующее разложение на неприводимые двоичные сомножители в двоичном поле:

где М число циклотомических классов, и следующее полное разложение на сомножители первой степени в поле GF(2^m)

(3.9)

Важно отметить, что степень минимального многочлена ф_i(x) равна мощности (т.е. числу элементов множества) циклотомического класса С_i. Отсюда следует способ нахождения всех неприводимых делителей бинома (х^п + 1):

Найти все циклотомические классы по модулю 2^т - 1.

Для каждого циклотомического класса C_s вычислить минимальный многочлен

(3.10)

Этот способ может быть использован для построения порождающих многочленов циклических кодов.

Пример 30. Рассмотрим поле GF(2³), порождаемое примитивным многочленом р(х) = х³ + х + 1. Корни каждого из делителей бинома х⁷ + 1 = (х+1)() показаны в таблице.

Так (x+α)(x+ α²)(x+ α⁴) = x³+x+1, а (x+α³)(x+ α⁶)(x+ α⁵) = x³+x² +1 с учётом того, что α⁶ =1+α² , α³ =1+α и т.д. (смотри таблицу в примере 27).

Покажите, что

имеет следующие циклотомические классы С₀={0}; С₁= {1,2,4,8}; C₃={3,6,12,9}; C₅={5,10}; C₇={7,14,13,11}

Примитивные многочлены до степени