Устройство для реализации переключательных функций в поле галуа gf /2 /.

 

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

СО1ОЗ СОВЕТСНИХ

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

РЕСПУБЛИН

А1

„„Я0„„1234861 (511 4 С 06 Г 7/00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

/ ч„»

ОПИСАНИЕ ИЗОБРЕТЕНИЙ, =»»„

Н A ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3739353/24-24 (22) 08.05.84 (46) 30.05.86. Бюл. Р 20 (71) Объединенный институт ядерных исследований (72) Н.М. Никитюк (53) 681.32(088.8) (56) Nuzio J.С. Particular Universal

function generation Electronics

Letter, 1975, v. 11, Р 18, р. 421.

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

У 883894, кл. G 06 F 7/00. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ПЕРЕКЛ10ЧАТЕЛЬНИХ ФУНКЦИЙ В ПОЛЕ ГАЛУА

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

Галуа GF (2 ), регистры и коммутатор

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

1234861

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

GF (2 ) при синтезе дискретных устройств.

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

На фиг. 1 приведена структурная блок-схема предлагаемого устройства для случая m=3, т.е. когда Х=

=f(X, Х„, Хг); на фиг. 2 — структур ная схема ячейки устройства, с помощью которой можно реализовать все булевы функции двух TIE ðåìåííûõ, т.е. вычисляется полином А, Х+А, Х +

2Л устройство содержит информационные входы 1 переменных, коммутатор

2, настроечные входы 3, управляющие входы 4, регистры 5-7 первой группы, регистр 8 второй группы, регистры

9-14 первой группы, регистр 15 второй группы, блоки 16-!8 умножения в поле Галуа, блоки 19 и 20-24 для одновременного возведения в степень и умнох<ения двух элементов в поле

Галуа, сумматоры 25 и 26, выходную магистраль 27. Ячейка состоит из эле ментов И ?8-36, двухразрядных регистров 37-39, сумматоров 40-45 по модулю два, выходов 46 и 47 ячейки, входа 48 установки регистров в состояние "0 . С помощью этой ячейки

/. 2« реализуютcë элементы поля GF (2 ) а =10=1; à =01 a =11.," 0=00.

Элементы этого лоля могут быть получены с помощью неприводимого г t многочлена Х +Х+1, полагая что а оявляетсл его корнем. Тогда а =-а +a причем ао =10=-1 — единичный элемент .

Два различных элемента А и Б в поле, 2

GF (2 ) представимы как о I О а A,+а А и а В,+a В,, где коэффициенты А„, А,, В, В„ могут принимать значения 0 или 1. а Aî,+a A„)(a ва+а В ).

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

Ао Во+A< В (a 7

А„В1+А, В +А„В, .а 7, Выражения для возведения элемента А в квадрат:

A +А(:а а 7;

А! аа 7, Одновременное возведение в квадпат и умножение двух элементов:

ВА2=(а В,+а В, ) (А„а +А,a );

А В +А, В„+А,В1 i ao7„

Рассмотрим пример работы ячейки.

5 Пусть . =а =01; А21 =а =10; Агг = о

=а =ll А . =а =10. Коэффициенты настройки запоминаются в регистрах

37-39. С помощью элементов И 32-36 и сумма."оров 42 и 43 по модулю два выполняются параллельное умножение коэффициента Аг =а на переменную г

X=a н результате этого на выходах

/ сумматоров 42 и 43 получается произведение

15 а а =а =а =10

С помощью логических элементов

И 28-31 и сумматоров 40 и 41 выполня. ется одновременное умножение коэффициента А21 и возведение в квадрат переменной Х в соответствии с

А, Х =а а =а г о г г

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

А 2 Х .) А Х „ А1,1 Х; А Х; А3ь Х .

Операции выполняются над элементами поля А и Х, которые образованы с помощью палинома Х +X+!. Тогда элеЗ<1 кент А=A а +А,а +Ага, а элемент о (, г

=0!0, а =001; а =а, +1=110; а =011; а =1!1; а =!01 и а =а

Г

0 "о о о 1 АаХ2 ОХ1 г Хо о

+A Х, о" г

Г

Г

АХ,=- ОХо АОХ +АоХ Хг+А„Хг+АХ Х+

ЛХ 1 Х1 Хг X 2+A ХаХг А1 1

ЛХ -А Х +А Х +А, Х, Х, +А, ХгХ, +

+АоХ<7Хг+А2Х„Хг

12348 6

AXî =АоXo+AoX1 Х 2+АоХ Х4+АгХоХ1+

+А Х

АХ, =А Хо+А г Х, Хг +А Х „Х, +Аг Х Х, +

+Aî X2+A1 Хо Хг+"г Хо Хг

АХ

2 -1

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

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

f(Xo > X „Хг ) =Х, Х,Х, Х,Х, Хг

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

2 -1 степени. При m=2 и m=3 функции двух и трех переменных можно пред- 20 ставить в виде

Г1 (Х) =À21 Х+Агг Х +Агэ

+Аэб X +А,, где Аг,, Агг, Агэ в выражении для f (х) — элементы по- 25 ля Галуа СГ (2 ), причем Х=(Х, Х,j в выражении для f2(x) А7,, А, А7, А74, Аээ, А э6, Аэг элементы поля

Галуа Оу (2 «, примам Х=«Х, Х,, X«) где Х„, Х,, Хг — булевы геременные.

Коэффициенты А,„„ вычисляются из выражения

Таблица 2

Выход

Входные переменные

Х XXX

000 = О

000 =0

О = 000

Х„Х Х а — 100

Х,Х,Х

Х Х„Х

Х Х,Х, ХОХ«Х2

000 = О а = 010

000 = О а = 001

000 = 0 а = 110

000 = 0

a=011

Х Х1Хг о 1 2 м

100 = à =1 а = ill о 1 2

Х Х,Х

000=0 а = 101

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

Таким образом, ячейки устройства параллельно реализуют булеву функцию

1(Х)=Хд+Х,Х,+Х Х, при заданных коэффициентах настройки. Для вычисления коэффициентов настройки реализующей функции трех переменных, т.е. переключательной функции Г(Х)=Аэ1 Х+

+Аэг Х +А77Х +А74Х +А Х +Аэ6Х +Аз используется табл. 2.

35 где G(r) — значения функции на выходе.

Для вычисления коэффициентов

Аг, А ги Агэ используется табл. 1.

Таблица 40

Входные переменные

Х о 1

Выход

0(3) О = 00 = Х Х, 00=0 о а =

Ю=ХОХ, 1О = a

01=ХХ, 10=a=1

2а

00 = 0

XoХ1

Значение Г(X) =Xa+X а при Х=а и

Х=а равно единичному элементу. Суммирование членов в формуле выполняЗдесь а -а — элементы поля Галуа

О 6 э

СР {2 ), и каждому элементу поля поставлена в соответствие булева функция трех переменных Х Х Хг.

В соответствии с табл. 2 коэффиии.

2 .. 6 енты настройки равны а, а, а, .а

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

f(X)=a Х+а X +а Х +а Х +а Х 1-а Х +

2 4 г 6 .3 t 4 7 т 5 6 э

+ао. При подстановке à =111=X X,Х получич f(x)=100=à . При остальных а это равенство равно нулю.

При вычисленных коэффициентах настройки устройство реализует все булевы функции трех переменнъrx, общее число которых равно 2 =25б. Для по«7 строения модуля на большое число переменных в схему необходимо параллельно подключать соответствующее число логических ячеек в поле Галуа, Так, например, при ш=4 необходимо

4 добавить ячейку поля Галуа GF {2 ) .

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

1234861

Lier>A

Фию. 1

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

Тираж b71 Подписное

Произв. -полигр. пр-тие, r. Ужгород, ул. Проектная, 4 благодаря блокам для одновременного возведения в степень и умножения двух элементов в поле Галуа СР (2 ), которые позволяют выполнять эти операции за такое же время, как и в схемах для умножения двух элементов.

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

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

tq возведения в степень, начиная со второй до (2 -2)-й степени, и умножения двух элементов в поле Галуа порядка m первые входы которых сое5 динены с информационными входами netn ременных устройства, по 2 -2 регистров первой группы и одному регистру второй группы, коммутатор, первые входы которого являются настроечными

1О входами устройства, вторые — управляющими, при этом входы регистров первой и второй групп подключены к выходам коммутатора, выход первого регистра первой группы каждой ячей15 ки подключен к второму входу блока умножения в поле Галуа порядка m данной ячейки, выход i-го регистра первой группы .(1=1, 2, 3,.... 2 -2) в каждой 1-й ячейке (1=2,..., m)

20 подключен к второму входу блока одновременного возведения в степень и умножения двух элементов в поле

Галуа порядка m i-й степени $-й ячейки, при этом выходы блоков од25 новременного возведения в степень и умножения двух элементов в ноле

Галуа порядка m,1-й ячейки, а также .выходы регистров второй группы ,1-й ячейки подключены к входам сум30 матора 1-й ячейки.