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



Поле GF(22),

Поле GF(2),

Поле СРСг*),

я(лс) +Х + 1

п{х) =Х + Х+1

Я(Х) = лс* + JC + 1

Тг(а<*) = 1

Тг(а*>) =0

Тг(а1) = 1

Тг(а1) =0

Tr(al) = 0

Тг(а2) =0

Тг(а2) =0

Тг(аЗ) = 1

Поле GF(2.

ПолеСР(2*),

Поле GF(2),

п{х) -х +х + 1

я (лс) = + JC + 1

Я(ЛС) = ЛС* +JC + 1

ti(ofi) = 1

Тг(а<*) = 0

Тг(а*>) = 1

Тг(а*) = 0

Тг(а1) = 0

Tr(al) = 0

Тг(а2) = 0

Тг(а2) = 0

Тг(а2) = 0

Тг(аЗ) = 1

Тг(аЗ) = 0

тт(о?) = 0

Тг(а4) = 0

Тг(а4) = 0

Тг(а4) = 0

Тг(а5) = 1

ТгСа) =0

Тг(а6) = 0

Рис. 3.9* Следы базисных элементов полей GF(2), г = 2 .. . 7

Тг(а2) = Тг(3) = 1(63 = о, б2 = Ь bi = 0. г>о = 0) = 63 = о,

что совпадает с результатами соответственно (3.41) и (3.42), (3.43) и (3.44), (3.45) и (3.46).

Пусть снова {-ь 2» • • •. г} произвольный базис попя GF(2), тогда хотя бы для одной компоненты Тг(Л.у) = 1. С другой стороны, слеДы TY всех элементов из одного и того же циклокласса, а следовательно, и нормального базиса, принимают одинаковые значения, поэтому для простоты будем говорить: "след циклокласса", "спед нормального базиса". Отсюда вытекает одно из важнейших свойств ~ свойство следа нормального базиса: его след, т. е. след всех компонент нормального базиса, равен 1. Вот почему след особенно просто находится тогда, когда элемент 6 представлен в нормальном базисе. ЛрЙствительно, подставляя в формулу (3.47) Тг(Л.,-) = 1, получаем

/ = г - 1

Тг(6) = Z = wt(6 j,6 2,...,6o) ,

/ = О

(3.49)

ПолеСР(22), я(л) = jc+jc + l

Поле GF(2).

я(лс)

= X +X + 1

Tiib) =Tr(6i 60) = bi

Tr(6) = тг(г>4

Ьз b2

bi bo) - Ьз + bo

noneGF(2, я(;с) = jc + jc + 1

Поле GF(2),

я(лс)

= JC* +JC + 1

Tr(6) = тг(г>2 bi bo) = bo

Tr(6) = Tiibs

64 63

h bi bo) = bs;

ПолеСР(2*), п{х) =jc*+jc + l

Tiib) = Tr(63 62 г>1 г>о) = г>з

Рис. 3.10. Логические выражения для функщй след Тг(6)



где 6 - координаты заданного вектора 6 в иормалыом базисе.

Ясно, что число единиц в представлении всякого элемента 0 поля GF(2) по любому нормалыюму базису всегда неизменно; причем, если оно четно, то след Тг 0 равен нулю, а если нечетно - то единице.

Обращаясь к табл. 3.4 и 3.16 и суммируя по модулю 2 координаты элементов 6 е GF(2), 11 е GF(2), 3 е GF(2), представленных в нормальных базисах, читатель без труда убедится в верности значений следов, ранее найденных для этих элементов другими способами.

Два базиса Л.2, ... , -/- и- £ i, £ 2. • • - , поля GF(2*) называются

двойственными, если выполняется соотнощение


при! =; ; при / Ф}.

10 =

12 = а", 16 =

Вьзысканне нормальных базисов. Свойство следов нормальных базисов позволяет в процессе поиска таких базисов отбраковать циклоклассы длины i -г, т. е. наборы вида {jv, N, 7v, . . ., л"} , = 2" если Тг (N) = о, и отнести к множеству нормальных базисов только те из них, для которых Tr(7v) = 1.

На рис. 3.11 дан пример испытаний нескольких циклоклассов на нормальный базис для поля GF(2®), я(лс) = + + + + i.

Следы циклоклассов с ведущими элементами 6 = а, = а, 22 = равны 1. Поэтому нормальными базисами данного поля являются наборы с этими элементами.

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

О

числами из табл. ПЛ. Подобный пример для поля GF(2 ) дан на рис. 3.12, где произведено испытание иа нормальный базис трех циклоклассов. След элемента 6 = о: равен 1, следовательно, соответствующий ему набор является нормальным базисом для рассматриваемого поля. (Как будет показано далее, всего у поля

GF(2 ) 16 нормальных базисов.)

В табл. 3.14 в последней колонке указаны следы циклоклассов, рассчитанные при задании полей GF(2) примитивными полиномами я(х), перечисленными в табл. 3.1- Из табл. 3-14, в частности, следует, что циклокласс -[б, 11, 21, 41, 81, 161, 66, 131 ] с ведущим элементом 6 = 0: является нормальным базисом для поля GF(2®), я(х) ~ х + х + х + х + 1 (см. также рис. 3.11). Изображения

всех элементов данного поля по указанному базису сведены в табл. П. 2 (переход 01 у). Там же эти изображения упорядочены по нарастанию (имеются в виду десятичное и двоичное представления изображений). Переход 7 -»-а используется в § 5.1 при рещеиии квадратных уравнений над полем GF (2®).

Число нормальных базисов. Рассмотрим теперь задачу подсчета числа нормальных базисов для поля GF(2) при фиксированном значении его размерности г.

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

Однако свойство циклокласса *быть нормальным базисом" ие всегда наследуется при изоморфном отображении. Другими словами, если набор [ А i, Л.2, • • » \г} является нормальным базисом при задании поля Галуа с помощью полинома



00000010

00001000

0010Q000

10000000

00000100

оюооооо

01110100

00010011

00010000

11001101

10110100

00011000

00011101

10001111

01101010

01011101

01001100

01000110

11111101

10000001

10011101

11011001

11100110

00010010

01011111

10000010

10111110

00011001

10000101

00010111

00101110

01011100

00000000

00000000

00000001

00000000

00111010

11101000

10000111

00100110

00101101

11101010

00000 по

01100000

00100101

11101110

00010100

10111001

01100101

11111110

00001101

00111011

10101000

11100011

01010001

00101100

00100111

10101111

11010001

00100100

01100001

00110010

11000010

01100100

10111000

01101101

11011010

Ш101001

00000001

00000001

00000000

00000001

01011010

01110101

11001001

00000011

10010100

10110101

10011111

00000101

00011110

01101011

01011011

00010001

01001001

111)1100

10010101

00011100

10001100

11100111

00011111

01001101

01000011

10U11H

01001000

10011100 -

11001000

00101111

10001101

01011110

10011110

00100001

01000010

10000100

00000000

00000001

00000000

00000000

Рис ЗЛ1. Испытание ряда циклоклассов, состоящих из элементов в векторной

:орме, на нормальный базис для поля GF(2®), п(х) - х° + х* + х + х + 1

7Г1(х), то при выборе полинома Я2 (х) этот набор нормальным базисом может и не быть.

Поясним сказанное простым примером. Существуют два неприводимых (минимальных) над полем GF (2) полинома степени 3 - см. рис. 3.7: тту (х) = х + + X + 1 н nj{x) = X + X + 1. На рис. 3.13 показаны два способа представления поля GF(2 ) с помощью этих полиномов и найдены следы двух циклоклассов: {l, 3, 5} и (4, 7, б}. В первом случае Тг (2) = О, Тг(4) = 1* поэтому набор 4, 7, 6} длины / = 3 является нормальным базисом поля GF(2 ), пу {х) = + + х + 1, а набор {2, 3, 5} таким базисом не является. Во втором случае, при выборе полинома 1Т2 (х) в качестве порождающего, распределение ролей у этих циклоклассов обратное, так как Тг(2) = 1, а Тг (4) = О- Подчеркнем еще раз, что оба

использованных способа задания поля GF(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.0106