8.1.4.2. Описание конечного поля с помощью примитивного полинома

Класс полиномов, называемых примитивными полиномами, интересует нас, поскольку такие объекты определяют конечные поля GF( ), которые, в свою очередь, нужны для описания кодов Рида-Соломона. Следующее утверждение является необходимым и достаточным условием примитивности полинома. Неприводимый полином f(X) порядка т будет примитивным, если наименьшим положительным целым числом п, для которого  делится на f(X), будет . Заметим, что неприводимый полином — это такой полином, который нельзя представить в виде произведения полиномов меньшего порядка; делимость А на В означает, что А делится на В с нулевым остатком и ненулевым частным. Обычно полином записывают в порядке возрастания степеней.  Иногда более удобным является обратный формат записи (например, при выполнении полиномиального деления).

Образующие элементы
Элементы поля
	0	0	0	0
		1	0	0
		0	1	0
		0	0	1
		1	1	0
		0	1	1
		1	1	1
		1	0	1
		1	0	0

Рис. 8.7. Отображение элементов поля в базисные элементы GF(8) с помощью

Пример 8.1. Проверка полинома на примитивность

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

а)      

б)      

Решение

а) Мы можем проверить этот полином порядка т = 4, определив, будет ли он делителем  для значений п из диапазона 1 < n < 15. Нетрудно убедиться, что + 1 делится на  (см. раздел 6.8.1), и после повторения вычислений можно проверить, что при любых значениях п из диапазона 1<n<15 полином +1 не делится на . Следовательно,  является примитивным полиномом.

б)       Легко проверить, что полином является делителем . Проверив, делится ли  на , для значений n, меньших 15, можно также видеть, что указанный полином является делителем X^s+1. Следовательно, несмотря на то что полином  является неприводимым, он не будет примитивным.

8.1.4.3. Поле расширения gf(23)

Рассмотрим пример, в котором будут задействованы примитивный полином и конечное поле, которое он определяет. В табл. 8.1 содержатся примеры некоторых примитивных полиномов. Мы выберем первый из указанных там полиномов, , который определяет конечное поле GF( ), где степень полинома т=3. Таким образом, в поле, определяемом полиномом f(Х), имеется 2^m = 2³ = 8 элементов. Поиск корней полинома f(Х) — это поиск таких значений X, при которых . Привычные нам двоичные элементы 0 и 1 не подходят полиному  (они не являются корнями), поскольку (в рамках операции по модулю 2). Кроме того, основная теорема алгебры утверждает, что полином порядка m должен иметь в точности m корней. Следовательно, в этом примере выражение должно иметь 3 корня. Возникает определенная проблема, поскольку 3 корня не лежат в одном конечном поле, что и коэффициенты f(X). А если они находятся где-то еще, то, наверняка, в поле расширения . Пусть, , элемент поля расширения, определяется как корень полинома f(X). Следовательно, можно записать следующее.

                                               (8.16)

Поскольку при операциях над двоичным полем +1=-1, то  можно представить следующим образом.

                                                   (8.17)

Таблица 8.1. Некоторые примитивные полиномы

m		M
3		14
4		15
5		16
6		17
7		18
8		19
9		20
10		21
11		22
12		23
13		24

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

                           (8.18,а)

А теперь взглянем на следующий случай.

                      (8.18,б)

Из уравнений (8.17) и (8.18), получаем следующее.

Из уравнений (8.17) и (8.18), получаем следующее.

                                               (8.18,в)

Из уравнений (8.17) и (8.18), получаем следующее.

                      (8.18,г)

А теперь из уравнения (8.18,г) вычисляем

                   (8.18,д)

Заметим, что  и, следовательно, восьмью элементами конечного поля GF( ) ,будут

                                   (8.19)

          Отображение элементов поля  в базисные элементы, короче описывается уравнением (8.14), можно проиллюстрировать с помощью схемы линейного регистра сдвига с обратной связью (linear feedback shift register – LFSR) (рис 8.8). Схема генерирует (при m = 3)  ненулевых элементов поля и, таким образом, обобщает процедуры, описанные в уравнениях (8.17) – (8.19). Следует отметить, что показанная на рис. 8.8. обратная связь соответствует коэффициентам полинома , как и в случае двоичных циклических кодов (см. раздел 6.7.5.). Пусть вначале схема находится в некотором состоянии, например 1 0 0; при выполнении правого сдвига на один такт можно убедиться, что каждый из элементов поля (за исключением нулевого), показанных на рис.8.7, циклически будет появляться в разрядах регистра сдвига. На данном конечном поле GF( ) можно определить две арифметические операции – сложение и умножение. В таб. 8.2. показана операция сложения, а в таб. 8.3. – операция умножения, но только для ненулевых элементов. Правила суммирования следуют из уравнений  (8.17) и (8.18,д); и их можно рассчитать путем сложения (по модулю 2) соответствующих коэффициентов из базисных элементов. Правила умножения, указанные в табл. 8.3, следуют из обычной процедуры, в которой произведение элементов поля вычисляются путем сложения по модулю  их показателей степеней или, для данного случая, по модулю 7.

 Таблица 8.2. Таблица сложения для GF(8) при

	0
		0
			0
				0
					0
						0
							0

Таблица 8.3. Таблица умножения для GF(8) при