Быстродействующий минимизатор булевых функций

271897 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических РеслублйнЗависимое от авт Заявлено 24,71,19 видетельства1251809/18-24 л 42 шз, 15/3 ением заявкири Приорите МПК 6 061 15/34 УДК 681.142(088.8 Комитет по делам обретений и открытий ри Совете Министров СССРубликовано 26.7.1970, Бюллетень18та опубликования описания 9.1 Х.1970 Автор зобретения Миронови Центральное проектно-конструкторское бюро механизации и автоматизациивит 1МИНИМИЗАТОР БУЛЕВЫХ ФУНКЦИЙ ЫСТРОДЕЙСТВУЮ Известны устройства для минимизации структуры логических схем, содержащие логические элементы, ключи ввода исходных данных и индикационное табло.Предлагаемый минимизатор содержит логический блок для формирования минимальны,: форм двухместной булевой функции, соединенный своими входами с выходами двухразрядного двоичного счетчика, подключенного к выходу управляемого генератора импульсов, а выходами - с одними входами входных схем совпадения, другие входы которых соединены с ключами ввода исходных данных. Выходы последних подключены к входам двух собирательных схем соответственно для единичного и нулевого наборов, выходы которых через собирательную схему подключены к разрешающему входу логического блока, и с одними входами ячеек неравнозначности, другие входы которых соединены с выходом собирательной схемы, соответствующей единичному набору, а выходы через логические схемы И - НЕ подключены ко входам триггеров памяти, соединенных своими выходами с входными шинами индикационного табло. Известные минимизаторы базируются на алгоритме последовательного поиска простейших импликант, что в конечном счете связано с перебором весьма большого количества вариантов и, следовательно, усложнением процесса синтеза.Алгоритм работы предлагаемого мпнпмизатора заключается в нахожде;ши минимальной 5 тупиковой формы булевой функции БФ па базе тупиковых форм, определяющих функции ";ат (Й - порядок определяющей функции, т ее номер).Алгоритм, как правило, заканчивается по- О лученпем минимальной тупиковой формы минимизируемой БФ в том случае, если исходные определяющие функциик =- 2) представленыы минимальными дизъюнктпвпымп формами МДФ.5 Применение предложенного мпппмпзаторсовместно с упомянутым алгоритмом позволяет получить минимальные формы б левых функций без перебора больигого числа роше.ний задач, что значительно упрощает и уде шевляст работы по синтезу логических структур.На чертеже приведена функциональная схема предлагаемого мпнимпзатора.В схему входят ключи ввода исходных дан пых В 1 - ВЬ, управляемый генератор пмпул- сов ГИ, логический блок для формирования всех пер еключа тельных фупкцпй двух переменных ЛБФ, формирователь разрешающих сигналов Ф, входные схемы совпадения И 1 - ЗО И 8, собирательные схемы, 11 ЛИ 1 - ИЛИЗ, 271897логические схемы совпадения с отрицанием И - НЕ 1 - И - НЕ 17, инвертор НЕ, схемы неравнозначности НР 1 - НР 16, триггер управления 7,1, ячейки Т,2 - Т,З двух- разрядного двоичного счетчика, ячейки памяти Т,4 - Т,19, усилители 1 - у 1 б и индикаторы Л 1 - Л 1 б.Любую задачу по синтезу логической схемы можно легко свести к цифровой форме. Тогда, при полностью определенной БФ, она задается только совокупностями кодовых,комби наций, на которых функции равна единице, т. е, 1,(х) х- х,) =1. Все остальные совокупности кодовых комбинаций нз их общего числа 2" будут равны нулю и поэтому не задаются. Если функции неполностью определена условиями задачи, то она задается совокупностями кодовых комбинаций, на которы;, БФ равна соответственно единице и нулю: Р(х, хт,х,) =1, Р,(х, х х,) =О, а оставшиеся кодовые комбинации из их общего числа представляют собой запретные или безразличные кодовые комбинации, которые следует доопределить таким образом, чтобы в результате синтеза искомая минимальная форма БФ была наиболее простой.Предлагаемое устройство оперирует только с двухместными БФ, которые имеют всего четыре кодовые комбинации входных переменных х), х. В связи с этим входные ключи В 1 - В 8 подразделены па две группы - В 1 - В 4 н Вб - В 8, соответственно предназначенные для введения единиц и нулей,Например, две двухместные Бф заданы в цифровой форме следующим образом:" " - 1.,(3). Это означает, что первая БФ на двоичных наборах входных переменных, десятичные эквиваленты которых равны О, 1, 2, равна единице, а на оставшемся наборе 3 - нулю. Вторая Бф на наборах О, 2 равна единице, на наборе 3 - нулю, а на наборе 1 пе опрсделена. Условия задачи при помощи входных ключей В 1 - В 4 и Вб - -В 8 вводятся следующим образом; для первой БФ в положение единицы ставятся ключи В 1, В 2, ВЗ, В 8, а для второй БФ в положение единицы ставятся ключи В 1, ВЗ, В 8, Следует отметить, что введение единицы через вторую группу ключей Вб - В 8 означает, что по условию задачи вводится нуль.Таким образом, вводятся нули и единицы, а запрстные, или безразличные состояния в схему не вводятся вообще, Входная информация через ключи В 1 - В 4, Вб - -В 8 подается на одни входы схем совпадения И 1 - И 8, на другие входы которых подаются сигналы с вы. ходов , , )з и блока ЛБФ, представляю. щего собой логический многополюсник с шестнадцатью выходами , - и шестью входамн ххх) х ЯЛ) из которых Р Й. являюгся разрешающими входами, а хь х, х, х, - логическими входами многополюсника с сш 5 10 15 20 25 30 35 40 45 50 55 60 65 налами, снимаемыми с выходом триггеров Тг 2, ТгЗ, включенных по схеме двоичного счетчика.На выходах , , з, )4 формируются сигна лы в соответствии со следующими формулами:, = х,х, (ЯЯ) ) , =хх, (РД) )=хх (К 1 К 2) ) 14 Х 2 х (Л 1 Л 2).При Я, равном О и Я равном 1 конъюнкция РЯ равна 1 и, следовательно, оставшиеся конъюнкции хх х,.х ххх,х, равны едини цам последовательно в соответствии со сменой состояний двоичного счетчика Тг 2, 7 гЗ. Эти единицы в этом же порядке вводятся на входы ячеек И 1 - И 8, выходы которых обьединяются собирательными схемами ИЛИ 2, ИЛИ 3. Эти схемы на каждом такте работы счетчика формируют единицы при значениях БФ единица и нуль в соответствии с условиями задачи.Таким образом, на выходе собирательной схемы ИЛИ 1 вырабатывается разрешающий сигнал Р для блока ЛБФ и для комбинаций х х Бф, определяемых условиями за. дачи.На тех кодовых комбинациях, на которых БФ не определена, ни на одном из выходов схем совпадения И 1 - И 8 не может быгь единичного сигнала и, следовательно, таковой отсутствует на выходах собирательных схем ИЛИ 2, ИЛИЗ, ИЛИ 1, в результате чего блок ЛБФ блокируется по входу йь и на всех его выходах ь ,, 6 устанавливаются нулевые сигналы.Выходы блока соединены с первыми входами ячеек НР 1 - -НР 16, выполняющих логическую операцию неравнозначности или операцию сложения по модулю 2. На вторые входы ячеек подается сигнал с выхода собирательной схемы ИЛИ 2) а сигналы с выходов всех ячеек неравнозначности через логические ячейки И - НЕ 1 - И - НЕ 1 б поступают на левые входы триггеров памяти Тг 4 - Тг 19, причем на входы триггеров импульсы подаются в определенные моменты времени, определяемые формирующим устройством ф. На вход его через инвертор НЕ поступают тактовые импульсы с управляемого генератора импульсов ГИ, а с выхода поступают импульсы Опроса на все вторые входы ячеек И - НЕ 1 - И - НЕ 17.Минпмизатор работает следующим образом, После установки по условиям задачи ключей В - В 4, Вб - В 8 в свои единичные положе. ния на соответствующую шину подается импульс сброса, в результате чего все триггеры устройства занимают положение, показанное на чертеже (заштрихованная половина триггера проводит).Затем на левый вход триггера Тг 1 подается импульс пуска, после чего он переходит в свбе второе устойчивое состояние, и генератор импульсов начинает генерировать тактовые импульсы. За четыре такта работы генератора происходйт полное сравнение введенных условий задачи с минимальными формами двух 271807Местных БФ, снимаемых с выходов , , , 6 в блока ЛБФ.Если какие-либо функции с выходов 1 - 1,в не удовлетворяют введенным условиям, то на выходах ячеек неравнозначности НР 1 - НР 16 вырабатываются импульсы, которые через ячейки И - НЕ 1 - И - НЕ 16 сбрасывают соответствующие триггеры из находящихся в первоначальный момент в состоянии 1 так, чтобы все индикаторные устройства Л 1 - Л 16 светились, На четвертом такте на выходе блока ЛБФ появляется единичный сигнал, который совместно с сигналом формирующего устройства Ф поступает на входы ячейки И - НЕ 12 С выхода ее триггер Гг 1 возвращает импульс в исходное состояние. На этом заканчивается цикл минимизации.Триггеры (из числа Тг 4 - Та 19), которые ос. тались в состоянии 1 свидетельствуют о том, что минимальные формы функций, снимаемые со входов , г, ", в блока ЛБФ, связанны . со входами триггеров через ячейки неравно. значности НР 1 - НР 16 и ячейки И - -НЕ 1 - . И - НЕ 16 удовлетворяют введенным в схему условиям задачи,Таким образом, наличие собирательной схемы ИЛИ и соответственно разрешающего входа Р в блоке ЛБФ позволяет минимизировать как полностью, так и неполностью определенные условиями задач БФ без дополнительного введения запрещенныхсостояний функции в схему. Каждому индикационному прибору соответствует минимальная форма двухместной БФ, так что по освещенным индикаторным приборам можно считывать соответствующие минимальные формы БФ, 5Предмет изобретенияБыстродействующий мпнимизатор булевыхфункций, содержащий логические ячейки, клю чп ввода исходных данных и индикационноетабло, отличаощицся тем, что, с целью упро щения ручного синтеза логических схем, он содержи логический блок для формирования минимальных форм двухместной булевой функ цпп, соединенный своими входами с выходампдвухразрядпого двоичного счетчика, подключенного к выходу управляемого генератора пм.пульсов, а выходами - с одними входами схем совпадения, другие входы которых соединены 20 с ключами ввода исходных данных, а выходыпоследних со входами двух собирательных схем, соответственно для единичного и нулевого наборов, выходы которых через собирательную схему подключены к разрешающему 25 входу логического блока, и с одними входамиячеек неравнозначности, другие входы которых соединены с выходом собирательной схемы, соответствующей единичному набору, а выходы через логические схемы И - НЕ подклю чены ко входам триггеров памяти, соединенных своими выходами с входными шинами индикационного табло.Заказ 2423/6 Тираж 480 Подписное ЦНИИПИ Комитета по делам изобретений и озкрьг;ий прн Совете Министров СССР Москва, Ж-З 5, Раушская иаб д. 415