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

 

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

СОЮЗ СО8ЕТСКИХ сОциАлистичесни х

РЕСПУБЛИК (5l)5 С 06 F 5/00, 7/00

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И OTHPblTHAM

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) .4409061/24-24 (22) 13.04.88 (46) 23.04.90, Бюл. !»- 15 (72) Л.Б. Авгуль и B.Ц. Супрун (53) 681 .3 (088.8) (56) Авторское свидетельство СССР

Ь" 1124281, кл. С 06 F 5/00, 1983.

Авторское свидетельство СССР

1! 144!380, кл, С 06 Р 5/00, 7/00, l9S7. (54) YCTPOACTBO ДЛЯ ПОЛИН(И!АЛЬ!!ОГО

РАЗЛОЖЕНИЯ ЛОГИЧЕСКИХ ФУНКЦК! (57) Изобретение относится к вычислительной технике и может быть использовано в ЭВ!1, интерпретирующих программу, написанную на языке высокого уровня, а также в специализированных процессорах. Цель изобретения — расширение функциональных возможностей устройства для полиномиального разложения логических функций за счет выполнения конъ».нктивно-полиномиальных разложений по М переменным (k =

= 0,1,...,n) с произвольным вектором поляризации. (n — количество переменных разлагаемой логической функции).

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

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

„„SU„„1559335 А1

2 переменных содержит . дешифратор, n-! элемент ИЛИ, и групп логических блоков по 2 блоков в каждой, причем каждый блок устройства содержит дьа элемента И, один элемент ИЛИ, один элемент ИЛИ-НЕ, один элемент равнозначности и один элемент СЛОЖЕНИЕ РО МОДУЛ! » ДВА, s = j1ор (n Ф

+ 1) Гуправ»»яющих входов первой группы, и управляющих входов второй группы, 2 информационных входов и 2 "

»» выходов. На управляющие входы первой групn».» устройства подаются сигналы настройки U>,...,U, определяющие количество k переменных Х,, Х,...,X по которым разлагается логическая функция f. = f(X», Х,...,Х„}, на управляющие входы второй группы — компоненты двоичного вектора поляризации G = (G,, б,...,6,„) переменных

Х,, Х,..., Х,„, на информационные входы — таблица истинности функции

Тогда на выходах устройства будут формироваться таблицы истинности логических функций n-k переменных

К-»

Ч»,(Х „,,...,Х„),где j = 0,1,... 2 на которые разлагается логическая функция f = f(X<,Х ....,Х,). 2 ил., 3 табл.

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

Х, если

Х р если и) с произвольным вектором поляриэа, цни (п — количество двоичных переменных разлагаемой логической функции)

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

Устройство (фиг.l) содержит дешифратор l и — 1 = 2 элемента ИЛИ п-

2.1 и ?.2-; 2" = 4 логических блока первой группы 3.1,...,3 ° 4, 2 = 4. и- логических блока второй группы, 4.1, 15 ...,4,4, 2 = 4 логических блока и-i третьей группы 5.1,...,5,4, s = $ 1op x

«(и + l) f = 2 управляющих входа пер вой группы 6.1 и 6.2, и = 3 управляющих входа второй группы ?.1 — 7.3, 29

2 = 8 информационных входов 8.1,..., и

8,8 и 2" = 8 выходов 9.1,...,9.8, Каждый логический блок (фиг.2) < содержит два элемента И 10 и 11, элемент ИЛИ 12, элемент 13 равнознач- 25 ности, элемент ИЛИ-НЕ 14, элемент

СЛОЖЕНИЕ ПО МОДУЛ!и ДВА !5 два настроечных входа 16 и 17, два информационных входа 18 и !9, два выхода 20 и 21е

ЗО

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

На Я -Й информационный вхоп уст35 ройства (Q = l 2... „,2") поступает значение у 1 реализуемой логической функции и переменных f = К(Х,,X,..., Х„) на (.Я вЂ” 1)--и наборе аргументов

Х,, Х,...,Х „. На управляющие входы 40 первой группы подаются .сигналы настройки U <,...,U» значения которых прннадленат множеству (О, Il. снтнелы

U<...,,U > ооппрреедделяют количество k = Бз с! 2 переменных Х1,Х,...,Х„

5-(g.-„а по которым разлагается функция f (Х,Х,...,Х„). На управляющие входы второй группы подаются компоненты двоичного вектора поляризации 0 — (8,,6<,...,бп) переменных Х „,Õ,...

Хи °

На выходах устройства формируются таблицы истинности логических функций и-Е переменных Ц (Х,,,...,Х1,), где ) = 0,1,...,2" — 1, на которые разлагается исходная логическая функцИЯ Р (Х рХ р е ° е рт ) ) р

2"-1

= Q k ;(XÄÄ,...,Х„) =

1сО .0;

Х (p (Х,. ° .,Х )

1 +1 где 3 <, ),..., 1 (0»- g< k) — номера единичних компонент :. двоичного kразрядного эквивалента числа j u

1 о—

Причем 6!I = 0 только тогда, когда аргумент Х (! 1 k) входит в конъюнкцию k (j = 0,1,...,2 -1) только без (э °

J отрицания. Если б р = l то Х входит в k только с отрицанием, т,е.

Переменные Х „ „,...,Х„ входят в функции (((Хк„,...,Х,„) только без отрицания независимо ат значения комгонент (р„„,..., 5> вектора поляризации 6 . Значения функций ц1 (j к

= 0,1 2 — i) на выходах устройства расположены последовательно, т.е. и-к на первых 2 выходах устройства формируются значения функции (g, на и-к а следующих 2 выходах — значения функции Ц», и т.д, Таким образом, значение функции („ (Хд .. .Х„) íà v-м наборе перемейных Х „,..., Х„() формируется на (2 j + ч + 1)-м

9 р р р выходе устройства.

Еслибы =U<=- ... = Пз— = О, то

k = 0 и сигнал на ч-м выходе устройства (w = 1,2... °,2 ) совпадает с сигналом на его ч-м входе, т.е. коэффициенты совершенной дизъюнктивной нормальной формы (д.н,ф,) функции f(X», ХО,...,Хп) передаются транзитом на выход устройства.

Поскольку Е = О,l,...,п, то устройство позволяет получить 2" — 1 раза+ личных разложений для каждой логической функции и переменных f = й(Х„, Х<р...,Х„), включая транзитную передачу коэффициентов совершенной д,н.ф. на выход, При и = 3 обшивай вид этих разложений представлен в табл ° 1, где символом Х обозначено безразличное значе ние сигнала на соответствующем входе.

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

„ь

Таол ила

1559335 бд

1 к" Р; (х„„,....х,) ,:с

f(x,,х„,х,) =

Примечание г Поляризонанное разлоьь<ение Акерса

x f(X«Xzi Х,) дРЬ (Х е у Хз ) Щ Х < !Рь (Х 1 у Х з ) дРо(Х2>хъ1Ю х<(p (хдь Ху) к zp,(x ) Ю х».дР,(x,) V». x, о, х, Rx, х, ср,(x,) (p«(X <)-)Xz0< (X з)@Х< hpz(x ®Хь Xz <Ру(Х у) СРо(Ху)9ХддР, (X 3+X< (Pz(xq®X< Хд<еу(Х у) х !Р (х,)6)хдсрь (х,)()х, сР,(x,)о)х, х,cp„(x,) 0 СР<ь9Х !РЯ)хд<Р<ОХЕХ ьь® Х,<Ру9 Х< Хз<Р 6)Х< Xz!p<8 Х< Ху Худ,!

Р<<Ю ХЪ1ЖХЙЦ ОХ Ху<Р<ОХ<<РбО Х< Хз!Р<Ж Х, Хд(Рь,@ Х< Хд Х |<

О !РЭХздР<9хдЬР<0+ ХдХфР,®Х<1Р<ЮХ< ХЗ(РуЯХ< Xz

1(РрЮХу<Р,9хд<Рдьб)хд? <Р<6Х<<Р<ЯХ<ху(Руьбх<хд!Рб&Х<Хдхь(Р

Дф х y9 XzzP

1 (ДЭху<Р19 Хднф<0 Х, Х

О (фЭХДО+ХЯО+ Х> Х<ЬР<Ю Х< <Р<0 Хь Х)<УуЯХ< ХАРЯ Х< Хд Xg(P! <<юх ььОь<ь<ьг удь ox) clx х<Зюх x, Qx x xi

Канонические поляризоеанндье полиноьбъь

Исходным для нахождения двоичных номеров таблиц истинности) логических функций Ц;(Х +<,...,Х ), = 0 1 ... 2 — 1 является вектор знау jа<4

20 чений разлагаемой логической функции у

f = 1(Х! уХ ...,,Х)!д =(У„, У..., еьь)= (Y уо уо у ду ° ° у последовательность векторов v„,дь ъ7 к(К = 1, 2, ° °,,и), компоненты ко- . 25 торшх вычисляются согласно следующим рекуррентным соотношениям:

E.

У;

Е< пь б1

Р (

УЕ;„„бт GB V Уа;б<) «.ЯЕ е- 3G

У, „О Y(z, 1 .z (2) и-е Е-ь где m = 2, i = 0,1,...,2 — 1; — 1,2,..., m и 1 = 1,2;...,k.

Значение функции q<; (X „„,...,Х„) на v-м набоРе геРеменных Х„б...,.,Х<ь к (j = Оу1уаэ ° у2 1у v = Оу!у ° ° ° у

Yl- ь<

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

40

Обозначим через z (q = 1,2, ° ° °,n) сигнал на первом настроечном входе

16 логических блоков g-й группы. Тогда на первом 20 и втором 21 выходах логических блоков а-й группы реализуются логические функции соответствен55! к< = 1зб(96<1 z

ot. Pz ю б

О о о о о о ! I

1 1

1 1

1 1

1 1

1 1

1 1

v x

0 х

1 х

О О

О к

1 О

О 0

О О

О

О

1 О

1 О

1 1

1 1 где 6ь t z) = !<б!О+13т — функция равнозначности; Р, и Pz — сигналы соответственно на первом 18 и втором 19 информационных входах логического блока; (з — q-й компонент вектора по1 ляризации, который подается на второй настроечный вход 17, логического блока а-й группы.

Пусть Ь (q = 1 2,...,n) †. сигнал на ц-м выходе дешифратора 1, Причем

Ь = 1, если только двоичный код на входах дешифратора равен а — 1, т.е.

5-<

1ь

4=о

Тогда z!,= Ь,; z< = z <ЧЬ и

2,3,...,n„

Очевидно, если код U<...,,U< па входах дешифратора 1 равен k (осуществляется разложение по переменным

Хе ° .. ° уХк).у To z = zz = °, °

= хк = О, а к„,! =кьь,д= ° ° =к„=1. Прн этом для логических блоков 1-й группы (1 1,2... °,1с) реализуемые ими логические функции, как следует из (3) и (4) у имеют вид о(=p > ье(I5 ®pг) =/ <(е@pz(зе у . (5)

Pь Ю Pz ° . (6) Сравнивая (5) и (6) соответственно с (1) и (2), можно сделать вывод о том, что логические блоки первых групп осуществляют преобразование исходного вектора коэффициентов совер-ш йь шенной д.н.ф. v в вектор v1„ составленный из двоичных номеров функ(Хк,у! у ° ° ° уХ!ь)у Д Оу 1 у в а ° у

2"- 1, Для логических блоков с-й группы (с = k + I у ° ° ° уп) z с 1 и формулы (3) и (4) преобразуются к виду

1559335

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

Таким образом, устройство выполняет поляризованные разложения произвольной логической функции. f(X» X .,Х„) заданной посредством таблицы истиннос-!О ти, по k(k = О,l,...,n) переменным

Х, Х,...,Х„(при k = О на выход устройства проходят сигналы с его входов, т,е, осуществляется транзитная передача таблицы истинности логической функции f (Х,, Х q,..., Х„) В качестве примера в табл,2 пред-, ставлены компоненты векторов w покь лучаемые устройством при n = 3, для функции К (Х,, Х, Х ) =Х Х Х Х„Х ч Х< Х для различных значений k(k = 0,1,2,3) и возможных векторов поляризации

G =(5,, 5,6 ). В табл.2 символ Х обозначает безразличное состояние, а жирной линией выделены кортежи из компонент векторов w,,которые составляют таблицы истинности соответствующих логических функций Cf (Х

1 кб! ...,Х„), где 1 = 0,1,...,2

Таблица 2

Вектор поляризации

Значения компонентов вектора w

Код числа переменных разложений у уб ут у8

У, у у у

9„9 9 94. 9 > 96 9 98

7з

6, 6 х О О 1 х О О

1 О х 0 0

1 О О х l 1 1 х О 1

О 0 О

1 0 О О 0 1 1 1

1 О 1 О

0 1 О 1

1 1 О О

О . О 1 1

1 1 1 О

Таким образом, устройство позволяет выполнить ? -1 полиномиальных

a+i разложений произвольной логической

Функции п переменных.

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

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

Т а б л и ц а 3

Ь b„Ь

Устройство для полиномиального разложения логических функций, содержащее и-1 элементов ИЛИ (и — количество двоичных переменных разлагаемой логической функции), и дешифратор,.

r-й вход которого (r = l,s; s

= 1 1о 1 (п+1)!) соединен с r. — ì управляющим входом устройства первой груп6.1 6,2

2 3

О

1

О

1

О

0 О

О 1

1 0

1 1

О 0 .0 .l

О . 1

1 0

1 0

l О

1 О

1 1

1 1

1 l

1 1

1 1

1 l

1 1 х

1

О

l

О

О

О

1

1 х х х

О !

О

0

1

0

О

О

1

О

0

О

1

1

1

1 О 1

1 1 1

1 1 1

1 О 0

1 О О

1 О О

1 0 О

О О О

О О 0

0 О О

0 О О

О 0 О

О О О

0 О 0

0 .О О

1559335

1О пы, первый и второй выходы дешифратора соединены соответственно с первым и-вторым входами первого элемента

ИЛИ, j-й вход дешифратора (3 = З,n) соединен с первым входом (j — 1)-го элемента ИЛИ, второй вход которого соединен с выходом (j — 2)-го элемента ИЛИ, о т л и ч а ю щ е е с.я тем, что, с целью расширения функцио- 10 нальных возможностей за счет выполнения конъюнктивно-полиномиальных разложений по 1 переменным (k = 0,n) с произвольным вектором поляризации, оно содержит и групп логических бло-. ков по 2" блоков в каждом, первый настроечный вход каждого логического блока первого яруса соединен с первым выходом дешифратора, первый настроечный вход каждого логического

20 блока t-й группы (t = 2,n) соединен с выходом (t — 1)-го элемента ИЛИ, второй настроечный вход каждого логического блока i-й группы (i = 1,n) соединен с i-м управляющим входом 25 устройства второй группы, первый информационный вход P-ro логического блока (P = 1,2 ) первой группы соединен с Р-м информационным входом устройства, (2 " + Р)-й информацион- З0 ный вход которого соединен с вторым информационным входом P-го логнческбго блока первой группы, первый выход (ш 2 + 1)-го логического блока -й групрыть = I, и — 1; m=О, 2" - I;

1 .= 1, 2" ь ) соединен с первым иифор<<-Ь мационным входом (m 2 + 1)-го логического блока (h + 1)-й группы, второй информационный вход которого

<<-И < соединен с первым выходом 2 <2m+.40

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

12 " (2тп + 1) + 11-го логического блока (h + 1)-й группы, второй информационный вход которого соединен с вторым выходом (2" (2m + 1) + ll го логического блока h-й группы, первый выход P-го логического блока и-й группы соединен с (2P-1)-м выходом устройства, 2P-A.выход которого соединен с вторым выходом P-го логи < ческого блока и-й .группы, причем каждый логический блок устройства< соДержит два элемента И, элемент ИЛИ, элемент ИЛИ-НЕ, элемент СЛОЖЕНИЕ ПО

МОДУЛЮ ДВА и элемент равнозначности, первый вход которого соединен с первым информационным входом логического блока и первым входом элемента

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым выходом логического блока, второй вход элемента

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом первого элемента И, первый вход которого соединен с выходом элемента ИЛИ-НЕ и первым входом элемента ИЛИ, выход 1 оторого соединен с вторым выходом логического блока, второй вход элемента ИЛИ соединен с выходом второго элемента И, первый вход которого соединен с вторым информационным входом логического блока и вторым входом элемента равнозначности, выход которого соединен с первым входом элемента ИЛИ-НЕ, второй вход .которого соединен с, вторым входом второго элемента И и первым настроечным входом логического блока, второй настроечный вход которого соединен с вторым входом первого эле" мента И.

1559335

Фие1

Редактор Л. Гратилло

Корректор Л. Бескид

Заказ 837 Тираж 561 Под.тисное

ВНИИПИ Государственного комитета но изобретениям и открытиям при ГЕНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

7g

7г

Составитель В. Сорокин

Техред A.Êðàâ÷óê