5.4.4. Циклические коды и корни полиномов

Поскольку многочлен  каждого кодового слова делится на порождающий полином , то корни , при подстановке в  обращающие его в 0, являются также и корнями многочлена . Число таких корней равно степени порождающего полинома .

Следовательно, многочлен  с коэффициентами из поля  будет кодовым словом в том и только в том случае, если элементы  из расширения  являются его корнями.

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

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

Условие  в развернутом виде означает

, .

(5.18)

Такая запись эквивалентна матричной

,

(5.19)

Где

.

Выражение (5.19) является определением проверочной матрицы  [3]. Строки  содержат степени корней порождающего полинома , а следовательно, и корней кодовых многочленов. Каждый элемент  есть -символьный столбец -ичного представления корня – элемента поля .

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

Из каждого такого множества корней  следует выбрать по одному (любому), и соответствующие им строки оставить в матрице, а остальные удалить как функционально зависимые от удерживаемых.

Дальнейшее обсуждение проведем для многочленов над полем . Рассмотрим несколько частных случаев.

1. Порождающий полином  неприводим и примитивен, а длина кода . Коды таких длин называют примитивными независимо от вида порождающего полинома.

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

,

а сам код носит название кода Хэмминга.

В качестве примера выберем код (7, 4, 3), порождающий полином которого  примитивен, а проверочная матрица

,

с точностью до порядка следования столбцов совпадает с ранее полученной проверочной матрицей (5.17) этого же кода. Смена порядка на обратный объясняется изменением в (5.18) порядка записи степеней переменной .

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

В табл. 5.6 представлены полиномы степеней до 8, заимствованные из [33], где можно найти сведения о полиномах до 34-й степени.

Неприводимые многочлены даны в восьмеричном представлении. Каждую цифру соответствующего многочлену числа следует перевести в трехразрядное двоичное число и рассматривать его разряды как коэффициенты при степенях  многочлена. Например, среди полиномов степени 5 есть восьмеричное число 67. Это означает: .

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

Таблица 5.6 Неприводимые полиномы над полем

Степень  полинома	Восьмеричное представление полиномов
2	1.7
3	1.13
4	1.23	3.37	5.007
5	1.45	3.75	5.67
6	1.103	3.127	5.147	7.111	9.115
	11.155	21.007
7	1.211	3.217	5.235	7.365	9.277
	11.325	13.203	19.303	21.345
8	1.435	3.567	5.763	7.551	9.765
	11.747	13.453	15.727	17.023	19.545
	21.613	23.543	25.433	27.477	37.537
	43.703	45.471	51.037	85.007

 

качестве корня  полинома 127 взять элемент  этого поля. Каждый из многочленов табл. 5.6 является минимальным многочленом указанного перед ним корня.

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

Показатель  степени примитивного элемента поля, соответствующий корню двойственного многочлена, определяется как , где -степень примитивного элемента – корня приведенного в табл. 5.6 полинома. Поскольку  и  нечетны, то  всегда четно. Например, корнем полинома, двойственного полиному 23, является элемент , так как , двойственного полиному 37 – элемент , и т.д.

Минимальный многочлен элемента  включен в таблицу, даже если степень многочлена меньше  (т.е. показатель  принадлежит циклотомиче-скому классу, содержащему меньшее  число компонентов, например, классу  (табл. 5.3)). Таким минимальным многочленом корня  в поле  является 007 второй степени. В табл. 5.6 подобные многочлены начинаются с нуля.

3. Порождающий полином  представляет собой произведение нескольких неприводимых многочленов, каждый из которых имеет корни в , и по-прежнему . Например,   (табл. 5.5) порождает код (15, 9, 3).

Очевидно, в этом случае среди  корней полинома  будут корни каждого из сомножителей, отыскиваемые изложенным выше способом.

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

Корни многочлена  для таких значений  являются элементами некоторого поля , причем показатели этих элементов принадлежат одному циклотомическому классу  по модулю . Полином  имеет корнями все элементы поля , в том числе и корни полинома . Следовательно,  делится на , а  делится на  (см. 5.3.5), т.е. , где  – целое число, причем одному значению  может соответствовать множество пар чисел . Например, при  справедливы равенства ;  и т.д.

Поскольку корни  лежат в поле , то корни неприводимых полиномов – делителей двучлена  также принадлежат этому полю, и их следовало бы обозначать показателями  степени примитивного элемента поля , как это делалось в табл. 5.6. По так как одному значению и может отвечать несколько полей , в перечнях кодов [33] корни помечаются отношением .

Табл. 5.7 содержит заимствованные из [30] двоичные циклические коды  нечетной длины до  с указанием нормированных показателей  корней. Здесь же приведены значения конструктивных расстояний , необходимые для изложения материала следующих разделов.

Таблица 5.7 Нормированные показатели корней

n	k	d0	δ	R	n	k	d0	δ	R
7	4	3	3	1	15	4	8	8	0,1,3,5
7	3	4	4	0,1	15	3	5	5	1,3,7
9	3	3	3	1	15	2	10	10	0,1,3,7
9	2	6	6	0,1	17	9	5	4	1
15	11	3	3	1	17	8	6	6	0,1
15	10	4	4	0,1	21	16	3	3	7,3
15	9	3	3	1,5	21	15	4	3	0,7,3
15	9	4	3	3,5	21	14	4	4	0,1
15	8	4	4	0,1,5	21	13	4	3	7,9,3
15	8	4	3	0,3,5	21	12	4	3	0,7,9,3
15	7	3	3	1,7	21	11	6	6	0,3,1
15	7	5	5	1,3	21	10	5	5	7,3,1
15	6	6	6	0,1,3	21	9	5	6	9,3,1
15	6	6	6	0,1,7	21	8	6	6	0,9,3,1
15	5	3	3	1,5,7	21	6	7	7	3,5,1
15	5	7	7	1,3,5	23	12	7	5	1
15	4	6	6	0,1,5,7	23	11	8	6	0,1

Например, для кода (9, 3, 3) величина . Это означает, что корнем порождающего полинома данного кода в поле  является элемент , в поле  – элемент  и т.д.

В заключение этого раздела обсудим задачу, обратную рассмотренной: по заданным корням требуется построить порождающий полином и код. Такая постановка характерна при формировании БЧХ-кодов.

Пусть  – элементы поля , являющиеся заданными корнями, а  – соответствующие им минимальные многочлены. Каждый из корней является некоторой степенью примитивного элемента поля. Если все показатели степени принадлежат разным циклотомическим классам по модулю , то в соответствии с (5.9), (5.10) и (5.11) порождающий полином

(5.20)

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

.

(5.21)