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

коммутатора; на фиг. 6 - функциональная схема второго коммутатора; на , 7 - графы состояний второго коммутатора для рассматриваемого примера,,

Устройство для полиномиального разложения логических функций (фиг„1-) содерхнт 2 -4 логические ячейки щервой группы If-l4, 2B 4 логические ячейки второй группы ; 4 логические ячейки третьей груп

4V3.

5 1 з, 6,-6в,

V7,

выхоп 1 2 узла управления 41 и, 4, коммутатора 5 и 5,, информационных: входов настроечных входа дов . ч

Каждая логическая ячейка 1,2 и 3 {фяг.2) содержит два информационных Ј хода 9 и 10, настроечный вход 11, 1ыход 12, элемент И 13„ элемент 14 СЛОЖЕНИЕ ПО МОДУЛЮ 2.

Узел 4 управления содержит два элемента НЕ 15 и 1 б, элемент ИЛИ-НЕ 7, элемент ИЛИ 18, элемент И 19, .шемент 20 СЛОЖЕНИЕ ПО МОДУЛЮ 2 20 пять выходов 21-25. Узел управления 4 а содержит эле- ij-seHT ИЛИ 26, элемент НЕ 27, два эле- ента И 28 и 29 и три выхода 30-32.

Коммутатор 51 образуют четыре эле Йента И-ИЛИ 33-36.

Коммутатор 5 Ј состоит из шести (злемектой И-ИЛИ 37-42.

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

На j-й информационный вход ( „ 2,,,.,2П) устройства подается значение у: разлагаемой логической функци f«f (х,,х ,..., х ) на (j-lX-м наборе

х

х п -

Ј(х1sx а$ оt

Х«к

та К 5 ,х.

о « ,Х g

2k-4 Ж К

5 0

s(xr.

(О

множество чсевозможных по

1 « л ц- nca J Л

переменных х1,ха,. „. ,х п« На настроечные входы 7 устройства поступают компоненты двоичного вектора настройки

U «(Uf ,1,.,, ,Uh) , определяклцие переменные, по которьЫ осуществляется разложение,. При этом, если U 1 (,2,.,.,п)9 то выполняется разложение по переменной х.; если U.0, разложение по х не производится. На выходах 8 устройства последовательно формируются таблицы истинности логической функции s(,о о.,2 -1), на которые разлагаемся исходная функция Ј«Ј(х15х

5

парно различных конъюнкций ранга г (,1,..„ ,k) переменных х ,х . ,at, ,..,х , по которым осуп{ествля-ется конъюнктивно-полиномиальное разложение.

Значение функции vs(xf«-t «x . «

ХГ„(

S

(2 S+v+l)-M выходе устройства.

В табл.1 для представлены виды 2 8 возможных конъюнктивно-поли- номиальных разложений логической функции трех -переменных (xf,x,x )

S чл л (1

на v-м наборе переменных

(., ,0,о,х f p (,1,... ,2 -1; 0,1,0..,2к-1) формируется на

хг„

Известно, что произвольная логи- ческая функция переменных (x1,x ,. ...,xh) допускает конъюнктивно-поли- номиальное разложение по переменной х; () вида:

5

,,,.. ,xn) V0(x1, |...xn) @ х. V,(xf ,.,. .х

i-f

где (х. ..,xlVl,

X1-1

,хп) (2)

х

X

ли

Xh)

« xn)

И

f (x,,... jXjH ,OjX, i

iv,(x 1t.., ,x j.,,x fH, .. . ,хп)в

- (-( х.и) г/„ „

(j L x i-i

0,xi +1

X

() ® f (x, ,... ,x,.,, I,

5

x)«, ) « « ХП

Выполнение менным х f ,x

5

д

0

ЛП)

разложения (2) по пере- {f,xfi,...,XfK дает возможность представить произвольную логическую функцию f(х,,х1,..,х„) в виде полиномиальной суммы (1) логических функций n-k переменных vs(xj

х|...

хр „) причем Х|

и«

Г

мз

f причем i к. i

Г.-1 1 ГНГ

х txi xnJ/lx (1 х г

.xt,«

Исходным для построения таблиц истинности функций является вектор зна(У,У, ... ,уг Ja(y

функции

чении w ...,У°

о i разлагаемой

i

f«f(x«

хд,...,хь)„ Полагаем, что разложение

а

4 мпроизводится последовательно по переменным К(,..,,Х(. Далее формируется последовательность векторов w,Wj,..,,wk, компоненты которых вычисляются согласно следующим рекуррентным соотношениям:

v h-

(3)

FV ©V () ijm«t (inlm

где i-0,1 ,. , . ,

t-l,2,...,m; ,2,...,k.

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

&ftit

где /3,, и /Jj - соответственно сигналы на первом и втором информационных входах логической ячейки; U. (,.,...

..п) - сигнал на настроечном

входе логической ячейки (индекс i указывает, , что ячейка гсаходится в i-м ярусе и на нее подается i-й компонент вектора нас-тройки U (U, ри...,Пп); ai - сигнал на выходе логической ячейки.

Как отмечалось выше, если U, 1 , то разложение осуществляется по переменной x.(lii,4n), т.е. ,

НЫЙ ДВОИЧНЫЙ КОД (Z У , 2 ,..., 7.

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

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

,z V 7 слрлл к 1чне:

10

(41

1, если U,Uj ,f., . ,и,., или z , если I U q-l; ;

/} J о

1 ; ,3,.,. ,п; ,3q.

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

Тогда (А) можно представить в пн- де:

rov

25 (5)

,3,...,П;

i где F., F., (1,ДГг 9, .. ,U .Л - Аук20

J« Следовательно, rf p, ©/14 3Q даменталыше (элементарные) симмет- н 1-й ярус логических ячеек обеспечи- рические булевы функции, зависящие

от переменных t ,U4 ,. , . ,11 ., , где ,1 . о. ,q-l . При этом F,вает преобразование входного вектора значений согласно (3). При переменная х -, принадлежит множеству

p,---Qt 1 ,. о. ,q-l . При этом Г , -1 тогда и олько тогда, когда . . ,+

.х1к+а х Ьй ярус Л0 35 /

гических ячеек обеспечивает транзит- Лункции Fp (, 1 ,3.. ,Р) поступают на вторые входы Р-го узла управления (,3,...п-2) со вторых выходов (P-l)-ro узла управления и ис- д0 пользуются для формирования сигналов .(5). В свою очередь, на своих

ну передачу входного вектора значений на выход.

Для выделения из векторов w,,;,., ,..,WH последовательных кортежей значений функций sслужат коммутаторы 5 (их общее количество п-1).

Если сумма значений первых q компонент U1 ,U7,... ,11 (,3,... ,п)

вектора настройки U равна 5. и,Кл,

ffl«t

то (q-l)-ft коммутатор 5 обеспечивает формирование на своих выходах упорядоченного вектора значений, в котором таблицы истинности промежуточных функций разложения (,1,... . . ), зависящих от kd переменных, располагаются последовательно в порядке возрастания к меров функции, т.е. V. vV , ,.

Для управления коммутаторами используются узлы 4 управления. Причем каждому (q-O-му коммутатору (, 3,««.,п) соответствует (q-l)-ft узел

45

вторых выходах Р-й узел управления реализует исходя из F р пункции

6

F P.|( I о которые поступают на вторые входы (Р+)-го узла управления:

Ь Fp, если

6 -Ь 6 если

50

.если б Р+1.

(6)

55

F р U p+1 Fp

П F6 1 ир«, tf ,

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

z;-u,vujj J

zJ-U,

504076

управления, который на ;торпых выходах формирует уннтарннП q-pa:-p«

НЫЙ ДВОИЧНЫЙ КОД (Z У , 2 ,..., 7. ).

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

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

,z V 7 слрлл к 1чне:

(41

1, если U,Uj ,f., . ,и,., или z , если I U q-l; ;

/} J о

,3,.,. ,п; ,3q.

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

Тогда (А) можно представить в пн- де:

rov

(5)

,3,...,П;

i где F., F., (1,ДГг 9, .. ,U .Л - Аук

даменталыше (элементарные) симмет- рические булевы функции, зависящие

5

вторых выходах Р-й узел управления реализует исходя из F р пункции

6

F P.|( I о которые поступают на вторые входы (Р+)-го узла управления:

Ь Fp, если

6 -Ь 6 если

0

.если б Р+1.

(6)

F р U p+1 Fp

П F6 1 ир«, tf ,

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

z;-u,vujj J

zJ-U,

,u,vu2;

, Ф U4;

Fj-U,U,;

z -Fjvfis;

«sl-UjF1,;

.

Схемы первого 4 и второго 4 уз- XJOB управления построены согласно (7) н (8)в В устройстве ()ft коммутатор содержит 2 п-2 элементов 1, (q«2,3,,..,n)s где , ,.., q - количество двухвходовых элементов И, выходы которых подключаются к входам соответствующего эле- Цента ИЛИ.

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

(7)коммутатора 5г для рассматриваемого примера, указываются направления передачи информации при различных

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

(8)|На основе графов однозначно восп| гоиэ- водится функциональная схема соответЮ ствующих коммутаторов.

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

f (x, ,x7,x3)x1xtx3vx,x3.

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

4V(,l,...,.

20

Как следует иэ табл.2, имеет место

Как следует иэ табл.2, имеет место

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

Ј (х ,xl,x3)x1xax3vx1Xj

xtx3 © ,УХ s)

(x, ® x 3) Ф хгх,хэ

© xi(x1vx-t)

© х,хэ Ф x, Ф х,хгхэ

хг Ф х}хг © х,хг Ф х,х3х,

х, © хэ @ хгх1 © х7х3х,я

1 © хэ © х5®:сгх3Ф ,®

Таким образом, устройство позволяет выполнять 2 конъюнктивно-полино- Циальных разложений.

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

1 Устройство для полиномиального разложения логических функдий, со- держащее п (п - количество переменных разлагаемой логической функции) групп логических ячеек по ячеек в каждой, первый информационный вход 1-й логической ячейки ( ,.„... ,2й 1) первой группы соединен с i-м информационным входом устройства, ()информационный вкод которого соединен с вторым информационным входом 1-й логической ячейки первой группы, пер- вый информационный вход j-й логической ячейки q-й группы (,2,..,,fc; ,3,,,,n; ) соединен с j-м информационным входом устройства, (2n +j}-Pi информационный вход кото- рого соединен с вторим информационным входом j-й логической ячейки q-й группы, первый информационный вход , )-ft логической ячейки q-й

5

0 5 «

группы соединен с выходом (2 -2t+ +j)-ft логической ячейки (q-O-й группы, выход ( -t+j)-8 логической ячейки которой соединен с вторым информационным входом (2 n -t+j)-ft логической ячейки q-й группы, первый информационный вход устройства соединен с первым выходом устройства, 2 -и выход которого соединен с выходом 2 -и логической ячейки п-й группы, отлич ающееся тем, что, с целью расширения функциональных возможностей за счет конъюнк- тивно-полиномиального разложения логических функций по произвольным переменным, содержит n-l узлов управления и п- коммутаторов, информационные входы первого из которых соединены соответственно с выходами первых 2й логических ячеек первой группы и выходами первых 2 логических ячеек второй группы, информационные входы 1-го коммутатора ( 3,...,п-1) соединены соответственно с выходами v-x логических ячеек 1-й группы -2 ,„.,, h -2П--М), выходами первых h логичес

ких ячеек (1-Н)-й группы, выходы и первые информационные входы w-x логических ячеек которой (,,.. . . , -h), выходы (i-l)-ro комму татора соедн тены соответственно с первым и вторым информационными входами w-x логических ячеек ()-Й группы, m-й выход (го«1,2,.,.,) (n-l)-ro коммутатора соединен с (т+)-м выходом устройства z-й настроечный вход которого (ив1,п) соединен с настроечным входом i-й логической ячейки z-й группы, первый и второй настроечные входы устройства соединены соответст- венно с первым и вторым входами первого узла управления, первые выходы которого соединены соответственно с управляющими входами первого коммутатора, (1+1)-й настроечный вход устрой- ства соединен с первым входом 1-го

Таблица 1

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

Таблица2

Таблица истинности логических функций ys(, r,,..,2 -I; kin-3) для рассматриваемого примера

узла управления, первые -выходы рого соединены соответственно с уп- равляюаими входами 1-го коммутатора,, вторые входы 1-го узла управления соединены с вторыми выходами (1-1 )то узла управления.

2, Устройство по п. I, отличающееся тем, что каждая логическая ячейка содержит элемент СЛОЖЕНИЕ ПО МОДУТЮ 2 и элемент И, первый вход которого соединен с первым информационным входом логической ячейки, настроечный вход которой соединен с вторым входом элемента И, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2, второй вход которого соединен с вторым информационным входом логической ячейки, выход которой соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2.

//

Фие.1

13

t:

№

5ifJ

Г

7г

Фиг.З

Г)

JS

W

/з

20

№

17

25

21

гг

Ј

L.J

фиг А

f///

Фиё.5

32 31 30

Фаг. 6

tf.

1S2+

V

«

V

«f

is,

+ f6,

,

-«t %

%

°