Устройство для полиномиального разложения симметрических булевых функций Советский патент 1990 года по МПК G06F7/00 G06F5/00 

Изобретение относится к области вычислительной техники и предназначено для использования в ЭВМ и спецпроцессорах с аппаратурной реализацией языка высокого уровня.

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

На чертеже представлена схема устройства для полиномиального разложения симметрических булевых функций при п 5.

Устройство содержит элементов 2-2И-2ИЛИ 10...,Uf элемент НЕ 2

Ь 1 элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 3 первой группы, Ь2 1 элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4 второй группы, Ц 2 элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5 и 6 третьей гоуппы, Ъл 1 элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 7 четвертой группы, bg. 2 элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА3 8 и 9 пятой группы, информационных входов 10,..., 10

б

управляющий вход 11, выходов 12 ,..., 126 .

Симметрическая булевая функция (с.б.ф.) п переменных F F (х4, х2, ...,хп) может быть представлена двоичным вектором /n(F) ( n л

5л ел

ф

СЈ СО 00

315593384

значение F на (любом) на- чем полином P(F) поляризован по переменным х,хе, . ..,хи положительно, а полином Q(F) - -отрицательно. В общем случае полиномы P(F), Q(F) для

где х

боре п двоичных переменных с i

ницами (,1,..,,п).

Пусть P(F), Q(F) - монотонно поляризованные полиномы с.б.ф. F. Прис.б.ф. F можно записать следующим об разом:

с.б.ф. F можно записать следующим образом:

Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с аппаратурной реализацией языка высокого уровня. Цель изобретения - упрощение конструкции устройства для полиномиального разложения симметрических булевых функций. Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых функций N переменных содержит элемент НЕ, N+1 элементов 2-2И-2ИЛИ, N групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, N +1 информационных входов, управляющий вход и N+1 выходов. На информационные входы устройства подается (N+1)-разрядный булевой вектор, однозначно задающий разлагаемую симметрическую булевую функцию, на управляющий вход - сигнал управления, определяющий вид полиномиального разложения (положительно поляризованный или отрицательно поляризованный полином). На выходах устройства реализуются коэффициенты требуемого полинома заданной симметрической булевой функции. 1 ил.

P(F) yo©y,(x1© х2©.. .@xn)+(x,x2©i. х,х„( Q(F)(,(x,©x,,©.. .®xh)+(U2(x, Хг®.. .©х,

®xtx3©.. .@xh, xn)

Ф|и„х,хг,...,х„,

где ;, |Ui6fO,l и ,1n.

Поскольку полиномы P(F), Q(F) одно значно определяются (n+1)-разрядными булевыми векторами (F) (J0, у,,..., УП) и (К (F) (p0,,,...,/UM) соответственно, то задача полиномиального раз- ложения с.б.ф. F сводится к преобразованию вектора п (F) в булевые векторы |f (F) .и |U (F).

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

Исходным для нахождения вектора Нр):(, W является вектор Wfl (W0°,W,°,... Х) (1Го,7( ,... ,7n) . Далее формируется последовательность векторов W, , WЈ,...,Wm, компоненты которых определяются следующим образом.

Пусть Wn - г - компонент вектора Wj(,1,...,п; ,2,...,т; т

loga(n+1)); Ir (jr ,j,

,Jrm)

- t- ; . I.TZ. ГИ

И 4«j, ,Jo2 ,-..,Jflm) -двоичные представления чисел г и g соответственно, причем g6 , 1 ,... ,n-1 j . Тогда

W.

(1,0,0,0,1,1); w, (1,0,0,0,0,1);

w

vo (1,1,0,0,0,1); v, (1,1,0,0,1,0);

,4 (1,0,1,0,0,1); vi (1,1,1,1,1,0); w, y(F (1,1,1,1,0,1); v, - |u(F) (1,0,1,0,1,1). Следовательно, полиномы P(F) и (F) .ф. F имеют следующий вид:

P(F)1@x,@xl@X}@x4@x5®x х х4-®х(х ®хгхэ© ®XiX4©xux5@x x4®x,xs®x x5©x xax3®x,xax4.®

@х1хгх5@х,х,х @х4х3х5®х4х4х5@хгх,х4®хгх,х5©

.Х5@Х, XUX,X4XS.

Q(F). @х, XjQx, , х4®Г, x 5ex2x3,1x4.®x2Xs® , X2x3x4xsffix, хгхэх 4©

@Х , Хй X, Х5ФХ, , X, Х4 Х5®ХгХ, Х4 Х.

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

Чхз

®xh,,xh )©...© jfnx4xz,...,xh;

5

Q

5

Q

W/ W

t-1

г , если jrg 0; t..e-

Wr -Wp @W| , если jhg

1 и (1) Ia Ih(Jn.).

r jrj:-u

Компоненты вектора У (F) совпадают с соответствующими компонентами вектора Wm.

Исходным для нахождения вектора |U(F) ((U0, /U,,. .. ,/Чи) является вектор

V fv°.vOлгП 7. 7

V0

(v0°,vf,...,v°)-(

П г tvi

).

5

Далее формируется последовательность векторов v4,VЈ,...,vn, компоненты которых находятся аналогично нахождению компонент векторов Wg по формулам (1), где 1 1,2,...,т. Компоненты вектора (U(F) совпадают с соответствующими компонентами вектора vm.

Л р и м е р. Применяя рассмотренные алгоритмы, построим полиномы P(F) и Q(F) для симметрической булевой

ФУНКЦИИ F(x, ,Ха,Х3,Х4.,Х5)Х(ГгХ3Х4Х5У

Vx,xax,,x4v x, х,хгх4х V х, XjX4x5 v хгх,хфх5.

Очевидно, что Ъ (F) (1 ,0,,0, 0,1,1)

Jor-да

. На r-й (,1,...,п) информационный вход устройства поступает г-й

компонент чf. вектора и (F) разлагаемой с.б.ф. F F(x,,хг, .. . ,хп), на управляющий вход - сигнал управления U (,1). Если U 1, на r-м выходе устройства формируется сигнал, соответствующий r-му компоненту г вектора J (F); если U 0, на r-м выходе реализуется r-й компонент fti вектора (U (F).

Так, для рассматриваемого примера (чертеж) на входы 104,...,10б поступают компоненты

о

вектора

« (F) соответственно, на управляющий вход 11 - сигнал управления U (UeЈ(J, 1 ) . При U 1 на выходах .t. формируются сигналы у0 ,..., у5 соответственно; при U 0 - сигналы rtj0,...,U5 соответственно,

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

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

Устройство для полиномиального разложения симметрических булевых функций, содержащее п (п - количество аргументов разлагаемых булевых функций) групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, отличающееся тем, что, с целью упрощения, оно содержит элемент НЕ и п+1 элементов 2-2И-2ИЛИ, Первый информационный вход s-ro из которых (,2,... ,п+1) соединен с s-м информационным входом устройства и вторым информационным входом (n-s+ +2)-го элемента 2-2И-2ИЛИ, первый управляющий вход которого соединен с уп равляющим входом устройства и входом элемента НЕ, выход которого соединен

с вторым управляющим входом s-ro элемента 2-2И-2ИЛИ, выход (i+1)-ro эле мента 2-2И-2ИЛИ (,2п) соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА i-й группы, выход L-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА h-й группы (,2,...,n; h 2k; k 0,1,о.., m-1, (n+1)) соединен с первым входом (t+1)-ro элемента ШЖЕНИЕ ПО МОДУЛЮ ДВА h-й

группы (,2,...,b|i-1; bh 21 з

Zh (JH, , J h3

0

h VJn, , J Ьг ньиичние

представление числа h, , 1 1,2,...,m, второй вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1-й группы соединен с выходом g-ro элемента 2-2И-2ИЛИ (I; (j, ,ЦЛ,

Jiw .0 w -1.2, ...,o6-1; ,l-1 (. )

OL fl)u,tlJ...,o,...,jtJ;

JU i;

(. T

J 1 4Jl(i ,nl

I - двоичные-представления i и g соответственно), вто- v-го элемента СЛОЖЕНИЕ ПО

I;. и

-

чисел 5 рой вход

МОДУЛЮ ДВА h-й группы (,3,...,bh) соединен с выходом (v-l)-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы /

. «-

( .Jhb - JhJ; 2 jh -.

- 1 г

v J jp(

P zn (Jhri e°Xjh

° Jhm) h и 1р Двоичные представления чисел h и р со ответствен- но), первый выход устройства соединен с выходом первого элемента 2-2И-2ИЛИ , (1+1)-й выход устройства соедо- выходом Ь-, -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1-й группы (, (j i , ,

.

«m

}

b

представление числа 1).