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

 

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

ОВ (Ш

SU, 427 A i (51)4 а 06 Р 7/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, К ASTOPGHOMV СВИДДтыжтву

) Ьиа4

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТЭЙ (21) 3856484/24-24 (22) 11.02.85 (46) 07.12.86. Бюл. N 45 (71) Владимирский политехнический институт

0 (72) В.Ф, Романов (53) 681.325.66(088,8) (56) Авторское свидетельство СССР

11 558275, кл. G 06 F 7/00, 1974, Авторское свидетельство СССР

У 1068930, кл. G 06 F 7/00, 17.05.82, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МННИИАЛЬНОГО IIOKPbff HH (57) Изобретение относится к вычислительной технике, Использование в специализированных устройствах обработки информации обеспечивает повышение его быстродействия, Оно содержит триггер, генератор импульсов, регистры, группы элементов И, хруппу элементов ИЛИ и элемент И. Благо"

:даря введению генератора двоичных

;последовательностей с неубывающим числОм единиц первое ме полученное в процессе работы покрытие является минимальным, 1 s.ï,ô-лы, 2 ил.

1 1г

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

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

Устройство (фиг.i) содержит триггер 1, генератор 2 импульсов, генератор 3 двоичных последовательностей с неубывающим числом единиц, m регистров 4, где m — - количество исходных кодов, m групп 5 по и элементов И, где n — число разрядов каждого исход. ного кода, группу 6 элементов ИЛИ, элемент И 7, вход 8 запуска устрой" ства.

Генератор 3 двоичных последовательностей (фиг,2) содержит m регистров 9, состоящих каждый из загрузочного триггера 10 и m+I-i разрядных триггеров 11 где i — номер регистра

9, а также из m-i элементов ИЛИ 12, первую группу 13 и последующие группы 14 элементов И, группу 15 элементов ИЛИ, тактовый вход 16.

Другая возможная реализация генератора 3 — по тактовый считыватель кодов в выходной регистр из блока памяти (постоянного или программируемого)„

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

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

В исходном состоянии в регистрах

4 зафиксированы m комбинаций и-разрядных кодов, составляющих двоичную

75427 матрицу Размера тп, минимальное покрытие которой требуется вычислить °

Триггер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов заблокирован, При поступлении сигнала на вход 8 запуска устройства триггер 1 переходит в единичное состояние, генератор 3 двоичных последоватсльностей устанавливается в начальное состояние, при котором на всех его выходах присутствуют нулевые сигналы (цепи начальной уста5 l0 новки не показаны). С выхода генератора 2 поступают тактовые импульсы

15 на вход генератора 3, который вырабатывает íà m выходах двоичные кодовые комбинации в следующем порядке: сначала всевозможные комбинации, содержащие одну единицу, затем всевоз-.

20 можные комбинации, содержащие двеединицы, затем комбинации, содержащие трн единицы, и т.д,; последней

fthm комбинацией является код 2 -1, содержащий единицы во всех разрядах, Единичные сигналы каждой кодовой комбинации, содержащей К единиц (1Жйп) на выходах генератора З,разрешают прохождение выходных сигналов К регистров 4 через элементы И соответствующих

30 групп 5. На выходе j-ro элемента ИЛИ группы 6 появляется единичный сигнал, если на j-м выходе хотя бы одного иэ регистров 4, выбранного с помощью генератора 3 на данном такте, присутствует еДиничный сигнал, ВыхОДнОЙ кОД генератора 3, при котором на всех выходах группы 6 элементов ИЛИ появляются единичные сигналы, соответствует покрытию двоичной матрицы. Приня,щ тый порядок выработки кодов генератором Зприводит к тому, что первое же полученное в процессе работы устройства покрытие будет минимальным, так как обеспечивается минимально

4- возможным количеством задействован"

Ъ ных регистров 4, В этом случае на выходе элемента И 7 появляется единичный сигнал, который устанавливает триггер 1 в нулевое состояние, и работа устройства заканчивается. Единичные сигналы в выходном коде генератора 3 указывают. номера регистров

4, которые соответствуют набору строк, образующих минимальное покрытие двоичной матрицы.

Генератор 3 двоичных последовательностей с неубывающим числом единиц функционирует следующим образом, 27

О 0001

I 000

1 О О

О 001 О

000

1 О О

О О! 00

О 1000

1 000

I О О

1 0000

1 000 ! О О

1 000

1 О О

1 0

1 О о о о

О 0010

О O I O

1 О О

0 000! о 1оо

О 0001

О 0!О

1 О 0

О о о оо10

О 100

1 0 О

О 0100

О I ОО

1 00 оо

1 О

1 0

1 О

1 О о оо!о

0010 о о

О 0001

О 0001 О 0001 О 0001

О 010

О 001 о о !

О OOI

О 001 о о о о

I О О

1 О

I О о! 0

О 000

О OO I

О О 1 о з 12754

В исходном состоянии на выходах загрузочных триггеров 10 установленыi значения "!" на выходах разрядных триггеров 11 всех регистров 9 — значение "0 (цепи начальной установки не показаны), При поступлении тактовых импульсов на вход 16 происходит сдвиг единицы вправо в первом реги-. стре 9, Прохождение тактовых импульсов на вход второго регистра 9 разре- 1О шается элементом И группы 13 только при наличии единичного сигнала в старшем (крайнем справа на фиг,2) разряде первого регистра 9, на вход синхронизации третьего регистра 9 15 тактовые импульсы могут поступить только при наличии единичного сигнала в последнем разряде второго регистра 9 (также крайнем справа) и т,д.сдвиг в k-м регистре 9 разрешен 20 (k"1)-м элементом И первой группы

1 3 только при наличии единичного сигнала в старшем разряде (k-1)-го регистра 9. При перемещении единицы в

1-й разряд k-ro регистра 9 единичные 25 значения одновременно устанавливаются в (1+1)-м разряде (k-1)-ro регистра 9, (1+2)-м разряде (k-2)-го регистра 9 и т.д,, наконец„ в (1+k-1)-м разряде первого регистра 9,т,е. сдвину-ЗО тал единица распространяется вправо и вверх по диагонали матрицы, что обеспечивается межрегистровыми соединениями с применением И элементов групп

14 и элементов ИЛИ 12. Элементы И групп 14 разрешают прохождение сигналов от разрядных триггеров 11 k-ro регистра 9 к разрядным триггерам 11 (k-1)-ro регистра 9 только при наличии единицы в старшем разряде (k-1)-го регистра 9, Таким образом, в разрядах каждого регистра 9, а также в каждом столбце треугольной матрицы присутствует в любой момент времени не более одной единицы. Сочетание ненулевых столбцов в треуголь-. ной матрице изменяются по тактам, образуя сначала всевозможные сочетания из m no i. затем всевозможные сочетания из m по 2, затем из m по 3 и т.д,, наконец, через 2 — 1тактов во всех столбцах будет по единицепосле чего схема. автоматически на 2-м такте возвращается в исхоДное состояние вследствие передачи. единицы из первого разряда ш-ro регистра 9 в нулевые разряды всех регистров 9.

Ниже приведены все 16 состояний схемы (фиг.2) при =4, которые последовательно сменяют друг друга по тактам.

Дизъюнкции значений элементов столбцов треугольной матрицы (без учета вспомогательного нулевого столбца) образуют требуемые выходные сигналы на выходах элементов ИЛИ группы 15.

В случае другого выйолнения генератора 3 с учетом конкретных значений элементов матрицы исходных данных некоторые коды в указанной последовательности при использовании программируемого блока памяти могут пропускаться, чтоведет к дальнейшему повышению быстродействия устройства. Например, если некоторый столбец матрицы содержит только одну единицу, строка, содержащая эту единицу, обязательно входит в минимальное покрытие, поэтому в соответствующем разряде выходного кода генератора 3 может быть постоянно зафиксирована единица, что сокращает перебор кодов в два раза, Кроме того, может быть зафиксиров;,ц ноль в разряде, соответствующем строке, поглощенной некоторой другой строкой и т,п, Таким образом, быстродействие устройства повышается.

30 формула изобретения

l. Устройство для вычисления минимального покрытия, содержащее генератор импульсов, m регистров, где m.количество исходныМ кодов, m групп по п элементов И, где и — число разрядов каждого исходного кода, п элементов ИЛИ, элемент И и триггер, выход которого подключен к входу запус" ка генератора импульсов, выход j-ro разряда в i-м регистре соединен с первым входом j-ro элемента И и !

1-й группы, выход j-го элемента И

i-й группы подключен к i-му входу

j- ãî элемента ИЛИ группы, выходы .всех элементов ИЛИ группы соединены с соответствующими входами элемента

И, вход установки триггера в единицу является входом запуска устройства, 50 о. т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен генератор двоичных последовательностей с неубывающим числом .единиц, выход каждого из m-разрядов

5г которого подключен к вторым входам элементов И соответствующей группы, выход элемента И соединен с входом обнуления триггера, выход генератора

427 а импульсов подключен к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц, 2, Устройство по п.l, о т л и ч аю щ е е с я тем, что генератор двоичных последовательностей с неубывающим числом единиц выполнен на группе элементов ИЛИ, m группах элементов И и на m регистрах, каждый i-й регистр включает в себя загрузочный

I и в+1-i-разрядных триггеров и m-i элементов ИЛИ, прямой выход i-го разрядного триггера, кроме последнего, в i-м регистре соединен с первым входом j-ro элемента ИЛИ этого регистра и i-м входом j-ro элемента ИЛИ группы, прямой выход последнего разрядного триггера i-го регистра, кроме последнего, соединен с первыми входами i-ro элемента И первой группы и элемента И (i+1)-й груп.пы и последним входом (ш+1-i)-ro элемента ИЛИ группы, выход j-го элемента И (i+1)-й группы подключен к второму входу 1-го элемента ИЛИ i-ro регистра, прямой выход разрядного триггера последнего регистра соединен с последним входом первого элемента ИЛИ группы и с информационными входами загрузочных триггеров всех регистров, прямой выход загрузочного триггера первого регистра соединен с информационным входом первого разрядного триггера этого регистра, выход j-го элемента ИЛИ первого регистра подключен к информационному входу (j+1)-го разрядного триггера этого регистра, прямой выход загрузочного триггера в каждом из остальных регистров соединен с информационным входом первого разрядного триггера этого регистра и вторым входом первого элемента И соответствующей группы, выход..j-го элемента ИЛИ в каждом регистре, кроме первого, подключенного к информационному входу (j+1)-ro разрядного триггера этого регистра и второму входу (3+1)-.го элемента И соответствующей группы, входы синхронизации загрузочного ивсех разрядных триггеров первого регистра объединен с вторыми входами элементов

И первой группы и подключены к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц, выход i-ro элемента И первой группы соединен с входами

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

)275427

Составитель О. Ревинский

Техред H.Ãëóùåíêî Корректор М. Самборская

Редактор В. Иванова

Заказ 656)/40 Тираж 671 Подписное

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

113035, Москва, Ж-35, Раушская наб,, д,4/5

Производственно- полиграфическое предприятие, г. Ужгород, ул, Проектная, 4