Устройство для вычисления минимального покрытия

(51)4 О 06 Р 7/38 ОПИСАНИЕ ИЗОБРЕТЕНИЯ;к двтоесному свиддтюмтвуЬйий ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ 19(56) Авторское свидетельство СССРМф 558275, кл. 6 06 Р 7/00, 1974,Авторское свидетельство СССРУ 1068930, кл, С 06 Р 7/00,17.05.82,(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЖНИИАЛЬНОГО ПОКРЫТИЯ(57) Изобретение относится к вычислительной технике, Использование вспециализированных устройствах обработки информации обеспечивает ловы"шение его быстродействия, Оно содер"жит триггер, генератор импульсов,регистры, группы элементов И, хруппу элементов ИЛИ и элемент И. Благо":даря введению генератора двоичных,последовательностей с неубывающимчислОм единиц первое ае полученноев процессе работы покрытие являетсяминимальным, 1 з,п,ф-лы, 2 ил.1 1 гИзобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации,Цель изобретения - повышение быстродействия.На фиг. изображена блок-схемаустройства для вычисления минимального покрытия на фиг,2 - функциональная схема генератора двоичныхпоследовательностей с неубывающимчислом единиц для случая ш 4.Устройство (фиг.1) содержит триггер 1, генератор 2 импульсов, генератор 3 двоичных последовательностейс неубывающим числом единиц, ш регистров 4, где ш " количество исходныхкодов, ш групп 5 по и элементов И,где и - число разрядов каждого исход.ного кода, группу 6 элементов ИЛИ,элемент И 7, вход 8 запуска устрой"ства.Генератор 3 двоичных последовательностей (фиг,2) содержит ш регистров 9, состоящих каждый из загрузочного триггера 10 и ш+1- разрядныхтриггеров 1, где- номер регистра9, а также из шэлементов ИЛИ 12первую группу 13 и последующие груп"пы 14 элементов И, группу 15 элементов ИЛИ, тактовый вход 6.Другая возможная реализация генератора 3 - по тактовый считывателькодов в выходной регистр из блокапамяти (постоянного или программируемого)Задача отыскания покрытия, особенно минимального покрытия, относитсяк универсальным экстремальным задачам и встречается довольно часто:при минимизации логических функций,при отыскании тестовых наборов дляцифровых схем, при формировании магазинокомплектов инструментов длястанков при обработке больших партий деталей и т.д,Под покрытием понимается наборстрок двоичной матрицы, содержащихв совокупности хотя бы одну единицув каждом столбце, а под минимальнымпокрытием - минимальный набор такихстрок.Устройство для вычисления минимального покрытия работает. следующимобразом,В исходном состоянии в регистрах4 зафиксированы ш комбинаций и-разрядных кодов, составляющих двоичную75427 матрицу, размера шп, минимальное покрытие которой требуется вычислитьТриггер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов заблокирован, При поступлениисигнала на вход 8 запуска устройства триггерпереходит в единичноесостояние, генератор 3 двоичных последоватсльностей устанавливается вначальное состояние, при которомна всех его выходах присутствуют нулевые сигналы (цепи начальной уста 50 новки не показаны). С выхода генератора 2 поступают тактовые импульсы 5 на вход генератора 3, который вырабатывает на ш выходах двоичные кодовые комбинации в следующем порядке:сначала всевозможные комбинации, содержащие одну единицу, затем всевоз-.20 можные комбинации, содержащие двеединицы затем комбинации, содержащие трн единицы, и т.д,; последнейкомбинацией является код 2 -1, содержащий единицы во всех разрядах, 25 Единичные сигналы каждой кодовой ком"бинации, содержащей К единиц ( 1 ФКбш) навыходах генератора З,разрешают прохождение выходных сигналов К регистров 4через элементы И соответствующих 30 групп 5. На выходе 1-го элемента ИЛИгруппы 6 появляется единичный сигнал,если на 1-м выходе хотя бы одного иэрегистров 4, выбранного с помощью генератора 3 на данном такте, присутстВует еДиничный сигнал ВЫХОДНОЙ кОДгенератора 3, при котором на всех выходах группы 6 элементов ИЛИ появляются единичные сигналы, соответствует покрытию двоичной матрицы. Приня,щ тый порядок выработки кодов генератором Зприводит к тому, что первоеже полученное в процессе работы устройства покрытие будет минимальным,так как обеспечивается минимально 4- возможным количеством задействован" йных регистров 4, В этом случае навыходе элемента И 7 появляется единичный сигнал, который устанавливаеттриггер 1 в нулевое состояние, и работа устройства заканчивается. Единичные сигналы в выходном коде генератора 3 указывают:номера регистров4, которые соответствуют наборустрок, образующих минимальное покрытие двоичной матрицы.Генератор 3 двоичных последовательностей с неубывающим числом единиц функционирует следующим образом,1 00001 0000 0 1 000 1 0 0 1 0 1 0 О 0 0010О 0101 0 0 О 0001О 100 0 0001О 0101 0 О0 О 0 00100 1001 0 0 О 01000 30000 0 0 1 0 О 0 0 О 00100010О 10 0 0001 0 0001 0 0001 0 0001 О 010 0 001О 01 О 001 0 001 О 10 О 10 1 0 0 1 О О 1 0 0 00030 0010 0 1 о з 12754В исходном состоянии на выходах загрузочных триггеров 10 установлены значения "1", на выходах разрядных триггеров 11 всех регистров 9 - значение "0" (цепи начальной установки не показаны), При поступлении тактовых импульсов на вход 16 происходит сдвиг единицы вправо в первом реги-. стре 9, Прохождение тактовых импульсов на вход второго регистра 9 разре О шается элементом И группы 13 только при наличии единичного сигнала в старшем (крайнем справа на фиг,2) разряде первого регистра 9, на вход синхронизации третьего регистра 9 15 тактовые импульсы могут поступить только при наличии единичного сигнала в последнем разряде второго регистра 9 (также крайнем справа) и т,д,- сдвиг в К-м регистре 9 разрешен 20 (Е"1)-м элементом И первой группы 13 только при наличии единичного сигнала в старшем разряде (1 с)-го регистра 9. При перемещении единицы в 1-й разряд 1-го регистра 9 единичные 25 значения одновременно устанавливаются в (1+1)-м разряде (1-1)-го регистра 9, (1+2)-м разряде (1-2)-го регистра 9 и т.д наконец в (1+1-1)-м разряде первого регистра 9,т,е, сдвину-ЗО тал единицараспространяется вправо ивверх по диагонали матрицы, что обеспечивается межрегистровыми соединениями с применением И элементов групп14 и элементов ИЛИ 12. Элементы Игрупп 14 разрешают прохождение сигналов от разрядных триггеров 11 1-горегистра 9 к разрядным триггерам 11(1-1)-го регистра 9 только при наличии единицы в старшем разряде(1-1)-го регистра 9. Таким образом,в разрядах каждого регистра 9, а также в каждом столбце треугольной матрицы присутствует в любой момент времени не более одной единицы. Сочетание ненулевых столбцов в треугольной матрице изменяются по тактам,образуя сначала всевозможные сочетания из ш по 1., затем всевозможные сочетания из ш по 2, затем из ш по 3и т.д наконец, через 2 - 1 тактовво всех столбцах будет по единицепосле чего схема, автоматически на 2-мтакте возвращается в исхоДное состояние вследствие передачи единицы изпервого разряда ш-го регистра 9 внулевые разряды всех регистров 9.Ниже приведены все 16 состояний схемы(фиг.2) при =4, которые последовательно сменяют друг друга по тактам.1275 5Дизъюнкции значений элементовстолбцов треугольной матрицы (безучета вспомогательного нулевогостолбца) образуют требуемые выходныесигналы на выходах элементов ИЛИгруппы 15,5В случае другого выйолнения генератора 3 с учетом конкретных значений элементов матрицы исходных данных некоторые коды в указанной последовательности при использованиипрограммируемого блока памяти могутпропускаться, чтоведет к дальнейшемуповышению быстродействия устройства. Например, если некоторый столбец матрицы содержит только одну единицу, строка, содержащая эту единицу, обязательно входит в минимальноепокрытие, поэтому в соответствующемразряде выходногокода генератора 3может быть постоянно зафиксированаединица, что сокращает перебор кодов в два раза, Кроме того, можетбыть зафиксирован ноль в разряде,соответствующемстроке, поглощеннойнекоторой другой строкой и т,п,Таким образом, быстродействие устройства повышается. 30Формула изобретения 1. Устройство для вычисления минимального покрытия, содержащее генератор импульсов, ш регистров, где ш.количество исходныМ кодов, ш групп по и элементов И, где и - число разрядов каждого исходного кода и элементов ИЛИ, элемент И и триггер, выход которого подключен к входу запус" ка генератора импульсов, выход 1-го разряда в 1-м регистре соединен с первым входом 3-го элемента И и д-й группы, выход 1-го элемента И 1-й группы подключен к 1-му входу45 3-го элемента ИЛИ группы, выходы ,всех элементов ИЛИ группы соединены с соответствующими входами элемента И, вход установки триггера в единицу является входом запуска устройства,50 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен генератор двоичных последовательностей с неубывающим числом .единиц, выход каждого из ш-разрядов5 г которого подключен к вторым входам элементов И соответствующей группы, выход элемента И соединен с входом обнуления триггера, выход генератора 427 а импульсов подключен к тактовому входу г ене ра тора двоичных последовательностей с неубывающим числом единиц,2, Устройство по п.1, о т л и ч аю щ е е с я тем, что генератор двоичных последовательностей с неубывающим числом единиц выполнен на группе элементов ИЛИ, ш группах элементов И и на ш регистрах, каждый 1-й регистр включает в себя загрузочный Ьи ш+1разрядных триггеров и ш- элементов ИЛИ, прямой выход 1-го разрядного триггера, кроме последнего, в 1-м регистре соединен с первым входом 1-го элемента ИЛИ этого регистра и -м входом 3-го элемента ИЛИ группы, прямой выход последнего разрядного триггера х-го регистра, кроме последнего, соединен с первыми входами д-го элемента И первой группы и элемента И (+1)-й груп,пы и последним входом (ш+1-1)-го элемента ИЛИ группы, выход З-го элемента И (1+1)-й группы подключен к второму входу 1-го элемента ИЛИ 1-го регистра, прямой выход разрядного триггера последнего регистра соединен с последним входом первого элемента ИЛИ группы и с информационными входами загрузочных триггеров всех регистров, прямой выход загрузочного триггера первого регистра соединен с информационным входом первого разрядного триггера этого регистра, выход 3-го элемента ИЛИ первого регистра подключен к информационному входу Я+1)-го разрядного триггера этого регистра, прямой выход загрузочного триггера в каждом из остальных регистров соединен с информационным входом первого разрядного триггера этого регистра и вторым входом первого элемента И соответствующей группы, выход 3-го элемента ИЛИ в каждом регистре, кроме первого, подключенного к информационному входу (3+1)-го разрядного триггера этого регистра и второму входу (3+1)-.го элемента И соответствующей группы, входы синхронизации загрузочного ивсех разрядных триггеровпервого регистра объединены с вторыми входами элементов И первой группы и подключены к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц, выход -го элемента И первой группы соединен с входами7 1275427 8синхронизации загрузочного,и всех ются соответствующими выходами генеразрядных триггеров (+1)-го регист- ратора двоичных последовательностейра, выходы элементов ИЛИ группы явля- с неубывающим числом единиц.1275427 Составитель О. РевинскийТехред Н,Глущенко Корректор И. Самборская Редактор В. Иванова Заказ 6561/40 Тираж 671 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, 3-35, Раушская наб д,4/5 Производственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4