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

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

Цель изобретения - упрощение устройства за счет уменьшения аппаратурных затрат.

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

Устройство (фиг, 1) содержит блок 1 памяти, узел 2 пересечения, узел 3 коммутации, группу информационных входов 4, прямой выход 5, инверсный выход 6, два входа 7 и 8 разрешения суммирования, вход 9 разрешения вычитания, тактовый вход 10, вход 11 разрешения сброса, два входа 12 и 13 разрешения записи, два входа 14 и 15 разрешения чтения, две группы выходов 16 и 17 блока 1 памяти, две группы выходов 18 и 19 узла 3 коммутации, вход 20 разрешения обнуления.

Блок 1 памяти (фиг. 2) содержит два операционных запоминающих устройства 21 и 22, два 23 и 24 реверсивных счетчика и три элемента И 25-27.

Узел пересечения 2 (фиг. 3) содержит группы элементов неравнозначности 28|- 28п (п - количество аргументов), группу элементов И-НЕ 29|-29п, элемент И 30, триггер 31.

Узел коммутации 3 (фиг. 4) содержит элемент ИЛИ 32 и дае группы элементов И ЗЗгЗЗп и 34|-34г).

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

В блок 1 памяти перед началом вычисления записывается значение D-покрытия (или R-покрытме) функции р .

D-покрытие (R-покрытие) функции р - это представленная в кубической форме ми- нимальная дизъюнктивная нормальная форма (МДНФ) прямой функции (инверсная функции) МДНФ прямой функции р (инверсной функции (J5) содержит все наборы, пз которых функция р принимает значение Логической 1 (логического О).

D-покрытие (R-покрытие) состоит из то (гпя) кубов, число которых равно числу ммпликант МДНФ прямой функции р(ш- версной функции tp }

D {didjodmD };

,.., ПК - rmR)

Число n компонент куба djo (пк) равно числу переменных МДНФ, а значениями компонент куба могут быть только три символа 0, 1, X, где Х€.{0, 1}. Каждый куб diofnR) соответствует одной импликанте МДНФ прямой функции (f (инверсной функции ф) таким образом, что единичное (нулевое) значение компоненты куба соответствует прямому (инверсном/) значению переменной в импликанте МДНФ.

Пусть, например, МДНФ прямой функции ср (а, Ь, с, е) инверсной функции tp (a, Ь. с, е) имеет вид

р (а, Ь, с, e)ab V се; р (а, Ь, дз) ас V аё V 5с V be Тогда соответствующие МДНФ указанных функций D-покрытие и R-локрытие име- ют вид

0

D

а Ь с е ГМ К х I |ХХ 01 J У

R

а Ь с е

О X 4 X О X О X 0 4 X

х о х о

Для представления кубов покрытий D и R в двоичном алфавите компоненты кубов djo(rjR) кодируются согласно табл, 1,

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

Пусть на некотором входном наборе L аргументов функции на выходе комбинационной схемы (КС) формируется значение лог. 1, тогда выполняемую КС операцию можно интерпретировать как установление

принадлежности входного набора L множеству наборов, на которых функция р принимает значение лог. 1.

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

принадлежности входного набора L указанному множеству наборов может быть выполнено аналитически с помощью операции пересечения кубов. Операция пересечения куба ...an и куба ...bn обозначается как и служит для выделения куба

c CiC2Сп. являющегося общей частью

куоов а и Ь. Значение компоненты d определяется выражением Ci ainbi().

Значения компоненты Ci з зависимости

от значений компоненты ai и Ы приведены в табл. 2. Знак $ означает пустое пересечение. Например, для куба и хуб С равен

X О п X /1 О

1 4 О

Входной набор L будет принадлежать множеству наборов, на которых функция р принимает значение логической 1 (логи4ecKoro d), если имеет место ьзпустое пере- сечение набора L хотя бы с одним кубом D-покрытия (R-покрытия)

(1« если L n djD для любого JD

L)- i

LO, если Ln TJR рдля любого JR,

где L(H,..., li...., In);

djD(dijD,.,., dijodnjD): ,mD)

rjR4ri)R HJR mjR),mR)

HanpiWip. набор LHD001 принадлежит множеству лаборов, на которых функция р(а, Ь, с, е) принимает единичное значение, так как

0001 i X X

п

0

О 004 X X 04 0004

Операция пересечения входного набора L с кубами D-покрытия (R-покрытия), записанных в блоке 1 памяти выполняется в узле 2 пересечения. Указанная операция пересечения выполняется за jo OR) тактов b каждом такте из блока 1 памяти поступает один куб D-покрытия (R-покрытия). Если на JD(JR) такте в узле 2 пересечения фиксируется непустое пересечение.на прямом выходе 5 устройства формируется единичный сигнал. Это свидетельствует, что на входном наборе L функция р , представленная в блоке 1 памяти D-покрытием (R-покрытием), принимает значение логической 1 (логического О). После появления единичного сигнала на выходе 5 устройства с оставшимися кубами D-покрытия (R-покрытия) операция пересечения не производится.

Если по истечении гпо(тр) тактов на прямом выходе 5 устройства остается нулевой сигнал, это означает, что на входном наборе L функция р , представленная в блоке 1 памяти D-покрытия (R-покрытием) принимает значение логического О (логической 1).

Перед началом вычисления триггер 31 узла 2 пересечения и реверсивные счетчики 23 и 24 блока 1 памяти обнуляются путем подачи единичного сигнала.

В блок 1 памяти D-покрытие (R-покры- тие) записывается в два этапа. На первом этапе при наличии единичного сигнала на первом входе 12 разрешения записи в первое операционное запоминающее устройство 21 записываются с информационных входов группы 4 через узел 3 коммутации

компоненты dljo (HJR) ,...то; ,...,mR) D-покрытия (Р-покрытмя), т. е. первая половина D-покрытия (R-покрытия). На втором этапе записи, при наличии сигнала разрешения записи на втором зходе 13 разрешения записи, во второе операцион5

ное запоминающее устройство зап /.оыаа

ются компоненты dl jo (rl jR), (jo 1rrm,

JR 1FDR) D-покрытия (R-покрытия) т. е.

вторая половина D-покрытия (R-покрытия), В блоке 1 памяти используется принцип

магазинной адресации адреса, по которым и записывается, считывается информация в первое и второе операционные запоминающие устройства 21 и 22, формирующаяся соответственно реверсивными счетчиками 23 и 24. В режиме записи информации сигналы тактового входа 10 при наличии единичного сигнала на первом и втором входах 7 и 8-разрешения суммирования поступают на суммирующие входы соответственно реверсивного счетчика 23 и 24. В режиме считывания информации сигналы с тактового входа 10 при наличии единичного сигнала на входе разрешения вычитания 9 поступа- ют одновременно на вычитающие входы реверсивных счетчиков 23 и 24.

Результат пересечения компонент dijD(rijR) и ||, формирующийся в узле 2 пересечения, приведен в табл. 3. 5 Компоненты входного набора L поступают на первые входы элементов неравнозначности, на вторые входы которых поступают компоненты d ijD(iJjR) куба D- покрытия (R-покрытия) на вторые входы элементов И-НЕ поступают компоненты d SpO R) куба d JD(HR) D-покрытия (R- покрытия).

При наличии непустого пересечения

входного набора с кубом djo(rjR) на выходе

элемента ИЗО и на прямом выходе триггера

31 формируется сигнал единичного уровня.

В качестве примера рассмотрим реализацию устройством функции р abvce ( )

0

0

Тогда Е

5

ГИхХ) . XX04

R

ОХ X OX XQ

Х01Х

v хохо В результате кодирования получим

р f« 10 «О 1 |(0 10 01 (( J

1 W Т|((1 т, fnool MUO,)

Пусть набор L имеет вид .

Результат пересечения набора L с пер- выми кубами о -покрытия и о -покрытия является непустым (на выходах всех элементов И-НЕ 29i-294 формируется единичный сигнал) и, следовательно, на выходе 5 устройства формируется сигнал единично- го уровня.

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

1. Устройство для вычисления булевых функций, содержащее блок памяти, причем первый и второй входы разрешения записи

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

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

которых соединены соответственно с выходами первого и второго реверсивных счетчиков, суммирующие входы которые соединены с выходами соответственно первого и второго элементов И, первые входы которых соединены с первым входом третьего элемента И и тактовым входом блока, вход разрешения вычитания которого соединен с вторым входом третьего элемента

И, выход которого соединен с вычитающими входами первого и второго реверсивных счетчиков, входы сброса которых соединены с входом разрешения обнуления блока, первый и второй входы разрешения суммирования которого соединены с вторыми йхо- дами соответственно первого и второго элементов И,

3. Устройство по п. 1,отличающее- с я тем, что узел пересечения содержит группу элементов неравнозначности, группу элементов И-НЕ, элемент И и триггер, причем 1-й информационный вход первой группы соединен с первым входом 1-го элемента неравнозначности группы ( п - количество аргументов функции), выход которого соединен с первым входом i-ro элемента И-НЕ группы, выход которого соединен с 1-м входом элемента И, выход которого соединен с входом установки в 1 триггера,

прямой выход которого соединен с прямым выходом узла, инверсный выход которого соединен с инверсным выходом триггера, вход установки в О которого соединен с входом установки в О узла, i-й информационный вход второй группы соединен с вторым входом i-ro элемента И-НЕ группы, 1-й информационный вход третьей группы соединен с вторым входом 1-го элемента неравнозначности группы.

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

управляющими входами узла, третий управляющий вход которого соединен с первым входом 1-го элемента И первой группы, второй вход которого соединен с i-м информационным входом узла и первым входом 1-го

элемента И второй группы, вторые входы элементов И второй группы соединены с выходом элемента ИЛИ, выходы элементов И первой и второй групп соединены с выходами соответственно первой и второй групп

узла.

Таблице 1

Примечание

-z-VZi

«а

Z-,-(e; nd ;iDnd Jiolu(8{n П Лцо)- (Ј; © d ;JD } П d ;JD для D - покрытия;

Z-,-(Mr;iRn

;)к)п JR для R - покрытие

Таблица 2

Таб лица 3

7 7

11 11 26

.

Щf fe

/7

/7

tf /ffГ7.

Фаг. 2

.

rt

J/

.5

5

фие&