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



Вычисляя искомое произведение Д/ау классическим способом логарифмирования - антилогарифмирования (по основанию аг), получим

aaj- =alog log(flfly) = alog (log +logfly) = = alog(/ - 1 + /- 1) =alog(/ + /-2) =

a. . при / + /<ае +2;

(3.3)

где знаки плюс и минус - обычные арифметические операции.

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

и константами:

а. , если i + /<Эе + 1;

= (3.4)

где = ае + 1.

Здесь можно восполнить оставленный выше пробел и доказать с помощью формулы (3.4) ассоциативность операции умножения, определяемой ганкелевым циркулянтом (рис. 3.3). По-существу это свойство вытекает из ассоциативности обычной арифметической операции сложения над множеством целых чисел. Действительно, независимо от последовательности составления пар получим после двукратного применения формулы (3.4):

ai aj а

«,>/+fc (ae,+2) если зе + 2<г +/ + /г<2(«. +1);

Итак, справедливо равенство (д/Ду)дд. = ду(дудд.), т.е. операция умножения, задаваемая ганкелевой циркулянтной матрицей (рис. 3.3), ассоциативна, и анонсированный ранее результат доказан.

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



Модифицированное логарифмирование элементов ганкелевых циркулянтов. С целью упрощения записи перейдем от элементов д,- G , Giy • , Оц.} к их индексам г G 1, 2, . . . , ж,} . Операцию, осуществляющую этот переход, назовем модифицированным логарифмированием и обозначим Log, а обратную ей операцию обозначим ALog. Итак, по определению

Log д/ i; ALog =

если I

а- , если i > зе.

Модифицированное логарифмирование, т. е. взаимно однозначное отображение множества элементов [д- \ на множество их индексов К = {l, 2, <е-б?- l}, позволяет буквенные циркулянты типа

рис. 3.3 заменить "числовыми" циркулянтными матрицами умножения, например:

с - а

а i

4 = 5

q = 6

1 ; (3.56)

(3.5в)

Построим для (7 = 4 ... 6 матрицы деления д = с : обратные мат-

рицам (3.5) : q = 4

а = с : b

с 2

(3.6а)

(3.66)

q = e

(З.бв)

Аналогичный вид имеют матрицы деления при любых q. Таким образом, если матрица прямой операции (умножения) является ганкелевым циркулянтом, то матрица обратной операции (деления) представляет собой теплицев циркулянт; причем, как можно убедиться.



обратная операция не коммутативна и не ассоциативна. Следовательно, в то время как алгебра <К; • > - циклическая группа, алгебра <К; : > - лишь квазигруппа (группой не является) .

Особое значение для нас имеют ганкелевы циркулянты порядка - 1=2"1, где г - натуральное число. Циркулянты этих порядков, трактуемые как матрицы-таблицы типа рис. 3.3, задают операцию умножения в мультипликативной группе ненулевых элементов

поля Галуа GF {2 ).

На рис. 3.4 представлены матрицы умножения и деления для множеств из Ж. -Тиэе - 15 элементов, соответствующих порядкам = 8 ид = 16 полей GF(2) hGF(2*).

2 3 4 5 6 7 8 9 А

= 8

аЪ

с : й

с -s

==16

123456789ABCDEF

1 234567 8 9ABCDEF 23456789ABCDEF1 3 4 5 6 7 8 9 Л в CD ЕЕ I 2

456789ABCDEF123 56789ABCDEF1234

6 7 89ABCDEF 12345 789ABCDEF 123456

89ABCDEF1234567 9ABCDEF 12345678 ABCDEF123456789 BCDEFI23456789A CDEF123456789AB DEF 1 2 3 4 5 6 7 8 9 АВС EF123456789ABCD F123456789ABCDE

123456789ABCDEF

1FEDCBA98765432

21FEDCBA9876543 321FEDCBA987654

432 1FEDCBA9 8765 5 4 3 2 1 FEDCBA9 8 7 6 654321FEDCBA987 76 5 4321FEDCBA98 87654321FEDCBA9 987654321 F EDCB А A9876543 21FEDCB ВА 9 8 76 5 4 3 2 1 FEDC CBA987654321FED DCBA9 87654321FE EDCBA987654321F

F EDCB А9 8 7 6 5 4 3 2 1

Рис 3.4. Ганкелевы и теплицевы циркулянты, задающие операции умножения и деления ненулевых элементов поля GF( = » + 1): д - для X = 7; 6 - Для

« = 15



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