Устройство для реализации переключательных функций в поле галуа GF /2 /. Советский патент 1986 года по МПК G06F7/00 

вычисляется полином Ajj Х+А

10

П1

20

«123486

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

Цель изобретения - увеличение, быстродействия.

На фиг. 1 приведена структурная блок-схема предлагаемого устройства для случая , т.е. когда Х Г(Хд, X,, Х); на фиг. 2 - структурная схема ячейки устройства, с помощью которой можно реализовать все булевы функции двух пефеменных, т.е.

А2Э

Устройство содержит информационные входы 1 переменных, коммутатор 2, настроечные входы 3, управляющие входы 4, регистры 5-7 первой группы,

регистр 8 второй группы, регистры первой группы, регистр 15 второй группы, блоки 16-18 умножения в поле Галуа, блоки 19 и 20-24 для

одновременного возведения в степень и умнох ения двух элементов в поле Галуа, сумматоры 25 и 26, выходную магистраль 27. Ячейка состоит из элементов И 28-36, двухразрядных регистров 37-39, сумматоров 40-45 но модулю два, выходов 46 и 47 ячейки, входа 48 установки регистров в состояние О. С помощью этой ячейки реализуются элементы поля GF (2 ) ; а 01 ; .

Элементы этого поля могут быть

получены с помощью ненриводимого

1

многочлена X -fX-i-I , полагая что а

является его корнем. Тогдаa a -i-a ,

причем - единичныйэлемент.

Два различных элемента А иВ в поле GF (2 ) представимы как

a A -i-a А, и В, ,.

25

30

35

40

где коэффициенты Ад, А,, В, В могут принимать значения О или 1.

АХВ(аЧо+а А, В, ) .

Аналитические выражения для пара л ельного умножения двух элементов в поле Галуа:

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

Выражения для возведения элемента А в квадрат:

АО+А,

,

А,

а .

Ч - Одновременное возведение в квадиат и умножение двух элементов:

1

0

Z

-а -

ВА (а°Во+а В; )(А„а%А,а );

АоВо+А,В„+А,В(

А,В„+АоВ, а . Рассмотрим пример работы ячейки. Пусть ,А А,,

10.

5

Коэффициенты настройки запоминаются в регистрах 37-39. С помощью элементов И 32-36 и су маторов 42 и 43 по модулю два выполняются параллельное умножение коэффициента г переменную 5 в результате этого на выходах сумматоров 42 и 43 получается произведение

10

С помощью логических элементов И 28-31 и сумматоров 40 и 41 выполняется одновременное умножение коэффициента А2, и возведение в квадрат переменной X в соответствии с л 2 г

rt. О4Л Э. 3. а.

Далее на сумматорах 44 и 45 по модулю два выполняется сложение. Ниже приводятся аналитические выражения

для вычисления членов 1 „ . . ,.} ,

А,.Х

А,

.Х

,,Х А,,Х.

П -- 34 35

Операции вынолняются над элементами поля А и X, которые образованы с помощью поли1 ома , Тогда эле- 0 мент A A a +А, , а элемент . а где а ; а а +-1 1 10;

f f л

5

Е

а

АХ

1 1 ; а 10 и а а

,Х,+А,Х2 АХ,, Х -нА„Х,+А,Х,+А,Х,4-А, Хг AX.,,+А.,Х,+А„Х,,

АХ,А„Х„+А Х, +А„Х, Х,

0

АХ

-fAjX X.+A,

+А,Х„Х,+А,Х

5

АХ

0

S

АХ {

5

АХ, -А,Х„+А, Х,Х +А, X, , -ь

-fA,,,X,,H-A,X,X + 3+А, ХоХ,+А,Хг

АХ,, А, Х, +А,,Х, , Х +А, Х„X, +

-f А, Х„ X, +А, X, +А Х X, -f А, Х„ X, + ,Х,

,Х„.4-А.,Х,-А,, ,.-А„Х,ч-А„Х2+А,,Х, ,Х М, X ,+А, , +А/.,

-А,Х„+А,Х, +А„Х,X, +А,Х

+А,Х,-А,Х,+А,Х„Х,+А,,Х,+ , А,Х,Х, . АХ, А,, X, Хг+А, X,;-fA, , X, +

х -нА X 2.x, -f А, Хр X, +АО х, -«, АоХ„Х,+А,Х„Х , н-А,Х,А, Х,Х, +A,XjX;+ -fA, Х„н-АоХ„ X, ,, + - А„ХоХ,4-А,,

АХ„ А„Х„+АоХ,Х2-1-А„Х,Х,,+

+A,X2+A,,-bA,, 6 А,Х, АХ -( АХ, А,Х„+А2Х, Х,+А,ХоХ, , +

+АЛ+А,,|А,Х„Хг ,Х„+А2Х,Хг+А,ХД,+А,Х,+ +А„Х,А„Х„Х,+А,Х„Х

Устройство работает следующим образом.

Допустим, что необходимо настроить модуль на выполнение следующей булевой функции трех переменных:

f(Xo, X,, Х :Х„УХ„ХЛХ„Х,Х,

Для вычисления коэффициентов настройки в поле Галуа GF (2) переключательную функцию m переменных можно представить в виде полинома степени. При и функции двух и трех переменных можно представить в виде

f,(X)A2, Х+А„Х +А

f,(X)-A, +A,gX +А,7 j Де Aj, , Агг , А, и X в выражении для f, (х) - элементы поля Галуа GF (2), причем , X, в выражении для f,,(x) А,,, А,2 АЗЗ Азб элементы поля Галуа GF (2), причем , X,, X,, где Хд, X,, Хг - булевы переменные. Коэффициенты А, вычисляются из выражения

(

A,z: ), 1(

выгде G(J) - значения функции на

ходе,

Дпя вычисления коэффициентов А, использует :я табл. 1.

Таблица

f У о

Значение f(X)Xa+X a при и равно единичному элементу. Суммирование членов в формуле выполня348614

ется с помощью сумматора 25, выходы которого подключены к шинам выходной магистрали 27.

Таким образом, ячейки устройства 5 параллельно реализуют булеву функцию f(x)Xjj+XgX,+XpX, при заданных коэффициентах настройки. Для вычисления коэффициентов настройки реализующей функции трех переменных, т.е. пере- 10 ключательной функции f(Х)А,, Х+ +А,.,,Х%А„Х +А,, используется табл. 2.

Т а б л и ц а . 2

35

Здесь - элемелты поля Галуа GF (2 ), и каждому элементу, поля поставлена в соответстш е булева функция трех переменных X

Y О)

X.

В соответствии с табл. 2 коэффициг 6 5 енты настройки равны а , а , а .а ,

а, а. Выражение для f(x) принимает

вид

f(X)-+а.

а-Х+а х +а iQ. При подстановке а ,Х2 .получим f(х) . При остальных а это равенство равно нулю.

При вычисленных коэффициентах настройки устройство реализует все булевы функции трех переменных, общее число которых раЬно 2 256. Дпя построения модуля на большое число переменных в схему необходимо параллельно подключать соответствующее число логических ячеек в поле Галуа. Так, например., при необходимо добавить ячейку поля Галуа GF (2 ).

Сокращение времени выполнения операций в устройстве достигается

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

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

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

второй до ()-и степени, и умножения двух элементов в поле Галуа порядка т, первые входы которых соединены с информационными входами переменных устройства, по 2 -2 регистров первой группы и одному регистру второй группы, коммутатор, первые входы которого являются настроечными входами устройства, вторые - управляющими, при этом входы регистров первой и второй групп подключены к выходам коммутатора, выход первого регистра первой группы каждой ячейки подключен к второму входу блока умножения в поле Галуа порядка m данной ячейки, выход i-ro регистра первой группы ,( S 2 , 3,.... 2-2) в каждой J-й ячейке (,..., т) Подключен к второму входу блока одновременного возведения в степень и умножения двух элементов в поле Галуа порядка m i-й степени -й ячейки, при этом выходы блоков одновременного возведения в степень и умножения двух элементов в поле Галуа порядка m j-й ячейки, а также увыходы регистров второй группы j-й ячейки подключены к входам сумматора j-й ячейки.

ei(/i /

IflUt. I

Изобретение относится к области вычислительной техники и может быть использовано для реализации переключательных функций в поле Галуа GF

ННИИПИ Заказ 2987/52

Проиэп.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4

Тираж 671

Подписное