Устройство для перебора сочетаний Советский патент 1988 года по МПК G06F17/10 

13

00

о

Од

сл ел

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

Фиг.

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

изобретения - повышение быст- Q ных разрядов в О

го нулевого разряд дующего восстановл них левых разрядах левых разрядах сто

родействия и упрощение устройства.

На фиг.1 приведена структурная схема устройства (5 разрядов); на фиг.2 - временные диаграммы работы устройства.

Устройство содержит группу 1 триггеров, четыре группы 2-5 элементов И, первую группу 6 элементов ИЛИ, группу 7 элементов ИЛИ-НЕ, регистр 8 сдвига, элемент 9 задержки, группу 10 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторую группу 11 элементов ИЛИ, группу 12 элементов запрета, элемент ИЛИ 13 и триггер 14. Устройство имеет тактовый 15 вход, информационный 16 выход, 25 всех сочетаний для и . 1. 11100 2. 11010 3. 10110 4. 01110 5. 11001

Перед началом работы тригге группы 1 по R-входам устанавливаются в нулевое состояние, а затем по S- входам в три первых триггера группы 1 записываются единицы. В случае перебора сочетаний с п по т, при п и m k, где k - максимальное количество элементов, происходит подача единичных потенциалов на (п-1) крайних слева разряда входа 17. В данном случае при п k 5 на все разряды вхо да 17 подается единичный потенциал. При подаче тактового импульса (ТИ) на вход 15 регистр 8 сдвига устанавливается в исходное состояние, т.е. в его первый разряд записьгеается еди ница, а во все остальные - нули. Триггер 14 устанавливается в нулевое состояние, разрывая связь через элементы И третьей группы 4 единичных выходов триггеров группы 1 с разрядами информационного выхода 16. Кроме того, ТИ поступает на первые элементы И первой и второй групп, так как первый триггер группы 1 находится в единичном состоянии, и через открытый первый элемент И первой группы 2 на входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и элемента 12 запрета и на вход установки в О первого

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

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

Каждое очередное сочетание получается из предыдущего путем перевода га левых следующих подряд единичных разрядов в О

а первого правого нулевого разряда - в 1 и последующего восстановления в (m-l) крайних левых разрядах единиц. Если в k левых разрядах стоят нули, то осуществляется обход этих разрядов и в О переводится m подряд следующих единичных разрядов начиная с (k-t-l)- го разряда, а (k+m+I)-й разряд переводится в 1. При этом независимо

от того, с каких разрядов начинается их перевод в нулевое состояние, в единичное состояние восстанавливаются (т-1) левых разрядов.

Рассмотрим пример формирования

. 10011

I 30

35

тся - пы пеиестединихслувхо-40ал. ) нав.е. еди-дд евое элехряКроэлеакдитз ее ЧАЮи

50

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

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

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

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

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

Одновременно с этим тактовый импульс поступает на вход третьего элемента ИЛИ второй группы 11 и, пройдя цепь элементов ИЛИ второй группы и элемент 9 задержки, поступает на вход установки в единицу триггера 14, переводя его в единичное состояние и открывая элементы И третьей группы 4. На вторые входы этих элементов поступает сочетание с прямых выходов соответствующих триггеров группы 1, которое проходит на соответствующие разряды информационного выхода 16.

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

0

5

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

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

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

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

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

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

группу элементов ИЛИ, группу элементов запрета, элемент ИЛИ и триггер, причем первые входы первых элементов И первой и второй групп подключены к тактовому входу устройства, входам установки исходного кода регистра сдвига и входу установки в О триггера, прямой выход которого соединен с первыми входами элементов И третьей группы, выходы которых являются соответствующими разрядами информационного выхода устройства, прямые выходы триггеров группы соединены с вторыми входами соответствующих элементов И первой и третьей групп, инверсные выходы с второго по (К-1)-й триггеров группы (где N - разрядность сочетания) соединены с первыми зходами с второго по (Н-1)-й элементов И второй и четвертой групп соответственно, инверсный выход первого триггера группы соединен с вторым входом первого элемента И второй группы, инверсный выход N-ro триггера группы соединен с первым входом N-ro элемента И четвертой группы, выход 1-го элемента И второй группы (i 1,N) соединен с первым входом i-ro элемента ИЛИ первой группы и вторым входом (i + 1)-го элеме т И второй группы, выход 1-го элемента И первой группы (i I,N - 2) соединен с первым входом i-ro элемента ИЛИ первой группы, вторым входом i- го элемента И четвертой группы, входом установки в О i-ro триггера группы, первым входом i-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, прямым входом i-ro элемента запрета, и первым входом i-ro элемента ШТИ-НЕ, выход которого подключен.к синхровходу i-ro триггера группы, выход (N-l)-ro элемента И первой группы подключен к второму входу (N-l)-ro элемента И четвертой группы, первому входу (N-l)-ro элемента Ш1И первой группы, входу установки в О (N-l)-ro триггера группы прямому входу (N-l)-ro элемента запрета, второму входу (N-2)-ro элемента ИСКШЧАЮЩЕЕ или И первому входу (N-l)-ro элемента ИЛИ-НЕ первой группы, выход которого подключен к синхроводу (N-l)-ro триггера группы, выход N-ro элемента И первой группы подключен к входу установки в О N-ro триггера группы, первому входу элемента ИЛИ и первому входу N-ro ,

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

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

входом установки в единицу (i+l)-ro триггера группы и с первым входом i-ro элемента ИЛИ второй группы, выход (N-I)-ro элемента И четвертой группы соединен с вторым входом N-ro

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

с вторым входом (i-l)-ro элемента

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

ф1/е, 2