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



(I + 2)2 = 4 1 + 2 = 7, откуда 1 + 3 = 7 или 1 + 7 = 3; (1 + 3)2 = 7 1 + 3 = 6,т. е. 1 + 5 = били 1 + 6 = 5.

Таким образом, для рассматриваемого поля модифицированные функции Зеха L (N) = \ + N при N> 2 будут:

L (2) = 4; L (3) =7; L (4) = 2; L (5) = 6; Z (6) = 5 ; L (7) = 3.

Подобный метод не требует предварительного порождения поля, т. е. нахождения всех его элементов в виде векторов или полиномов. Но, конечно, удобнее пользоваться заранее составленными таблицами для функций L {N).

Логарифмы Зеха (обычные Log и модифицированные L) для полей Галуа GF (2) размерностей г = 2 ... 5 приведены в табл. 3.4 . . . 3.6, а в табл. П.1 приложения представлены модифицированные логарифмы (функции) Зеха L для г = 6 ... 8.

Проиллюстрируем применение функций L (N). Пусть, как и в рассматривавшемся примере, требуется над полем GF (2), 7т(х) =х +

+ + +1 вычислить величины Аг = S2S0 S\,A - SSq +521, А о =8381 + 5*2, где параметры 5*/,/= О ... 3 заданы десятичными номерами - модифицированными логарифмами: So ~ ИЗ, Si = 226, 5*2 =

= 163, = 203.

Пользуясь табл. П.1 и соотношениями (3.23), (3.24), получим

Аг = S2S0 Sf = 163 . ИЗ + 226 = 20 + 196 = 20- (1 + 196 : 20) =

= 20- (1 + 177) = 201 (177) = 20 96= 115; (3.28)

Al = S3S0 + 5*2.1 = 203-113+ 163 - 226 = 60+ 133 =

= 60 (1 + 133 : 60) = 60 • (1 + 74) = 60i: (74) = 60 - 237 = 41; (3.29)

Ао = S3S1 -f Si = 203 • 226 + 163 = 173 + 70 =

= 70 (1 + 173 : 70) = 70(1 + 104) = 701 (104) = 70 • 75 = 144. (3.30)

По сравнению с расчетами (3.25) . . . (3.27), требующими обращения к двум таблицам (логарифмов и антилогарифмов), в вычислениях (3.28) . . . (3.30) использовано всего одно обращение к таблице модифицированных функций Зеха L {N).

Как видно из рассмотренного примера, функции Зеха i, (Л) удобно сочетать с десятичным представлением элементов поля. Естественно, при использовании вычислительных устройств для расчета в конечных поДях десятичное представление заменяется обычным двоичным. Еще один способ умножения элементов поля с помощью преобразования Ганкеля - Теплица будет изложен в § 4.4.



3.4. СОПРЯЖЕННЫЕ ЭЛЕМЕНТЫ И НОРМАЛЬНЫЕ БАЗИСЫ ПОЛЯ GF(2)

Сопряженные элементы и их классы. Далее при рассмотрении нормальных базисов, минимальных полиномов и спектральных методов кодирования необходимо уточнить важное понятие - класс сопряженных элементов.

Пусть элемент задан таким, что & G G¥{q =2),0ФОк0а, где а -примитивный элемент поля, i = О, I, .... q - 2. Тогда элементы 3, 13**, ... , т.е. элементы вида о:, а, а, назьшаются сопряженными элементами поля GF(2), а множество [ i, 2/, 4/,...] их индексов (показателей степеней элемента о: - логарифмов log по основанию а) - циклотомическим классом [8, И, 35, 36].

ОТ 2

Так как по теореме Ферма = при q = 2 , то среди элементов , , . .. не более г различных. Каждый цикл ото мический класс представляет собой цикл лд\тъ1 I; I - наименьшее целое положительное число, удовлетворяющее сравнению

12 = i, то(Х(Ъ =2 - 1),

(3.31)

причем длины / являются делителями г, включая 1 и само число г.

Перейдем от степенного представления 3 = а элементов поля GF(2) и от обычных логарифмов logQ. к числовому представлению Л, т. е. к модифицированным логарифмам Log ft = i + 1 = (здесь- операция обычного сложения). Тогда сопряженными будут элементы Л, n, N, . . . , где возведение в степень осуществляется по правилу (3.12) при q - 2 с обычными арифметическими действиями над целыми числами и с последующим приведением результата по модулю 2* - 1.

Множество сопряженных элементов ( Л Л, ,... ) шазовем циклоклассом, а элемент Л- ведущим в этом классе.

В табл. 3.14 представлены циклоклассы, их длины / и порядки ндг входящих в них элементов для модулей 2 - 1, г = 2 ... Ъ. (Возможна трактовка цикло-классов и как структур спектра [И].) Так как во всех полях GF(2) элемент 1 имеет порядок w = 1 и образует самостоятельный циклокласс 1 длины / = 1, то они в табл. 3.14 при / = 7, 8 опущены, так же как и циклоклассы, \ о} .

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

Важное свойство циклоклассов: порядки w входящих в них элементов равны. Напомним, что согласно теореме Лагранжа (см. § 3.1) порядок w любого элемента N> 2 равен ц /ri, где = 2" - 1 - порядок мультипликативной группы поля

GF(2),77 =НОД [X , (Л - 1) ]. Например, для поля GF (2**) расчет порядков w всех элементов, разбитых на циклоклассы, приведен на рис. 3.6, откуда видно, что элементы разных циклоклассов - в данном случае (2, 3, 5, 9) и (8, 15, 14, 12) -могут иметь одинаковые порядки w.

Циклоклассы тесно связаны с так называемыми минимальными и круговыми полиномами.

Минимальные и круговые полиномы- Условимся полиномом о{х) степени п\ о(х) = л:" + o„ j л:" ~ + . . . + а,л: + оо = ,

с коэффициентами о,- из поля GF (2), т. е. о- G О, 1 , / = О, 1, . . . , «; о= 1, называть«oлмнoJИ надполем GF (2).



Таблица 3.14

Циклоклассы сопряженных элементов полей GF(2 )уГ - 2... 8

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

Модуль 1

Ведущий

элемент N

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


12-7 {4 = 5

3, 5] 7.6}

(4 {6 =

3,5,9} 7, 13, 10

15, 14, 12}

{4 = {6 = {8

iJ2 = {16

29" * 27~*

3, 5, 9, 17} 7,13, 25,18} 11, 21, 10. 19} 15, 29. 26, 20} 23, 14, 27, 22) 31, 30, 28, 24}

U} (2 {4 {6

{8 U0 (12 {14 U6 122 124 {28 (32

3,5,9,17,33} 7, 13,25, 49, 34}

11.21.41, 18,35} 15, 29,57,50, 36} 19,37}

23,45. 26, 51, 38}

27.53.42, 20, 39} 31,61.58, 52, 40} 431

47, 30.59. 54, 44J 55, 46}

63,62, 60,56,48}

Длина

цикла /

1 1 4 4 2 4

1 1 5 5 5 5 5 5

1 1 6 6 6 6 3 6 6 6 2 6 3 6

Порядок

1 15 5 3

1 31 31 31 31 31 31

63 21 63

7 63 63 21

3 63

7 63

След

о 1 о 1

о о о 1 о 1

о 1 о 1 1 о

о о о о 1 о о 1 о 1 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.0195