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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН ш 606 Г ОБРЕТЕ истра, вы иены с втор ния кодов оединен с ервой гру ГОСУДАРСТВЕННЫ 9 НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ И АВТОРСКОМУ С(72) В, Ф, Романов и В. И. Козлов (71) Владимирский политехнический институт(56) 1. Кузнецов О, П., Адельсон-Вельский Г. М, Дискретная математика для инженера, М., Энергия, 1980, с. 304.2, Авторское свидетельство СССР Ж 558275, кл. б 06 Г 7/00, 1974 (прототии).(54) - (57) УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ, со-. держашее счетчик, регистр и первую группу элементов И, отличающееся тем, что, с целью расширения области .применения путем обеспечения возможности вычисления минимального покрытия, оно содержит триггер, генератор импульсов, в регистров, где в - количество исходных кодов, в групп по. п элементов И, где п - количество разрядов, и элементов ИЛИ, первый и второй элементы И и схему сравнения кодов по числу единиц, причем вход установки тригБО, 1068930 А гера в О и 1 подключены соответственно к входу запуска .устройства н к выходу первого элемента И, единичный выход триг-, гера соединен с входом запуска генератора импульсов; выход которого соединен со счетным входом счетчика, выход 1-го разряда которого, где 1 = 1,2, ,тп, соединен с 1-м входом первой группы входов схемы сравнения кодов по числу единиц, первым входом 1-го элемента И первой группы, 1-м входом первого элемента И и первыми входами элементов И (1+1)-й группы, к вторым входам которых подключены соответствующие выходы (1+1)-го регистра, выход каждого 1-го элемента И (1+ 1) -й чруппы, где 1=1,2,п, соединен с 1-м входом 1-го элемента ИЛИ группы, выход которого соединен с .1-м входом второго элемента И, выход которого соединен с вторыми входами элементов И первой группы, выходы которых соединены с установочными входами реоды разрядов которого соеди- С ой группой входов схемы сравне- . по числу единиц, выход которой Я третьими входами элементов И пы. МевЮ1Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации.Задача отыскания покрытия, особенно минимального покрытия, встречается довольно часто: прн минимизации логических функций, при отыскании тестовых наборов для цифровых схем, формирования магазинокомплектов инструментов для станков при обработке больших партий деталей и т. д, 1.Под покрытием понимается набор строк. двоичной матрицы, содержащих в совокупности хотя бы одну единицу в каждом столб. це, а под минимальным покрытием - минимальный набор таких строк,В настоящее время минимальное покрытие в матрицах небольшой размерности отыскивается вручную, а в матрицах большой размерности - с помощью универсаль ных ЭВМ по известным процедурам. Однако эти процедуры громоздки и их реализация на ЭВМ требует значительных затрат машинного времени и оперативной памяти, поэтому поиск минимального покрытия с помощью ЭВМ оказывается неэконо мичным.Известно устройство для минимизации логических функций, содержащее последовательно соединенные пульт управления преобразователь дизъюнктивной нормальной формы логических выражений и совершенную дизьюнктивную нормальную форму, регистр, группу элементов И, выходной блок и блок регистрации, а также счетчик и дешифратор, выходы которого соединены с вторыми входами элементов И группы 21,Однако это устройство предназначено для минимизации логических функций на основе графовых методов представления функций; т. е,.имеет достаточно узкие функциональные возможности.Целью изобретения является расширение области применения устройства путем обеслечения возможности вычисления минимального покрытия,Цель достигается тем, что в устройство, содержащее счетчик, регистр и первую группу элементов И, введены триггер, генера тор импульсов, а регистров, где в - ко личество исходных кодов в групп по и элементов И, где п - количество разрядов кодов и элементов ИЛИ, первый и второй элементы И и схему сравнения кодов по числу единиц, причем входы установки триггера в О и 1 подключены соответственно к входу запуска устройства и к выходу первого элемента И, единичный выход триггера соединен с входом запуска генератора импульсов, выход которого соединен со счетным входом счетчика, выход 1-га разряда которого, где= 1,2,лл, соединен с 1-м входом первой группы входов схемы равнения кодов по числу единиц, первым 2входом -го элемента И первой группы, 1-м входом первого элементаИ и первыми входами элементов И (+1) -й группы, к вторым входам которых подключены соот.ветствующие выходы (+ 1) -го регистра, выход каждого 1-го элемента И (+1)-й группы, где 1=1,2 п, соединен с 1-м входом 1-го элемента ИЛИ группы, выход которого соединен с 1-м входом второго элемента И, выход которого соединен с вто- О рыми входами элементов И первой группы,выходы которых соединены с установочныМи входами регистра, выходы разрядов ко.торого соединены с второй группой входов схемы сравнения кодов по числу единиц, выход которой соединен с третьими входамиэлементов И первой группы.На чертеже представлена схема устройства.Устройство содержит триггер 1, генератор 2 импульсов, первый элемент И 3, счетчик 4, в регистров 5 - 5 е, е групп по п элементов И, 6 6., 66 6", 6 6, 61,.6 группы из и элементов ЙЛИ 7, второй элемент И 8, группу из гп элементов И 9, регистр 10, схему 11 сравнения кодов по числу единиц, вход 12 запуска устройства.25 Устройство работает следующим образом.В исходном состоянии в п-разрядныхрегистрах 5, - 5 щ зафиксированы т комбинаций и-разрядных кодов, составляющих двоичную матрицу размерности акп, мини мальное покрытие которой требуется вычислить. Триггер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов забло.кирован, При поступлении сигнала на вход 2 запуска устройства триггер 1 переходит в единичное состояние, счетчик 4 устанав-. З 5 ливается в нулевое состояние, а разряды.регистра 0 - в единичное состояние (цепи начальной установки не показаны). С выхода генератора 2 поступают импульсы на .счетный вход счетчика 4.Ю Счетчик 4 - двоичный гп-разрядный счет:чик, на его выходах последовательно фор- мируются все 2 комбинаций единичных и нулевых сигналов. При поступлении иа вход счетчика первого импульса от генератора 2 единичный сигнал появляется на его первом 45 выходе. При этом разрешено прохождениеединичных сигналов через те разрядные эле,менты (А) группы И 6 на которые поступают единичные сигналы с выходов регистра 5 . При поступлении на вход счетчика 4 второго импульса единичный сигнал появляется на втором выходе счетчика и, соответственно, разрешено прохождение единичных .выходных сигналов регистра 5 через разрядные элементы И 6,. При поступлении третьего импульса разрешено одновременное прохождение единичных выходных сигналов регистров 5 у и 5 и т. д. Каждуй из выходов разрядных элементов И 6, - .6 П 1 1-го3.яо делам нзобретеннй н открытий 3035, Иосква, Ж - 35, Раушская наб., д 4/Ь Фялнал ППП Патентэ г. Ужгород, ул, Проектная, 43соответствующих входов элемента ИЛИ 7 1-го разряда, поэтому на выходе элемента ИЛИ 7 1-го разряда появляется единичный Сигнал, если на 1-м выходе хотя бы одного йз регистров 5, - 5 н 1, выбранного с помощью счетчика 4 в данный момент, присутствует единичный сигнал. Код счетчика 4, при котором на всех выходах группы элементов ИЛИ 7 возникают единичные сигналы, соответствует покрытию двоичной матрицы, В этом случае на выходе элемента И 8 так же будет единичный сигнал, который по .ступает иа входы элементов И 9 первой группы, Если одновременно количество еди ниц кода в счетчике 4 меньше, чем числб единиц кода, хранящегося в регистре 1 О (это определяется схемой 11 сравнения ко :дов по числу единиц), то код этого покрытия переписывается в регистр 10. Если в результате дальнейшего функционирования устройства выявлено другое покрытие, обеспеченное меньшим количеством за 4действованных регистров б, - 5 я т. е. цеиьшим числом единиц в выходном коде счетчика 4, то в регистре 10 результата заносится этот код,После того, как перебраны все возмож 5 ные комбинации выходных кодов счетчика 4,т.е, после поступления на его вход 2 ф в .1импульсов, на всех выходах счетчика присутствуют единичные сигналы и на выходе элемента Й 3 появляется едицичный сигнал,1 О который устанавливает триггер 1 в нулевоесостояние, и работа устройства заканчивается. Единичные .сигналы в выходном кодерегистра Ю результата указывают номерарегистров 5, - 5 а, которые соответствуютнабору строк, образующих минимальное по.15 крытие двоичной матрицыИспользование специализированного устройства для выполнения вычисления минимального покрытия обеспечивает высокуюэффективность такого вычисления, экономитресурсы универсальных ЭВМ.