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



О 1 2

5 6 7 8 9

10 11 12 13 14 15

Нормальные базисы поляGF(2), я (jc) = jc + х + 1

Таблица 3.16

Непримитивный элемент у= а

Прямоугольные коорди-

наты

уЬ у* у2 у1

0 0 0 0

1111

10 0 1 0 0 11 0 0 0 1 0 110 10 10 0 0 10

0 111 110 0 10 0 0 0 10 1 10 10 0 10 0 110 1 1110

Полярные координаты

=5 10

2 7 12 у =7 =7

7з =8 «13

4 9 14

7 =7 =7

-.7

Примитивный элемент 7 - а

прямоугольные коорди-

наты

у* у* у т

Полярные координаты

Тг(д) = Тг(д) = Tiia*) = . .. = Тг(д).

Далее всегда Тг(д) е GF (2), если д е GF(2* ), т. е. след элемента а расширенного поля характеристики 2 равен либо нулю, либо единице. Причем строго половина = 2" элементов поля имеет слеД О, а вторая половина - след 1.

Другие важные свойства функции след:

Тг(д +Ь) = Тг(д) +Tr(6); Тг(0) = 0; Тг(1) = г mod 2,

т. е, Тг(1) = О, если размерность поля г - четное число; Тг(1) = 1, если г -нечетное число.

Методы вычисления следа. Спед любого элемента поля может быть вычислен не только по формуле (3.39), но и с помощью минимальных полиномов. Пусть минимальный полином для элемента b поля GF(2 ) имеет вид

+ ... ;

тогда след этого элемента определяется соотиощеиием

(3.40)

/1-1

Тх(Ь) = г/п, mod 2,

где М - коэффициент при степени х а косая черта - символ деления целых чисел с последующим приведением результата по модулю 2. Проиллюстрируем формулу (3.40) несколькими примерами.



таблица 3.17

Нормальные базисы поля GF(2 ) ,it(x) = х + х + 1

Примитивный элемент

7= а

Прямоугольные координаты

Полярные координаты

Примитивный элемент

7 = а*

Прямоугольные координаты

0 0,0

Полярные координаты

1&

Примитивный элемент

Г"

Г"

Прямоугольные координаты

16 8 4 2 1

7 7 7 7 7

Полярные координаты

17 20

23 9

1Ь 15

25 11

Т у7&

Элементг>= 6 - поля GF(2 ),7г(лс) = + х+1, имеет минимальный полином т(х) = X + X + 1 - см. рис. 3.7. В данном cny4aeiV;, i = 1 (коэффициент при , Поэтому



Tr(6) = Tr(6) =Mn i r/n = 3/3 = 1. (3.41)

Проверка. Непосредственное вычисление no формуле (3.39) дает

Ti(b) = 6 +6+6"* = 6 + 4 + 7= (ill) + (Oil) + (101) = (001) = 1, (3.42)

где использованы представления элементов из табл. 3-4.

Элемент /J = 11 = О:** поля GF(2), п(х) = + х + I, имеет минимальный полином тц (х) = х + X + 1 ~ см. рис. 3.7. Таким образом, = 1 (коэффи-

циент при х) н

Tiib) = Tr(ll) = 4/2 = О, mod 2.

(3.43)

Проверка:

Tiib) =b+b = 11 + 11 + 1И + 11® = 11+6 + 11+6=0, (3.44)

где учтено, чтод + д = О для любого поля GF(2).

Наконец, для элемента /J = 3 = того же поля w3 = х + х + 1 (рис. 3.7).

Следовательно, = О (коэффициентпри отсутствующем члене х) и

Tr(6) = Тг(3) = 0.

(3.45)

Проверка:

Tiib) = 6+6 + 6*+6®=3 + 3 + 3* + 3® = 3 + 5 + 9 + 2 =

= (0100) + (ООП) + (0101) + (0010) = (0000) = О, (3.46)

где векторные представления взяты из табл. 3-5.

Приведем еще один способ вычисления функции след. Предположим, что задан некоторый базис (Л. i» 2 * * *» 0)* элемент b представлен в этом базисе так: b = (bf 1 -2 * * * io)> тде bf ~ координаты элемента bi = О, 1,. .., г - 1. Тогда след находится по формуле

г = / - 1 Tiib) = Z b.TiiX:).

/ = О

В частности, при использовании степенного базиса

г = г -1

Tr(6) = Х A.Ti(a).

/ = О

(3.47)

(3.48)

Следы базисных элементов а постоянны для данного поля и могут быть вычислены заранее. рис. 3-9 приведены функции Тг(о:) для полей GF(2*) размерностей г = 2 ... 7. Подставив в формулу (3-48) значения Тг(а), можно найти логические выражения для расчета функции след. Они представлены на рис. 3.10.

Так, для рассматриваемых выще примеров имеем: для поля GF(2)

Тг(а5) = тг(б) = тг(г>2 = 1,г>1 = 1,г>о = 1) = бо = 1;

для попя GF(2) Tr(aiO) =Tr(ll) =Тг(г>з = 0,62 = 1.61 = 1,60 = 1) =г>з = 0;



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