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

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

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

п) с произвольным вектором поляриза Пии (п - количество двоичных переменных разлагаемой логической функции)5

На фиг.1 представлена структурная схема устройства для полиномиального разложения логических функций при п 3 ; на фиг. 2 - .функциональная схема логического блока.1Q

Устройство (фиг.1) содержит дешифратор 1s n - элемента ИЛИ 2,1 и 2.2-,- 2п 4 логических блока

1л t

первой группы 3.1,...,3.4, 2 4 логических блока второй группы, 4.1, }5 ...,4,4, 2 4 логических блока третьей группы 5.1,...,5.4, s J Iog2 х (n + 1) 2 управляющих входа перр вой группы 6,1 и 6.2, п 3 управляю- пщх входа второй группы 7.1-7.3, 20 информационных входов 8.1,.... 8,8 и 2м 8 выходов 9.1,...,9.8.

Каждый логический блок (фиг.2)/ содержит два элемента И 10 и 11, элемент ИЛИ 12, элемент 13 равнознач- 25 ности, элемент ИЛИ-НЕ 14, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 15, два настроечных входа 16 и 17 5 два информационных входа 18 и 19, два выхода 20 и 21 ,

30

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

На СО -и информационный вход уст- ройства (С0 1 ,2,.. „,2м) поступает значение у реализуемой логической функции п переменных f f (X,, ,Xg,..., Х) на (.СО- 1)-м наборе аргументов X,s Х2,... 5Х (1. На управляющие входы первой группы подаются .сигналы настройки И,...,Us, значения которых принадлежат множеству Јo,lj. Сигналы

U.,...,UK определяют количество

5-« . k 51 2 переменных Х ,Х2,.. .,ХК

по которым разлагается функция f

(X,SXЈ,...,ХК). На управляющие входы второй группы подаются компоненты двоичного вектора поляризации (5 - ( ,$Ј,, . ,6,,) переменных X4,Х„,... Хм.

На выходах устройства формируются таблицы истинности логических функ- ций n-k переменных ср: (X.,,,,,.. ,Хи),

где j 0,1, .. . , 2 к - 1 , на которые разлагается исходная логическая функция f (X, . .. ,Xh) ,

2к-1

f (Х„ . . .Х2, . . .Хп) Ж Ц (Xt,,, ,Х„)

-и . п

г-1

- y-J /„. fxУ

-Xj, Xja XJa Uk + i Xhb

r°

где j t, JЈ,.. ., j|(06 g k) - номера единичных компонент ч двоичного kразрядного эквивалента числа i и 1 .

о

Причем bg 0 только тогда, когда

аргумент X() входит в конъюнк цию k-(j 0,1,...,2 -1) только без отрицания. Если 6g 1, то Xg входит в k. только с отрицанием, т.е.

Х8, если G g 0; Xg, если GЈ 1 .

Переменные X к + 4 ,,. , . ,Х входят в функции Cfj (Х,,.. . ,ХИ) только без отрицания независимо от значения компонент , о. . .j СУ вектора поляризации 0 . Значения Функций (|j (j - О,),...,2 - 1) на выходах устройства расположены последовательно, т.е. на первых 2 выходах устройства формируются значения функции (f0 , на следующих 2 выходах - значения функции Ц, и т.д. Таким образом, значение функции (XKt|,.. . ,Х„) на V-M

наборе переменных Xk+, Хл (j

I « IT Л 1 9 - 1

- и,.,«,.,z - «j v- и,),...,/ « J

формируется на (2П j + v + 1)-м выходе устройства.

Если U Uu ... Us О, то k 0 и сигнал на w-м выходе устройства (w 1,2,„..,2П) совпадает с сигналом на его w-м входе, т.е. коэффициенты совершенной дизъюнктивной нормальной формы (д.н.ф.) функции f(X«, Х, ...,Xrj) передаются транзитом на выход устройства.

Поскольку ,l,...,n, то устройство позволяет получить 1 различных разложений для каждой логической функции п перемеьшых f f( Х4,...,ХП), включая транзитную передачу коэффициентов совершенной д.н.ф. на выход.

При п - 3 общий вид этих разложений представлен в табл.1, где символом X обозначено безразличное значе- ние сигнала на соответствующем входе.

Устройство реализует следующий алгоритм поляризованного конъюнктивно полиномиального разложения.

Исходным для нахождения двоичных номеров (таблиц истинности) логических функциг, (XK+I ,...,Xn), j - 0,1,..2 - 1 является вектор значений разлагаемой логической функции f f(X,,X2,,..,Xn) (Y,, Y4,...,V

(Y

Y°

2.

v° ) / «

Далее формируется

последовательность векторов w4,w ,..,

(k l,2,...,n), компоненты которых вычисляются согласно следующим рекуррентным соотношениям:

Y

e-t

-im4t

Ср v

t- Yr2;+i)

(l)

5E- x

Y(2Ui) Yi;,«+-t © Y(4i + 0m+i ; (2)

0n-«

где m 2 ,

e-«

i 0,I,...,2 - 1; t 1,2,..., ти 1 1,2-, ...,k.

Значение функции Cfj (X к+| ,...,Х„)

на v-м наборе переменных Х«4,Хц

(J 0,1,...,2 - 1; v 0,1 ,..., -1 ) совпадает с (2й j + v + I )-й компонентой вектора wk,

В соответствии со сказанным компоненты вектора wK(k 1,2,...,п) формируются на выходах 20 и 21 логических блоков k-ой группы. Дешифратор и п-1 элемент ИЛИ обеспечивают прохождение компонент сформированного вектора кна соответствующие выходы устройства.

Обозначим через z(q 1,2,...,п) сигнал на первом настроечном входе 16 логических блоков g-й группы. Тогда на первом 20 и втором 21. выходах логических блоков q-й группы.реализуются логические функции соответственно

ct, R(p, ,p2); (.p, , /Ьг) V (31 ,

(3)

(A)

где R((3,,pi) |©рг - функция равнозначности; p, и рг - сигналы соответственно на-первом 18 и втором 19 информационных входах логического блока; СГа - q-й компонент вектора поляризации, который подается на второй настроечный вход 17. логического блока q-й группы.

Пусть ba(q 1,2,...,п) - сигнал на q-м выходе дешифратора 1. Причем Ъа 1, если только двоичный код на входах дешифратора равен q - 1, т.е.

S-1

з-d

2d

Тогда z, b,; z z.Ј.,vb

f - 2,3,...,n.

Очевидно, если код U{,...SUS на входах дешифратора I равен k (ocy- ществляется разложение по переменньгм X,, Хй,...,Хк), то ZH za ... z K 0, a z ки zU2. . . zn . При этом для логических блоков 1-й группы (1 l,2,,,.,k) реализуемые ими логические функции, как следует из (3) и (4), имеют вид .

х,-р.©Се(р«©рг)-р,Се©ргаг-, (5) 1, (6)

Сравнивая (5) и (6) соответственно с (1) и (2), можно сделать вывод о том, что логические блоки первых k групп осуществляют преобразование исходного вектора коэффициентов совершенной д.н.ф. w0 в вектор wk, составленный из двоичных номеров функц™ хх.их) J 0,1,...,

1.

Для логических блоков с-й группы

(с k + l,...,n) zc 1 и формулы (3) и (4) преобразуются к виду

Рм

«г Рг.

(7) (8)

715

Соотношения (7) и (8) указывают, что сформированный на выходах логических блоков k-й группы вектор WK без дальнейших преобразований проходит на выход устройства.

Таким образом, устройство выполняет поляризованные разложения произволной логической функции f (Х{ ,Х2, . „ „ ,ХП заданной посредством таблицы истинное

ти, по k(k 0,1,...,п) переменным Х0,...,ХК (при k О на выход

и

X

устройства проходят сигналы с его входов, т.е. осуществляется транзитная передача таблицы истинности логи- ческой функции f (Xt ,Х2,.. . ,Xh)

В качестве примера в табл.2 пред-1, ставлены компоненты векторов w , получаемые устройством при п 3, для функции f (X,,Ха, Хэ) Х, X2X,V X, Xj,V X, X , для различных значений k(k 0,,2,3) и возможных векторов поляризации G1 (G, ,(,(53) . В табл.2 символ X обозначает безразличное состояние, а жирной линией выделены кортежи из компонент векторов w, которые составляют таблицы истинности соответствующих логических функций С|ь (Хк+1 , ...,Х„), где j 0,1,....2 - 1.

Изобретение относится к вычислительной технике и может быть использовано в ЭВМ, интерпретирующих программу, написанную на языке высокого уровня, а также в специализированных процессорах. Цель изобретения - расширение функциональных возможностей устройства для полиномиального разложения логических функций за счет выполнения конъюнктивно-полиномиальных разложений по K переменным (K=0,1,...,N) с произвольным вектором поляризации (N-количество переменных разлагаемой логической функции). Устройство для полиномиального разложения логических функций N переменных содержит дешифратор, N-1 элемент ИЛИ, N групп логических блоков по 2^N-1 блоков в каждой. Причем каждый блок устройства содержит 2 элемента И, один элемент ИЛИ, один элемент ИЛИ-НЕ, один элемент равнозначности и один элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, S=]LOG₂(N+1)[ управляющих входов первой группы, N управляющих входов второй группы, 2^N информационных входов и 2^N выходов. На управляющие входы первой группы устройства подаются сигналы настройки U₁,...,U_S, определяющие количество K переменных X₁,X₂,..,X_K, по которым разлагается логическая функция F=F(X₁,X₂,...,X_N), на управляющие входы второй группы - компоненты двоичного вектора поляризации σ = (σ₁,σ₂,...,σ_N) переменных X₁,X₂,...,X_N, на информационные входы - таблица истинности функции F ,тогда на выходах устройства будут формироваться таблицы истинности логических функций N-K переменных φ_J(X_K+1,...,X_N), где J = 0,1,...,2^K-1, на которые разлагается логическая функция F=F (X₁, X₂,...,X_N). 2 ил, 3 табл.

Значения сигналов на выходах дешифратора 1 при различных комбинациях сигналов на его входах представлены в табл,3„

ТаблицаЗ

Таблица2

Таким обоазом, устройство позволяет выполнить 2h+1 -1 полиномиальных разложений произвольной логической функции п переменных. I Формула изобретения

Устройство для полиномиального разложения логических функций, содержащее п-1 элементов ИЛИ (п - количество двоичных переменных разлагаемой логической функции), и дешифратор,. r-й вход которого (г l,s; s 3logz(n+l)t) соединен с r-м управляющим входом устройства первой труппы, первый и второй выходы дешифратора соединены соответственно с первым и вторым входами первого элемента ИЛИ, j-й вход дешифратора (j 3,п) соединен с первым входом (j - 1)-го элемента ИЛИ, второй вход которого соединен с выходом (j - 2)-го элемента ИЛИ, отличающее с-я

логического блока h-й группы соединен с первым информационным входом ((2m + 1) + логического блока (h + 1)-й группы, второй информационный вход которого соединен с вторым выходом 2М (2m f 1) + го логического блока h-й группы, первый выход Р-го логического блока

тем, что, с целью расширения функцио- JQn-й группы соединен с (2Р-1)-м выхо- нальных возможностей за счет выполне-ДОМ устройства, 2Р-й выход которого ния конъюнктивно-полиномиальных разло-соединен с вторым выходом Р-го логи- жений по k переменным (k 0,п) сческого блока n-й группы, причем произвольным вектором поляризации,каждый логический блок устройства оно содержит п групп логических бло- j содержит два элемента И, элемент ИЛИ, ков по блоков в каждом, первыйэлемент ИЛИ-НЕ, элемент СЛОЖЕНИЕ ПО настроечный вход каждого логическо-МОДУЛЮ ДВА и элемент равнозначности, го блока первого яруса соединен с пер-первый вход которого соединен с первым выходом дешифратора, первый наст-вым информационным входом логичес- роечный вход каждого логического 20кого блока и первым входом элемента блока t-й Группы (t 2,п) соединенСЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которо- с выходом (t - 1)-го элемента ИЛИ,го соединен с первым выходом логи- второй настроечный вход каждого ло-ческого блока, второй вход элемента гического блока i-й группы (i 1,п)СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с вы- соединен с i-м управляющим входом 25ходом первого элемента И, первый устройства второй группы, первый ин-вход которого соединен с выходом эле- формационный вход Р-го логическогомента ИЛИ-НЕ и первым входом элемен- блока (Р 1,2 ) первой группы сое-та ИЛИ, выход которого соединен с динен с Р-м информационным входомвторым выходом логического блока, устройства, ( + Р)-й информацией- 30второй вход элемента ИЛИ соединен ный вход которого соединен с вторымс выходом второго элемента И, первый информационным входом Р-го логически-вход которого соединен с вторым ин- го блока первой группы, первый выходформационным входом логического бло- (т 2 + 1)-го логического блока.h-йка и вторым входом элемента равноэ- группы (h 1, п - 1; m О, 2 35начн°стк, выход которого соединен с 1 1, ) соединен с первым инфор-первым входом элемента ИЛИ-НЕ, вто- мационным входом (т 2 + 1)-го ло-рой вход которого соединен с, вторым гического блока (h + 1)-й группы,входом второго элемента И и первым второй информационный вход которогонастроечным входом логического бло- соединен с первым выходом (2т+ дока, второй настроечный вход которого +1) + логического блока h-йсоединен с вторым входом первого эле- группы, второй выход (т«2 + 1)-гомента И.

335Ю

логического блока h-й группы соединен с первым информационным входом ((2m + 1) + логического блока (h + 1)-й группы, второй информационный вход которого соединен с вторым выходом 2М (2m f 1) + го логического блока h-й группы, первый выход Р-го логического блока

16

Ю

JS

21

TJJE

ЛГ

Hj

ifasn