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



Единственный не тождественно нулевой вектор, удовлетворяющий условиям (3.36), имеет координаты W3 = т( = то = 1, W2 = О, т. е.Л/= (1 О 1 1) и минимальный полином т(х) = ms (х) = + X + i,

Аналогично для элемента (3=4, взятого из другого циклокласса поля GF(2), я(х) = х +Х+ 1, получим

3

" 1

"1

1"

1 .

тз то

где переход к последней матрице осуществлен за счет суммирования третьего столбца с двумя другими в предьщущей матрице. Следовательно, тз + т2=0, mi = = О, тз + mo = О, откуда тз = т2 = то = 1, mj = О, т. е.Л/ = (1 1 О 1) и т4 (х) =

= х + X + i.

Рассмотрим более сложный пример для элемента (3= 86 поля GF(2 ), п(х) = X* + х** + х + 1. Пользуясь табл. 3.7, составим матрицу

171 "

"1

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

Следовательно, т2 + т = О, тг +то= 0; откуда тг = =то = 1 и т85(х) = = х + х+ 1.

Другой универсальный метод отыскания минимального полинома т(х) элемента (3 основан на соотношении (3.32) и предполагает, что не только поле GF(2) уже построено, но и его элементы разбиты на циклоклассы (или хотя бы найден циклокласс для элемента р). Пусть, например, задано поле GF(2 ), я(х) = X® + х** + х + х + 1 - см. табл. 3.7 и необходимо найти полином т2-Из табл. 3.14 видно, что элемент = 52 находится в циклоклассе {52, 103, 205, 154 I . Воспользовавшись соотношением (3.32) и теоремой Виета, получим

Ws2() = (х+52) (х+ 103) (х+ 205) (х+ 154) =

г

= х** + (52 + 103 + 205 + 154)х + (52 • 103 + 52 • 205 + 52 • 154 +

+ 103 • 205 + 103 • 154 + 205 154)х + (52- 103 • 205 +52 • 103 • 154 +

+ 52- 205 154+ 103 • 205 • 154)х + 52 • 103 • 205 • 154 = х** + х + х + х+ 1,

так как согласно формуле (3.23) и табл. 3.7 для используемого поля справедлив! соотношения:

5 - 1610



52-103 52-205 52-154

103 - 205 103 • 154 205 - 154

154 1

205 52 1

1 0 0 1 0 0 1 0

0 0 0 0 0 0 0 1

110 1110 1

0 0 0 0 1 0 1 0

0 0 0 0 0 0 0 1

0 1 0 0 0 1 0 0

0 0 0 0 0 0 0 1

52 52 52 103

103 103 205 205

205 154 154 154

103 52 154 205

0 1 0 0 0 1 0 0

0 0 0 0 1 0 1 0

1 0 0 1 0 0 1 0 110 1110 1

0 0 0 0 0 0 0 1

следовательно, 52 + 103 + 205 + 154 = 1, а также 52 - 103 - 205 • 154 = 1.

Число циклокласоов неприводимых и минималы1ых полииомов. Подсчет

числа неприводимых над полем GF (2) и, следовательно, минимальных полиномов степени i может быть осуществлен по формуле [8]

(3.37)

где м(/) - функция Мебиуса, определяемая соотношениями (3.34), а суммирование ведется по всем (делителям i числа /, включая 1 и само /. Например, 1=6 имеет делители i { 1» 2, 3, в] , следовательно, м(1) = 1, м(2) = -1, м(3) =-1,

J(6) = (-1)2= 1. Поэтому/б = (2*

2" + 2) : 6 = 9.

Число неприводимых полиномов степени / совпадает с числом циклокласоов длины /. Это позволяет вывести рекуррентную формулу для If. Пусть / делится на /о = 1, i. • - •» jt 1, lie Тогда

7

i - А: - 1 i = О

(3.38)

В частном случае, когда / - простое число, из выражений (3.37) и (3.38) следует

А (2

-2), 2<1 - простое число.

Если / = 2 - степень числа 2, то

/. =

*

i = О

21 V

Так, для / = 1 из в: муле учтено, что b

S (... ) =0 при b < а а

(3.37) и (3.38) следует/i =2; в последней фор-



Таблица 3.15

Количество циклоклассов Ir (минимальных и неприводимых полиномов) и нормальных базисов

для полей GF(2)

Размер-

Значение • /• при длине щ

лкла /, равной

ное ты

2 (00)

(01)

2 (00)

2 (01)

2 (00)

2 (00)

2 (01)

18/9

(00)

(ООО)

30/16

2 (01)

2 (01)

56/28

(00)

(0 ... 0)

99/51



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.0099