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

(51)5 6 06 Р 7/О БРЕТЕ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР ПИСАНИЕ И СКОМУ СВИДЕТЕЛЬСТВУ(71) Винницкий политехнический институт (72) В. П. Семеренко(56) Авторское свидетельство СССР, В 1608641, кл.о 06 Р 7/ОО, 30.11.88.Авторское свидетельство СССР М 1084782, кл, 6 06 Р 7/00, 1982. (54) УСТРОйстно ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ(57) Изобретение относится к автоматике и вычислительной технике и предназначено для вычисления значения логической функции на входном наборе ее аргументов. Цель изобоетения - упроЩение устройства за счет уменьшения аппаратурных затрат. Устройство содержит блок памяти 1, узел пересечения 2 и узел коммутации 3, В блок памяти 1 записывается значение кубического представления функции, подаваемого в узел пересечения 2, где производится идентификация входного набора множеству наборов, на которых функция принимает значение логической единицы. 3 3, и, ф-лы, 3 табл.,4 ил.Изобретение относится к автоматике ивычислительной технике и предназначенодля вычисления значения логической функции на входном наборе ее аргументов,Цель изобретения - упрощение устройства за счет уменьшения аппаратурных затрат,На фиг, 1 приведена структурная схемаустройства для вычисления булевьх функций на фиг. 2 - функциональная схема блока памяти; на фиг. 3 - функциональнаясхема узла пересечения; на фиг, 4 - функциональная схема узла коммутации,Устройство (фиг. 1) содержит блок 1 памяти, узел 2 пересечения, узел 3 коммутации, группу информационных входов 4,прямой выход 5, инверсный выход б, двавхода 7 и 8 разрешения суммирования, вход9 разрешения вычитания, тактовый вход 10,вход 11 разрешения сброса, два входа 12 и13 разрешения записи, два входа 14 и 15разрешения чтениядве группы вьходов 1 би 17 блока 1 памяти, две группы выходов 18и 19 узла 3 коммутации, вход 20 разрешенияобнуления.Блок 1 памяти (фиг, 2) содержит дваоперационных запоминающих устройства21 и 22, два 23 и 24 реверсивных счетчика итри элемента И 25 - 27.Узел пересечения 2 (фиг. 3) содержитгруппы элементов нерааноэначности 2828 п (и - количество аргументов), группу элементов И - НЕ 29 - 29 п, элемент И 30, триггер31.Узел коммутации 3 (фиг, 4) содержитэлемент ИЛИ 32 и дае группы элементов ИЗЗ;-ЗЗп и 34-34 я,Устройство работает следующим обраВ блок 1 памяти перед началом вычисления записывается значение О-покрытия(или Я-покрытие) функции (О-покрытие (Я-покрытие) функции р -это представленная а кубической форме минимальная дизъюнктивная нормальнаяформа (МДНФ) прямой функции (инверснаяфункции) МДНФ прямой функции р (инверсной функции р ) содержит все наборы,а которых функция у принимает значениелогической "1" (логического "О").О-покрытие (Я-покрытие) состоит изгпо (ар) кубов, число которых равно числуимпликант МДНФ прямой функции р(инверсной функции у )О=(б 1 б 1 о дноЯ=(г., гй гп 1 й),цисло и компонент куба 010 (гав) равночислу переменных МДНФ, а значениямикомпонент куба могут быть только три символа О, 1, Х, где Хб.(0;1). Каждый куб с 3 о(гр) соответствует одной импликанте МДНФ прямой функции р (инверсной функции Дтаким образом, что единичное (нулевое) 5 значение компоненты куба соответствуетпрямому (инверсному) значению переменной в импликанте МДНФ.Пусть, например, МДНФ прямой функции р (а, Ь, с, е) инверсной функции р (а, 10 Ь., с, е) имеет видр (а, Ь, с, е)=аЬ Ч се;.р(а, Ь, с,е) = ас/ ае Ч Рс ЧЬеТогда соответствующие МДНФ указанных функций О-покрытие и Я-покрытие име ют виддосе а Ьсе1 ХХ ОХАХ ХхсОх ХО холх ХОХО Для представления кубов покрытий О и Я в двоичном алфавите компоненты кубов О;р(гк) кодируются согласно табл, 1, 25 Каждое из покрытий О и Я однозначно определяет функционирование устройства, поэтому в блок памяти записывается только одно из них, а именно то покрытие, которое содержит меньшее число кубов. ЗО Пусть на некотором входном набореаргументов функции р на выходе комбинационной схемы (КС) формируется значение лог, "1", тогда выполняемую КС операцию можно интерпретировать как установление 35 принадлежности входного наборамножеству наборов, на которых функция р принимает значение лог, "1",При использовании кубического представления булевых функций установление 40 принадлежности входного наборауказанному множеству наборов может быть выполнено аналитически с помощью операции пересечения кубов. Операция пересечения куба а=а 1 агап и куба Ь=Ь 1 Ь 2 Ьп обознача ется как с=апЬ и служит для выделения куба с=-С 1 С 2"С, являющегося общей частью кубов а и Ь. Значение компоненты С определяется выражением С=апЬ (1=1 и).Значения компоненты С в зависимости 50 от значений компоненты а и Ы приведены в табл. 2. Знак ф означает пустое пересечение. Например, для куба а=1 ХО и Ь=Х 10 куб С равен4 Х 0 55 Х 4 0Л 0Входной наборбудет принадлежать множеству наборов, на которых функция р принимает значение логической "1" (логи 1683002ческого О), если имеет место нпустое пересечение набора . хотя бы с одним кубом О-покрытия (В-покрытия)1, если 1 бо 4 фдля любого )о6-)О, если .где фдля любого )в, где =(11 1о); бо=(био Фо бпо):. )о=1,п)О) г)в"(г 1 в, пв гпту) )в=(1,аВ) Наприм;р., набор =0001 принадлежит множеству наборов, на которых функция фа, Ьс, е) принимает единичное значение, тэк как ООО 1 ООО 1 1 ХХ ХХ 01ф Ооо 1 Операция пересечения входного набора . с кубами 0-покрытия (В-покрытия), записанных в блоке 1 памяти выполняется вузле 2 пересечения. Указанная операция пересечения выполняется эа )о ) тактов Ькаждом такте из блока 1 памяти поступаетодин куб 0-покрытия (В-покрытия). Если на)оЦв) такте в узле 2 пересечения фиксируется непустое пересечение,на прямом выходе5 устройства формируется единичный сигнал. Это свидетельствует, что на входномнаборефункция у, представленная вблоке 1 памяти О-покрытием (В-покрытием),принимает значение логической "1" (логического "0"), После появления единичного сигнала нэ выходе 5 устройства с оставшимисякубами 0-покрытия (В-покрытия) операцияпересечения не производится.Если по истечении юо(ав) тактов напрямом выходе 5 устройства остается нулевой сигнал, это означает, что на входномнаборе . функция р , представленная вблоке 1 памяти 0-покрытия (В-покрытием)принимает значение логического "0" (логической "1"),Перед началом вычисления триггер 31узла 2 пересечения и реверсивные счетчики23 и 24 блока 1 памяти обнуляются путемподачи единичного сигнала.В блок 1 памяти 0-покрытие (В-покрытие) записывается в два этапа, На первомэтапе при наличии единичного сигнала напервом входе 12 разрешения записи в первое операционное запоминающее устройство 21 записываются с информационныхвходов группы 4 через узел 3 коммутациикомпоненты бо (гв): о=1.,яо:)в 1 щв) О-покрытия (В-покрытия), " е,первая половина О-покрытия (В-покрытия).На втором этапе записи, при наличии сигнала разрешения записи на втором входе 13разрешения записи, во второе операционное запоминающее устройство зап ыва ются компоненты бо (гв), о=1,".,гпо, )в=1вв) О-покрытия (В-покрытия) т. е. вторая половина О-покрытия(В-покрытия),В блоке 1 памяти используется принцип магазинной адресации адреса, по которым и записывается, считывается информация в первое и второе операционные запоминающие устройства 21 и 22, формирующаяся соответственно реверсивными счетчиками 23 и 24. В режиме записи информации сигналы тактового входа 10 при наличии единичного сигнала на первом и втором входах 7 и 8.разрешения суммирования поступают на суммирующие входы соответственно реверсивного счетчика 23 и 24, В режиме считывания информации сигналы с тактового входа 10 при наличии единичного сигнала на входе разрешения вычитания 9 поступают одновременно на вычитающие входы реверсивных счетчиков 23 и 24,Результат пересечения компонент бо(ов) и 1 ь формирующийся в узле 2 пересечения, приведен в табл, 3.Компоненты входного наборапоступают на первые входы элементов 281-28 неравнозначности, на вторые входы которых поступают компоненты б цо(р) куба 0- покрытия (В-покрытия) на вторые входы элементов И - НЕ 291 - 29 П поступают компоненты б цофв) куба б о(гв) О-покрытия (В- покрытия).При наличии непустого пересечения входного набора Ь кубом бо(бв) на выходе элемента ИЗО и на прямом выходе триггера 31 формируется сигнал единичного уровня.Б качестве примера рассмотрим реализацию устройством функции р =аЬчсе (и; 40во=2) Тогда О 11 хМ 1 й= ОХ Х ХХО ) ОХХО Х 01 Х ХОХО В результате кодирования получим . 45Гп цво 1 3 м1 о д в цИ,.",1 С.", Пусть набор . имеет вид =1111. Результат пересечения набора 1. с первыми кубами О -покрытия и О -покрытия яв 1 в ляется непустым (на выходах всех элементов И-НЕ 291 - 29 формируется единичный сигнал) и, следовательно, на выходе 5 устройства формируется сигнал единично-го уровня, Формула изобретения 1, Устройство для вычисления булевых функций, содержащее блок памяти, причем первый и второй входы разрешения записи10 15 20 25 30 35 40 45 50 устройства соединены соответственно с первым и вторым входами разрешения записи блока памяти, первый и второй входы разрешения чтения которого соединены соответственно с первым и вторым входами разрешения чтения устройства, о т л и ч а ющ е е с я тем, что, с целью упрощения за счет уменьшения аппаратурных затрат, оно содержит узел пересечения и узел коммутации, причем информационные входы группы соединены с информационными входами узла коммутации, первый и второй управляющие входы которого соединены соответственно с первым и вторым входами разрешения суммирования устройства и с первым и вторым входами разрешения суммирования блока памяти, вход разрешения вычитания которого соединен с третьим управляющим входом узла коммутации и входом разрешения вычитания устройства, тактовый вход и вход разрешения обнуления которого соединены соответственно с тактовым входом блока памяти и входом разрешения обнуления блока памяти, выходы первой и второй групп блока памяти соединены с информационными входами соответственно первой и второй групп узла пересечения, прямой и инверсный выходы которого соединены соответственно с прямым и инверсным выходом устройства, вход разрешения сброса которого соединен с входом устанорки в "О" узла пересечения, информационные входы третьей группы которого соединены с выходом первой группы узла коммутации; выход второй группы которого соединен с информационным входом блока памяти.2.Устройство поп.1, отл ича ю щеес я тем, что блок памяти содержит два операционных запоминающих устройства, два реверсивных счетчика и три элемента И, причем информационные входы первого и второго операционных запоминающих устройств соединены с информационным входом блока, первый и второй входы разрешения записи которого соединены с входами разрешения записи соответственно первого и второго операционных запоминающих устройств, выходы которых соединены с выходами соответственно первой и второй групп блока, первый и второй входы разрешения чтения которого соединены с входами разрешения чтения соответственно первого и второго операционных запоминающих устройств, адресные входы которых соединены соответственно с выходами первого и второго реверсивных счетчиков, суммирующие входы которых соединены с выходами соответственно первого и второго элементов И, первые входы которых соединены с первым входом третьего элемента И и тактовым входом блока, вход разрешения вычитания которого соединен с вторым входом третьего элемента И, выход которого соединен с вычитающими входами первого и второго реверсивных счетчиков, входы сброса которых соединены с входом разрешения обнуления блока, первый и второй входы разрешения суммирования которого соединены с вторыми входами соответственно первого и второго. элементов И. 3. Устройство по и, 1, о т л и ч а ю щ еес я тем, что узел пересечения содержит группу элементов неравнозначности, группу элементов И-НЕэлемент И и триггер, причем 1-й информационный вход первой группы соединен с первым входом 1-го элемента неравнозначности группы (1=1, и; и - количество аргументов функции), выход которого соединен с первым входом 1-го элемента И-НЕ группы, выход которого соединен с 1-м входом элемента И, выход которого соединен с входом установки в "1" триггера, прямой выход которого соединен с прямым выходом узла, инверсный выход которого соединен с инверсным выходом триггера, вход установки в "О" которого соединен с входом установки в "О" узла, 1-й информационный вход второй группы соединен с вторым входом 1-го элемента И - НЕ группы, 1-й информационный вход третьей группы соединен с вторым входом 1-го элемента неравнозначности группы.4,Устройство поп,1, отл ичаю щеес я тем, что узел коммутации содержит,две группы элементов И и элемент ИЛИ, причем первый и второй входы элемента ИЛИ соединены соответственно с первым и вторым управляющими входами узла, третий управляющий вход которого соединен с первым входом 1-го элемента И первой группы, второй вход которого соединен с 1-м информационным входом узла и первым входом 1-го элемента И второй группы, вторые входы элементов И второй группы соединены с выходом элемента ИЛИ,выходы элементов И первой и второй групп соединены с выходами соответственно первой и второй групп узла.1683002 Редакто оизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 Составитель В. Сорокинатрушева Техред М.Моргентал Корректор С. Шевкун аказ 3413 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям 113035, Москва, Ж, Раушская наб., 4/5 ВНТ СССР