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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с аппаратурной реализацией языка высокого уровня. Цель изобретения - упрощение конструкции устройства для полиномиального разложения симметрических булевых функций. Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых функций 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