Устройство для минимизации логических функций

Устройство для минимизации логических функций

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ, со-. держащее счетчик, регистр и первую группу элементов И, отличающееся тем, что, с целью расширения области .применения путем обеспечения возможности вычисления минимального покрытия, оно содержит триггер , генератор импульсов, m регистров, где m - количество исходных кодов, m групп по п элементов И, где п - количество разрядов , п элементов ИЛИ, первый и второй элементы И и схему сравнения кодов по числу единиц, причем вход установки тригtz гера в «О и «1 подключены соответственно к входу запуска устройства и К выходу первого элемента И, единичный выход триггера соединен с входом запуска генератора импульсов, выход которого соединен со счетным входом счфтчика, выход i-ro разряда которого, где i l,2,...,m, соединен с i-M входом первой группы входов схемы сравнения кодов по числу единиц, первым входом i-ro элемента И первой группы, i-м входом первого элемента И и первыми входами элементов И (i + 1)-и группы, к вторым входам которых подключены соответствующие выходы (i-fl)-ro регистра выход каждого j-ro элемента И (i-f 1)-й ipynпы , где j 1,2,...п, соединен с i-M входом j-ro элемента ИЛИ группы, выход которого соединен с .j-м входом второго элемента И, выход которого соединен с вторыми входами (Л элементов И первой группы, выходы которых соединены с установочными входами рес гистра, выходы разрядот которого соединены с второй группой входов схемы сравнения кодов по числу единиц, выход которой соединен с третьими входами элементов И первой группы. о 05 00 СО со

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН у G 06 F 7/00

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

И ASTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЬф НОМИТЕТ СССР

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3439826/18-24 . (22) 17.05.82 (46) 23.01.84. Бюл. № 3 (72) В. Ф. Романов и В. И. Козлов (71) Владимирский политехнический институт (53) 681.325.66 (088.8) (56) l. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М., «Энергия», 1980, с. 304.

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

¹ 558275, кл. G 06 F 7/00, 1974 (прототи и). (54)- (57) УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ, со-.держащее счетчик, регистр и первую группу элементов И, отличающееся тем, что, с целью расширения области применения путем обеспечения возможности вычисления минимального покрытия, оно содержит триггер, генератор импульсов, m регистров, где

m — количество исходных кодов, m групп по. и элементов И, где и — количество разрядов, и элементов ИЛИ, первый и второй элементы И и схему сравнения кодов по числу единиц, причем вход установки тригÄÄSUÄÄ 1068930 А гера в «О» и «1» подключены соответственно к входу запуска .устройства н к выходу первого элемента И, единичный выход триг-, гера соединен с входом запуска генератора импульсов; выход которого соединен со счетным входом счетчика, выход I-ro разряда которого, где i=1,2,...,m, соединен с

i-м входом первой группы входов схемы сравнения кодов по числу единиц, первым входом i-го элемента И первой группы, i-u входом первого элемента И и первыми входами элементов И (i+1)-й группы, к вторым входам которых подключены соответствующие выходы (i+1)-го регистра, выход каждого j-ro элемента И {i+1)-й группы, где j= 1,2,...п, соединен с i-м входом

j-ro элемента ИЛИ группы, выход которого соединен с .j-м входом второго элемента И, Q выход которого соединен с вторыми входами элементов И первой группы, выходы которых соединены с установочными входами регистра, выходы разрядов которого соеди- С иены с второй группой входов схемы сравне- . ния кодов по числу единиц, выход которой Я соединен с третьими входами элементов И первой группы. Мю

CO!

068930

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

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

t. a. !!!.

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

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

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

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

Цель достигается тем, что в устройство, содержащее счетчик, регистр и первую группу элементов И, введены триггер, генера. тор импульсов, m р еeг и с тр оaвa, где m — ко личество исходных кодов m групп по и элементов И, где n — количество разрядов кодов и элементов ИЛИ, первый и второй элементы И и схему сравнения кодов по числу единиц, причем входы установки триггера в «О» и «1» подключены соответственно к входу запуска устройства и к выходу первого элемента И, единичный выход триггера соединен с входом запуска генератора импульсов, выход которого соеди нен со счетным входом счетчика, выход i-ra разряда которого, где i=1,2, лл, соединен с i-м входом первой группы входов схемы равнения кодов по числу единиц, первым

2 входом i-го элемента И первой группы, i-м входом первого элемента И и первыми входами элементов И (i+1)-й группы, к вторым входам которых подключены соответствующие выходы (!+! ) -го регистра, выход каждого j-го элемента И (i+1) -й группы, где j= 1,2,...,n, соединен с i-м входом j-ro элемента ИЛИ группы, выход которого соединен с j-м входом второго элемента И, выход которого соединен с втоl0 рыми входами элементов И первой группы, выходы которых соединены с установочными входами регистра, выходы разрядов которого соединены с второй группой входов схемы сравнения кодов по числу единиц, выход которой соединен с третьими входами

1 элементов И первой группы.

На чертеже представлена схема устройства.

Устройство содержит триггер 1, генератор 2 импульсов, первый элемент И 3, счетчик 4, m регистров 5g — 5m, m групп по п элементов И, 6,, 6z..., 6, 6,, 6, ", 6„, 6, 6 ..., 6 группы из и элементов ЙЛИ 7, второй элемент И 8, группу из m элементов И 9, регистр 10, схему 11 сравнения кодов по числу единиц, вход 12 запуска устройства.

25 Устройство работает следующим образом.

В исходном состоянии в п-разрядных регистрах 5 — Sm зафиксированы m комбинаций и-разрядных кодов, составляющих двоичную матрицу размерности акп, миниM мальное покрытие которой требуется вычислить. Триггер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов забло.кирован, При поступлении сигнала на вход

12 запуска устройства триггер 1 переходит

:в единичное состояние, счетчик 4 устанав-.

35 ливается в нулевое состояние, а разряды .регистра !0 — в единичное состояние (цепи начальной установки не показаны). С выхода генератора 2 поступают импульсы на .счетный вход счетчика 4.

40 Счетчик 4 — двоичный m-разрядный счет: чик, на его выходах последовательно фор- мируются все 2 комбинаций единичных и нулевых сигналов. При поступлении иа вход счетчика первого импульса от генератора 2 единичный сигнал появляется на его первом

45 выходе. При этом разрешено прохождение единичных сигналов через те разрядные эле, менты { 4) группы И 6,, на которые поступают единичные сигналы с выходов регистра 5 . При поступлении на вход счетчика 4 второго импульса единичный сигнал появляется на втором выходе счетчика и, соответственно, разрешено прохождение единичных .выходных сигналов регистра 5» через разрядные элементы И 6,. При поступлении третьего импульса разрешено одновремен««ное прохождение единичных выходных сигналов регистров 5g и 5 и т. д. Каждуй из выходов разрядных элементов И 6,—.6П1 i-ro

:разряда (! = 1,2,..., п) соединен с одним из

1068930

Состаннтель В. Горохов

Редактор И. НиколаАчук Техред И. Верес Корректор И. Зрдейн

Заказ l 0932/44- тираж N6- Подписное

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

I l 3035, Иосква, Ж вЂ” 35, Раушская наб., д. 4/5

Фялнал ППП «Патента,, r. Ужгород, ул. Проектная, 4

3 соответствующих входов элемента ИЛИ 7

1-ro разряда, поэтому на выходе элемента

ИЛИ 7 i-ro разряда появляется единичный

Сигнал, если íà i-м выходе хотя бы одного йз регистров 5т — 5m, выбранного с помощью счетчика 4 в данный момент, присутствует единичный сигнал. Код счетчика 4, при котором на всех выходах группы элементов

ИЛИ 7 возникают единичные сигналы, соответствует покрытию двоичной матрицы, В этом случае на выходе элемента И 8 так же будет единичный сигнал, который по- .ступает на входы элементов И 9 первой группы. Если одновременно количество единиц кода в счетчике 4 меньше, чем число единиц кода, хранящегося в регистре 10 (это определяется схемой 11 сравнения ко:дов по числу единиц), то код этого покрытия переписывается в регистр 10. Если в результате дальнейшего функционирования устройства выявлено другое покрытие, обеспеченное меньшим количеством за4 действованных регистров б,— 5 т. е. чеиьtllHM числом единиц в выходном коде счетчика 4, то в регистре 10 результата заносится этот код.

После того, как перебраны все возмож5 ные комбинации выходных кодов счетчика 4, т.е. после поступления на его вход 2 " †.1 импульсов, на всех выходах счетчика присутствуют единичные сигналы и на выходе элемента Й 3 появляется едицичный сигнал, 1О который устанавливает триггер 1 в нулевое состояние, и работа устройства заканчивается. Единичные .сигналы в выходном коде регистра Ю результата указывают номера регистров 5 — 5», которые соответствуют набору строк, образующих минимальное по15 крытие двоичной матрицы..

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