Устройство для выполнения операций возведения в степень деления и умножения двух элементов в поле Галуа @ (2 @ ) Советский патент 1986 года по МПК G06F7/00 

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

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

На чертеже приведена структурная схема устройства для случая вычисле- НИН выражений В/А и АВ+С при , где m - число переменных.

Устройство содержит шины 1-3 записи делимого в поле Галуа GF (2 ), шинь 4-6 записи делителя в пол€ Галуа GF (2 ), первую группу 7-15 умножителей, вторую группу 16-24 умножителей, коммутационное поле 25 задани вычисленных функций, первую группу сумматоров 26-28, вторую группу сумматоров 29-31, третью группу сумматоров 32-34, мультиплексоры 35-37, управляющие входы 38 мультиплексоров, выходные шины 39 устройства, шины 40-42 записи слагаемого в поле Галуа GF (2 ), входы 43 Г1ультиплексоров,

В качестве примера рассматривают соединение выходов умножителей с входами сумматоров 32-34 для вычисления выражения В/А, Подключение выходов умножителей к входам сумматоров 32- 34 осуществляется через коммутационное поле 25 задания функций, Св.язи для вычисл ения остальных выражений типа В/А В/А% В/А, В/А и В/А получают из аналитических выражений. Подключение выходов умножителей к входам соответствующих сумматоров 32-34 осуществляется через поле 25, Выходы сумматоров 32-34 по модулю дв подключены к входам мультиплексоров так, что при заданном коде, подавав- мом на управляющие входы 38, на , +А, В„+А,В„ +А А, В„ +А„ А., +А, В, ч-А

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

,В,

А ,

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

АО В, + +А, А В„ +В, А„А, +В, А,А,+В, А +В А В, А, , Л

А, +А, В„ +А„ В ,+А, А, В, +А„ А, В., +А,А,,В +А„А, В +А,, +А, В,, I В/А

А,А, В, -ЬА,А,В„ +А, ,А,В, +А,Ъ , -ьА,В, 4.А, В,А,В,ч-А, A,+A,A,B,,J

A,B,+B,,+В,А, 1

В, А„ +В, А +В А, +В,,А н-В, А , В/А BoA,,B,A,+B,

364582

ходных шинах 39 вычисляется одно из выражений В/А . Выходы сумматоров 26- 28 по модулю два соединены с первыми входами сумматоров 29-31 по модулю

5 два, выходы которых подключены к входам мультиплексоров 35-37, на выходах 39 которых получают решения выражений типа АВ-ьС и .

Элементы поля Галуа А, В.и С при

0 представлены в виде , а + В Воа +В,а +В,,а и С С„а +С,а , где знак -f - суммирование по модулю два.

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

А„А.+А„; А

Галуа GF (2) будут а 010; а 110; а П1 и а 101 .

Схема умножения двух элементов поля Галуа для А.и В описываются следующими аналитическими выражениями: {AoBp+A Bj+A,Bi ) - коэффициент при (А„В,+А,В„+А, , коэффициент при а ; ,B, +А,,Во + ) - коэффициенты при а.

Известно,НТО деление элемента В на элементы А выполняется

путем умножения элементов В на элемент А , ко- Topbtfi является инверсным к элементу А, причем АА , Для данного элемента А А°а°+А, а в поле Галуа GF (2 ) аналитические выражения для вычисления инверсного элемента А имеют вид ,, А, ; А/

А.А,+А,+А

или -А

-(,,A,)a +(A A +Aja +(,+

M.+Aja

45

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

В/А

312364584

В„А„+В„А,+В,А,+В,А,,+В, А, ;Л

В„А„+В„А„А,+В, А,+В, А,+В, А,+ В, , А, А,+В, А„ ,А,+В А L В/А ., , А„А,+В, А,,,

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

, А„+В, А,+В, ,А,+В,А,+В„А„А I В/А

,,,А„+В,,А, /

В„А„+В,А,+В,А,+В, , 1 , ВоА,+В,,А,,В/А

В,А,+В,,А,-«-В А„-нВ А +В А,+В,А,1

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

Напримерм для и 110, имеем l, , и А,. Подставляя значения этих ко- эффициентов в аналитические выражения для вычисления В/А, получают . .При (a)a-Va а а а а , так как инверсным элементом для элемента а является эле6

мент а .

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

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

45

50

При в устройстве содержатся шесть групп сумматоров по модулю два Случай вычисления выражения В/А является тривиальным, так как т.е. равно единичному элементу. Выражение АВ+С вычисляется при помощи схемы, состоящей из первой и второй групп сумматоров по модулю два подключенных через коммутационное поле 25 к выходам умножителей первой группы. Имея набор аналогичных устройств, можно создавать устройства дпя вычис- совокупности всех выражений В/А , где 1 1-6, и выражение АВ+С в данном поле.

д

0

5

0

.Формула изобретения

Устройство для выполнения операций возведения в степень, деления и умножения двух элементов в поле Га- луа GF (2), содержащее первую матрицу размером умножителей, две группы из п сумматоров по модулю два, коммутирующее поле задания вычисляемых функций, причем выходы умножителей первой группы через коммутирую щее поле задания вычисленных функций подключены к входам сумматоров по модулю два первой группы, выход i-ro сумматора по модулю два первой группы подключен к первому входу i-ro сумматора по модулю два (,2,.. ...,п) второй группы, второй вход которого подключен к 1-му входу слагаемого в поле Галуа GF (2) устройства, k-e входы делимого (,2,... „.,,m) и j-e входы делителя (,2,.,. ...m) подключены соответственно к первому и второму входам умножителя k-й строки j-ro столбца первой матрицы умножителей, отличающее- с я тем, что, с целью расширения функциональных возможностей за счет выполнения операций возведения в степень и- деления двух элементов в поле Галуа GF (2), в него введены вторая матрица размером mum умножителей, с третьей по ()-ю группы сумматоров по модулю два, m мультиплексоров, первые и вторые входы умножителей k-й строки j-ro столбца второй матрицы умножителей подключены соответственно k-M входам делимого и J-м входам делителя устройства, а их третьи входы - к ( +1 )-м входам (.,2,... ..,5m-I).делителя, третьи входы умножителей т-го столбца второй матрицы подключены к первому входу делителя устройства, выходы умножителей первой и второй матрицы через коммутирующее поле задания вычисляемых функций подключены к входам сумматоров по модулю два с третьей по (2 +1 ) группу, выходы J-X (,2,,..,т)

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

к информационным входам i-x мультиплексоров., управляющие входы которых являются входами кода операции Со f Cf

.jbT Cz

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

Составитель В Смирнов Техред М.Ходанич Корректор В. Бутяга

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4