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

 

УСТРОЙСТВО ДЛЯ ПЕРЕВОРА 5СОЧЕТАЛИЙ, содержащее т-разрядный регистр, первую группу из (m-l) элементов И, вторую группу из m элементов И, третью группу из (m-l) элементов И, четвертую группу из (т-2) элементов И, первую группу из (m-l) элементов ИЛИ, вторую группу из (т-2) элементов ИЛИ, группу из (т-2) элементов задержки, элемент И и триггер, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, первый вход которого подключен к нулевому выходу триггера, второй вход элемента И подключен к выходу I первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход i-ro элемента И второй группы (,2,...,т) подключен к единичному выходу j-ro разряда регистра и к первому входу элемента И четвертой группы (,3,..j m-2), выход i-ro элемента И второй fi... - -С -Л- fi%- .; 11 «.... ,., f-I 5 -i J .-s .v; 5J- . . ,.I группы (i йп) подключён к первьт входам 1-ых элементов И и ИЛИ первых групп соответственно ( 1 1,2,...,m-l), второй вход 1-го элемента ИЛИ первой группы подключен к выходу 1-го элемента И третьей группы и к первому входу

СОЮЗ COBETCHHX

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

РЕСПУБЛИК.

09} (И}

3(50 G 06 F 15 31

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

l э -, еч., ОПИСАНИЕ ИЗОБРЕТЕНИЯ(":::::-:---::-,,:,::,::::

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3486358/18-24 (22) 24.08.82 (46) 23 ° 11.83. Бюл. Ф 43 (72) В.И.Полищук (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

II 634285, кл. G 06 F 7/32, 1974.

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

11 903891, кл. G 06 F 7/31, 1980 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА

- СОЧЕТАНИЙ, содержащее m-разрядный регистр, первую группу из (m-1) элементов И, вторую группу из m элементов И, третью группу из (в-1) элементов И, четвертую группу из (m-2) элементов И, первую группу из (m-1) эле" ментов ИЛИ, вторую группу из (m-2) элементов ИЛИ, группу из (m-2) элементов задержки, элемент И и триггер, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента

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

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

И второй группы (i=1,2,...,m) подключен к единичному выходу j-го разряда регистр и к первому входу j-го элемента И четвертой группы (1=2,3, m-2), выход i-го элемента И второй группы (I+) подключен к первым входам I-ых элементов И и ИЛИ первых групп соответственна (1 1,2,...,m-1), второй вход l-го элемента ИЛИ первой группы подключен к выходу 1-ro элемента И третьей группы и к первому входу (1+1)-го элемента И третьей группы, второй вход 1-го элемента И третьей группы подключен к нулевому выходу I-ro разряда регистра соответственно, который подключен к второму входу I-ro элемента И:первой группы, выход которого подключен к первому единичному. входу разряда регистра, второй единичный вход которого подключен к выходу )-го эле- д мента И четвертой груйпы и к второму входу (Э+3}-го элемента И четвертой (/} группы, нулевой вход i-го разряда регистра (i/mJ .подключен к выходу

i-ro элемента И второй группы и к ч первому входу j ro элемента ИЛИ второй группы, второй вход которого подключен к выходу у го элемента задержк}е группы, вход которого подключен к выходу (1+1)-го (jism-3) элемента ИЛИ второй группы, выход

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

3> произвольного значения п(п-l,m),îío дополн n ельно содержит (m-1)-ый и

m-ый элементы И четвертой группы, (m-1) -й, m-É и (m+1)-ый элементы

ИЛИ второй группы, (m-l)-ый, m-ый и (в+1)-ый элементы задержки груп1056 пы, причем первый вход (m-1)-го элемента И четвертой группы соединен с выходом (m-2)"го элемента И четвертой. группы, второй вход (m-1)-ro элемента И четвертой группы соединен с единичным выходом (m-2)-го разряда регистра устройства, первый вход

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

m-го элемента И четвертой группы соединен с единичным выходом (m-1)-ro разряда регистра, выход m"ãî элемента И четвертой группы подключен к второму единичному входу m-го разряда регистра и к второму выходу окончания перебора сочетаний устройства,, первый вход (m-1)-ro элемента ИЛИ второй группы подключен к выходу

205 (m-1)-го элемента И второй группы, а первые входы m-ro и (m+1)-го элементов ИХИ второй группы подключены к выходу m-го элемента И второй группы, вторые входы m-ro u ),в-1)-го элементов ИЛИ второй группы соединены с выходами m-го и (m-1)-го элементов задержки группы соответственно, входы которых соединены с выходами (а+1)-го и m-го элементов ИЛИ второй группы соответственно, выход (m-1)-ro элемента ИЛИ второй группы соединен с входом (m-2)-го элемента задержки группы, второй вход (m+1) -го элемента ИЛИ второй группы подключен к выходу (m +1)"ro элемента задержки группы, вхоц которого подключен к выходу m-ro элемента И второй

:группы.

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

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

И, элементы задержки и распределитель импульсов (1) .

Недостатками известного устройства являются его сложность, невысокое быстродействие и слабая приспособленность к схемным изменениям при увеличении разрядности устройства, I

Наиболее близким по технической сущности к изобретению является устройство для перебора сочетаний из m элементов по и содержащее m-разрядный регистр, первую группу из (m-1) элементов И, вторую группу из m элементов И, третью группу из (m-1) элементов И, четвертую группу из (ru-2) элементов И, первую группу из (m-1) элементов ИЛИ, вторую группу из (m-2) элементов ИЛИ, группу из (m-2) элементов задержки, элемент И и триггер, причем вход устройства подключен к первому входу первого элемента И Bto рой группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элементов И, первый вход которого подключен к нулевому выходу триггера, а

5 второй вход — к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход 1-го элемента И второй группы (i-=-1,2,. ° .,m) подключен к единичному выходу i-ro разряда регистра и к первому входу j-го,элемента И,четвертой группы (j=2,3,...,m-2), выход

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

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

l 056205 4 группы и к второму входу (j+1) -ro элемента И четвертой группы, нулевой вход i-го разряда регистра (iA) подключен к выходу i-го элемента И второй группы и к первому входу j-го элемента ИЛИ второй группы, второй вход которого подключен к выходу j"ãî элемента задержки группы, вход которого подключен к выходу (j+1)-ro ()Фа-3) элемента ИЛИ второй группы, выход m-го элемента И второй груп . пы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу m-ro разряда регист ра (2) .

Недостатком известного устройства является то, что область его применения ограничена, поскольку устройство позволяет получить все сочетания иэ m элементов по и для фиксированного значения и. На практике часто возникает необходимость получения всех сочетаний из m элементов по и при произвольном изменении значения и от l до m;.

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

n-=1,m.

Поставленная цель достигается тем, что устройство для перебора сочетаний, содержащее m-разрядный регистр, первую группу из (m-1) элементов И, вторую группу из m элементов И, третью группу из (m-1) элементов И, четвертую группу из (m-2) элементов И, первую группу иэ (m-1) элементов ИЛИ, вторую группу из (m-2) элементов ИЛИ группу из (m-2) элементов задержки, элемент

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

55 группы (i=1,2,...,m) подключен к единичному выходу j-ro разряда регистра и к первому входу j --ro эле" мента И четвертой группы (j=,3,..., 1 )

m 2), выход 1-го элемент» И второй группы (1 ь ) подключен к первым входам 1-ых элементов И и ИЛИ первых групп соответственно (1=1,2,..., m-1), второй вход 1 -го элемента ИЛИ первой группы подключен к выходу

1-ro элемента И третьей группы и к первому входу (1+1)-го элемента

И третьей группы, второй вход 1-го элемента И третьей группы подключен к нулевому выходу i-го разряда регистра соответственно, который подключен к второму входу 1 -го элемента И первой группы,. выход которого подключен к первому единичному входу разряда регистра, второй единичный вход которого подключен к выходу j-го элемента И четвертой группы и к второму входу (j+1)-го элемента И четвертой группы, нулевой вход i-ro разряда регистра (1Фв) подключен к выходу 1-го элемента И второй группы и к первому входу j-го элемента ИЛИ второй группы, второй вход которого подключен к выходу j ""ro элемента задержки группы, вход которого подключен к выходу (j+1)-го 4 Am-3) элемента ИЛИ второй группы, выход

m-го элемента И второй группы подключен к первому выходу окончания перебора сочетаний устройства и к нулевому входу m-го разряда регистра, дополнительно содержит (m-1)-ый ив-ый элементы И четвертой группы (m-1)-ый, ti-ый и (mal)-ый элементы ИЛИ второй группы, (ш-1) -ый, m-ый и (в+1) -ый элементы задержки группы, причем первый вход (m"1)-го элемента И четвертой .группы соединен с выходом (m-2)-го элемента И четвертой группы, второй вход (m-1)-го элемента И четвертой группы соединен с единичным выходом (m-2)-го разряда регистра устройства, первый вход m-ro элемента И четвертой группы соединен с выходом (m-1)-ro элемента И четвертой группы, второй вход m-ro элемента И четвертой группы соединен с единичным выходом (m-1)-го разряда регистра, выход m-го элемента И четвертой группы подключен к второму единичному входу m-ro разряда регистра и к второму выходу окончания перебора сочетаний устройства, первый вход (m-1}-го элемен1056205 та ИЛИ вЂ .торой группы подключен к выхору (m-!)-го элемента И второй группы, а первые входы m-ro и (я-т1) -го элементов ИЛ! второй группы подключеньт к выходу m-го элемента И второй 5 группы, вторые входы m-ro и (m-1)-го элемеьттов ИЛИ второй группы соединены с выходами m-ro и (m-1)-ro элес ментов "-.ãäàðæêè группы соответственно. входы которых соединены с выхода- !О ми (ш+!)-го и m-го элементов ИЛИ второй группы соответстветтно выход (m""1)-го элемента ИЛИ второй группы соединен с входом (m-2)-го элемента задержки группы, второй вход (пт+1)"го !5 эле"еита Ит1И второй группы подключен

b3.!i:oui, (m+1 ) -po элемента задержки, груптть... вход которого подключен к вы:.-.еду и-т-о элемента И второй группы

1. - а -чертеже представлена схема пред-20 лагае ого устройства.

Устрокство содержит регистр, образованный триггерами 1, и распредели ель импульсов обра-„.ова-,-,т;.,пт элемент ами И 2 элементами, 3.„. элементами ИЛИ,4 эле-тентат-о:: И 5, элементами И 6... элемента=: ацер;кки, элементат ттт ИЛИ 8 тр:"тггером 9, элементом И 10, шину

11 uxîöiioãî импульса, шину 12 пер- 30 вого сигнала окончания перебора и т (Г Второго сттг нала Окопчания перебора

Прт переборе сочетаний каждое очередное . остояние образуется из 35 предыдущего путеьт замены крайней справа комбинации 01" на "10" и ттерегтистт всех единиц, расположенных правее, в крайние правые нозищжтт: При этом B первоначальном сос щ тоянии все единицы должны располагать ся в крайних справа позициях, в последнем же состоянии они переходят в крайние слева позиции. Например,, при и=5 и п=3 устройством вырабатываются сочетания:

00111 6 10101

2 01011 7 10110

3 0!101 8 11001

4 0!110 9 11010 50

5 10011 10 11100

Устройство может работать в двух режимах, В первом режиме обеспечивается перебор сочетаний из ш элементов по и для фттксироваттного зттачения 5 и, а во втором — для п=1,ш, j3 первом режиме перед началом Ра— боты для перебора всех сочетаний из

m элементов по и производится установка всех триггеров 1 регистра в нулевое состояние, а затем запись. единиц в и крайние справа триггеры (и=

1,2,...,m-1).

Каждый раз при поступлении входного импульса по шине .11 триггер 9 распределителя импульсов устанавливается в нулевое состояние, обеспечивая тем самым разрешающий потенциал на управляющем входе элемента И 10 и запрещающий — на управляющем входе элемента И 10 и на управляющем входе первого элемента И 6 четвертой группы. Этот же импульс поступает на информационные входы первого элемента И 3 второй группы и первого элемента И 5 третьей группы. При единичном состоянии триггеров 1 регистра

< на управляющих входах элементов И 3 и б второй и четвертой групп находятся разрешающие потенциалы, а на управляющих входах элементов И 2 и

5 — запрещающие потенциалы, при нулевом состоянии триггеров 1 регистра, наоборот, на управляющих входах элементов И 3 и б находятся запрещающие потенциалы, а на управляющих входах элементов И 2 и S — разрешающие.

Если r (г=1,2,...,m) крайние справа триггеры 1 находятся в единичном состоянии, то входной импульс проходит последовательно элементы И 3 второй группы и ИЛИ 4 первой группы и устанавливает зти триггеры в нулевое состояние, а (гт1)-ый триггер 1 через открытый элемент И 2 первой группы— в единичное состояние и, кроме того, поступает на входы элементов

ИЛИ 8 второй групгтьт, что обеспечивает формирование на выходе первого элемента ИЛИ 8 второй группы серию лз r импульсов (элементы 7 задержки обеспечивают временную растяжку серии импульсов,, необходимую для стабильности переходных процессов при дальнейшей работе). Первый импульс серии, пройдя через элемент И 10, устанав.ливает триггер 9 распределителя импульсов в единичное состояние, чем обеспечивается подача на управляющий вход первого элемента И б четвертой группт>т разрешающего потенциала.

Второй импульс серии, пройдя первый элемент И бчетвертой группы, устанавливает первый триггер 1 регистра в единичное состояние, чем обеспечивается прохождение третьего импуль1056205

40 са серии через второй элемент И 6 четвертой группы и установка в единичное состояние второго. триггера 1 регистра, а с каждым очередным им пульсом серии - установка очеред- 5 ного по порядку триггера I регистра включительно (r-1)"ый триггер. На, этом заканчивается такт фбрмирования очередного сочетания, которое снимается с единично< входов (а4, а ;...,а„,) триггеров 1 регистра.

Если r (r=1,2,...,m-n) крайние правые триггеры 1 регистра находятся в нулевом состоянии, то входной

,импульс, пройдя г открытых элемен-. 15

;. тов И 5 третьей группы, поступает через r-ый элемент ИЗТИ 4 первой груп пы на открытый (r+1)-ый элемент И 3 ! второй группы и в дальнейшем выпол»

:няет действия, аналогичные описанным. 20

Если в текущем сочетании в крайней справа позиции имеется комбинация "О!", то при формировании очередного сочетания она преобразуется в комбинацию "10", что соответствует 25 сдвигу единицы на один разряд влево.

Если и крайние слева триггеры 1 регистра находятся в единичном состоянии (последнее из формируемых сочетаний), то при поступлении очередного 30 входного импульса с выхода послед. него элемента И 3 второй группы выдается по шине 12 первого сигнала окончания перебора.

Во втоРом Режиме перед началом работы производится установка всех триггеров 1 регистра в нулевое сос-, тояние„ а затем запись единицы в первый крайний справа триггер. В дальнейшем устройство работает анаФ логично вьипеописанному до перемещения единицы в крайний слева триггер регистра.

Очередной входной импульс, по ступивший по шине 11, пРойдет все 45 открытые элементы И 5 третьей группы, (m-1)-ый элемент ИЛИ 4 первой группы и открытый (m-1)-ый элемент

И 3 второй группы, с выхода котороro он поступит на установку)ш-го i триггера регистра в ноль и на шину

12 (в данном режиме сигнал с шины

12 не воспринимается как сигнал окон. чания перебора), Одновременно этот сигнал поступает на первые входы

m-го:.и (m+1)-го элементов ИЛИ 8 второй группы, а также через элемент 7 задержки на второй вход (m+1)-го элемента ИЛИ 8 этой же группы. Последнее обеспечивает формирование на выходе первого элемента ИЛИ второй группы серии из трех. сигналов,, первый из которых установит в единичное состояние триггер 9, а последующие — в единичное состояние первый и второй крайние справа триггеры 1 регистра. Пооле этого начинается цикл формирования сочетаний из

m элементов по и при n=2.

В дальнейшем каждый раз при поступлении входного сигнала, когда ,11 крайние слева триггеры 1 регист« ра находятся в единичном состоянии, эти триггеры сбрасываются в нулевое состояние, а на выходе первого элемента ИЛИ 8 второй группы формируется серия из 11 2 импульсов, которые Обеспечивают вышеопнсанньп об» разом установку в единичное состояние 11+1 крайних справа триггеров регистра. Если все триггеры 1 регистра окажутся в единичном состоянии (последнее из формируемых сочетание),, то при поступлении очередного входного импульса с выхода.последнего элемента И 6 четвертой группы выдается по шине 13 сигнал, который для данного режима является сигналом окончания перебора.

Технико-экономический эффект от использования предлагаемого устройства состоит в расширении области применения, поскольку оно в отличие от йзвестного позволяет формировать сочетания нз ш элементов по и не только для фиксированных значений и но и для п=1,m.

Составитель H,Êàéäàíoâ

Редактор А.Козориз Техред Т„Маточка Корректор А.Зимокосов

Заказ 9308/43 Тираж 706 Подписной

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4