Устройство для перебора сочетаний

 

Изобретение относится к вычислительной технике и может быть использовано для построения вычислительных устройств, решающих комбинаторные задачи. Целью изобретения является повышение быстродействия и упрощение устройства. Для достижения поставленной цели устройство содержит четыре группы элементов И 2-5, две группы элементов ИЛИ 6,. 11, регистр 8 сдвига, элементы ИЛИ-НЕ 7, которые обеспечивают сквозной перенос информации одновременно с переключением триггеров и только время переключения последнего триггера складывается со временем сквозного переноса. 2 ил. ш (Л

СО1ОЗ COBETCHHX

СО1ф1АЛИСТИЧЕСНИХ

РЕСПУБЛИК (51)4 G 06 F 15/31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCKOMY СВИДЕТЕЛЬСТВУ

Фиг. 1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4101805/24-24 (22) 11.06.86 (46) 30.01.88. Бюл. В 4 (7I) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань и А.В.Пришибской (53) 681 ° 325(088.8) (56) Авторское свидетельство СССР

У 903891, кл. С 06 F 15/3), 1980.

Авторское свидетельство СССР, Ф 1140127, кл. G 06 F 15/31, 1983.

Авторское свидетельство СССР

У 1262520, кл. G 06 F 15/31, 1985, „„SU„,1 70655 А1 (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИИ (57) Изобретение относится к вычислительной технике и может быть использовано для построения вычислительных устройств, решающих комбинаторные задачи. Целью изобретения является повышение быстродействия и упрощение устройства. Для достижения поставленной цели устройство содержит четыре группы элементов И 2-5, две группы элементов ИЛИ 6, ll, регистр 8 сдвига, элементы ИЛИ-НЕ 7, которые обеспечивают сквозной перенос информации одновременно с переключением триггеров и только время переключения последнего триггера складывается со временем сквозного переноса. 2 ил.

1 137065

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

Цель изобретения — повышение быст- 10 родействия и упрощение устройства.

На фиг.1 приведена структурная схема устройства (5 разрядов); на фиг.2 — временные диаграммы работы устройства. 15 устройство содержит группу 1 триггеров, четыре группы 2 — 5 элементов

И, первую группу 6 элементов ИЛИ, группу 7 элементов ИЛИ-НЕ, регистр 8 сдвига, элемент 9 задержки, группу

10 элементов ИСКЛОЧАЮЩЕЕ ИЛИ, вторую группу ll элементов ИЛИ, группу 12 элементов запрета, элемент ИЛИ 13 и триггер 14. Устройство имеет тактовый 15 вход, информационный 16 25

5 2 вход 17 количества перебираемых элементов и выход 18 признака окончания перебора.

Принцип работы устройства состоит в следующем.

Каждое очередное сочетание получается из предыдущего путем перевода и левых следующих подряд единичных разрядов в "0", а первого правого нулевого разряда — в "1 и последующего восстановления в (m-I) крайних левых разрядах единиц. Если в k левых разрядах стоят нули, то осуществляется обход этих разрядов и в

"0" переводится m подряд следующих единичных разрядов начиная с (k+I)ro разряда, à (k+m+1) é разряд переводится в "1". При этом независимо от того, с каких разрядов начинается их перевод в нулевое состояние, в единичное состояние восстанавливаются (m-1) левых разрядов.

Рассмотрим пример формирования всех сочетаний для п=5 и m=3.

1. 11100 2. 11010 3. 10110

6. 10101 7. 01101 8. 10011

Перед началом работы триггер ° 30 группы 1 по R-входам устанавливаются в нулевое состояние, а затем по Sвходам в три первых триггера группы

l записываются единицы. В случае перебора сочетаний с и по m, при п и

m k, где k — максимальное количество элементов, происходит подача единичных потенциалов íà (n-1) крайних слева разряда входа 17. В данном случае при и = 1 = 5 на все разряды вхо- 40 да 17 подается единичный потенциал.

При подаче тактового импульса (ТИ) на вход 15 регистр 8 сдвига устанавливается в исходное состояние, т.е. в его первый разряд записывается еди-45 ница, а во все остальные — нули.

Триггер 14 устанавливается в нулевое состояние, разрывая связь через элементы If третьей группы 4 единичных триггеров rpynrrv 1 с разря- 50 дами информационного выхода 16. Кроме того, ТИ поступает на первые элементы И первой и второй групп, таккак первый триггер группы I находится В единичнОм сОстОянии, и через 55 открытый первый элемент И первой группы 2 на входы элемента ИСКЛЮЧАIОЩЕЕ ИЛИ 10 и элемента 12 запрета и на вход установки в "0" первого

4. 01110 5. 11001

9. 01011 10. 00111 триггера группы, а через первый элемент ИЛИ-НЕ группы 7 — на синхровход первого триггера групп 1, переводя этот триггер в нулевое состояние. С выхода первого элемента И первой группы 2 ТИ поступает на вход первого элемента И четвертой группы 5 и, пройдя через первый элемент ИЛИ первой группы 6, поступает на вход второго элемента И первой группы 2. Поскольку второй триггер группы 1 находится в единичном состоянии, то ТИ не проходит через первый элемент И

1 четвертой группы 5, так как на его второй вход поступает нулевой потенциал с инверсного выхода второго триггера группы 1, а через открытый второй элемент И первой 2 группы поступает на входы вторых элементов

ИСКЛ1ОЧАЮЩИЕ ИЛИ 10 и запрета 12, вход установки в ноль и через второй элемент ИЛИ-НЕ 7 групп на вход синхронизации триггера 14. Пройдя через открытый второй элемент И первой группы 2, ТИ проходит через второй элемент ИЛИ группы 6 и поступает на третий элемент И первой группы 2, открытый единичным потенциалом триггера 14. С выхода третьего элемента

И первой группы ТИ проходит на входы

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

Устройство для перебора сочетаний, содержащее группу триггеров, четыре

50 группы элементов И, первую группу элементов ИЛИ, группу элементов ИЛИНЕ, регистр сдвига и элемент задержки, причем выходы разрядов регистра сдвига подключены к входам установки

55 в "1" соответствующих триггеров группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и упрощения, оно содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторую

3 137065 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и запрета 12, вход установки нулевого состояния и через третий элемент ИЛИ-HE группы 7 на вход синхронизации треЬ тьего триггера группы I. С выхода третьего элемента И первой 2 группы

ТИ поступает на третий элемент И четвертой группы 5, открытый единичным потенциалом с инверсного выхода четвертого триггера группы I, и, пройдя его, попадает на вход установки единичного состояния, а эатем через элемент ИЛИ-НЕ группы 7 — на вход синхронизации четвертого триггера группы 1, переводя его из нулевого состояния в единичное. Далее происходит восстановление единичного состояния первого и второго триггеров группы I.

При этом с выходов первых трех элементов И первой группы 2 импульсы, рассредоточенные по времени с некоторой задержкой, поступают на вход соответствующих элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ группы 10, образующих цепи форми- 25 рования последовательности сдвинутых во времени импульсов восстановления, поступающих на вход сдвига регистра

8. На выходе этой цепи получается последовательность из трех сдвинутых gp во времени импульсов (фиг.2).

Первый импульс этой последовательности продвигает единицу из первого во второй разряд регистра 8 сдвига.

Второй импульс передвигает в третий разряд единицу, которая поступает на вход принудительной установки единичного состояния первого триггера группы 1. По третьему импульсу, единица переходит в четвертый разряд регистра 8 сдвига и переводит второй триггер группы 1 в единичное состояние.

Одновременно с этим тактовый импульс поступает на вход третьего элемента ИЛИ второй группы 11 и, пройдя 45 цепь элементов ИЛИ второй группы и элемент 9 задержки, поступает на вход установки в единицу триггера 14, переводя его в единичное состояние и открывая элементы И третьей группы

4. На вторые входы этих элементов поступает сочетание с прямых выходов соответствующих триггеров группы 1, которое проходит на соответствующие разряды информационного выхода 16.

При формировании сочетания, следующего эа сочетанием 01110, ТИ проходит через открытый первый элемент И второй группы 3 и поступает на г ч вход второго элемента И первой группы 2, открытого единичным потенциалом с прямого выхода второго триггера группы I. Далее прохождение импульса аналогично описанному.

Таким образом, по цепи, состоящей из первых и вторых элементов И группы 2 и ИЛИ первой группы 6, осуществляется сквозной проход импульса че— рез триггеры, находящиеся в единичном состоянии, и их перевод в нулевое состояние, а по цепи элементов

И второй группы 3 осуществляется сквоэной проход импульса через триггеры, находящиеся в нулевом состоянии. После формирования последнего сочетания 00111 ТИ поступая на вход

15, проходит по цепи, состоящей из первого и второго элементов И второй группы, осуществляя обход триггеров группы 1, находящихся в нулевом состоянии, и по цепи, состоящей из второго элемента ИЛИ первой группы 6 элемента И 13, третьего элемента И первой группы 2, переводя триггеры группы 1, которые находятся в единичном состоянии, в нулевое состояние.

Пройдя открытый пятый элемент И первой группы, импульс поступает на входы элемента ИЛИ 13 и через пятый элемент ИЛИ-НЕ группы 7 на вход синхронизации пятого триггера группы 1, переводя его в нулевое состояние.

Пройдя элемент ИЛИ 13, импульс оказывается на выходе окончания перебора всех сочетаний. з

В случае перебора сочетаний С, сигнал проходит на выход 18 признака окончания перебора через элемент 12 запрета и элемент ИЛИ 13, когда сформируется сочетание Olll, т.е. когда в единичном состоянии окажутся правые подряд стоящие триггеры.

5 137065 группу элементов ИЛИ, группу элементов запрета, элемент ИЛИ и триггер, причем первые входы первых элементов

И первой и второй групп подключены к тактовому входу устройства, входам установки исходного кода регистра сдвига и входу установки в "0" триггера, прямой выход которого соединен с первыми входами элементов И третьей группы, выходы которых являются 10 соответствующими разрядами информационного выхода устройства, прямые выходы триггеров группы соединены с вторыми входами соответствующих элементов И первой и третьей групп, ин- 15 версные выходы с второго по (N-1)-й триггеров группы (где N — разрядность сочетания) соединены с первыми зходами с второго по (N-1)-й элементов И второй и четвертой групп соот- 20 ветственно, инверсный выход первого триггера группы соединен с вторым входом первого элемента И второй группы, инверсный выход И-го триггера группы соединен с первым входом

N-го элемента И четвертой группы, выход i-ro элемента И второй группы (1. = 1,."1) соединен с первым входом

i-го элемента ИЛИ первой группы и вторым входом (i + 1)-го элемег э И 30 второй группы, выход i-го элемента

И первой группы (i = 1,N — 2) соединен с первым входом 1.-ro элемента

ИЛИ первой группы, вторым входом го элемента И четвертой группы, входом установки в "0" i ro триггера группы, первым входом 1.-ro элемента

ИСКЛ10ЧАЮЩЕЕ ИЛИ, г рямым входом i-гс элемента запрета, и первым входом

i-го элемента ИЛИ-НЕ, выход которого 40 подключен.к синхровходу 1-го триггера группы, выход (N-1)-го элемента

И первой группы подключен к второму входу (N-1)-го элемента И четвертой группы, первому входу (N-1)-го эле- 45 мента ИЛИ первой группы, входу установки в "0" (N-1)-ro триггера группы, прямому входу ;N-1)-го элемента зап5 6 рета, второму входу (N-2) -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первому входу (N-1)-го элемента ИЛИ-HF первой группы, выход которого подключен к синхроводу (N-1)-ro триггера группы, выход N-го элемента И первой группы подключен к входу установки в "0"

N-го триггера группы, первому входу элемента ИЛИ и первому входу N-ro, элемента ИЛИ-HE первой группы, выход которого подключен к синхровходу Nго триггера группы, выход i-ro элемента ИЛИ первой группы (i = 1,N) соединен с вторым входом (i+1)-го элемента И первой группы, выход i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (1 = 2,N) группы соединен с вторым входом (i-l)-го элемента ИСКЛ10ЧА10ЩЕЕ ИЛИ той же группы, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ группы соединен с входом сдвига регистра сдвига, инверсный вход i-го элемента запрета (i = 1,N) является i-м разрядом входа количества перебираемых элементов устройства и подключен к третьему входу i-го элемента И четвертой группы, выходы элементов запрета подключены к соответствующим входам начиная с второго элемента ИЛИ, выход которого является выходом признака окончания перебора устройства, выход

z-го элемента И четвертой группы (i = 1,N — ", соединен с вторым входом (i+1)-го элемента ИЛИ-НЕ группы, входом установки в единицу (i+1)-го триггера группы и с первым входом

i-го элемента ИЛИ второй группы, выход (N-l)-ro элемента И четвертой группы соединен с вторым входом N-ro элемента ИЛИ-НЕ группы, входом установки в "1" N-го три"гера группы и вторым входом (N-2, -го элемента ИЛИ второй группы, выход i-ro элемента

ИЛИ второй группы (i = 2, 1) соединен с вторым входом (i-1)-го элемента

ИЛИ второй группы, выход первого элемента ИЛИ второй группы подключен к входу установки в "1" триггера.

1370655

8о/Х

Еих

Еыхм1-Ф

Редактор Л. Пчолинская

Тира к 704 Подписное

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

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

Заказ 42 I /49

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

Вэи

Фскю.

Составитель Н.Захаревич

Техред И. дндык Корректор Л.Патай