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



Например, для поля GF(2), 7т(х) = + х+ 1, имеем с = = (tf2 "о) =

= Uo + 3fli + 5fl2-

Так как 1 - (001), 3 - (100), 5 -(110). то окончательно получим

С2 +fli; Cl -021 Cq - Oq.

Вообще для возведения в *двоичную" степень 7 = 2 , п = 1, 2, ..., можно использовать формулу

г - 1

с = аУ =. S а.\.; \- = ( + l\ ю

/ - О

(4.39)

Для произвольной степени а можно составить такую формулу

г - 1

г - 1

г - 1

= S а/ S а. ... S а,- Х,- ;

/j = o Ч2 = 0 * /„=0 и /Ь.

где \= 1 11 + 12 + - •. + i

Например, для поля GF(2), я(х) = х + х + 1, при п~ г = 3 имеем

г - 1 г - 1 г - 1

= tf = 2 tf. 2 а. е tf,

/=0 /=оА: = 0

( i +/ +X: + li 10 =

-flo[flo(lflo + 2fli + 3tf2) (2tfo + 3tfi +42) +

+ fl2 (3tfo +4fli + Stfj)] +tfi[tfo(2tfo + 3tfi +42) +

+ fll (3tfo + 4fli + 5fl2) + tf2 (4tfo + 5tfi + 62)] +2[flo(30 +

+ 4tfi + 52) +Я1 (4flo + 5aI +602) +fl2 (5tfo + 6tfi + 7tf2)]-

{скрывая скобки, приводя подобные по Правилам поля GF(2) и заменяя их д преобразований:

члены, складывая десятичные числа оичными векторами, получим после

С2-tfitfo + 2; Cl - Д2 flo+fli flo+ fli "fli flo V fljflo;

Co = fl2fll +fl2 +fll +flO- (fllV U2) +fl0»

где использованы символы логических операций (tfo ~ инверсия от Oq; V -дизъюнкция).

Пример 4.1. 5* (fl2fliflo) = (110) (С2 Cq) (111)6, GF(2). Большой интерес представляет вычисление мультипликативного обратного

а [55].

Как показано в работе [50], i-я компонента обратного элемента а =

= {а* J, fl/ 2 • • » fl/* • » fli* flo) равна минору элемента 0. в матрице Г а =

Тд. Так, для поли GF(2), я(х) = х + х+ 1, составим матрицу

"3

" fl2

(fl2 ax flo) (fl2 ai flo)2

. (fl2 fli flo)3

fl2 fli

fl2 +flo

fl2 + flo fl2 + fl 1

r = 3

fl2 fllJ

11 /



Компоненты искомого вектора а находятся так:

где - элементы последнего столбца. Таким образом, имеем

flo* =

во +2 2 +1.

= tf2 fl 1 + fl2 + fl 1 + flo ~* fl2 fl 1 + fl2 + flo ;

•fll

tfj + tfo fl2 *fll.

fll flo +fl2;

fl2* =

fll fl2 + flo

- tf2 flo + fl2 fl 1 ~ fl2 flo fl 1

Например, для элементам =4-*- (fl2fliflo)= (Oil) попучаем - 0; * - 1;

tfj= 1, t. e. (tfJtfftfS) = (110)- fl * = 5.

таблица 4. 7

Выражения для компонент tf,* мультипликативио-обратиого элемента

tf/> • • • »flb flo)~* = (fl*» flr-1 • • * .fl*.• • • .flf.tfo)

tf"* = (tf;.,tf

2» • • •

Поле

Выражения

GF(2,

я (j:) = j: + j: + 1

0* =

fli;

tfi +tfo

GF(23),

я(х) = +д:+ 1

tf-tf2flo+fl2+fli; tfT-tfiflo+fl2;

fl? ~fl2fll *tf2 fll *flo

GF(2*),

-nix) = + X + i

a-Ojax + tf3tf2 + tf3tf 1 + tf3tfo + tfs + fl2 + fliJ

tf3tf2tfo +tf3fl0 +fl2flo tfltfO +fl3 +fl2;

flafliflo +tf3fli +fl2fli +fl2flo;

fl3fl2fll fl2 fll flo tf3 + fl2 *fll * flo

GF(2),

7Т{Х) = x +jc+ 1

tf 4 = tf 1 tf2 tf3 tf4 + tfo fl2 fla fl4 +flo fll fl2 fl4 + tfo Al АЗ + tf 1 tf3 tf4 + tfo аз + Al tf2 + tfo tf2 + aq tf4 + tf2 tf4;

tf3 - aq tf2 fl3 a4 +tfo tfl tf3 a4 +Ao tfl tf2 a3 +tfi tf2 tf4 + + tf2 a3 + tf3 tf4 + tfo tfl + tfo a2 +Ai tf3;

tf = tf 1 tf2 tf3 tf4 + tfo Al tf2 tf4 + flo Al tf3 + tfo tf2 a3 + + tf3 tf4 + tfo tfl + tfl tf2 + a2 tf4;

tf * ~ Ao tfl tf2 tf4 + tfo Al tf2 + tfl tf2 a3 tf4 + tfo tfl tf2 a3 + + tfO tf3tf4 +Ai tfo + tfo a3 +a4;

Ao ~ flo Al tf2 tf3 + tfo a2 аз tf4 +tf 1 tf2 tf3 tf4 + tfo Ai tf3 tf4 + + tfl tf4 +tfo tfl +tfo a2 + Al tf3



Трансформация входных векторов

cycle б)

(«о)Гц(й„.1 ft) = [7ro(fl)]r4[7r„ j(ft)]

Трансформация матриц Г и Т

аЬ cyde

fl(rut)T==flTft-fl(T)ft

а(гй = л(т)й = л(ТцПь

Трансформация выходного (результирующего) вектора

аЪ = 7г(с) = 7r(jraft) = v{aJb) cyde

Рис. 4.22. Вычисление циклических сверток с помощью циркулянтного преобразования Ганкеля-Теплица

В табл. 4.7 приведены логические выражения для синтеза схем, вычисляющих мультипликативные обратные элементы а в полях Галуа невысокой размерности.

В заключение рассмотрим вычисление циклических сверток. Для этой цели может использоваться циркулянтное ГТ-преобразование на основе матриц (4.14). Основные соотноше№1Я для вычисления циклических сверток представл&ны на рис. 4.22 и разбиты на три группы: с трансформацией (перестановкой компонент) перемножаемых векторов а и ft; с трансформацией Гц и Тц матриц (с перестановкой их строк, столбцов и, возможно, транспонированием); с трансформацией (перестановкой компонент) результирующего вектора с. Рассмотрим, например,

для п - Ъ формулу

аЪ = д Тц ft . (cycle)

Имеем д = (д2 fli «о); * = (*о *i ; с = (сг ci cq) ;

(4.40)

с- ab = (д2 fli Ао)Тц (fto fti ft2) = (cycle)

"2 0 г

(fl2 fli flo)

1 2 0

0 1 2

= д2 0 +fll

fti +до*2;

Cl =

flifto +

2 fli flo fli до fl2 flo fl2 fli-



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