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



продолжение табл. 3.14

Раз-

мерность поля г

Модуль

Ведущий элемент

Сопряженные с элементы

Длина

цикла /

Порядок

След TiN

3,5,9,17, 33, 65)

-.....

7, 13, 25,49, 97. 6б}

11,21,41,81,34,67}

15, 29, 57, ИЗ, 98,68}

19, 37,73, 18, 35,69}

23, 45, 89, 50, 99, 70}

27,53, 105, 82, 36,71}

31, 61, 121. 114, 100, 72}

39, 77, 26,51, 101,74}

43, 85,42, 83, 38, 75}

47, 93,58,115,102, 7б}

55, 109. 90,52, 103,78}

59, 117, 106, 84,40, 79}

63, 125, 122, 116, 104, 80}

87,46,91,54, 107, 86}

95,62, 123, 118. 108, 88}

111,94, 60, 119, 110,92}

127, 126, 124. 120, 112, 96}

3.5,9,17,33,65,129]

7,13, 25.49. 97,193, 130}

И, 21,41, 81, 161, 66, 13lV

15, 29,57, ИЗ, 225, 194, 132}

19,37, 73, 145, 34,67, 133>

23,45,89,177, 98,195.134}

27,53, 105, 209, 162.68, 135}

31,61, 121, 241. 226. 196, 13б}

35,69, 137 }

39, 77, 153,50, 99, 197, 138 }

43, 85, 169, 82, 163, 70, 139)

47, 93, 185, 114, 227, 198, 140}

51, 101, 201, 146, 36. 71, 141)

55. 109, 217, 178, 100, 199, 142}

59, И7, 233, 210, 164, 72, 143)

63, 125, 249, 242, 228, 200, 144}

75. 149,42, 83, 165, 74, 147}

79, 157,58. 115, 229, 202, 148}

87. 173,90, 179.102, 203,150)

91, 181, 106, 2И, 166, 76, 151}

95, 189, 122, 243, 230, 204, 152)

103, 205, 154J



продолжение табл. 3.14

Размерность поля г

Модуль 2- 1

Ведущий элемент

Сопряженные с 7V элементы

Длина цикла /

Порядок

След ttjv

107,213.170. 84, 167.78, 155}

111,221,186, 116,231,206, 156}

119, 237, 218, 180, 104, 207, 158}

123, 245, 234, 212, 168, 80, 159}

-164

127, 253, 250, 244, 232, 208, 160}

171]

175, 94,187,118. 235, 214, 172

183, 110, 219, 182, 108, 215, 174}

191, 126. 251, 246, 236, 216, 176}

(112

223, 190, 124, 247, 238, 220, 184}

(120

239, 222, 188}

{128

255, 254, 252, 248, 240, 224, 192}

элемент р поля gf( - 2*) удовлетворяет уравнению + х = о степени q (следствие теоремы ферма). более того, любой элемент {3 является корнем полинома меньшей степени, а именно степени /, где / - длина циклокласса, в который элемент (3 входит, причем ни одному уравнению меньшей степени этот элемент не удовлетворяет.

полином над полем gf (2) наименьшей степени, содержащий корень е gf(2), назьшается минимальным полиномом т{х) элемента его степень равна /, а i корнями кроме р являются также / - 1 различных сопряженных с 0 элементов (последнее утверждение может бьпь принято за определение минимального полинома).

(2. 3, 5, 9)

(6, 11}

w2 = 15/(15,1)

= 15/нол (15, N -i) = 15/(15, N- {) = из - 15/(15,2) = ws= 15/(15,4) = = vv9 = 15/(15,8) 15/1 = 15 [4, 7, 13, 10} w4 15/(15,3) = w7 = 15/(15,6) = wi3= 15/(15, 12) =

- viio = 15/(15, 9) = 15/3 = 5 We = 15/(15, 5) = wu = 15/(15, 10) - 15/(15, 5) = 15/5 = 3 (8, 15, 14, 12] wg = 15/(15, 7) - wis = 15/(15, 14) = 4,4= 15/(15, 13) =

= w12 = 15/(15. 11) = 15/1 = 15

рис. 3.6. расчет порядков w элементов TV > 1 поляср(2*)



Таким образом,

i = I 1 7=0.

i = о,

} = 1

Полиномы, имеющие своими корнями все элементы одного и того же порядка, называются круговыми. На рис. 3.7 представлены минимальные mj{x) и круговые \1у{х) полиномы для полей GF {2 г =2 ... 5; причем во всех полях

GF(2) wo = х, mj =х + 1, Vl = wom, = х(х + 1).

Перечислим некоторые свойства минимальных и круговых полиномов.

Важнейшее свойство минимального полинома т(х) - его неприводимость над полем GF(2), так как все его корни лежат в расширенном поле GF(2), гле t - степень полинома т{х). Наоборот, всякий неприводимый над полем GF (2) полином степени t является минимальным и все его корни лежат в поле GF(2).

Произведение всех нормированных неприводимых над полем GF (2) полиномов, т. е. всех минимальных полиномов, а следовательно, и произведение всех круговых полиномов, равно двучлену

x* + 1 = П m (x) = Пхр. (x). ае. - 2* - I, (3.33)

где переменная / берется из множества представителей, например, ведущих элементов, циклоклассов, а / - из множества делителей числа 3£ , включая у = 1 и / =ав .

Для круговых многочленов формула (3.33) допускает следующее обобщение:

х" - 1 = П .(х). GF( ),

где/ «, т, е. пробегает по всем делителям заданного натурального числа п. Введем функцию Мёбиуса [8, 17]:

w.(x) = (x +) (х + ) (х+ р") .= П {х+р ), (3.32)

где / - длина циклокласса, содержащего р.

Если 3 - примитивный элемент поля, то соответствующий ему минимальный полином также называется примитивным.

Напомним, что элемент 3 = а является примитивным, если стелены* взаимно проста с числом Х = 2* - I. Количество таких элементов определяется функцией Эйлера tpilt ), т. е. равно количеству чисел, меньших X и взаимно простых сХ . Если Э& = (2" - 1) - простое число, то любой элемент j3 = а при i > О является

примитивным. Если же 32. = Пр/ , i = 1, . . . , х, то лишь элемент , удовлетворяющий неравенству 3* Ф \> v = /р, i = 1, . . . , х, является примитивным.

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

корни разных минимальных полиномов.

Объединим циклоклассы с ведущими элементами i, 32. • • . % в одно множество, если их элементы имеют один и тот же порядок w, и введем полиномы

i - к,

i = к i =1-1



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