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

 

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

(51) G.06 F 5/00, 7/00

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

К Д ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕНЙЫЙ HOMNTET

ПО ЧЗОБРЕТЕ11ИЯМ И ОТНРЫТИЯЦ1

ПРИ ГННТ СССР

{21) 4443227/24-24 (22) 16.05.88 (46) 15.03,90, Бюл. И 10 (72) Л.Б, Авгуль, В.П. Супрун и Н.А, Егоров (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф !124281, кл. G 06 F 5/ОО,, 1983.

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

У 1441380, кл. 0 06 F 5/00, G 06 Р 7/00, 1987. (54) УСТРОЙСТВО ДЛЯ ПОЛИНОМИАЛЬНОГО

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

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

„„ЯО;„, Ц5ОБО7

2 ких функций содержит и (и - кол-во. переменных раэлагаемых логической функции} групп логических ячеек по

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

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

7(11,,Б,...,U ), определяющие пере" менные, по которым осуществляется . CL разложение (единичные компоненты век". тора V определяют переменные, по которым производится разложение), Ha ( выходах устройства последовательно формируются таблицы истинности логи- Я

1с ческий функций з(8=0,1,...,2 -1), на которые разлагается исходная логи- ввиФ ческая функция и переменных. 1 э.н., ф-лы, 2 табл. 7 ил. ©t

Ю логических Функций по произвольным

kgb переменным.

На Фиг. 1 представлена структурная схема устройства длл полнномиального разложения логических функций прн и 3; на Фиг.2 — функциональная схема логической ячейки; на фиг. 3— функциональнал схема первого узла управления; на Фиг. 4 — Функциональнал схема второго узла управления; на фиг. 5 — функциональная ".хема первого

1550507 коммутатора; на фиг. 6 — Функциональная схема второго коммутатора; иа фиг. 7 — графы состояний второго коммутатора для рассматриваемого примЕpeе

Устройство для полиномиального разложения. логических функций (фиг.1) р4 содержит 2 --4 логические ячейки п ервой группы l 1, 2 =-4 логическйе ячейки второй группы 2 -?.

2" =4 логические ячейки третьей груп3,-3, и-1=2 узла управления 4, и.

42, 11-1 2 коммутатора 5, и 52, 2"=8 нформационных входов 6,-6, п=З астроечных входа 7, -7, 2"=8 выхо- ов 8,-8!I ., Каждая логическая ячейка l,2 и 3 фиг.2) содержит два информационных хода 9 и 10, настроечный вход 11, ..ыход 12, элемент И 13, элемент 14 ,ЛОЖЕНИЕ ПО ИОДУЛЯ 2.

Узел 4„ управления содержит два лемента НЕ 15 и !6, элемент ИЛИ-НЕ

7, элемент ИЛИ 18, элемент И 19, .:лемент 20 СЛО)КЕНИЕ .ПО МОДУЛЮ 2 20 пять выходов 21-25.

Узел управления 4 содержит зле-! ент ИЛИ 26, элемент НЕ 27, два элемента И 28 и 29 и три выхода 30-32.

Коммутатор 5, образуют четыре зле-! (ента И-ИЛИ 33-36, Коммутатор 5 состоит из шести элементов И-ИЛИ 37-42.

Устройство работаег следующим об35 разом, На 1-й информационный вход (j l»

2»...,2") устройства подается значе" ние у разлагаемой логической функции

f f(x „x,...,х „} на (j-1);м наборе,»О переменнйх х„,x,...,õ „. На настроечные входы 7 устройства поступают компоненты двоичного вектора настройки

П =(®,»Ц ...,,U„), определяющие переменные, по которым осуществляется разложение. При этом, если 1! =1 (i=1 2,...,n) то выполняется разложение по перемейной х,; если U.=О, разложение по х; ие производится, На выходах 8 устройства последовательно 5Î формируются таблицы истинности логической функции ((($=0»!» „? I)»

Ъ на которые разлагается исходная функция ЕЕ(xx,,x x...,xx„):

2 =(55

I (X»Х2»е е е»Хее),1 11 З Ч (А(»

Хее»еее»Х2 к»1» n де (K -(— множество всевозможных попарно различных конъюнкций ранга r (t0,1,...,k) переменных х < »х ». ° .

»» ...,х, по которым осуществляется конъюнктивно-полиномиальное разложе we, Значение функции (»»g (X C„,,х <, ...,х g ) на ч-м наборе переменньас

Tt (»-к х2„.(„х „„,...,х р (ч0,1,...,2 -1; к и

S=0,I,...»2 -1) формируется на (2 " S+v+I)-м выходе устройства.

В табл.! для п=З представлены вин ды 2 =8 возможных конъюнктивно-полиномиальных разложений логической функции трех переменных f=f(x<»х,х }.

2» 3

Известно, что произвольная логиl ческая функция переменных f f(x »х

1» 2» ...,х„) допускает конъюнктивно-йолиномиальное разложение по переменной х; (16!.(п) вида

Е(Х»»Х2»е ° ° »Х ) еГ,Х» ° ° ° ° »Х»Х ° ° ° е (Ф еееХ ) Q Х. (»(X,...,Х.,Х,...,Х ), 1 1 t )+»»» (2) где у (х»... »х;,,х(„,...,X „}

=Е (х (» ° ° ° » х !.1» О» х 1.1» ° ° ° » х к) и

4,(х 1» ° ° ° »х (-»X I»»» ° ° ° »х „) (.)

Е(х,...,х (»»

ОХ

0»Х ° » ° ° е»Х ) ® f(x»» ° ° ° »Х(1»1»

Х(е1» ° е е»Хк) °

Выполнение разложения (2) по переменным х!,х!,...,Х2 дает возмож»» ность предс1"аBèòü произвольную логическую функцию Е(х,,х,...,х„) в виде полиномиальной суммы (l) логических функций n-k переменных (»z(х х» »...,х ), причем 1х» »х( ке 2 ».ее К»Я ...,х 2 =(х,х,. ° .,х„ / х (,,х (,... е ° еХ f 1o

Исходным дпя йостроения таблиц ис" тинности функций является вектор значений r,=(у,,у,...,у „) (;,y,... ...,у „ раэлагаемой функции f f(x „ х,...,х „,. Полагаем, что разложение производится последовательно по переменным х1,,х 1,...,х g . Далее формируется последовательность векторов ч »ч,...,й, компоненты которых вы»» числяются согласно следующим рекуррентным соотношениям: (3)

®

y(!. i е()АГУ 2(ве t (!» ((,-1 где ш= 2 "; ь=*0»I,...,,? " "-1 „

tI,2. ..m;

Ьч1,2,...,k.! 150507

В соответствии с приведенным алгоритмом разложения (3) устройство содержит и ярусов логических ячеек (фиг,2), работа которых описывается выражением: упpа ли ели я ° который нл с л(«.i «с»лик

Выходах формируBT vHHT 3p«11Л ный двоичный код (в >е > °

> который предназначен для коммутац«и входных сигналов коммутатора по с1 направлениям .

Условия формирован«н сигналов

z >,х,...>к слелуюр не:

Ч i 1> 4Ь > ("piU> е619 где де: -> >1>

=Р,ч» з-1 у- в1

q=2 З,...,п;

1 >- 9 >Ч> где F <, =Р,, (»,, Ó,..., U ч,) — фунр

30 даментальные (элементарные) симметрические булевы функ««и> зависящие от переменных И,,» ...,,11,, где р-.0,1 >...,q-1. При этом Р, —.l тогда и "олько тогда, когда I,+» +...+

35 ц %- Р г

@yHKL HH F р V=0,1>. ° °,P) поступают на вторые входы Р-ro узла управления (P=2,3,...,п-2) со вторых выходов (P-I)-го узла управления и ис40 пользуются для формирования сигналов .(5). В свои очередь, на своих вторых выходах P-й уэеп управления реализует исходя из F р функции

Р „(6=0>I...,,P+l), которые посту"

45 паит на вторые входы (Р+I )-ro узла управления:

U -, Fð, если 6=0;

50 Рр -Ipe> Р р Б р+> Рр, е >< 046аР+1;

iJ р+> F, если Ь =Р+ I, (6)

° . Для рассматриваемого примера (и 3) с учетом (5), (6) можно записать ус55 ловия формирования сигналоэ узлами 4 управления:

Я 5>ЧД2 >

2 р и p> — соответственно сигналы на первом и втором информационных входах логической ячейки;

U (1-!,2,... ...,n) — сигнал на настроечном . входе логической ячейки (индекс i указывает, что ячейка находится в i-м ярусе и ка нее подается i-й компонент вектора настройки

=(» » у «9»p)!

»(— - сигнал на выходе логической ячейки.

Как отмечалось выше, если U, 1, то разложение осуществляется по переменной х,(l i ), т. е. х; с х р,, х>> ...,,х . Гледовательно, е(= р, 9р Э к и -Й ярус логических ячеек обеспечивает преобразование входного вектора значений согласно (3). При U;=0 переменная х; принадлежит множеству (x р >х р >...,х < и )-й ярус логических ячеек обеспечивает транзитную передачу входного вектора значений на выход,,Для выделения иэ векторов Й,>ч ...> |„ последовательных кортежей значений функций »> служат коммутато"

pbl 5 (их об@ее количество п-l), Если сумма значений первых q компонент U,,U,...,» (q=2,3,...,п)

Ф вектора настройки U равна X U„=k > е1 то (q-1)-й коммутатор 5 обеспечивает формирование на своих выходах упорядоченного вектора значений, в котором таблицы истинности промежуточных функций разложения y (f 0>1>... ...,2 +,), зависящих от I>;< переменных, располагаются последовательно в порядке возрастания к-меров функч, > > Ф ции, т.е. V„V,, V,, Для управления коммутаторами используются узлы 4 управления. Причем каждому (q-1)-му коммутатору (q 2, 3y ° ee ° A) соответствует (q-I)-й узел г =I, если U, U =р...>=»,, l т или U 0; (41

z Ъ =1; если X U- аq-1- U =1 °

l 1=1

« Ъ Ъ

1 *>- 9 e >п> =2>3,... „q, Узлы -4 управления могут быть построены на основе фундаментальлага

20 симметрического многаг!олюсника.

Тогда (4) можно представить в ви1550507

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

«х х © х1(х чх ) =(х1 е 3) е .,1.3 Rx 9 х (хvõ)

Щх х, фх; 9х,х,х

=х, (3 х х., 9 x X Ю х,xgxg

16хз ХР1 3 — 1 B хз ® х Юх х 9 х 6х1х 6 х1х Х3

У 0,0 0, 0 (7)

Р 11, Ж Ug, Г, U,Бт, 5

1 2

12ЧУь в. *УзP, (8) и в .1.АР

Схемы первого 41 и второго 4 уэг ов управления построены согласно

7) и (8), В устройстве (q-1)-й ком"

Мутатор содержит 2 -2 1 элементов

-2И-БИЛИ (q 2,3,...,n), где L2, 15 ,...,q — количество двухвходовых ементов И, выходы которых подклю аются к входам сООтветствуюцего элеента ИЛИ.

В качестве пояснения на фиг.7 (а, 20 „в) приведены графы работы второго

Таким образом, устройство поэволяЬт выполнять 2 конъюнктнвно-полиноtl

Миальных разложений.

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

1. Устройство для полиноми льного разложения логических Аункдий1 со 4б держащее и (и — количество переменных раэлагаемой логической функции) групп логических ячеек по 2 " ячеек в каждой, первый информационный вход i-й логической ячейки (i I 2,...,2" ) первой группы соединен с i-м информационным входом устройства, (2" +1.)-й информационный вход которого соединен с вторым информационным входом i-й логической ячейки первой группы, пер- «О ьый информационный вход j-й логической ячейки q-й группы (j=1,2,...,t;

О**2,3,...,n; =2" ) соединен с j-u информационным входом устройства, (2" +1)-й информационньщ вход кото3 55 рог0 BòîðHM информационным входом.j-й логической ячейки q-й группы, первый информационный вход ь-i i (2 -t+j)-й логической ячейки q-Й коммутатора 5 для рассматриваемого примера, указываются направпения передачи информации при различных векторах настройки. Такие графы могут быть легко построены для всех коммутаторов при произвольном значении и.

1 На основе графов однозначно воспроиз водится функциональная схема Соответ4 ствуюцих коммутаторов.

В качестве иллюстрации в табл,2 представлены реализуемые устройством восемь видов конъюнктивно-полиномиальных разложений логической функции трех переменных:

f (xi 9x2 9x 3) x ix ex3vx f x 3

В табл.2 жирной линией выделены кортежи значений логических функций

Ч3,-(В-О,l 2"-1).

Как следует иэ табл.2., имеет место группы соединен с выходом (2 " -2t+

+1)-й логической ячейки (q-1)-й группы, выход (2 -t+j)-й логической ячейки которой соединен с вторым информационным входом (2 " -t+j)-A логической ячейки q-й группы, первый информационный вход устройства соединен с первым выходом устройства, 2"-й выход которого соединен с выходом 2 -й логической ячейки и-й группы, о т. л и ч а ю щ е е с я тем, что, с целью раснирения функциональных воэможностей эа счет конъюнктивно-полиномиального разложения логических функций по произвольным 1с4п переменным, содержит и-! узлов уп" равления н и-1 коммутаторов, информационные входы первого иэ которых соединены соответственно с выходами nepit- 7. вых 2 логических ячеек первой

1l-Й группы и выходамн первых 2 логических ячеек второй группы, информационные входы 1-го коммутатора (1 2, 3 и-1) соединены соответственно с выходами v-x логических ячеек 1-й группы (v 2" -2 ",...,2 Ь; Ь=*

=2 ), выходами первых h погичес! "tn-п7

Таблица 1

Виды конъюнктивно-полиномиальных разложений по произвольным

14п переменным при и 3 1

Б U Виды разложения (х11Х2 х 3) ! 0 0 "(3 3) ® 1 Ч 1(" 3) 0 1 0 +р(Х1 фх3) ® X2 1 1(х1 фхэ) 4 0 0 ) р(х1x2 ® X3 Ч1(x1эх2) о

3!j0 fft (X3)®x2 fftt(x )®xt +IX)9x fx2 tftp(xg) 0 l су,(х ) (+) х3 ср,(х ) Ю х, tf (X ) Е х х у,(х ) 6 1

3р(1) О 3 f(1) 24 4 1) 2 3 93(1) В ! ftI9xtft®х IIIЕх х y9xtftt®x x I!I@ X Õ2ü6õ,х X ttt.

° В ВЮ

Таблица 2.

Таблица истинности логических функций ы (30,) ... 2 -1; Мп3)

Ъ для рассматрмваемого лрймера

УФ ч ; Вектор настройки 3

% Х0

4»

tIg/7 )) /72 03/7

Вектора эначений функций 4 3

1 0 0 0 0

2, 1 I 0 0

3 t 0 1 0

4 . 1 0 0 )

5 2 1 ) 0

6 - 2 I 0

7 2 0 1 1

8 3 . I I 1

1 0

1 0

0 0

I t

0 0

О 1

0 I

1

0 !

1

О. 0 а. 0 1 0 . 0 0 I

1 0 0 I I

) - 0 0 0 1

1,0 I О !

1 0 0 1

1 0 1 i - ) I t 1 1 ких ячеек (1+I)-й группы, выходы и первые информационные входы и-х логических ячеек которой (w h+t,...

It-1 ...,2 -h), выходы (l-l)-ro коммутатора соеди )ены соответственно с пер. вым и вторым ипформацнонными входами

w-х логических ячеек (1+!)-й группы, щ-й выход (л* !,2,...,2""2) (и-l)-го коммутатора соединен с (m+!)-м вихо!

О дом устройства z-й настроечный вхрд которого (в),n) соединен с настроечным входом ).-й логической ячейки z-й группы, первый и второй настроечные входы устройства соединены соответст5 венно с первым и вторым входами первого узла управления, первые выходы которого соединены соответственно с управляющими входами первого коммутатора, (1+!)-й настроечный вход устройства соединен с первым входом 1-ro узла управления, первые -выходы кото= рого соединены соответственно с упpaBlIHIortHHH входами 1-ro коммутатора., вторые входы 1-го узла управления соединены с вторыми выходамн (1"!)"го узла управления.

2, Устройство.flo ff ° I o T л H ч а ю щ е е с я тем, что каждая логическая ячейка содеркит элемент СЛОЖЕНИЕ ПО МОДУЛИ 2 и элемент И, первый вход которого соединен с первым информациойным входом логической ячейки, настроечный вход которой соединен с вторым входом элемента И, выход которого соединен с первым входом элемен" та СЛОЖЕНИЕ ПО МОДУЛ!0 2, второй вход которого соединен с вторым информационным входом логической ячейки, выход которой соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛ)0 2.

1550507

У г 3

3550507

f550507

1550507

®4

f5

УЮ

f6

f6

Фиг. 7

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

Редактор Л,Пчолннская Техред М.Дидык Корректор С.Шекмар

Заказ 1170 Тирам 562 - Подписное

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

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

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