Главная Помехоустойчивое кодирование



Ци клок ласе

(0) 12.3}

(2, 3, 5} (4. 7, 6}

(6,11)

(4, 7, 13, 10}

(2, 3, 5, 9}

(8, 15, 14, 12}

{2, 3,5,9, 17} {4, 7,13, 25.18} б. И, 21. 10, 19} {8, 15, 29, 26, 20} {12, 23, 14, 27, 28* {16, 31, 30, 28, 24

Порядок

Минимальный

полином М

Круговой Полином ф

ПолеСР(22), п{х) = +х+\

то= X mi = X + 1

т2 = тз = х" + X + i

Ф1 = mom, = х(х + 1)

т2=х+х +1

Поле GF(2), п(х) = х +х + \

1 3 3

mi =

т2 = шз = ms = х" + X + i т4 = т = т =

momi = х(х + 1)

х + х+ 1

Фз = m2m4 = = х +х +jc* + 1

ПолеОР(2*), п{х) =х +Х+1

то = х mi=x+l

fe - "11 - +х + I т4 = т7 = mi3 = тю =

= х* +х + х + х + I

Фх = mQmi = х(х + 1)

Фз- б = х +Х + 1

Ф$ = = х" + х +

+ х +Х+1

т2 =тз - ms - - = х + Х + I

8 = "15 = "14 = 12 = х +Х + I

15 - 2&- =Х +Х +Х Х +Х + 1

5 5 5 5 5 5

ПолеОР(2Ъ, я(л:) = х + х + 1

то = х

mi = X + I

т2 = х +х + i

т4 = х +х +х +х + 1

ms = х +х + х + X+1 ms = x + х +х + X+1 mi2 = х + х + х + х + 1 mi6 = х +х + 1

Фх - mQmi = х(х+ 1) Xml6 = xЗ*+x2 +:с28

+ j25 +24 23

Риа 3.7. Минимальные и круговые полиномы для полей GF(2 ), г - 2 ... 5

м(«) =

1, если « = 1;

(-1), если п - произведение р различных простых чисел;

О-в остальных случаях, т. е. если п делится на квадрат какого-либо числа.

Тогда круговой полином степени п может быть представлен в виде

(3-34)



фах)=тх . l)"/> = п(х"/ . /\п. (3.35)

рассмотрим пример поля gf(2*). так как?в = 2 - 1 = 15, то порядки w элементов этого поля, являющиеся делителями числа ъ , принимают значения из множества {1, 3, 5, 15. таким образом, над полем gf(2 ) существуют следующие круговые полиномы: ( j, фз, i s, фхв- воспользовавшись формулой (3.35), найдем:

при w = 1 / = 1, м(1) = 1, Ф1 (x) = x + 1; х + 1

nphw = 3 /е i 1,3\ , м(1) = 1, м(3) - -1, з() = - =х +Х + 1-

х +1

при W

= 5 / g (1,5} , м(1) = 1, м(5) = -1, ФзМ =

х+ 1

= хпхз +

+ х + x + 1;

при w= 15 / g ( 1, 3, 5, 15} , м(15) = (-1) = 1, так как 15 = 3 5 и р = = 2, (x) = (x. 1)> (х . 1) (х . 1)<> (х- . 1) =

(х+1)(х» + 1) 8 7 5 4 3

- = х°+х +х+х +х +х+ 1.

(х + 1) (х + 1)

полученный полином (х) допускает разложение на неприводимые над gf (2) множители: фгз (х) = (х** + х + 1) (х** + х + 1), в чем можно убедиться путем раскрьпия скобок. заметим, что полиномы четвертой степени в скобках являются минимальными (и, следовательно, неприводимыми) многочленами соответственно для элементов [2, 3, 5, 9] и {8, 15, 14, 12 поля gf (2**) - см. рис. 3.7.

подробно свойства круговых и минимальных многочленов рассмотрены в монографиях [8, 35, 36].

полиномы /(х) и g (х) одинаковой степени t назьгоаются взаимными, двойственными или симметричными, если их корни (ненулевые) взаимно обратны, т. е. если /(х) = х(1/х). у взаимных полиномов последовательности коэффициентов обратны, например х + х + 1 и х + х + 1. полиномы типа х + х + 1 симметричны относительно своих коэффициентов й называются самодвойственными.

если полином / (х) неприводим (примитивен), то и симметричный ему полином g (х) неприводим (примитивен). это позволяет при поиске неприводимых полиномов ограничиться нахождением только /(х) .

один из традиционных способов построения неприводимых, т. е. минимальных, полиномов состоит в последовательном разложении двучлена х? - х на множители, начиная с малых степеней [ 36J.

другой способ, также основанный на последовательном переборе полиномов над gf (2), начиная с низших степеней, состоит в следующем [43 j. вначале рассматривается полином первой степени/j (х) - х + д. так как а g gf (2), то либо д = о, либо д = 1; в результате имеем два полинома первой степени: хи х + 1, которые по определению неприводимы. затем задаемся полиномом второй степени/2 (х) = + ах + ь, который при д, й } е gf (2) соответствует четырем полиномам. для того чтобы выявить среди них неприводимые, нужно потребовать, чтобы они не делились ни на х, т. е. /2 (0) ф о, ни на х+ 1, т. е. /2 (1) 0. в первом случае имеем/2 (0) = b ф 0,т. е. b = 1, во втором - /2(1) = l"*"* + b ф 0,т. е. i +а + b =

= х2



= 1, откуда а = I. Следовательно, единственный неприводимый полином второй

степени имеет вид х + х + 1.

Далее рассматривается полином /з(х) = + ах + Ьх + с, который также

ие должен делиться ни на х, ни на x+ 1, а следовательно, полином третьей степени

/з (х) не будет делиться инал: + х +1. Требования/з (0) # О и /з (1) Ф О дают

два условия: с Ф О и I + а + b + с Ф что эквивалентно равенствам с = 1ид + b =

= 1. В последнем случае можно принять либо а = Q и b = 1, либо а = 1 и й = 0.

В результате получаем два неприводимых полинома третьей степени: х + х + I и x+x + l, которые оказываются симметричными. Аналогично исследуются

полиномы более высоких степеней Г, хотя с ростом t требуемый перебор вариантов быстро нарастает.

Еще один универсальный метод, предложенный в монографии [8] и позволяющий находить минимальные полиномы для произвольных элементов поля GF(2), основан на следующем. Предположим, что задан примитивный элемент а поля GF(2) и известны представления элементов этого поля в виде полиномов (векторов) по степеням о:, а,. . ., Ot. Минимальный полином [векторЛ/ = (т, т. J, . . . , mi, mo) ] для элемента р G GF(2) находится как равная нулю линей-

" . . . , р. Проиллюстрируем этот метод не-

пая комбинация элементов р

сколькими примерами.

Пусть требуется отыскать минимальный полином для элемента (3=5 поля GF(2), я(х) = х + х + 1. Найдем степени этого элемента и соответствующие им векторы (см. табл. 3.4):

= 1 -и

- 0

= 5 -и

- 1

= 2

= 6 *

* 1

Составим матрицу из найденных векторов, взятых в обратном порядке

" 1

Искомый вектор М должен удовлетворять уравнению МА = 0. Добавляя первый столбец ко второму и меняя их местами, приведем Л к следующей сопровождающей матрице (см. § 4.4) :

где для удобства строки помечены координатами искомого вектора Л/.

Таким обпазом. пля координат этого вектора должны быть справедлив

соотношения:

тг = О, тз + mi = О, тз + то-0.

(3.36)



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 [41] 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0115