Устройство для вычисления булевых функций

Устройство для вычисления булевых функций

Иллюстрации

Показать все

Реферат

 

СОЮЗ СОВЕТСКИ.:.

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (sl)s 6 06 F 7/00

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

flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

_#_7,У 5 10 /ÃQ14.б

1 (21) 4656947/24 (22) 27.12.88 (46) 07.10.91, Бал, М 37 (71) Винницкий политехнический институт (72) В. П. Семеренко (53) 681.3(088,8) (56) Авторское свидетельство СССР, М 1608641, кл.G 06 F 7/00, 30.11.88.

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

М 1084782, кл. 6 06F 7/00, 1982. (54) Уст1РОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к автоматике и вычислительной технике и предназначено

„„SU „„1683002 А1 для вычисления значения логической функции на входном наборе ее аргументов. Цель изобретения — упро@ение устройства за счет уменьшения аппаратурных затрат. Устройство содержит блок памяти 1, узел пересечения 2 и узел коммутации 3. В блок памяти 1 записывается значение кубического представления функции, подаваемого в узел пересечения 2, где производится идентификация входного набора множеству наборов, на которых функция принимает значение логической единицы. 3 з, и. ф-лы, 3 табл., 4 ил.

1683002

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

На фиг, 1 приведена структурная схема устройства для вычисления булевых функций на фиг. 2 — функциональная схема Gnoка памяти; на фиг. 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! — 29n, элемент И ЗО, триггер 31.

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

33;-ЗЗ и 34(-34я, Устройство работает следующим обраВ блок 1 памяти перед началом вычисления записывается значение 0-покрытия (или R-покрытие) функции р

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

0-покрытие (Я-покрытие) состоит из ар (ma) кубов, число которых равно числу импликант МДНФ прямой функции 2(инверсной функции P )

0=(d1Ä... diO,..., dms

Й=(Г1..., rjR,..., r"mR).

Число и компонент куба б1о (riR) равно числу переменных МДНФ, а значениями компонент куба могут быть только три символа О, 1, Х, где Хб.(0;1). Каждый куб d!p(rip) соответствует одной импликанте МДНФ прямой функции р (инверсной функции @ таким образом, что единичное (нулевое)

5 значение компоненты куба соответствует прямому (инверсному) значению переменной в импликанте МДНФ.

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

p(a, Ь, с,е) = ас V ае \/ Рс V be

Тогда соответствующие МДНФ указанных функций 0-покрытие и R-покрытие име15 ют вид

abce а Ьсе (lXX1 aX3Х = XX> 1 хо х хрхо

Для представления кубов покрытий 0 и

R в двоичном алфавите компоненты кубов

dig(riR) кодируются согласно табл. 1, 25 Каждое из покрытий 0 и R однозначно определяет функционирование устройства, поэтому в блок памяти записывается только одно из них, а именно то покрытие, которое содержит меньшее число кубов.

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

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

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

40 принадлежности входного набора L указанному множеству наборов может быть выполнено аналитически с помощью операции пересечения кубов. Операция пересечения куба 8=8182".àn и куба Ь=Ь1Ь2...bn обозначается как с-anb и служит для выделения куба

С=-C1C2.....Ñn, ЯВЛЯЮЩЕГОСЯ ОбЩЕй ЧаСтЬЮ кубов а и b. Значение компоненты С! определяется выражением Ci=aiabi(i=1,..., n).

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

50 от значений компоненты ai и Ы приведены в табл. 2. Знак ф означает пустое пересечение. Например, для куба а=1ХО и Ь=Х10 куб

C равен

X 0

X 4 О

«о

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

0-покрытия (R-покрытия) l, если 1 „др 4фдля любого jo 6-)

О, если L„ãlR4 фдля любого Jq, где L=(lI,..., lI,..., 1};

dlogd>lo,..., dIlo,..., благо):. Jo+1,mD)

jR (ã1jR,..., I.IJR,..., гпту) )в=(1,mR)

Например, набор L=0001 принадлежит множеству наборов, на которых функция фа, b., c, е) принимает единичное значение, так как

OOOO 0003

ХХО< ф ООО

Операция пересечения входного набора L с кубами 0-покрытия (R-покрытия), записанных в блоке 1 памяти выполняется в узле 2 пересечения. Указанная операция пересечения выполняется эа Jo (JII) тактов b каждом такте из блока 1 памяти поступает .один куб 0-покрытия (R-покрытия). Если на

JoOR) такте в узле 2 пересечения фиксируется непустое пересечение,на прямом выходе

5 устройства формируется единичный сигнал. Это свидетельствует, что на входном наборе L функция у, представленная в блоке 1 памяти 0-покрытием (R-покрытием}, принимает значение логической "1" (логического "0"). После появления единичногосигнала на выходе 5 устройства с оставшимися кубами 0-покрытия (R-покрытия) операция пересечения не производится.

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

Перед началом вычисления триггер 31 узла 2 пересечения и реверсивные счетчики

23 и 24 блока 1 памяти обнуляются путем подачи единичного сигнала.

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

)я1...„mR) 0-покрытия (R-покрытия), ",. e, первая половина 0-покрытия (R-покрытия).

На втором этапе записи, при наличии сигнала разрешения записи на втором входе 13 разрешения записи. во второе операционное запоминающее устройство зап;; ыва ются компоненты dl )o (rllR), (Jo=1,...,mo, )к=1,...,тв} 0-покрытия (R-покрытия) т. е. вторая половина D-покрытия(Н-покрытия).

В блоке 1 памяти используется принцип магазинной адресации адреса, по которым и записывается, считывается информация в первое и второе операционные запоминающие устройства 21 и 22, формирующаяся соответственно реверсивными счетчиками

23 и 24. В режиме записи информации сигналы тактового входа 10 при наличии единичного сигнала на первом и втором входах

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

dIlo(rile} и lI, формирующийся в узле 2 пересечения, приведен в табл, 3.

Компоненты входного набора L поступают на первые входы элементов 281-28> неравнозначности, на вторые входы которых поступают компоненты б;р(р) куба Dпокрытия (R-покрытия) на вторые входы элементов И вЂ” НЕ 29> — 29> поступают компоненты d" iр(IJR) куба d о(гр) 0-покрытия (Rпокрытия).

При наличии непустого пересечения входного набора Lc кубом djo(rjR} на выходе элемента ИЗО и на прямом выходе триггера

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

Б качестве примера рассмотрим реализацию устройством функции р =abduce (и-4;

40 пц;>=2) тогда r>- хХ1 а= ОХ Х

)Х,,О," ) ОХХО

Х01 Х

ХОХО

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

Г и

$

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

Результат пересечения набора 1 с первыми кубами D ïoêðûòèÿ и D -покрытия явI II ляется непустым (на выходах всех элементов И-НЕ 291 — 29 формируется единичный сигнал) и, следовательно, на выходе

5 устройства формируется сигнал единично- го уровня, Формула изобретения

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

1683002

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

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

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

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

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

И-HE группы, выход которого соединен с

i-м входом элемента И, выход которого соединен с входом установки в "1" триггера, прямой выход которого соединен с прямым выходом узла, инверсный выход которого соединен с инверсным выходом триггера, вход goòàíoâêè в "0" которого соединен с входом установки в "0" узла, 1-й информационный вход второй группы соединен с вторым входом 1-ro элемента И вЂ” НЕ группы, i-й информационный вход третьей группы соединен с вторым входом i-го элемента неравнозначности группы.

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

И первой и второй групп соединены с выходами соответственно первой и второй групп узла.

1683002

Таблица 1

Таблица 2

Тэб лица 3

Примечание

z-М;

1-

z,=(e,nd ;; ïd; ; о(Е,пд;; nd )=(Р; И d,;;„1 Й d;" ð -длн Π— покрытнн;

, =(,,и „, и,.,, u(P; n F; п т,; Ä (=

И

= (jQ j jgI Л т;;к доя и — покрытно

1683002

1683002

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

Редактор С. Патрушева Техред M.Моргентал Корректор С. Шевкун

Заказ 3413 Тираж Подписное

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

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

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