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



где {i = 0, 1, . . . , г ~ 1) ~ коэффициенты полинома n{x) = +flr -1 + . . . + flj x +flo- Матрица (4.33) может рассматриваться как примитивный элемент 0:= 2 поля GF(fl = 2), а ее степени ~

= 4; . , . ; = q - 1 М~ = 1. Например, для полинома п{х) = + j: + 1

как ненулевые элементы: М =3; =

ненулевые элементы поля GF(2 ) задаются следующими матрицами:

"0

"0 0

"1 1 0"

"0 1

"1 1

1 0

"1 0

0"

0 1 1

а 1

-1 1 1-

- 1 0

.0 1

-0 0

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

5, С

"0

"1

0"

"0

" 1

0"

"0

0 iJ

к достоинствам метода следует отнести возможность производить вычисления без обращения к таблицам логарифмов. Его недостаток ~ вычисление сверток сводится к умножению матриц. Рассмотренный метод вычисления можно усовершенствовать. Подметим, что матрица, подобная (но с обратным расположением столбцов) и соответствующая некоторому элементу 7V лоля GF(2), равна скалярному произведению T{N)q, где Т ~ теплицева матрица порядка г, {N)q -двоичный вектор, соответствующий 7V, как элементу поля GF(2). Так, имеем

3 2 1

4 3 2

5 4 3

О 1 О J

2 3 .4

0 1 О

1 О О О 1 1

2. GF(2);

"3

"2 + Г

" 4

3 + 2

.4 + 3J

. 6

4, GF(2)

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

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

Вычисление сверток с помощью ГТ-преобразования. Прежде всего дадим "числовую" трактовку (основных) соотношений ГТ-преобразования, представленных на рнс 4.18. Обозначим а = (д, г-!» - • • . «1» «о). = (с;., c-i* • - * Ci, Cq). Тогда компоненты результирующего вектора с (как произведения исходного вектора а на Г и Т матрицы) найдутся из соотношений:



для с - аГу с - аТ

- * ir-1-k-i ~

с S а.2 = S a.Xj.. (4.34)

/ = О 1=0

для с = аГ, с=аТ

с = S д-2 = S а.\.., / = О / = о

(4.35)

где запись \ = - . ю означает, что вычисление величины \ производится по правилам обычной арифметики - сложения целых чисел в десятичной форме.

Ясно, что Ху.

Например, дли рассмотренного выше примера над полем GF(2 ) получим

с = (со ci) =аТ= [(Хоо 0 + 01 "О» iiQ "о + >ч1 "i)]. где\оо = 3; Xqi = 2; \io = 2; Хп = 1.

Выражения, аналогичные (4.34) и (4.35), можно составить и для векторного ГТ-преобразования.

Основные соотношения, вытекающие из ГТ-преобразования и позволяющие производить вычисления сверток в конечных полях, представлены на рис 4.21. (Естественно, достаточно использовать лишь одну из формул.)

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

Из рис. 4.21 следует, что вычисление полевой свертки может осуществляться за два шага: ,

1) нахождение ГТ-преобразованни G для одного из векторов-сомножителей;

2) умножение полученного изображения G на второй вектор-сомножитель.

Полученное произведение н является искомым результатом. Однако более привлекателен следующий подход к вычислению полевых сверток. Перейдем от векторно-матричных представлений к числовым. Утверждение 4.}. Надполем ГалуаОГ(2) произведение с = (c i, с 2*

ci, со) двух векторов а = (fl;. i. в 2 • • •. «1. о) и 6 = (6 i. *г-2* *о)

определяется соотношением в £П-форме:

с = S fl S b. Х-., X.. = i/ + / + 1 Г 10, (4.36)

( = О / = о

где символы £ означают многоместную операцию сложения по модулю 2 [см. также пояснение к формуле (4.35) ].

рассматривая коэффициент Ху как десятичный номер (модифицированный логарифм) и заменяя его соответствующим двоичным эквивалентом как элемен-



Свертка векторов в прямой форме аЬ

аЪ - а X b


bVa = а ТЬ ЬТа = (а гЧ

Свертка векторов в перестановочной форме а Ь (ftrV)= (Тт*)= {ЬТа)

Свертки векторов в смешанной форме а b яа b

аТ =Т Ы = ЬТа * =ТтЬ = ЬТа*

а ь = дГ ft = ft Га = tfTft = ftTtf = = (аГТ)= (TrV)= (ТтТ)

(ftxV)

Рнс. 4.21. Вычисление полевых сверток с помощью преобразования

Ганкеля -Теплица

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

Поясним формулу (4.36) простейшим примером вычислении произведения над полем GF(2). Задаваясь значениями / G {о, 1},/ G {о, l] . найдем коэффициенты Ху в формуле (4.36); Xqo ~ 1; oi ~ ~ ~ 3. Следовательно,

с = Хоо "о 0 + 01 1 + 10 "1 0 + fli 1 ~ = Itfo 0 + 2flo bi + 2fli fto + 3fli bi.

Заменим десятичные коэффициенты соответствующими векторами заданного поля (см. табл. 3.4): 1 (01). 2**- (10), 3 (11). Тогда

с= (Cl Со) = (Ol)tfo bo + (10)flofti+ (10)flifto+ (IDflib

т. е. для компонент вектора с = Aft, GF(2 ) получим: cj = ОАоо + 1*Ао1 +1 0 + Ifli bi =

= Aoftl +Ai fto +Ai ftj;

olfloo + Ooi 1 fto + lAjfti =

= Aq fto + fli 1*

(4.37)



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