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

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

Цель изобретения - расширение функциональных возможностей преобразователя формы представления логичест ких функций за счет преобразования совершенных дизъюнктивных нормальных форм (ДНФ) логических функций в монотонно-поляризованные конъюктивно- полиномиальное и дизъюнктивно-полиномиальное разложение.

На чертеже представлена схема преобразователя при (п - количество переменных).

Преобразователь содержит элемент liE 1, шестнадцать элементов И , восемь элементов ИЛИ , элемент РАВНОЗНАЧНОСТЬ 4, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА первого яруса, четыре элемента СЛОЖЕНИЕ НО МОДУЛЮ ДВА 6,-64 второго яруса, четыре элемента СЛОЖЕНИЕ ПО МОДУЯО ДВА 7-1-Уф третьего яруса, восемь ин

10

15

20

25

f(x ,.x,Xз)Ч в®Xз 1®x м ®X2Xз /J® ФX, X j4 5ex XJ f Фх ,X iX 3 if,

где if/etO, 1} и ,...,7.

При и i на выходах 1 ,,., реализуются коэффициенты соответ венно Ve Vy отрицательно пол зованного конъюнктивно-полиномиа го разложения

, ,х,Хз )Ув©ХзУ,® XJЧ4® z з з ®

®X, X XjM jex X V eX XjXjV,,

где 4,,1} и ,...,7.

Нри и, 1 и на выходах 1Ц 11g реализуются коэффициенты соо ственно ы ,..., (.4-, положительно п ризованного дизъюнктивно-полином ного разложения

f(x, ,Xj,X3)4®(x3VUJ,)®(x,VU)2)® @(x5yX3VOJj)®(x, VU4)©(x,VX3VW5)® Ф(у X/CJj)®(x, 340)7),

где ,l} и ,...,7.

При на выходах 11 ,.. реализуются коэффициенты соответ венно ,, .., , отрицательно пол зованного дизъюнктивно- полиномиа го разложения

°Г(х,,хг,хэ) ,®(x3vj.,)e(xiv-j.)e

формагщонных входов oi- 8 преобразова-®(xjvic j V3-j)®(xi v )©(xiVx,j vy )©

теля, два настроечных входа 9 и -. - г г- ..г-. . преобразователя, восемь выходов I,- 11g преобразователя.

®(x,VXiV J j)®(x,VX2.VX }V у,),

где TfjelO, и ,...,7.

В качестве npHNiepa в таблице ставлены значения коэффициентов ,...,о(7 полиномиальных разложе логической функции f(x,-K, для четырех возможных комб ций сигналов и и U на настроеч входах преобразователя.

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

На 1-й информационный вход преобразователя ( ,... ,2 О подается значение jfj преобразуемой логической 40 функции f(x,...,x) на (1-1)-м наборе переменных х,,...,х,, (фактически на информационные входы устройства поступают коэффициенты совершенной ДНФ преобразуемой логической функции) 45 на настроечные входы - сигналы настройки и и и-г, значения которых приА надлежат множеству 0,lJ, На входах устройства реализуются коэффициенты

f(x ,.x,Xз)Ч в®Xз 1®x м ®X2Xз /J®x,в ФX, X j4 5ex XJ f Фх ,X iX 3 if,

где if/etO, 1} и ,...,7.

При и i на выходах 1 ,,.,., 1. реализуются коэффициенты соответственно Ve Vy отрицательно поляризованного конъюнктивно-полиномиапьно- го разложения

, ,х,Хз )Ув©ХзУ,® XJЧ4® z з з ®

®X, X XjM jex X V eX XjXjV,,

где 4,,1} и ,...,7.

Нри и, 1 и на выходах 1Ц,... 11g реализуются коэффициенты соответственно ы ,..., (.4-, положительно поляризованного дизъюнктивно-полиномиального разложения

f(x, ,Xj,X3)4®(x3VUJ,)®(x,VU)2)® @(x5yX3VOJj)®(x, VU4)©(x,VX3VW5)® Ф(у X/CJj)®(x, 340)7),

где ,l} и ,...,7.

При на выходах 11 ,..., Ij реализуются коэффициенты соответственно ,, .., , отрицательно поляризованного дизъюнктивно- полиномиально- го разложения

®(xjvic j V3-j)®(xi v )©(xiVx,j vy )©

f- -. - г г- ..г-. .

®(x,VXiV J j)®(x,VX2.VX }V у,),

где TfjelO, и ,...,7.

В качестве npHNiepa в таблице представлены значения коэффициентов ,...,о(7 полиномиальных разложений логической функции f(x,-K, для четырех возможных комбинаций сигналов и и U на настроечных входах преобразователя.

J

Как следует из таблицы

f(Xi ,Xi,X3)XiX}VX4Xj Xj®X,jXj®XtX3 l®X2Xj®X,®X-,Xj (, )®Х1®(х,УХз) l®Xj®(xJVX j)@(x,V Xj).

Исходным для нахождения коэффициентов ) положительно

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

монотонно-поляризованных полиномиаль-50 поляризованного конъюнктивно-полиноньк разложений.

I

Так, для рассматриваемого преобразователя () при и,0 (вход 9) и (вход 10) на выходах 11,., ., реализуются коэффициенты соответственно 1 ,,,,, (/т положительно поляризо- . ванного конъюктивно-полиномиального разложения:

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

функции , (У , , . . . ,yjn) |У°У2«|.

Далее формируется последовательность векторов W,...,.., компоненты которых вычисляются согласно следующим реккуррентным соотношениям:

%i+il(T,,t® (2M) (

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

функции , (У , , . . . ,yjn) |У°У2«|.

Далее формируется последовательность векторов W,...,.., компоненты которых вычисляются согласно следующим реккуррентным соотношениям:

%i+il(T,,t® (2M) (

«-

где ; , . .. , -1; ,...,m и ,...,n.

Компоненты вектора ),.., ,y совпадают с соответствуюп им коэффициентами положительно поляризованного конъюнктивно-полиномиального разложения, т.е. (,-у,, где ,..., .

Коэффициенты отрицательно поляри- зованного дизъюнктивно-полиномиально- го разложения jg инверсны соответствующим коэф4ж циентам положительно поляризованного конъюнктивно-поли5У

номиального разложения, т.е. f5 Ч где ,...,2 -I.

Исходным для нахождения коэффициентов отрицательно поляризованного конъюнктивно-полиномиального разложения является вектор We(y,n,,, у ).Далее проводятся п иагов преобразований, аналогичные (1) - сформируется последовательность векторов 7,... ,WjI, причем компоненты вектора J, совпадают с соответствующими коэффициентами .полиномиального вектора разложения, т. е . у у , где ,.., .

Коэффициенты положительно поляризованного дизъюнктивно-полиномиального разложения uis инверсны соответствующим коэффициентами отрицательно поляризованного конъюнктивно-полиномиального разложения, т.е. Ы5 ,...,2 -1.

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

144

1379

Формула

изобретения

Преобразователь формы представле- ния логических функций по авт. св. № 1124281, .0 тличающийся тем, что, с целью расширения функциональных возможностей за счет преобразования дизъюнктивной нормальной

10 формы логических функций в монотонно- поляризованные конъюнктивно-полиноми- апьные и дизъюнктивно-полиномиальные разложения, он содержит элемент РАВНОЗНАЧНОСТЬ, 2 элементов И 2 эле15 ментов ИЛИ и элемент НЕ, причем первый настроечный вход преобразователя соединен с входом элемента НЕ, выход которого соединен с первым входом (2f-)-ro элемента И (,...,2),

20 второй вход которого соединен с f-м информационным входом преобразогате- ля и с первым входом ()-ro элемента И (,..., ), второй вход которого соединен с первым настроеч-

25 иым входом преобразователя, а выход соединен с первым входом f-ro элемента ИЛИ, второй вход которого соединен с выходом (2f-l)-ro элемента И, выход (2i-l)-ro элемента ИЛИ соеди30 нен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1-й группы первого яруса, вторые входы элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА каждой группы, кроме последней, первого яруса соединены с

35 выходом соответствующего элемента ИЛИ, выход 2 -го элемента ИЛИ соединен с первым входом элемента РАВНОЗНАЧНОСТЬ, второй вход которого соединен с вторым настроечным входом преобразовате40 ля, а вьпсод соединен с 2 -м выходом устройства.