Устройство для минимизации логических функций Советский патент 1984 года по МПК G06F7/00 

Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации. Задача отыскания покрытия, особенно минимального покрытия, встречается довольно часто: при минимизации логических функций, при отыскании тестовых наборов для цифровых схем, формирования магазинокомплектов инструментов для станков при обработке больших партий деталей и т. Д- IUПод покрытием понимается набор строк Двончной матрицы, содержащих в совокупности хотя бы одну еднннцу в каждом столбце, а под минимальным покрытием - минимальный набор таких строк. В настоящее время минимальное покрытие в матрицах небольшой размерности отыскивается вручную, а в матрицах большой размерности - с помощью универсальных ЭВМ по известным процедурам. Однако эти процедуры громоздки и их реализация на ЭВМ требует значительных затрат машинного времени и оперативной памяти, поэтому поиск минимального покрытия с помощью ЭВМ оказывается неэкономичным.. Известно устройство для минимизации логических функций, содержащее последовательно соединенные пульт управления преобразователь дизъюнктивной нормальной формы логических выражений и совершенную дизъюнктивную нормальную форму, регистр, группу элементов И, выходной блок и блок регистрации, а также счетчик и дешифратор, выходы которого соединены с вторыми входами элементов И группы (2. «Однако это устройство предназначено с. «иии„„оо.,„ы nV-ru....,.,. и для минимизации логических функций на основе графовых методов представление функций, т. е..имеет достаточно узкие функциональные возможности. Целью изобретения является расширение области применения устройства путем обеспечения возможности вычисления минимального покрытия. Цель достигается тем, что в устройство, содержащее счетчик, регистр и первую группу элементой И, введены триггер, генера тор импульсов, П1 регистров, где m - количество исходных кодов m групп по п элементов И, где п - количество разрядов кодов п элементов ИЛИ, и второй элементы И и схему сравнения кодов по числу единиц, причем входы установки триггера в «О и tl подключены соответсгвенно к входу запуска устройства н к выходу первого элемента И, единичный выход триггера соединен с йходом запуска .генератора импульсов, выход которого соединен со счетным входом счетчика, выход i-ro55 ное прохождение единичных выходных снгразряда которого, где i l,2,...m, соединенналов регистров 5i и 5} и т. д. Каждый из

с i-M входом первой группы входов схемывыходов разрядных элементов И i-ro

«сравнения кодов по числу единиц, первым :разряда (.1 1,2п) соединен с одним из входом i-ro элемента И первой группы, i-M входом первого элемента И и первыми входами элементов И (1 + 1)-й группы, к вторым входам которых подключены соответствующие выходы (i-fl)-ro регистра, выход каждого j-ro элемента И (1 + 1)-й группы, где j l,2п, соединен с i-м входом j-ro элемента ИЛИ группы, выход которого соединен с j-м входом второго элемента И, выход которого соединен с вторыми входами элементов И первой группы, выходы которых соединены с установочными входами регистра, выходы разрядов которого соединены с второй группой входов схемы сравнения кодов по числу единиц, выход которой соединен с третьими входами элементов И первой группы. На чертеже представлена схема устройства. Устройство содержит триггер I, генератор 2 импульсов, первый элемент И 3, счет...... Pf ТР°Л 71 fi 1 °й элементов И, 6,, Gj..., 6„, 6,, Ь,..- 6„ , 6,, j..., 6 группы из п элементов ИЛИ 7, второи элемент И 8, группу из ш элементов И 9, регистр 10, схему 11 сравнения кодов по числу единиц, вход 12 запуска устройства. Устройство работает следующим образом. . В исходном состоянии в п-разрядных регистрах 5j-5гч зафиксированы m комбинаций п-разрядных кодов, составляющих Двоичную матрицу размерности тхп, минимальное покрытие которой требуется вычис« ть. Триггер 1 находится в нулевом состоя поэтому генератор 2 импульсов заблокирован. При поступлении сигнала на вход 2 запуска устройства триггер 1 переходит « единичное состояние, счетчик 4. устанав. лнвается в нулевое состояние, а разряды .регистра 10 - в единичное состояние (цепи начальной установки не показаны). С выхода генератора 2 поступают импульсы на счетный вход счетчика 4. Счетчик 4 - двоичный т-разрядный счет.чик, на его выходах последовательно формируются все 2 комбинаций единичных и нулевых сигналов. При поступлении на вход счетчика первого нмпульса от генератора 2 единичный сигнал появляется на его первом „,.. .., выходе. При этом разрешено прохождение единичных сигналов через те разрядные элементы {et группы И 6 на которые поступают единичные сигналы с выходов регнстра 5 . При поступлении на вход счетчика 4 второго импульса единичный сигнал появляется на втором выходе счетчика и, соответственно, разрещено прохождение еднничных выходных сигналов регистра 5z через разрядные элементы И 6. При поступленнн третьего импульса разрешено одновременсоответствующих входов элемента ИЛИ 7 i-ro разряда, поэтому на выходе элемента ИЛИ 7 )-го разряда появляется единичный tиrнaл, если на i-м выходе хотя бы одного Из регистров 5|-5т, выбранного с помощью Счетчика 4 в данный момент, присутствует единичный сигнал. Код счетчика 4, при котором на всех выходах группы элементов ИЛИ 7 возникают единичные сигналы, соответствует покрытию двоичной матрицы В этом случае на выходе элемента И 8 так же будет единичный сигнал, который по ступает на входы элёмеитов И 9 первой группы. Если одиовременИо количество единиц кода в счетчике 4 меньше, чем чнслб единиц кода, хранящегося в регистре 10 (это определяется схемой 11 сравнения кодов по числу единиц), то код этого покрытия переписывается в регистр 10. Еслн в результате дальнейшего функционирования устройства выявлено другое покрытие, обеспечеииое меньшим количеством задействованных регистров 6j-5tn, т. е. меньшим числом единиц в выходном коде счетчика 4, то в регистре 10 результата заносится этот код.

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

который устанавливает: триггер 1 в нулевое состояние, и работа устройства заканчива/ется. Единичные сигналы в выходном коде регистра Ю результата указывают номера регистров 5|-5т, которые соответствуют набору строк, образующих минимальное покрытие двоичной матрицы.

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

УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ, со-. держащее счетчик, регистр и первую группу элементов И, отличающееся тем, что, с целью расширения области .применения путем обеспечения возможности вычисления минимального покрытия, оно содержит триггер, генератор импульсов, 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 СО со