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



Многоместные операции над конечными циркулянтами. Упоминаемые выше схемы, реализующие бинарные операции и должны содержать пороговое устройство, оценивающее соответственно сумму д + Ь или разность а ~ Ь.

Пусть требуется реализовать с помощью одной схемы многоместную (многоарную) операцию умножения

ai 02 . . . а

i = Т

П а

i ~ 1

(ЗЛО)

обобщающую бинарную операцию, задаваемую ганкелевым циркулянтом. В этом случае количество пороговых устройств увеличивается; их количество г, пороги срабатывания П/ и выходная координата

определяются соотношениями:

т - 2)

=/+Т- z; Uj - 1,

где int I. . . " целое число; / По = 0; t/o -

малая Антье-функция, выделяющая ближайшее меньшее Е {1, 2, . . . , т); Т - арность операции умножения; - 1.

Многоместная мультипликативная операция (3.10) может быть выражена следующей аддитивной формулой:

/ = т П а

i = 1

i = Т

/ = Т

Б д"Т+1шо(1(ге =-1),если Z +

/ = 1

/ 1

+ 1 О mod q-\\

i = Т

, если Z " Т + 1 - О mod - 1,

/ = 1

(3.11)

Например, для q - 6 имеем 2-3-4 = 2 + 3 + 4- 3+ 1=7 = 2 mod (q ~ 1 = 5); 2-3-4 = 5, так как 2 + 3 + 4 + 4- 4+ 1 = 10 = = 0mod (- 1 =5).

Приведенные расчеты можно проверить непосредственно по матрице (3.5в):

2-3.4= (2*3) •4 = 4-4 = 2; 2-3-4

4 - 4

4-2 = 5.

Для степенной функции а при д- = д = const следует

а а ...а (Т раз) из формулы (3.11)



Т(д - 1) + 1 mod (ТЕ, 1),если Т(д - 1) +

Ф О mod ТЕ. ;

Ж. , если Т(д " 1) + 1 = О mod .

(3.12)

Например, для q = бимеем З* = 4 • (3 - 1) + 1 = 9 = 4 mod(« = 5), в чем можно непосредственно убедиться по матрице (3.5в): 3* == 3 X X 3 = 5 • 5 = 4.

В частности, при Т=3£ =:"1иТ = получим

= X (д - 1) + 1 = 1 mod за ; =zq(a - 1) + 1 = д +(д - 1) =а mod* .

Эти соотношения совпадают с формулами (3.7а) и (3.76), выражающими теорему Ферма.

Зависимость (3.12) справедлива также и для отрицательных степеней Т. Пусть, например, необходимо вычислить 3"* для q = в. Тогда по формуле (3.12) находим: З"* = -4(3 - 1) + 1 = -8 + 1 = -7 = = 3modX . Действительно, так как 3* = 4, то согласно матрице (З.бв) получаем 3"* = 1/3* = 1/4 - 3.

Формулу (3.12) можно модифицировать следующим образом:

а =Т(д - 1) + 1 ± Х /,

(3.13)

где i ЕКо= [о, 1, 2, . . . , - 2] ; -q <T<q; перед / знак плюс берется при Т < О, а минус - при Т > О, причем значения / выбираются

так, чтобы а" Е К - { 1, 2, . . . , , т. е. чтобы величина лежала

в диапазоне 0<д<9е= - L

Например, для = 6 получаем 3* = 4 • (3 - 1) + 1 - 5/ = 4 при / =1; 3"* =-4* (3- 1) + 1 + 5г - 3 при / =2.

Аналогично

д- 1 = /:+ 1 " д при / = 1;

= (д - 1) + 1 - -at / = 1 при / = д - 1;

-q{a -1) + 1- 9е/ = д при / = д - 1,

что вновь совпадает с формулами (3.7а) и (3.76).

Расрмотрим теперь корни, т. е. дробные значения Т в формулах

(3.12) и (3.13).

Извлечение корней произвольной степени из элементов ганкелевых

циркулянтов. Обозначим д = т. е. д \fb . Тогда с учетом формулы

(3.13) получим следующее арифметическое выражение для корня:

4-1610

д й+т-1±ас/

(3.14)



i EKo= (a 1,2, ...,-2},

где знак " -" берется при Т < О, знак " + " - при Т > О, а значения / выбираются так, чтобы величина а была целым числом, лежащим в диапазоне 0<д<= - 1,т. е. чтобы а ЕК.

Поясним выражение (3.14) Несколькими примерами:

- 5 + 2-1 + 5/

= 6, v5 = -- = 3 при i = 0;

= 6, = - =2 при г = 1

-1-5/

1 + 5

-1 + 5/

3 + 2

-1+4/

2 + 2

- 1 + 4/

I + 5 - 1 + 5/ . л

6, = - е к при / G {о, 1,. . . , 4} ;

= 5, 3 = - е {2,4} при i е [0,1];

= 5, = - Е 0 при / ЕКо,

где 0 - символ пустого множества, т. е. л/2 над множеством К при = 5 не существует.

Для произвольного множества К ]лд>0

а + q - 1+ 1)/

- - =Г д fjpjl / =ГД - 1


что совпадает с формулой (3.7в), выражающей теорему Ферма.

Вьппе отмечалось, что корни у некоторых степеней Т, не взаимно простых с порядком з& = - 1 циклической группы, могут существовать не для всех значений свободной переменной. Рассмотрим этот вопрос подробнее.

Обозначим НОД (*аЬ , Т) = т?. Тогда лишь для v -31 /т] элементов существует корень степени Т, причем этот корень принимает т? значений, определяемых формулой (3.14).

Во всех случаях корень степени Т =3£ извлекается лишь из единицы и имеет X значений: 1, 2, . . . , ТП. Далее, если Ж* простое число, а следовательно, НОД (ЗЕ/ , Т) = 1, то корень произвольной положительной степени Т, удовлетворяющей условию Т < "aC , может быть извлечен из любого элементах Е К =• 2, . . . и значение корня единственно.

Предположим теперь, что - составное число. Если Т и 9t взаимно

просты, т. е. НОД (X , Т) = 1, то корень степени Т также существует для Произвольных x и принимает единственное значение.

Пусть Т и не взаимно просты и НОД ( Ж., Т) - цф 1. Депо, что извлечение корня возможно только из тех элементов для которых



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