БЫСТРОДЕЙСТВУЮЩИЙ МИНИМИЗАТОР БУЛЕВЫХ ФУНКЦИЙ Советский патент 1970 года по МПК G06F7/38 

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

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

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

Алгоритм работы предлагаемого миннмизатора заключается в нахождении п ппмaлbпoй

тупиковой формы булевой фуикци.и БФ па базе тупиковых форм, определяющих функции fti (/г - порядок оирсделяющей функцни, i - ее номер). Алгоритм, как правило, закапчивается получеппем минимальной тупиковой формы минимизируемой БФ в том случае, если исходные определяющие фуикцип /j ( 2) представлены минимальными дизъюпктпвпымп формами МДФ.

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

В схему входят ключи ввода исходных даииых В1-BS, управляемый генератор имиулисов ГИ, логический блок для формироваиия всех переключательных функций двух переменных ЛБФ, формнрователь разрешающих сигналов Ф, входные схемы совпадення И1-

логические схемы совпадеиия с отрицанием - 17, инвертор НЕ, схемы неравиозиачности , триггер управления , ячейки 722-Т З двухразрядного двоичного счетчика, ячейки намята .219, усилители У1-У16 и индикаторы Л1-Л16.

Любую задачу но синтезу логической схемы можно легко свести к цифровой форме. Тогда, нри нолностью онределенной БФ, она задается только совокунностями кодовых.комбинаций, на которых функции равна единице, т. е. /1(л;„, ,.:, х)1. Все остальные совокупности кодовых комбинаций из их общего числа 2 будут равны нулю и поэтому не задаются. Если функции ненолностью онределена условиями задачи, то она задается совокунностями кодовых комбннаций, на которых БФ равна соответственно единице и нулю; h(Xn, , ..., Xi) i, о(х„, Xn-i , ..., Xi)0, a оставшиеся кодовые комбинации из их общего числа представляют собой «занретные или безразличные кодовые комбинации, которые следует доопределить таким образом,чтобы в результате синтеза искомая минимальная форма БФ была наиболее простой.

Предлагаемое устройство оперирует только с двухместными БФ, которые имеют всего четыре кодовые комбинации входных переменных Xi, Xz. В связи с этим входные ключи В1- В8 подразделены на две группы - и В5-В8, соответственно предназначенные для введения единиц и нулей.

Нанример, две двухместные БФ заданы в цифровой форме следующим образом: , Xi)- Sfi{0, 1, 2);

«--)ЧШз).

Это означает, что первая БФ на двоичных наборах входных неременных, десятичные эквиваленты которых равны О, 1,2, равна единице, а на оставшемся наборе 3 - нулю. Вторая БФ на наборах О, 2 равна единице, на наборе 3 - нулю, а на наборе 1 не определена. Условия задачи при помощи входных ключей В1-В4 и Во-В8 вводятся следующим образом: для нервой БФ в положенне единицы ставятся ключи В}, В2, ВЗ, В8, а для второй БФ в положение единицы ставятся ключи В1, ВЗ, В8. Следует отметить, что введение единицы через вторую группу ключей В5-В8 означает, что по условию задачи вводится нуль.

Таким образом, вводятся нули и единицы, а «занретные, или безразличные состояния в схему не вводятся вообще. Входная информация через ключи В1-В4, В5-В8 подается на одни входы схем совнадения , на другие входы которых нодаются сигналы с выходов /1, /2, /3 и /4 блока ЛБФ, нредставляющего собой логический многополюсник с шестнадцатью выходами /1-/10 и шестью входами

налами, снимаемыми с выходом триггеров Тг2 ТгЗ, включенных по схеме двоичного счетчика. На выходах /i, fa, /3, /4 формируются сигналы в соответствии со следующими формулами:

,(), (2),

f3 X-2X(KiK2), fi X2Xi{RiR2).

При Ri равном О и 2 равном 1 конъюнкция RiRz равна 1 и, следовательно, оставшиеся:

конъюнкции XzXi, XzXi, XzXi, xzXi равны единицам последовательно в соотвегствии со сменой состояний двоичного счетчика Тг2, ТгЗ. Эти единицы в этом же порядке вводятся на входы ячеек , выходы которых объединяются собирательными схемами . . Эти схемы на каждом такте работы счетчика формируют единицы при значениях БФ единица и нуль в соответствии с условия,ми задачи.

Таким образом, на выходе собирательной схемы вырабатывается разрешающнй сигнал 2 для блока ЛБФ и для комбинаций X, xz БФ, онределяемых условиями задачи.

На тех кодовых комбинациях, на которых БФ не онределена, ни на одном из выходов схем совнадения не может быть едииичного сигнала и, следовательно, таковой отсутствует на выходах собирательных схе.м

, , , в результате чего

блок ЛБФ блокируется но входу 2, и на всех

его выходах /ь /2, /з, ..., /ю устанавливаются

нулевые сигналы.

Выходы блока соединены с первыми входами ячеек 16, выполняющих логическую операцию «неравнозначности или операцию сложения по модулю 2. На вторые входы ячеек подается сигнал с выхода собирательной схемы а сигналы с выходов

всех ячеек «неравнозначности через логические ячейки «И-НЕ 1-«И--НЕ 16 поступают на левые входы триггеров памяти Тг4- Тг19, причем на входы триггеров имнульсы нодаются в определенные моменты времени, оиределяемые формирующим устройством Ф. На вход его через инвертор «НЕ поступают тактовые импульсы с управляемого генератора импульсов ГИ, а с выхода поступают импульсы «Опроса на все вторые входы ячеек «И-

.

Минимизатор работает следующим образом. Носле установки но условиям задачи ключей В1-В4, В5-В8 в свои единичные положения на соответствующую щину подается имнульс сброса, в результате чего все триггеры устройства занимают положение, показанное на чертеже (заштрихованная половина триггера проводит). Затем на левый вход триггера Тг1 подается импульс пуска, после чего он переходит в свое второе устойчивое состояние, и генератор имнульсов начинает генерировать тактовые импульсы. За четыре такта работы генератора происходит полное сравнение введенных услоiviecTHbix БФ, снимаемых с выходов fi, fg, ..., fie блока ЛБФ.

Если какие-либо функции с выходов ,; не удовлетворяют введенным условиям, то па выходах ячеек неравнозначности ЯР/-НР16 вырабатываются импульсы, которые чере:з ячейки «И-НЕ 1-«И-HE:- }6 сбрасывают соответствующие триггеры из находящихся в нервоначальный момент в состоянии «1 так, чтобы все индикаторные устройства светились. На четвертом такте на выходе | блока ЛБФ появляется единичный сигнал, который совместно с сигналом формирующего устройства Ф поступает на входы ячейки «И- . С выхода ее триггер Тг1 возвращает импульс в исходное состояние. На этом заканчивается цикл минимизации.

Триггеры (из числа Тг4-Тг19), которые остались в состо5 нии «1 свидетельствуют о том, что минимальиые формы функций, снимаемые со входов /1, /2, ., /16 блока ЛБФ, связанных со входами триггеров через ячейки неравнозначности НР1-НР16 и ячейки «Я-НЕ 1- «И-НЕ 16 удовлетворяют введенным в схему условиям задачи.

Таким образом, наличие собирательной схемы «ИЛИ и соответственно разрещающего входа Rz в блоке ЛБФ позволяет минимизировать как полностью, так и неполностью определенные условиями задач БФ без дополнительного введения «запрещенных состояний функции в схему. Каждому индикационному

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

Предмет изобретения

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

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

входу логического блока, и с одними входами ячеек неравнозначности, другие входы которых соединены с выходом собирательной схемы, соответствующей единичному набору, а выходы через логические схемы «И-НЕ подключеиы ко входам триггеров памяти, соединенных своими выходами с входными щинами индикациониого табло.