Главная Помехоустойчивое кодирование где {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 ) задаются следующими матрицами:
Сложение и умножение элементов поля, заданных подобным образом, выполняются по обычным правилам сложения и умножения (скалярного) матриц. На пример.
к достоинствам метода следует отнести возможность производить вычисления без обращения к таблицам логарифмов. Его недостаток ~ вычисление сверток сводится к умножению матриц. Рассмотренный метод вычисления можно усовершенствовать. Подметим, что матрица, подобная (но с обратным расположением столбцов) и соответствующая некоторому элементу 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);
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 |