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

 

Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств,предназначенных , например, для автоматизированного решения задач конструирования радиоэлектронной аппаратуры. Целью изобретения является повышение быстродействия устройства. Устройство содержит две группы триггеров, четыре группы элементов И,две группы элементов ИЛИ,группу элементов задержки,две группы элементов Ш1И-НЕ, регистр сдвига, два элемента задержки, элемент коммутации, переключатель и . с элемент ИЛИ. 1 ил.

СОЮЗ СО8ЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (511 4 С 06 F 15/20

OllHCAHME ИЗОБРЕТ

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTVM (21) 3877933/24-24 (22) 03.04.85 (46) 07.!0.86, Бюл.Ф 37 (71) Таганрогский радиотехнический институт им. В.g.Êàëìûêoâà (72) В.И.Глушань, А.В.Пришибской, М.И,Пупков и Л.И,Щербаков (53) 681.323(088.8) (56) Авторское свидетельство СССР

М 634285, кл. G 06 F 15/32, 1975.

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

И 903891, кл, G 06 F 15/31, 1980. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, SU„„262520 (57) Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной аппаратуры.

Целью изобретения является повышение быстродействия устройства. Устройство содержит две группы триггеров, четыре группы элементов И,две группы элементов ИЛИ,группу элементов задержки,две группы элементов ИЛИ-НЕ, регистр сдвига, два элемента задержки, элемент коммутации, переключатель и элемент. ИЛИ, 1 ил, 1 12625

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

На чертеже представлена схема устройства.

Устройство содержит триггеры 1 — 6, элементы ИЛИ 7 — 11, триггеры 12

17, элементы И 18 — 29, элементы

ИЛИ-НЕ 30. — 38, элементы И 39. — 43, элементы 44 — 48 задержки, регистр

49 сдвига, элемент 50 задержки, переключатель 51 элемент 52 задержки, элемент ИЛИ 53, элементы И 54 — 59 20 и имеет тактовый вход 60, элемент

61 коммутации, информационные выходы

62 — 67, выход 68.

Устройство работает по следующему принципу, 25

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

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

Пример формирования всех сочетаний для случая и = 6 и л1 = 3.

1.111000 6.101010 11,110001 16 ° 001301

2.110100 7.011010 12.101001 17.1000!1

3,101100 8,100110 13,011001 18.010011

4.011100 9, 010110 14,100101 19 ° 001011

5.110010 10,001110 15.010101 20.000111

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

20 2

1 — 6 в устройстве представляют собой обычный двоичный счетчик с той лишь разницей, что на счетных входах триггеров 5 — 6 стоят дополнительные элементы ИЛИ. Для получения очередного сочетания перевода (1)-го нулевого разряда в единицу недостаточно.

Необходимо еще в (пз-1) левых разрядах восстановить единицы, Это обеспечивается триггерами 12 — 17 с элементами

И 18 — 28 на выходах, элементами 30—

48 и регистром 49 сдвига. Кроме того триггеры 12 — 17 с элементами 18—

?8 обеспечивают обход нулевых разрядов. Элементы 54 — 59 И обеспечивают выдачу сочетаний после прекращения переходных процессов, Элементы 50—

53 обеспечивают подготовку к работе триггеров 13 — 17 и регистра сдвига. !

Перед началом работы триггеры 1

6 по нулевым входам устанавливаются в нулевое состояние, а затем по единичным входам в триггеры 1 — 3 записываются единицы. После этого замыкается контакт элемента 61, в результате чего в триггеры 12 — 14 переписываются единицы из триггеров 1 — 3, а в триггеры 15 — 17 переписываются нули. Кроме того„ регистр 49 устанавливается в исходное состояние, т.е. в его первый разряд записывается единица, а во все остальные — нули.

Первый тактовый импульс через переключатель 51 поступает на элементы 18 и 24 и, так как триггер 12 находится в единичном состоянии, через открытый элемент 18 поступает на счетный вход триггера 1. В результате этого триггеры 1 — 3 последовательно перебрасываются в нулевое состояние, а триггер 4 — в единичное, При этом на элемент И 39 поступают единичные сигналы соответственно с единичного выхода триггера 12 с нулевого выхода триггера 1, Положительный перепад напряжения с выхода элемента 39, проходя через элемент 35

ИЛИ-НЕ инвертируется, и уже отрицательный проходит на вход элемента 30

ИЛИ-НЕ, на входе которого вновь получаем положительный перепад, На вход элемента ИЛИ-НЕ 30 через элемент 44 задержки также поступает положительный потенциал, но с определенной задержкой, До тех пор, пока на обоих входах элемента ИЛИ-НЕ 30 находятся нулевые потенциалы, на его выходе будет положительный импульс ° Как

3 1262 только с выхода элемента 44 задержки поступит на вход элемента 30 ИЛИ-НЕ единичный потенциал, на его выходе появится отрицательный перепад и положительный импульс закончится. Этот импульс передвинет единицу с первого разряда во второй в регистре 49. Формирование импульса цепочкой элементов 3,35,39,44 и аналогичными последующими цепочками необходимо, для !О того, чтобы сигналы с последующих триггеров не поглотились сигналами с предыдущих триггеров, а во-вторых, чтобы с триггеров 1 — 6, находящихся в нулевом состоянии, на вход регист- 1 ра 49 не подавались постоянно единичные потенциалы, Так как первый и второй разряды регистра 49 не подключены, то при поступлении на него перво-го импульса никаких изменений не про- ур изойдет. Первый импульс является как бы подготовительным. При переходе триггера 2 из единичного состояния в нулевое, аналогично описанному, элементы ИЛИ-НЕ 31, ИЛИ-НЕ 36, И 40 25 и 45 задержки. сформируют единичный импульс, который, пройдя элементы 35 и 30, передвинет в регистре 49 единицу с второго разряда в третий. При этом, поскольку единичный выход тре- ЗО тьего разряда регистра 49 соединен со входом триггера 1, то он восстановится в ециничное состояние. Таким же образом при переходе в нулевое состояние триггера 3 на выходе элемента ИЛИ-НЕ 32 сформируется единичный импульс, который, пройдя через элементы 36,31,35 и 30, передвинет единицу с третьего разряда в четвертый в регистре 49, и в триггере 2 4О восстановится единица. Таким образом, на единичных выходах триггеров 1

6 будем иметь второе сочетание

110100. После этого первый тактовый импульс, задержанный элементом 52, 4 перепишет информацию из триггеров 1

6 в триггеры 12 — !7, а регистр 49 установит в исходное состояние.

Второй тактовый импульс аналогично описанному установит триггер 3 в единичное состояние, а триггеры 1 и

2 в нулевое состояние. В моменты перехода триггеров 1 и 2 из единичного в нулевое состояние будут сформированы последовательно два единичных им- у пульса. Первый иэ этих импульсов подготовит регистр 49, т.е. продвинет единицу с первого разряда во второй, 520 4 а по второму импульсу произойдет восстановление единицы в триггере 1, в результате чего получим третье сочетание 101100. Затем второй задержанный элементом 52 тактовый импульс перепишет информацию из триггеров 1

6 в . .Риггеры 12 — 17, Третий тактовый импульс аналогичным образом сформирует на выходах триггеров 1 — 6 четвертое сочетание 011100. Теперь к моменту поступления четвертого тактового импульса триггер 12 будет находиться в нулевом состоянии, и элемент 18 И будет закрыт, а элемент

И 24 открыт. Поэтому четвертый тактовый импульс не пройдет на вход триггера 1, а обойдет его и через открытый единичным потенциалом с триггера 13 элемент И 19 поступит на счетный вход триггера 2. При этом триггеры 2 — 4 последовательно перейдут из единичного состояния в нулевое, а триггер 5 — в единичное, На выходах элементов 31 — 33 будут последовательно сформированы единичные импульсы, которые через регистр 49 запишут единицы в триггеры 1 и 2.

При этом будет сформировано пятое сочетание 110010, Так будет продолжаться до тех пор, пока все три единицы не окажутся в трех последних триггерах соответственно 4 — 6 и 15 — 17. Тогда очередной тактовый импульс поступит на счетный вход триггера 4, последовательно переведет из единичного в нулевое состояние триггеры 4 — 6 и появится на выходе элемента И 29. Появление сигнала на выходе элемента .

29 является признаком окончания геребора всех сочетаний.

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

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

45 с

В

И 4„

/ т

f

r гг

У

1

r, 5

/ т, r5 г

4

7

ll 1 з у Р Р P

Составитель А,Жеренов

Техред И.Попович

Редактор H,Èàðãoëèíà

Корректор Т. Колб

Тираж 671 Подписное

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

113035, москва, Ж вЂ” 35, Раущская наб., д.4/5

Заказ 5430/48

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

S !2б2 устройства, вторрй вход элемента ИЛИ через элемент задержки соединен с ньгходом переключателя и с первыми входами первых элементов И первой и второй групп, информационный вход

5 переключателя соединен с тактовым входом устройства, управляющий вход переключателя через второй элемент задержки соединен с выходом элемента коммутации, выход элемента ИЛИ со- !р единен с синхронизирующими входами триггеров второй группы и с установочным входом регистра сдвига (i+2) é выход которого соединен с единичным входом i-го триггера первой группы 15 (! = l,2,...n-2), где п — число пере— бираемых элементов, .счетный вход первого триггера первой группы соединен с выходом первого элемента И первой группы, счетный вход i-го триггера 2р первой группы (i = 2,3,...n) соединен с выходом соответствующего элемента

ИЛИ первой группы, первый вход которого соединен с выходом 1 го элемента И первой группы, второй вход 25 соединен с нулевым выходом (э — 1)-го триггера первой группы, с первым входом (i-1)-го элемента И третьей группы, второй вход которого и второй вход (i 1)-ro элемента И первой Зр группы соединены с единичным вь|ходом (i-1)-го триггера второй группы, единичный выход i-ro rrrr o (i=1,2, ...п) первой группы соединен с первым входом i-го элемента И четвертой

57 5

Я 55 э20 Ь ээнфо1эмгэционньэм входом г r o триг.гера второй r руппы, нулевой выход которого соединен с RTорым входом

i-го элемента II второй группы, выход которого гоелинен с первыми входами (i+I)-х элементов И первой и второй групп, кроме. (и-1)-го элемента И второй группы, ныкод которого соединен с первым нходом и-го элемента И первой группы, вьход 1. го элемента третьей группы (i=l,2,....n 1), кроме (n-l)-го, соединен с первым входом ь го элемента KIII НГ первой Группы и через r-й элемент задержки группы соединен с первым входом 1 го элемента ИЛ!И-1!1. второй группы, ныход которого соединен с вторым входом (i-!)-го элемента ИЛИ-НЕ первой группы, выход первого элемента ИЛИ-НЕ: второй группы соединен с входом управления сднигом регистра сдвига, выход (и-1)-r o элемента И третьей группы соединен с инверсным входом (и-1)-гn гэлемента ИЛИ-HF. второй группы и через соответствующий элемент задержки группы соединен с прямым входом (п-1)-го элемента ИЛИ-НЕ, вторые входы элементов И четвертой группы соединены с выходом первого элемента задержки, выходы элементов И четнертой группы являются информационным выходгэм устройства, выход последнего элемента И второй группы является выходом признака окончания работы устройства.

54 В5 Я dl