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



нормальному базису {7®, у, у, у] с ведущим элементом 7= а, а именно:

= 3 7 + 2 7 + 1 7 + 0 7 = (0101) у .

Таким образом, с?з = 0; с?2 = 1; di = 0; do = 1. Так как Tr(D) = d -\- di + di + do = Оу то уравнение (5.10) имеет пару корней z, z" G GF(2"*), определяемых по формулам (5.8) и (5.7):

z = (z4, Z3,Z2, zi) = (1100);

Z" = (Z4,Z3,Z2,Zi) = (00 1 1),

где учтено, что 7 = а,

2о = 0; Zi = с?1 = 0; Z2 = 2i + с?2 = 1; Z3 = Z2 + rf3=l* Из табл. 3.16 находим

Z =(1100) = 5; z = (00 1 1) = 2.

Используя подстановку x=4z, найдем правильные (с точностью до обозначений) значения корней исходного уравнения (5.9) :

x=4z = S; x"=4z" = 5.

Пример 5.2. Предположим, что над полем GF(2®) с порождающим полиномом я = а® + + + + 1 задано уравнение

Z 2 + Z + 22 = 0.

(5.11)

Обращаясь к табл.П.2 (а 7)» находим, что элементу Л? = 22 соответствуют комбинации

22= (01110101) = (11111101)

Число единице последней комбинации нечетно: wt(llllllOl) = 1, поэтому Тг(22) = 1 и заданное уравнение (5.11) надОГ(2®) решений не имеет, т. е. полином z + z + 22 неприводим.

njHiMep 5.3. Пусть над тем же полем GF (2) задано уравнение

Z 2 + Z + 207 = 0.

(5.12)

Согласно табл. П.2 (а 7) представление элемента = 207 имеет

вид:

dj d ds с?4 с?з di di do 7V = 207 = (01010011)= (1 10 110 11).

Так как Tt(D) = wt(l 1011011) = 0, то уравнение (5.12) имеет решение - пару корней z иг", определяемых соотношениями (5.8), (5.7):



(7 J 6) • • • » 2 1, Zo)

(10 1 10 1 10);

(Z7,Z6, ...,FbZo)= (0 1 0 0 1 0 0 1),

(5.13)

где Zo = 0; Zj = rfj

+ с?4 = 1; Zs = z4 +

по табл. п.2 (7

= 1; Z2 = Zi + с?2 = 1; Z3 = Z2 + c?2 = 0;

= 1; 2б = Zg + £/5 = 0; 27 = 75 + 7 = >a для 182 и 73) и табл. 3.13 находим

z4 1.

= Z-J -г

z= (11110101)= 232; z"= (11110100) = 231.

проверка: (11110101) + (11110100) = (00000001) = 1 и (z +

+ 231) (z +232) = z2 + (231 +232)z + 232 • 231 = z + z +207, GF(2).

формулы для корней канонического квадратного уравнения.

в табл. 5.1 приведены формулы, полученные в работе [53], для корней уравнения

таблица 5.1

Формулы дли корней квадратного уравнения 2+7 +d

надполем gf(2), tr(z)) = о

нечетное число

/ = (0,2, 4,..., 1); j = [h 3, 5,. ..,r-2}

четное число: г = 2 mod 4

2i=a+ Б {d + d) , /=2+4/;

[ 0 при t4id) = 0; 2 при t4id) = 1

/ = (0, 1, 2, ..., С-6)/4

r = 0 mod 4

ft = 2i +г/2;

a - Б z)b c- 2 +2 ;

{ d, g = 0 при Г4(/)) = 1; -d++r при 7-4(1)) = 0

/ = (о, 1, 2, ...,

С-М) -

7 = /\[o] = l, 2, (/4) - 1]

примечание. = Zi + i - lizi); = 2 - i; g g¥(2 ); g - такой

элемент, что trig) = 1; г4 (d) = Б z)

, л:= (о, 1, 2,(г-2)/2) .



z2 + 2 +/) =0, GF(2).

(5.14)

Поясним вывод формулы для корня Zi, например, когда г - нечетное число.

Предположим, что Zi - корень уравнения (5.14). Возведем обе части тождества z\ + Zi + Z)=Ob ряд степеней 2, / = О, 2, . .. , г - 1. Учитывая, что для поля GF(2) справедливо равенство {а +Ь) = = + А, имеем:

3 2 2

при /=0 Zi+Zi=Z); при Z = 2 z\ z\ ~ D ;

при / = 4 Zj +zf = Z) ; при г = г - 1 2 + zf = D

Суммируя последние соотношения по всем г, получаем

-,г -/ .r

Б = Б Z? +Z? ,

где / = (о, 2, 4, . . ., г- 1} ; / = (l, 2, 3, . . ., г- 2 ; £ = / U / = = (о, 1, 2, 1} - множества целых положительных чисел, мень-

ших г, соответственно четных, нечетных и всех; U - символ объединения множеств.

По определению функции след сумма по i в правой части равна Tr(zi), а по теореме Ферма последнее слагаемое суть Zj, т. е.

DD +/)* +. .. -D =Tr(zi) +Zi.

Так как для поля GF(2) след любого элемента равен О или 1, а сумма корней уравнения (5.14) равна 1, то получаем формулу для расчета одного из корней по параметру Z):

Zi =i) + /)4 +/) + . . = Б (5.15)

Исходное уравнение имеет решение лишь при Tx{D) = О, поэтому равенство (5.15) не нарушится, если к его правой части добавить Tr(Z)):

zi = (/) + D* +...+/)2~) +

После приведения подобных членов с учетом соотношения а -У а = 0 найдем

zi +/) +...+/)~ = Б (5.16)

i G /

Итак, окончательно получили формулы (5.15) и (5,16) для корня Zi, указанные в табл. 5.1.

Пример 5.4. Проиллюстрируем формулу (5.16) на примере решения уравнения



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