Устройство для полиномиального разложения симметрических булевых функций
Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с аппаратурной реализацией языка высокого уровня. Цель изобретения - упрощение конструкции устройства для полиномиального разложения симметрических булевых функций. Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых функций N переменных содержит элемент НЕ, N+1 элементов 2-2И-2ИЛИ, N групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, N +1 информационных входов, управляющий вход и N+1 выходов. На информационные входы устройства подается (N+1)-разрядный булевой вектор, однозначно задающий разлагаемую симметрическую булевую функцию, на управляющий вход - сигнал управления, определяющий вид полиномиального разложения (положительно поляризованный или отрицательно поляризованный полином). На выходах устройства реализуются коэффициенты требуемого полинома заданной симметрической булевой функции. 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
nwSU no (1)5 G 06 F 7/00, 5/00 с
ЕНИЯ
ПРИ ГКНТ СССР
СПИСАНИЕ ИЗОБРЕТ
Н A BTOPCHOMV СВМДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ (21) 4467722/24-24 (22) 20.06.88 (46) 23.04.90. Бюл. 11 15 (72) Л.Б. Авгуль и В,П. Супрун (53) 681.3(088.8) (56) Авторское свидетельство СССР
М 1124281, кл. С 06 F 5/00, 1983.
Авторское свидетельство СССР
1444743, кл. G 06 F 5/00, G 06 F 7/00, 198!. (54) УСТРОЙСТВО ДЛЯ ПОЛИНОМИАЛЬНОГО
РАЗЛОЖЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ
ФУНКЦИЙ (57) Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с аппаратурной реализацией языка высокого уровня. Цель изобретения - упрощение конструкции устройства для
Изобретение относится к области вычислительной техники и предназначено для использования в ЭВМ и спецпроцессорах с аппаратурной реализацией языка высокого уровня.
Цель изобретения - упрощение конструкции устройства для полиномиального разложения симметрических булевых функций.
На чертеже представлена схема устройства для полиномиального разложе- ния симметрических булевых функций
fl pN и=
Устройство содержит n+1=6 элементов 2-2И-2ИЛИ 1,,..., 16, элемент НЕ 2, 2 полиномиального разложения симметрических булевых функций. Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых функций и переменных содержит элемент НЕ, и+1 элементов 2-2И-2ИЛИ, и групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и+1 информационных входов, управляющий вход и и+1 выходов. На информационные входы устройства подается (и+I)-разрядный булевой вектор, однозначно задающий разлагаемую симметрическую булевую функцию, на управляющий вход - сигнал управления, определяющий вид полиномиального разложения (положительно поляризованный или отрицательно поляризованный полином), на выходах устройства реализуются коэффициенты требуемого полинома.заданной симметрической булевой функции. 1 ил.
Ь » — 1 элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА 3 первой группы, Ь = 1 элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4 второй группы, b = 2 элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА 5 и 6 третьей гоуппы, Ь вЂ” — 1 элемент СЛОЖЕНИЕ "0 МОДУЛЮ ДВА 7 четвертой группы, Ь = 2 элемента СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА 8 и 9 пятой группы, и+1=6 информационных входов 10»,..., 106, управляющий вход 11, и+1=6 выходов l 2» ° ° е, 126 .
Симметрическая булевая функция (с.б.ф.) n переменных F = F (х,, х,...,х„) может быть представлена двоичным вектором « (F) =(«,, «,, ...,« ) . чем полином P(F) поляризован по переменным х<,х,...,х положительно, а полином Q(F) - -отрицательно. В общем случае полиномы Р(Р), Q(F) для с.б.ф, F можно записать следующим образом: () (,0 <(X,C) X,C) ° Ох ) (х<х,®..Вх,х ®х Х,О+...9Х„<х„)О+ ° 9 („х<х,...,х„, Q(F) =р,О+р,(х ®хфе ° e®x<,)+p>(x х Ю...QX x„f)
®XgX>Qi ®Х < < Х< )® ° e 9 Р<< Х< X «» ° ° «Х<<
w = (1 0 О 0 1 1) v (1,1,0 О О 1) — g(F), = (1«1,1,1,0,1); р (F) .= (1,0,1,0,1,1) °
Следовательно, полиномы P(F) и
Q (F) с, б.ф. F имеют следующий вид:
P (F) =19х, ЯХЯХ,9Х4®Х ЭХ< Х ЩХ< х 9Х< X4®K Х 9Х,Х ®
9Х<Х4®х х 9х x4®x>х ®Х4Х ЮХ< х х ®х< х х4®
9Х< Xg Xg®x< Х Х4.®х < х, х ®х, X4xg9xg Х««Х4®xó xó х ®
ЯХЗ Х4 Х5®Х< Х Х Х4Х5 °
Q(F ) =1®Х < ХЯХ< Х < Х4®Х < ХЯХ,Х,ЮХ Х;„ЮХ Х,Ж
ЭХ ХдЮХ X +4Хg®x< Х«хgх4Х ЮХ< ХgХgХ 4Ю
®Х < Х«Х ХЯХ< Х Х4Х ЗХ < Х Х4 Х5®Х Х Х4Х
Устройство. работает следующим образом.
На r-й (r=0,1,...,ï) информационный вход устройства поступает r-й з
155933 где и, - значение F на (любом) наборе и двоичных переменных с i единицами (i=.0,1,...,п).
Пусть P(F), Q(F) — монотонно поляризованные полиномы с.б.ф. F. Приl где (,, p, <= I 0,1) и i=0,1,...,n.
Поскольку полиномы P(F), Q(F) однозначно определяются (и+1) -разрядными булевыми векторами g (F)=((o, g,,..., и) и (U (F) =((tlо, p.« ° . °,p„) соответственно, то задача полиномиального раз- gp ложения с.б.ф. F сводится к преобразованию вектора « (F) в булевые векторы (F),и P (F)
Устройство реализует следующий алгоритм полиномиального разложения сим-25 метрических булевых функций.
Исходным для нахождения вектора
f(F)=(<О, << «..., 3«) является вектор (1 «W.« .° ° ° «.1 < о « <
Далее формируется последовательйость векторов W<, Wz,...,W» компоненты которых определяются следующим образом.
Пусть W „ - r - компонент вектора
W (r=0,1,...,n; 1=1,2,...,m; m =
=11 2(п+1)(); 1r = (jr, „,..., р ) и Iy = (j j « ° ..«j ) — двоичные представлейия чйсел r u g соответственно, причем g6 (0«1,...,п-1) .
Тогда е e-<
W< =,И,., если )„ = 0;
<«-/ е-.Ф
И„=Яр ЖИ, если 1„ =. 1 и (1)
I II
Компоненты вектора 3 (F) совпадают с соответствующими компонентами вектора W
Исходным для нахождения вектора
P(F) =(<,, 5»...,P«) является вектор
v<«(« О «v< «. ° ° «v«)=(n ««-< « «< о ) °
Далее формируется последовательность векторов ч„,ч,...,v компоненты которых находятся аналогично нахождению компонент векторов WI« по формулам (1), где 1 = 1,2,...,m. Компоненты вектора (U(F) совпадают с соответствующими компонентами вектора v 1 р и м е р. Применяя рассмотренные алгоритмы, построим полиномы P(F) и Q(F) для симметрической булевой функции Е(х<«х««х «х4«х )=х<х «х х4х ч
U Х< Х Х«Х4 Ч Х < Х«Х<Х Y Х< Х Х4Х М
Очевидно, что «(F) = (1,0,,0,0,1,1), Тогда
15593 компонент вектора (F) разлагаемой с.б.ф. F = F(x,,õ,...,х„), на управляющий вход — сигнал управления
Т (U Е (О, 1 ) . Если U = 1, íà r-м вы5 ходе устройства формируется сигнал, соответствующий r-му компоненту /,, вектора II (F); если U = О, на r-м выходе реализуется r-й компонент |1|„ вектора (О (F) .
Так, для рассматриваемого примера (чертеж) на входы 10Ä,...,106 поступают компоненты п,,..., 5 вектора (1 ) соответственно, на управляющий вход 11 - сигнал управления Ц (UG(9,1)), При U = 1 на выходах 12|,...,12
Г формируются сигналы ... °, соответственно; при U = О - сигналы
P"""
° ° °, (И соответственно, Дополнительным эффектом является . 20 увеличение, быст родей ст вия уст ройст ва для полиномиального разложения симметрических булевых функций. формула изобретения 25
Устройство для полиномиального разложения симметрических булевых функций, содержащее n (n - количество аргументов разлагаемых булевых функций) групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, о т л и ч а ю щ е е с я тем, что, с целью упрощения, оно содержит рлемент НЕ и и+1 элементов 2-2И-2ИЛИ, первый информационный вход s-ro из ! ,которых (s=1,2,...,n+1) соединен с
s-м информационным входом устройства и вторым информационным входом (и-s+
+2)-ro элемента 2-2И-2ИЛИ, первый управляющий вход которого соединен с уп 40 равляющим входом устройства и входом элемента НЕ, выход которого соединен
38
6 с вторым управляющим входом s-ro элемента 2-2И-2ИЛИ, выход (i+1) -ro эле" мента 2-2И-2ИЛИ (i=1,2,...,n) соединен с первым входом первого элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА i-й группы, выход t-ro элемента СЛОЖЕНИЕ ПО МОДУДО ДВА h"é группы (h=l,2,...,n; h =
= 2; k = 0,1,..., m-l, m=glog (n+1) j) соединен с первым входом (t+1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА h-й группы (t=1,2,...,Ú„-1; b> = ;!» j е1|, =() |1,, 3 J,,...,)ь ) — двоичное представление числа Р, jh< s 10,1 ;
1 = 1,2,...,т, второй вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА i-й группы соединен с выходом g-го элемента 2-2И-2ИЛИ (I =(j j
1< в ° ° ° э (,я
); 1, = О, ы.=1,2,...,е6-1;
1 I 9 ,! 1 у ) () у ° ° ° у 1 фу ° ° ° у) ) у п и Х вЂ” двоичные. предста вления ф чисел i u g соответственно), вто- рой вход ч-го элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА h-й группы (v=2 3,...,Ú|,) соединен с выходом (v-1)-го элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы
1 Э (, =(.! |, ф ° ° ° э..1| ъ ° ° ° эЗ ) . 3
Ь "е
tlat . ьр = p = .Ъ" j р
° 3 le = h (з„=0) =i3h, О,..., j h ); Ih и Х двоичные представления чисел h и р соответственно), первый выход устройства соеди нен с выходом первого элемента 2-2И-2ИЛИ, (i+1)-й выход устройства соединен с выходом b;-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА i-й группы (Е; (j"
1;Ъ
1ц е= двоичное представление числа i).
1559338
Составитель В. Сорокин
Техред M.Õoäàíè÷ Корректор Л. Патай
Редактор Л. Гратилло
Заказ 838 Тираж 563 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, M-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101
