Устройство для выполнения операций возведения в степень деления и умножения двух элементов в поле галуа @ (2 @ )

Устройство для выполнения операций возведения в степень деления и умножения двух элементов в поле галуа @ (2 @ )

Иллюстрации

Показать все

Реферат

 

СОЮЗ СООЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (50 4 G 06 F 7 00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМЪ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3750998/24-24 (22) 06.06.84 (46) 07.06.86. Бюл. У 21 (71) Объединенный институт ядерных исследований (72) Н.М. Никитюк (53) 681.325(088.8) (56) Lows В.А. and. other. А Cellular-array multiplied for GF(2).

IREE Transaction on Computers. 1973, 20. В 12, р. !573.

Патент США Ф 3805037, кл. G 06 f.

I/02, опублик. 1974.

Авторское свидетельство СССР

У 875408, кл. G 06 F 7/00, !979. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ ВОЗВЕДЕНИЯ В СТЕПЕНЬ, ДЕЛЕНИЯ И

УМНОЖЕНИЯ ДВУХ ЭЛЕМЕНТОВ В ПОЛЕ ГАЛУА

GF (2 } .(57) Изобретение относится к вычислительной технике и предназначено для

„, SU,» 1236458 А 1 использования в качестве специализированной ячейки для реализации операций одновременного возведения в сте- пень, деления и умножения двух элементов в поле Галуа GF (2 ). Цель изобретения — увеличение функциональных возможностей ячейки за счет. выполнения операций одновременного возведения в степень и деления двух элементов в поле Галуа GF (2 ). Поставленная цель достигается тем, что устройство содержит 2 m умножителей, коммутационное поле задания вычисляемых функций, сумматоры, m мультиплексоров. В устройстве происходит вычисление выражений Е/А (i=1,6) и АВ+С . в поле GF (2 ) путем реализации соответствующих аналитических выражений, содержащих операции умножения и сложения. ил.

1236458

Аналитические выражения, с помощью которых строятся схемы для аппаратной реализации выражений В/А, В/А

В/А, В/А, В/Л, В/А, имеют следующий вид:, +Л„А, В,+А В

В +А В +А2В +A„A Bî +B„A À, +B, А,A 2+Â, «+H, Л

Л А В +Л В +А В +AoH +А В +Л Л В +Ao A В +А1 В„ +Л В +Л А В + В

A A В +A A В +A„ B +А,А,В, +А„В„ +А В +А В, +А,В, +Л2:3,,+Л„ А В А Л В +Л2В, АоВо В1Л2 В Л В А2 о о 1 2 2 2 Я ь

В„Л +H. А +В Л„+В,.Л„+В,А В/Л

В А +В А +В А +В А +В А

0 2 1 1 Ъ 2 О 2 2

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

Цель изобретения — увеличение функциональных возможностей ячейки за счет выполнения операций одновременного возведения в степень и деление двух элементов в поле Галуа

Gr (2 ).

На чертеже приведена структурная схема устройства для случая вычисления выражений В/А и АВ+С при ш=З, где m — число переменных. устройство содержит шины 1-3 записи делимого в поле Галуа GF ), шины 4-6 записи делителя в поле Галуа GF (2 ), первую группу 7-15 умно т жителей, вторую группу 16-24 умножителей, коммутационное поле 25 задания вычисленных функций, первую группу сумматоров 26-28, вторую группу сумматоров 29-31, третью группу сумматоров 32-34, мультиплексоры 35-37, управляющие входы 38 мультиплексоров, выходные шины 39 устройства, шины

40-42 записи слагаемого в поле Галуа

GF (2 ), входы 43 мультиплексоров.

В качестве примера рассматривают соединение выходов умножителей с входами сумматоров 32-34 для вычиспения выражения В/А . Подключение выходов

5 умножителей к входам сумматоров 3234 осуществляется через коммутационное поле 25 задания функций, Связи для вычисления остальных выражений типа В/А, В/А, В/А, В/А и В/A получают из аналитических выражений.

Подключение выходов умножителей к входам соответствующих сумматоров

32-34 осуществляется через поле 25.

Выходы сумматоров 32 — 34 по модулю. два подключены к входам мультиплексоров так, что при заданном коде, подавае- . мом на управляющие входы 38, на выаВо+А, В +А Во +А„А2 B, +A Л2В, +A„H„A. Б

16

IS

2Î

ЗО

4О ходных шинах 39 вычисляется одно из выражений В/А" . Выходы сумматоров 2628 по модулю два соединены с первыми входами сумматоров 29-31 по модулю два, выходы которых подключены к входам мультиплексоров 35-37, на выходах

39 которых получают решения выражений типа АВ+С и В/А

Элементы поля Галуа А, В.и С при ш=З представлены в виде A=A а +А,а +

+А, " В=в.а +В à +B2а и С=

=С.а, +С, а +С1а2 где знак "+" — суммирование по модулю два.

Поле Галуа GF (2 ) содержит 2 +1 различных элементов, которые образуют циклический код, среди которых m элементов этого поля являются линейно независимыми. Путем линейной комбинации этих элементов получают остальные. Так при m=3 элементами поля

Галуа GF (2 ) будут а =100; а =010 а =001; а =110; а"=011; а =111 и а =101, Схема умножения двух элементов поля Галуа для ш=З А и В описываются следующими аналитическими выражениями. (А В,+А,В,+А2В„ ) — коэффициент при а ; (А.B +А,В, +A, В,+А В, +А,В,) коэффициент при а ; (A,Â,+Л,В, +А В +

+А В ) — коэффициенты при а

Известно,что деление элемента В на элементы А выполняется путем умно-1 жения элементов В на элемент А, который является инверсным к элементу

-1 о

А, причем AA =А =l. Для данного элемента А=А а +7i,а +А а в поле Галуа

GF (2 ) аналитические выражения для вычисления инверсного элемента A имеют вид А, =А +А, +А,+А, Л,; А„

А, А„,+А; А =-А, А,+А +А или А

=(А,+А, +А +А, Л)а +(А А,+Л )а +(А A +

+Л +Л )а2.

3 1236458 4

В,A +В.Л„+В,А,+В,Л„А,+В А A +В.,Л, +B, A

Л +В A A +B А +В„А +В„А,+ B„A +B,А,Л +В А,А +В Л,+В А

В А А +В А +В, А А +В,А А +B„A,+B A +B AÄ+B А

В/А

В А +В,А А+В,А,+В А

B,À,+Ç,À +В,Л„+В, А +В А, В/А

Для вычисления выражения В/А выI ходы умножителей, на которых вычисля- 5 ются необходимые произведения, где коммутационное поле 25 задания функций, подключаются к входам трех сумматоров 32-34, на выходах которых образуются три слагаемых суммы, соот- о

t ветствующие В/А

1 з

Напримерм для В=а =Ill и A=a =

=110 имеем В, =В, =В =1, А,=А, =) и

А =О. Подставляя значения этих ко2 эффициентов в аналитические выражения а для вычисления В/А, получают 011--а

При этом a /(а ) =а /а =а /а =а а =

° =a =a а =а, так как инверсным эле1Г ) и ll ментом для элемента а является элеб 30 мент а

Логическая ячейка работает следующим образом.

На входы 1-3 подаются сигналы, соответствующие коду элемента В (коэффициенты В,, В,, В ) на входы 4-6— сигналы, соответствующие коду элемен— та А (коэффициенты А,, А,, А ). При подаче двоичного кода на управляющие входы 43 выполняется передача резульао тата вычисления на выходы устройства с выходов сумматоров по модулю два.

При m=3 в устройстве содержатся шесть групп сумматоров по модулю два.

Случай вычисления выражения В/А явT o ляется тривиальным, так как А =А т,е. равно единичному элементу, Выражение АВ+С вычисляется при помощи схемы, состоящей из первой и второй групп сумматоров по модулю два подключенных через коммутационное поле

25 к выходам умножителей первой группы. Имея набор аналогичных устройств, можно создавать устройства для вычисления совокупности всех выражений

В/А, где i=I 6, и выражение АВ+С в данном поле.,Формула из об ре те ния

Устройство для выполнения операций возведения в степень, деления и умножения двух элементов в поле Галуа GF (2 ), содержащее первую матрицу размером m m умножителей, две группы из и сумматоров по модулю два, коммутирующее поле задания вычисляемых функций, причем выходы умножителей первой группы через коммутирующее поле задания вычисленных функций подключены к входам сумматоров по модулю два первой группы, выход i-го . сумматора по модулю два первой группы подключен к первому входу i-ro сумматора по модулю два (i=1 2, ...,n) второй группы, второй вход которого подключен к i-му входу слагаемого в поле Галуа GF (2 ) устройства, k-е входы делимого (k=1 2,... ...,тп) и g-e входы делителя (Д=1,2,. ° . ...m) подключены соответственно к первому и второму входам умножителя

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

Галуа GF (2 ), в него введены вторая матрица размером ткш умножителей, с третьей по (2 +!)-ю группы сумматоров по модулю два, m мультиплексоров, первые и вторые входы умножителей

k-й строки j-го столбца второй.матрицы умножителей подключены соответственно k-м входам делимого и -м входам делителя устройства, а их третьи входы — к (1+1)-м входам (.t=!,2,... ...,m-I) делителя, третьи входы умножителей m-ro столбца второй матрицы подключены к первому входу делителя устройства, выходы умножителей первой и второй матрицы через коммутирующее поле задания вычисляемых функ1236458

Составит ель В. Смирнов

Техред N.Ходанич Корректор В, Бутяга

Редактор Н. Гулько

Заказ 3091/5I Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

I13035, Москва, Ж-35, Раущская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 ций подключены к входам сумматоров и по модулю два с третьей по (2 +1)-ю группу, выходы J-x ()=I,2,...,т) сумматоров по модулю два, начиная с

tn второй по (2 +i)-ю, групп подключены к информационным входам 1-х мультиплексоров,, управляющие входы которых являются входами кода операции устройства, а выходы — выходами результата устройства,