Устройство для вычисления минимального покрытия Советский патент 1986 года по МПК G06F7/38 

to

СП

ii(

1C

Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации. Цель изобретения - повышение быстродействия . На фиг.1 изображена блок-схема устройства для вычисления минимального покрытия; на фиг,2 - функциональная схема генератора двоичных последовательностей с неубывающим числом единиц для случая . Устройство (фиг.О содержит триггер 1, генератор 2 импульсов, генератор 3 двоичных последовательностей с неубывающим числом единиц, m реги стров 4, где m - количество исходных кодов, m групп 5 по п элементов И, где п - число разрядов каждого исход него кода, группу 6 элементов ИЛИ, элемент И 7, вход 8 запуска устройства. Генератор 3 двоичных последовательностей (фиг,2) содержит m регист ров 9, состоящих каждый из загрузочного триггера 10 и m+1-i разрядных триггеров 11, где i - номер регистра 9, а также из m-i элементов ИЛИ 12, первую группу 13 и последующие группы 14 элементов И, группу 15 элементов ИЛИ, тактовый вход 16. Другая возможная реализация генератора 3 - по тактовый считыватель кодов в выходной регистр из блока памяти (постоянного или программируемого ) Задача отыскания покрытия, особен но минимальнбго покрытия, относится к универсальным экстремальным задачам и встречается довольно часто: при минимизации логических функций, при отыскании тестовых наборов для цифровых схем, при формировании магазинокомплектов инструментов для станков при обработке больших партий деталей и т.д. Под покрытием понимается набор строк двоичной матрицы, содержащих в совокупности хотя бы одну единицу в каждом столбце, а под минимальным покрытием -минимальный набор таких строк. Устройство для вычисления минимального покрытия работает . следующим образом, В исходном состоянии в регистрах 4 зафиксированы m комбинаций п-разрядных кодов, составляющих ДВОИЧНУЮ 272 матрицу,размера , минимальное покрытие которой требуется вычислить. Триггер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов заблокирован. При поступлении сигнала на вход 8 запуска устройства триггер i переходит в единичное состояние, генератор 3 двоичных последовательностей устанавливается в начальное состояние, при котором на всех его выходах присутствуют нулевые сигналы (цепи начальной установки не показаны), С выхода генератора 2 поступают тактовые импульсы на вход генератора 3, который вырабатывает на m выходах двоичные кодовые комбинации в следукнцем порядке: сначала всевозможные комбинации, содержащие одну единицу, затем всевоз-. можные комбинации, содержащие двеединицы, затем комбинации, содержащие три единицы, и т,д,; последней комбинацией является код 2 -1, содержащий единицы во всех разрядах, Единичные сигналы каждой кодовой комбинации, содержащей К единиц (ISQSm) на выходах генератора 3,разрешают прохождение выходных сигналов К регистров 4 через элементы И соответствующих групп 5, На выходе j-ro элемента ИЛИ группы 6 появляется единичный сигнал, если на j-м выходе хотя бы одного из регистров 4, выбранного с помощью генератора 3 на данном такте, присутст- вует единичный сигнал. Выходной код генератора 3, при котором на всех выходах группы 6 элементов ИЛИ появляются единичные сигналы, соответствует покрытию двоичной матрицы, Принятый порядок выработки кодов генератором 3 приводит к тому, что первое же полученное в процессе работы устройства покрытие будет минимальным, так как обеспечивается минимально возможным количеством задействованных регистров 4, В этом случае на выходе элемента И 7 появляется единичный сигнал, который устанавливает триггер 1 в нулевое состояние, и работа устройства заканчивается. Единичные сигналы в выходном коде генератора 3 указывают номера регистров 4, которые соответствуют набору строк, образующих минимальное покрытие двоичной матрицы. Генератор 3 двоичных последовательностей с неубывающим числом единиц функционирует следующим образом. 312 В исходном состоянии на выходах загрузочных триггеров 10 установлены значения 1, на выходах разрядных триггеров 11 всех регистров 9 - значение О (цепи начальной установки не показаны). При поступлении тактовых импульсов на вход 16 происходит сдвиг единицы вправо в первом реги-. стре 9. Прохождение тактовых импульсов на вход второго регистра 9 разре шается элементом И группы 13 только при наличии единичного сигнала в старшем (крайнем справа на фиг.2) разряде первого регистра 9, на вход синхронизации третьего регистра 9 тактовые импульсы могут поступить только при наличии единичного сигнала в последнем разряде второго регистра 9 (также крайнем справа) и т.д, сдвиг в k-M perHctpe 9 разрешен (k-l)-M элементом И первой группы 13 только при наличии единичного сиг нала в старшем разряде (k-l)-ro реги стра 9. При перемещении единицы в 1-й разряд k-ro регистра 9 единичные значения одновременно устанавливаются в (1+1)-м разряде (k-l)-ro регист ра 9, (1+2)-м разряде (k-2)-ro регистра 9 и т.д., наконец в (l+k-l)-M разряде первого регистра 9,т.е. сдвину

о 1000

I 0000

00010

о 0001

00100 7 тая единица распространяется вправо и вверх по диагонали матрицы, что обеспечив ется межрегистровыми соединениями с применением И элементов групп 14 и элементов ИЛИ 12. Элементы И групп 14 разрешают прохождение сигналов от разрядных триггеров 11 k-ro регистра 9 к разрядным триггерам 11 (k-l)-ro регистра 9 только при наличии единицы в старшем разряде (k-l)-ro регистра 9. Таким образом, в разрядах каждого регистра 9, а также д каждом столбце треугольной матрицы присутствует в любой момент времени не более одной единицы. Сочетание ненулевых столб цов в треугольт ной матрице изменяются по тактам| образуя сначала всевозможные сочетания из m по 1, затем всевозможные toчетания из m по 2, затем из га по 3 и т.д., наконец, через 2 - тактов во всех столбцах будет по eдйннцeJ после чего схема .автоматически на такте возвращается в исходное состояние вследствие передачи единицы из первого разряда т-го регистра 9 в нулевые разряды всех регистров 9. Ниже приведены все 16 состояний схемы (фиг. 2) при 4, которые последовательно сменяют друг друга по тактам.

Изобретение относится к вычислительной технике. Использоваине в специализированных устройствах обработки информации обеспечивает повышение его быстродействия. Оно содержит триггер, генератор импульсов, регистры, группы элементов И, тр уппу элементов ИЛИ и элемент И. Благо:даря введению генератора двоичных :последовательностей с неубывающим числим единиц первое же полученное в процессе работы покрытие является минимальным. 1 э.п.ф-лы, 2 ил. (Л С

00001 0001

о о I о I s Дизъюнкции значений элементов столбцов треугольной матрицы (без учета вспомогательного нулевого столбца) образуют требуемые выходные сигналы на выходах элементов ИЛИ группы 15. В случае другого выйолнения генератора 3 с учетом конкретных значений элементов матрицы исходных данных некоторые кодьт в указанной последовательности при использовании программируемого блока памяти могут пропускаться, чтоведет к дальнейшему повышению быстродействия устройства. Например, если некоторый столбец матрицы содержит только одну еди ницу, строка, содержащая эту единицу, обязательно входит в минимальное покрытие, поэтому в соответствующем разряде выходногокода генератора 3 может быть постоянно зафиксирована единица, что сокращает перебор кодов в два раза. Кроме того, может быть зафиксирован ноль в разряде, соответствующем строке, поглощенной некоторой другой строкой и т.п. Таким образом, быстродействие ус ройства повьпиается. Формула изобретения I. Устройство для вычисления мини мального покрытия, содержащее генератор импульсов, m регистров, где гаколичество исходные кодов, m групп по п элементов И, где п - число ра рядов каждого исходного кода, п элементов ИЛИ, элемент И и триггер, выход которого подключен к входу запус ка генератора импульсов, выход j-rp разряда в i-м регистре соединен с первым входом j-ro элемента И и 1-й группы, выход j-ro элемента И i-й группы подключен к i-му входу элемента ИЛИ группы, выходы .всех элементов ИЛИ группы соединены с соответствующими входами элемента И, вход установки триггера в единицу является входом запуска устройства отличающееся тем, что, с целью повьппения быстродействия, в него введен генератор двоичных после довательностей с неубывающим числом единиц, выход каждого из т-разрядов i OTOporo подключен к вторым входам элементов И соответствующей группы вькод элемента И соединен с входом обнуления триггера, выход генератора 27- -ft импульсов подключен к тактовому входу генератора двоичных последовательностей с неубываюшим числом единиц. 2, Устройство по п,, отличающееся тем, что генератор дноичных последовательностей с неубывающим числом единиц выполнен на группе элементов ИЛИ, m группах элементов И и на m регистрах, каждый i-й регистр включает в себя загрузочный и m+l-i-разрядных триггеров и m-i элементов ИЛИ, прямой выход i-ro разрядного триггера, кроме последнего, в i-M регистре соединен с первым входом j-ro элемента 1ШИ этого регистра и i-м входом j-ro элемента ИЛИ группы, прямой выход последнего разрядного триггера i-ro регистра, кроме последнего, соединен с первьми входами i-ro элемента И первой группы и элемента И (i-ll)-й груп.пы и последним входом ()-ro элемента ИЛИ группы, выход j-ro элемента И (i+l)-A группы подключен к второму входу j-ro элемента ИЛИ i-ro регистра, прямой выход разрядного триггера последнего регистра соединен с последним входом первого элемента ИЛИ группы и с информационными входами загрузочных триггеров всех регистров, прямой выход загрузочного триггера первого регистра соединен с информационным входом первого разрядного триггера этого регистра,выход j-ro элемента ИЛИ первого регистра подключен к информационному входу (j+l)-ro разрядного триггера этого регистра, прямой выход загрузочного триггера в каждом из остальных регистров соединен с информационным входом первого разрядного триггера этого регистра и вторым входом первого элемента И соответствующей группы, выход j-ro элемента ИЛИ в каждом регистрер кроме первого, подключенного к информационному вхоДУ (j+l)-ro разрядного триггера этого регистра и второму входу (j + l)r-ro элемента И соответствующей группы, входы синхронизации загрузочного ивсех разрядных триггеров первого регистра объединены с вторыми входами элементов И первой группы и подключены к тактовому входу генератора двоичных последовательностей с неубьшающим числом единиц, выход i-ro элемента И первой группы соединен с входами

712754278

синхронизации загрузочного и всех ются.соответствующими выходами генеразрядных триггеров (i+l)-ro регист- ратора двоичных последовательностей ра, выходы элементов ИЛИ группы явля- с неубьгоающим числом единиц.

16, J

фиг. г