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



в общем случае

/ /-1

т. е. Д1 = ; Д2 = , • - \ uj = , . . . ; .

Вспомним, что минимальное целое положительное число w, для которого aj-ai, называется мультипликативным порядком элемента OLj .

Следовательно, мультипликативные порядки и элемента ai и элемента равны ж. - порядку (числу элементов) циклической группы G = <K\ • > с операцией умножения, задаваемой ганкелевым циркулянтом (рис. 3.3)

Итак, G„=<K\ •> ~ циклическая группа; при этом если ж -

простое число, то любая степень а\ или aL при О </ < ае , а следова-

тельно, любой элемент = 2" = « ~ > кроме элемента а\, является примитивным, так как имеет порядок w = w(fly) = ае .

Если же зг - составное число, то согласно теореме Лагранжа (§ 3.1) порядок W любого элемента Qj , кроме , равен Mj, где rjj = НОД [96 , (/ " 1)] ~ наибольший общий делитель чисел и / - 1. Например, при Х = 6 имеем

7?2 =

Н0Д(6, 1) = 1

; {2)

= Э& /7?2 =

V3 =

НОД (6, 2) = 2

= » /773 =

НОД (6, 3) - 3

; н(д4)

= Ж /??4 =

НОД (6, 4) = 2

= Х /775 =

НОД (6, 5) = 1

; И(«б)

- Ж /7?б -

Непосредственное вычисление для элементов 3,4, as дает al=a5,al=ai; al=ai; д = Д3, д = Д5 Д3 = ,

т. е. порядки непримитивных элементов а.а, as будут (дз) = 3, w(a4) = 2, w{as) = 3.

Все элементы циклической группы G = <K; • > могут быть представлены степенями примитивных элементов или Д92, ; например, для ае, = 6 имеем такие поедставления:



д, = д, Д2 6 3 Й4 = = al, ав = Дб-

Откуда, в частности, следует: Дз «4 = д aiai = Дб;

Д4 Д5 = дйГ2 = «2 = 2 2 = 1 2 ~ 2-

Таким образом, для произвольного целого положительного числах всегда существует циклическая группа Сц~ <К; • >, мультипликативная операция которой представляет собой ганкелев циркулянт (рис. 3.3). Эта группа изоморфна аддитивной группевычетов целых чисел по модулю . Поэтому часто используется не мультипликативная,

а аддитивная форма записи групповой операции, т. е. знак "+", вместо степеней вводятся коэффициенты, нейтральный элемент обозначается нулем или До и т. п. Здесь преднамеренно используется мультипликативный язык, для того чтобы упростить переход к рассматриваемым далее расширенным полям Галуа GF (р/*) - алгебрам с двумя бинарными операциями, так как умножение над полем GF (р) задается как раз ганкелевым циркулянтом.

Логарифмирование элементов ганкелевых циркулянтов. Естественно, удобнее работать не с показательными функциями, а с числами, т. е. перейти к арифметическим зависимостям. Традиционный метод

такого перехода - логарифмирование, которое вводится следующим образом.

Пусть Ду - aja . . . а (/ сомножителей), т. е. Ду = а д., где операция умножения задается ганкелевым циркулянтом (рис. 3.3). Тогда степень / является логарифмом по основанию д для элемента ду и наоборот ду - это антилогарифм по основанию а для степени /. Здесь а - какой-либо примитивный элемент группы G.

По аналогии с обычными логарифмами используем обозначения:

если Ду =д,то / =]ogry; Ду = aiogz;

причем для упрощения записи подстрочные индексы у символов log и alog будем опускать, отдельно указывая основание дд..

Логарифмы log и антилогарифмы alog по основаниям Д2 и д для ганкелевых циркулянтов (рис. 3.3) определяются следующими подстановками и формулами:

основание Дг

log Д/

а\ fl2 Аз - • «ае

з£ 1 2 ... ге-2 ае~1/



z - 1, если i > \ y ae, если i ~ l\

1 2 ... 2 ae- 1 36

alog /

+ j, если z <Э£; fli , если / = as ;

основание Дае log д. = -

\ 36 1 . • • 2 1

эе + 1 - z;

1 2 ... -at- 1

alog / = ( - + i - r

Следовательно, логика логарифмирования по последнему элементу (основанию а) проще, так как отсутствуют условные переходы "если. . ., то ,. .

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

Например, логарифмируя по основанию д2 > приводя по модулю аг = 6 и антилогарифмируя, найдем произведения

Дз «4 alog log (дз д4) =alog {loga +logfl4) =

= alog (2 + 3) = alog5=fl6;

д4 = alog log (д4 as) = aJog (log a + log as)

= alog (3 + 4) = alog 7 = alog 1 = д2.

где знаком + обозначена обычная сумма целых чисел.

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

Рассмотрим произведение aaj. Так как ауа = аа\ =д, где а Е: К, ai Е А", то достаточно принять/ # 1,I. Кроме того, при имеем



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