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



Та бли ца 3.2

Степени для ганкелевых циркулянтов

4

J н

х"

ч

Многократно применяя правила умножения, задаваемые матрицами (3.5) и рис. 3.4, построим для равного 4, 5, 6, 8, 16, та&1ицы степеней (табл. 3.2), а по ним - таблицы корней (табл. 3.3). Из табл. 3.3 видно, что для ряда значений свободной переменной х не существует корней некоторых степеней. Точнее, не для всех значений х существуют корни тех степеней которые не взаимно просты с порядком х ~q~ 1. Это непосредственно вытекает из следствия упоминавшейся в § 3.1 теоремы Лагранжа о порядке подгруппы конечной группы.

Можно заметить, что \fх =х при Т» = 1, где Т и ф умножаются

по модулю эе = - 1. Например,Vx~=х дляхЕ GF (q == 2"), ??= ql2.

Таблицы степеней и корней иллюстрируют теорему Ферма (см. § 3.1), согласно которой цдяд = эе + ].



Таблица 3.3

Корни для ганкелюых циркулянтов

«7 =

г = 8

1.2,3

1,2, 3,4

1, 2, 3,4, 5

1,2,..., 7

- -

х-»

х-»

= 16

•>5Т

1,6, U

1.4, 7, 10, 13

1,6, 11

1,6, и

1,4, 7, 10, 13

1,6,11

1,2,3,. .., 15

2, 7,12

4, 9, 14

3,8, 13

5, 10, 15

1 -

2,5,8, 11, 14

6,9, 12, 15,3

3,8, 13

2,7,12

5, 10, 15

4, 9, 14

- -

--

4, 9, 14

5, 10, 15

2,7, 12

3, 8, 13

3, 6, 9, 12, 15

2,5,8, 11, 14

5. ЮЛ 5

3,8,13

4, 9, 14

2, 7, 12

х"



fl--l; (3-7a) aa; (3.76) =a, (ЗЛв)

где 76 - порядок Сц,

Наша задача состоит в нахождении арифметических зависимостей между элементами множества К, удобных при вычислении произведений аЬу частных а : Ь, степеней и корней п-й степени \/а ,

Так, при Q>4 и использовании матриц умножения типа (3.5) всегда 2-2 - 3 и т. п. Конечно, необходимо помнить, что под "произве-

.>? 5, 51 Я >> »> Ч

дением , частным , степенью и корнем понимаются не результаты обычных операций над числовым множеством, а результаты специальных операций, лишь для простоты называемых "умножением", "делением" и т. п. и обозначаемых соответствующими традиционными символами, но определяемых матрицами вида (3.5), (3.6) и табл. 3.2, 3.3.

Анализ матриц (3.5) показывает, что они побочной диагональю из элементов q - I разделяются на две части, причем справа от этой

и„

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

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

Можно показать [см., например, вывод формулы (3.4)], что при любых целых > 2 справедливы следующие соотношения:

для операции умножения, задаваемой ганкелевыми циркулянтами типа матриц (3.5),

а + b - 1, если а b <,q\ I д + Ь - q, если а b>q;

(3.8)

для операции деления, задаваемой теплицевыми циркулянтами типа матриц (3.6),

с : b

1 + с - если с > + с - by если с<Ь,

(3.9)

где " + " и "-" - обычные арифметические операции над множеством целых чисел. .,

Таким образом, операции умножения и деления, определяемые циркулянтами (3.5) и (3.6) над конечными множествами К, выражаются через обычные арифметические операции сложения и вычитания,

которые могут быть реализованы средствами цифровой и аналого-цифровой техники.



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