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



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

Размер-

Значение -/«/ при длине цикла /, равной

ность г

/ =r

2 (01)

186/93

(00)

2 (00)

(011)

(0 ... 0)

335/170

2 (01)

i 1

630/315

(00)

(0 ... 0)

1161/585

(01)

2 (01)

(0 ... 0)

2182/1092

2 (00)

(ООО)

30 (0 ... 0)

4080/2048

2 (01)

7710/3855

2 (00)

(00)

(110... 0)

56 (0 ... 0)

14532/7281

(01)

27594/13797

2 (00)

(ОН)

(0 ... 0)

j

99 (0 ... 0)

52377/26214



.4

Для / = 2 имеем I2 = 1; далее /3 = {2 - 2)/3 = 2; /4 = (2 - 2 - 2) = 3 и т. д.

В табл. 3.15 приведены значения 1 для г = 1... 20 (цифры в скобках и в знаменателе используются в следующей рубрике при подсчете числа нормальных базисов). Из этой таблицы, например, видно, что в поле GF(2 ) имеется 335 циклоклассов (неприводимых и минимальных полиномов) длины (степени) 12,

9 - длины 6 и т. д.

Нормальный базис. Как уже отмечалось в § 3.1, расщиренное поле Галуа GF(p*) является векторным пространством над простым полем GF(p). Далее ограничимся случаем р = 2, т. е. рассмотрением векторных пространств GF(2) над GF(2). Размерность этих пространств равна поэтому любой базис всегда содержит г иезависим1>1х компонент. В частности, степенной базис а**, а,

а, ..., а* "" j , уже неоднократно использовавщийся при изложении предьщу-щего материала, образован набором из г векторов:

\oi = (00 ... 001); = (00.. . 010),... = (10 .. . ООО)) ,

где а - примитивный элемент поля.

Подобный базис, каждая компонента которого содержит всего одну единицу, а остальные - нули, называется каноническим.

Базисы всякого векторного пространства, а следовательно, и базисы поля GF(2*) могут быть выбраны различными способами. Наибольщее применение для полей GF(2) находят упоминавщийся степенной базис и так назьшаемые нормальные базисы.

Нормальным базисом поля GF(2) называется базис вида у, 7, 7, -. . , ) , где = 2"", а порождающим элементом этого базиса является 7 е GF(2) [35].

Согласно теореме Ферма ~ у, где q - 2, поэтому в качестве элемента, порождающего нормальный базис, может быть выбран не только элемент 7, но и любая его степень; это приведет лищь к перестановке координат внутри набора

(24 7, 7 ,7 , - . - , 7 J •

Можно заметить сходство между нормальными базисами и циклоклассами {tV, 7V,7V, ...)-итеи другие состоят из набора сопряженных элементов. Их коренное отличие состоит в том, что циклокласс содержит произвольное число элементов и не обязательно является базисом, а нормальный базис состоит строго из г элементов, причем таких, которые образуют базис.

Итак, нормальный базис - это циклокласс длины г, компоненты которого составляют независимую систему. (Напомним, что по определению базис представляет собой набор различных компонент - векторов, образующих независимую систему.)

В любом поле GF(2) всегда существует по крайней мере один нормальный базис. Более того, среди элементов 7, порождающих такие базисы, всегда найдется примитивный; порождаемый им нормальный базис также будем назьшать примитивным. Конечно, не всякий примитивный элемент поля порождает нормальный базис. С другой стороны, если 7 - непримитивный элемент поля GF(2*), а набор

7, 7, .. ., 7*) , д = 2, является базисом, то его будем называть неприми-тивным нормальным базисом.

В табл. 3.4 в последней колонке приведены представления всех элементов полей GF(2*), /• = 2, 3 по нормальным базисам.



Поля GF(22) и GF(2) имеют по одному, а следовательно, примитивному, нормальному базису, порожденному примитивными элементами соответственно 7 = = 2) и 7 = (г = 3).

В то же время примитивный элемент о: в поле GF(2), п{х) = + х + i, нормальный базис не порождает. Действительно, в координатах 7 = а = 2, 7 = = = 3, 7 = = 5} могут быть выражены только следующие элементы этого поля: TVe [ О, 2, 3, $} > что подтверждается рис. 3.8.

У поля GF(2) два нормальных базиса: примитивный, порождаемый примитивным элементом 7 = а = 8, и непримитивный, порождаемый непримитивиым элементом 7 = = 4. В табл. 3.16 даны представления всех элементов поля GF(2)у -п (х) = х + X + it в координатах {7, 7, 7, 7® этих базисов, а также в виде степеней примитивного элемента 7= сР- Непримитивный элемент 7=0: имеет порядок 5, так как 7 = (Ос) = о: = 1, и, следовательно, с помощью степеней этого элемента нельзя выразить все элементы данного поля.

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

Итак, подытожим. В любом поле GF(2*) всегда существует степенной базис, являюиц1Йся каноническим, и имеется хотя бы один нормальный базис, причем примитивный. Нормальный базис может быть порожден как примитивным, так и непримитивиым элементом поля. В то же время не всякий примитивный элемент порождает нормальный базис.

След. Выявление нормальных базисов для полей даже не очень высоких размерностей является трудоемкой задачей. Для того чтобы рассмотреть этот вопрос подробнее, нам необходимо ввести понятие функции "след" [35].

Следом (обозначение Тг ) элементам поля GF(2 ) называется сумма:

/ = / - 1

Тг(д) = Z а- = а + . . . +ау

i = О

(3.39)

где д = 2~, а знаками £ и обозначена аддитивная операция поля GF(2*).

От Перестановки слагаемых в формуле (3.39) сумма не изменяется; кроме того, в любом поле характеристики 2 выполняются тождества S ~ а при q - 2

и(д+6) Поэтому справедливы равенства

7= 2,

2 1 7=3,

Л= 5

7V= 3

Л/ = 3 + 5 = (100)

+ (UO) =

(010)

7V= 2

iV = 2 + 5 = (010)

+ (UO) =

(100)

TV = 2 + 3 = (010)

+ (100) =

(НО)

Л = 2 + 3 + 5 = 0

Рис. 3-8. Попытка представления злементов поля GF(2), я(х) = + х + 1 по на-

шления злементов поля GF(2 ), я бору { 7 = а, 7 = 0=2, =



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