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

 

27)897

0П ИСА НИ Е

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Реслублйн

Зависимое от авт. свидетельства №

Заявлено 24.V1.1968 (№ 1251809/18-24) с присоединением заявки №

Приоритет

Опубликовано 26.V.1970. Бюллетень ¹ 18

Дата опубликования описания 9.IX.1970

Кл. 42ша, 15/34

Комитет по делам иаобретений и открытий ори Совете Министров

СССР

МПК G 06f 15/34

УДК 681.142(088.8) Автор изобретения

Ю. P. Миронович

Центральное проектно-конструкторское бюро механизации и автоматизации

Заявитель

1

БЫСТРОДЕЙСТВУЮЩИЙ МИНИМИЗАТОР БУЛЕВЫХ ФУНКЦИЙ

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

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

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

«И — НЕ» подключены ко входам триггеров памяти, соединенных своими выходами с входными шинами индикационного табло.

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

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

":а, (/г — порядок определяющей функции. i-ee номер).

Алгоритм, как правило, заканчивается по10 лученпем минимальной тупиковой формы минимизируемой БФ в том случае, если исходные определяющие функции „. (к =- 2) представленыы мtøèмальными дизъюнктивными форм»ми МДФ.

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

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

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

30 И8», собирательные схемы, «1!ЛИ 1 — ИЛИЗ», 271897 логические схемы совпадения с отрицанием

«И» — «HE»l — «И» — «НЕ»17, инвертор НЕ, схемы неравнозначности «НР»1 — «HP»16, триггер управления 7 21, ячейки T22 — Т З двухразрядного двоичного счетчика, ячейки памяти

T 4 — T 19, усилители У1 — у 1б и индикаторы

Лl — Л1б.

Любую задачу по синтезу логической схемы можно легко свести к цифровой форме. Тогда, при полнос1ью определенной БФ, она задается только совокупностями кодовых,комбинаций, на которых функции равна единице, т. е. 11(х„, х„ i,"., х1) =1. Все остальные совокупности кодовых комбинаций нз их общего числа 2" будут равны нулю и поэтому не задаются. Если функции неполностью определена условиями задачи, то она задается совокупностями кодовых комбинаций, на которы:, БФ равна соответственно единице и нулю:

/,(х„, х„т, ..., х1) =1, /,(х„, х„, ..., х,) =О, а оставшиеся кодовые комбинации из их оищего числа представляют собой «запретные или безразличные кодовые комбинации, которые следует доопределить таким образом, чтобы в результате синтеза искомая минимальная форма БФ была наиболее простой.

Предлагаемое устройство оперирует только с двухместными БФ, которые имеют всего четыре кодовые комбинации входных переменных xi, х . В связи с этим входные ключи 81—

88 подразделены па две группы — 81 — 84 н

85 — 88, соответственно предназначенные для введения единиц и нулей.

Например, две двухместные БФ заданы в цифровой форме следующим образом:

f(x>, х1) =-Х/ (0, 1, 2);

f Х/ (0, 2), fo(3).

Это означает, что первая БФ на двоичных наборах входных переменных, десятичные эквиваленты которых равны О, 1, 2, равна единице, а на оставшемся наборе 3 — нулю. Вторая

БФ на наборах О, 2 равна единице, на наборе 3 — нулю, а на наборе 1 пе опрсделена. Условия задачи при помощи входных ключей

Bl — B4 и Ва — -88 вводятся следующим образом: для первой БФ в положение единицы ставятся ключи 81, 82, ВЗ, 88, а для второй БФ в положение единицы ставятся ключи Bl, 83, 88. Следует отметить, что введение единицы через вторую группу ключей 85 — 88 означает, что по условию задачи вводится нуль.

Таким образом, вводятся нули и единицы, а

«запретные», или безразличные состояния в схему не вводятся вообще. Входная информация через ключи 81 — 84, 85 — -88 подается на одни входы схем совпадения «И»1 — «И»8, на другие входы которых подаются сигналы с выходов fi, fz, fz и, «блока ЛБФ, представляющего собой логический многополюсник с шестнадцатью выходами f> — /1„и шестью входамн х„хь х2, х2, R>, R2) нз которых R>. R являюгся разрешающими входами, а хь х1, х2, х,— логическими входами многополюсника с сш.5

65 налами, снимаемыми с выходом триггеров Тг2)

ТгЗ, включенных по схеме двоичного счетчика.

На-выходах fi, f», fa, f4 формируются сигна. лы в соответствии со следующими формулами:

f1 x»х1 (Л2) ) f2 х2х1 ()) 1)) 2) )

fg = x2x1 (К1К2) ) 14 = Х2х! (1 А 2) .

При R> равном О и Rz равном 1 конъюнкция

1<11<2 равна 1 и, следовательно, оставшиеся конъюнкции х х,, х,.х,, х х„х,х, равны едини. цам последовательно в соответствии со сменой состояний двоичного счетчика Тг2, 7 гЗ. Эти единицы в этом же порядке вводятся на входы ячеек «И»1 — «И»8, выходы которых об ьединяются собирательными схемами «ИЛИ»2, «ИЛИ»3. Эти схемы на каждом такте работы счетчика формируют единицы при значениях

БФ единица и нуль в соответствии с условиями задачи.

Таким образом, на выходе собирательной схемы «ИЛИ»1 вырабатывается разрешающий сигнал Rq для блока ЛБФ и для комбинаций хь х> БФ, определяемых условиями задачи.

На тех кодовых комбинациях, на которых

БФ не определена, ни на одном из выходов схем совпадения «И»1 — «И»8 не может быгь единичного сигнала и, следовательно, таковой отсутствует на выходах собирательных схем

«ИЛИ»2, «ÈËÈ»3, «ИЛИ»1, в результате чего блок ЛБФ блокируется по входу Rz, и на всех его выходах f>, 4, f, ..., f>< устанавливаются нулевые сигналы.

Выходы блока соединены с первыми входами ячеек НР1 — -НР16, выполняющих логическую операцию «неравнозначности» или операцию сложения по модулю 2. На вторые входы ячеек подается сигнал с выхода собирательной схемы < ИЛИ»2, а сигналы с выходов всех ячеек «неравнозначности» через логические ячейки «И вЂ” НЕ»1 — «И — НЕ»lб поступают на левые входы триггеров памяти Тг4—

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

«НЕ»1 — «И» — ИЕ»17.

Минпмизатор работает следующим образом, После установки по условиям задачи ключей Bl — 84, 85 — 88 в свои единичные положения на соответствующую шину подается импульс сброса, в результате чего все триггеры устройства занимают положение, показанное на чертеже (заштрихованная половина триггера проводит).

Затем на левый вход триггера Тгl подается импульс пуска, после чего он переходит в свбе второе устойчивое состояние, и генератор импульсов начинает генерировать тактовые импульсы. За четыре такта работы генератора происходйт полное сравнение введенных условий задачи с минимальными формами двух271807

Местных БФ, снимаемых с выходов f>, f, ..., f 6 блока ЛБФ.

Если какие-либо функции с выходов fi — fi,. не удовлетворяют введенным условиям, то на выходах ячеек неравнозначности НР1 — FJPlli вырабатываются импульсы, которые через ячейки «È вЂ” HL»1 — «И — НЕ»1б сбрасывают соответствующие триггеры из находящихся в первоначальный момент в состоянии «1» так, чтобы все индикаторные устройства J71 — ЛИ светились. I-la четвертом такте на выходе /, блока ЛБФ появляется единичный сигнал, который совместно с сигналом формирующего устройства Ф поступает на входы ячейки «И—

НЕ»12..С выхода ее триггер Гг1 возвращает импульс в исходное состояние. На этом заканчивается цикл минимизации.

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

Таким образом, наличие собирательной схемы «ИЛИ» и соответственно разрешающего входа Rz в блоке ЛБФ позволяет минимизировать как полностью, так и неполностью определенные условиями задач БФ без дополнительного введения «запрещенных > состояний функции в схему. b,àæäoìó индикационному прибору соответствует минимальная форма двухместной БФ, так что по освещенным индикаторным приборам можно считывать соответствующие минимальные формы БФ.

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

Быстродействующий мпнимизатор булевых функций. содержащий логические ячейки, клю10 чи ввода исходных данных и индикационное табло, отлича ощийся тем, что, с целью упро. щения ручного синтеза логических схем, он содержит логический блок для формирования минимальных форм двухместной булевой функ15 цпи, соединенный своими входами с выходамп двухразрядпого двоичного счетчика, подключенного к выходу управляемого генератора импульсов, а выходами — с одними входами cxeì совпадения, другие входы которых соединены

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

25 входу логического блока, и с одними входами ячеек неравнозначности, другие входы которых соединены с выходом собирательной схемы, соответствующей единичному набору, а выходы через логические схемы «И — FFF» подклю30 чены ко входам триггеров памяти, соединенных своими выходами с входными шинами индикационного табло.

Составитель Л. Горская

Редактор М. И. Андреева Техред T. П. Курилко Корректор И. С. Хлыстова

Заказ 2423/6 Тираж 480 Подписное

ЦН11ИПИ Комитета по делам изобретений и озкрытий прн Совете Министров СССР

Москва, Ж-З5, Раушская иаб,, д. 4 5

Типография, пр. Сапунова, 2