Устройство для перебора сочетаний — SU 1056205 (original) (raw)
кое с6 06е свиС 06 к рск кла ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(54)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, содержащее е-разрядный регистр, первую группу из (щ) элементов И, вторую группу из в элементов И, третью группу из (е) элементов И, четвертую группу из (е) элементов И, первую группу из (а) эле" ментов ИЛИ, вторую группу из (а) элементов ИЛИ, группу из (в) элементов задержки, элемент И и триггер, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, первый вход которого подключен к нулевому выходу триггера, второй вход элемента И подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход 1-го элемента И второй группы (1=1,2в) подключен к единичному выходу -га разряда регистр и к первому входу 1-га элемента И четвертой группы (1=2,3 а 2), выход 1-го элемента И второй группы (1 Фщ) подключен к первым входам 1-ых элементов И и ИЛИ первых групп соответственна ( 1 1,2, ,е), второй вход 1-го элемента ИЛИ первой группы подключен к выходу 1-го элемента И третьей группы и к первому входу ( 1+1)-го элемента И третьей группы, второй вход 1"го элемента И третьей группы подключен к нулевому выходу 1-го разряда регистра соответственно, который подключен к второму входу 1-го элемента И первой группы, выход которого подключен к первому единичному. входу разряда регистра, второй единичный вход которого подключен к выходу )-го эле- д мента И четвертой груйпы и к второму входу +1)-го элемента И четвертой группы, нулевой вход 1-го разряда регистра (1 Фп 1) .подключен к выходу1-го элемента И второй группы и к первому входу 1 го элемента ИЛИ вто. рой группы, второй вход которого подключен к выходу у го элемента задержкй группы, вход которого подключен к выходу (+1)-го ФЯ"3) элемента ИЛИ второй группы, выход а-го элемента И второй группы подклю чен к первому выходу окончания перебора сочетаний устройства и к нулевому входу щ-го разряда регистра, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности задания произвольного значения п(п,щ),оно дополнительно содержит (щ)-ый и в-ый элементы И четвертой группы, (л) -й, ш-й и (в+1)-ый элементы ИЛИ второй группы, (щ)-ый, в-ый и (в+1)-ый элементы задержки груп 1056пы, причем первый вход (щ)-го элемента И четвертой группы соединен с выходом (щ)"го элемента И четвертой группы, второй вход (щ)-го элемента И четвертой группы соединен с единичным выходом (щ)-го разряда регистра устройства, первый вход щ-го элемента И четвертой группы соединен с выходом (щ)-го элемента И четвертой группы, второй вход щ-го элемента И четвертой группы соединен с единичным выходом (щ"1)-го разряда регистра, выход щ"го элемента И четвертой группы подключен к второму единичному входу щ-го разряда регистра и к второму выходу окончания перебора сочетаний устройства первый вход (щ"1)-го элемента ИЛИ второй группы подключен к выходу 2 О 5(щ)-го элемента И второй группы,а первые входы щ-го и (щ+1)-го элементов ИХИ второй группы подключенык выходу щ-го элемента И второй группы, вторые входы щ-го и ),щ)-гоэлементов ИЛИ второй группы соединены с выходами щ-го и (щ)-го эле"ментов задержки группы соответственно, входы которых соединены с выходами (щ+1)-го и щ"го элементов ИЛИ второй группы соответственно, выход(щ+1) -го элемента ИЛИ второй группыподключен к выходу (ъ 41)"го элементазадержки группы, вхоц Которого подключен к выходу щ-го элемента И второйгруппы.Изобретение относится к вычислительной технике и может быть применено, например, в вычислительных машинах, решающих комбинаторные задачи.Известно устройство для переборасочетаний, содержащее регистры, счетчик, дешифратор, триггер, элементыИ, элементы задержки и распределитель импульсов 1 .Недостатками известного устройства являются его сложность, невысокое быстродействие и слабая приспособленность к схемным изменениямпри увеличении разрядности устройства,1Наиболее близким по техническойсущности к изобретению является устройство для перебора сочетаний из щэлементов по и, содержащее щ-разрядный регистр, первую группу из (щ)элементов И, вторую группу из щ элементов И, третью группу из (щ) элементов И, четвертую группу из (щ)элементов И, первую группу из (щ)элементов ИЛИ, вторую группу из (щ)элементов ИЛИ, группу из (щ) элементов задержки, элемент И и триггер,причем вход устройства подключен кпервому входу первого элемента И второй группы, к первому входу первогоэлемента И третьей группы и к нулвому входу триггера, единичный входкоторого подключен к выходу элементов И, первый вход которого подключен к нулевому выходу триггера, а 5 второй вход - к выходу первого элемента ИЛИ второй группы и к первомувходу первого элемента И четвертойгруппы, второй вход которого подк.ночен к единичному выходу триггера, второй вход 1-го элемента И второй группы (1=1,2щ) подключен к единичному выходу 1-го разряда регистра ик первому входу 1-го,элемента И,четвертой группы ( у 2,3 щ), выход1-го элемента И второй группы (1=й) подключен к первым входам 1-ых элементов И и ИЛИ первых групп соответственно (1=1,2щ) второй вход1-го элемента ИЛИ первой группы подключен к выходу 1-го элемента И третьей группы и к первому входу ( 1+1)-го элемента И третьей группы, второй вход .1-го элемента И третьей группы подключен к нулевому выходу 1-го разряда регистра соответственно, который подключен к второму входу 1-гоэлемента И первой группы, выход которого подключен к первому единичному входу разряда регистра, второйединичный вход которого подключенк выходу -го элемента И четвертой1056205 4 группы и к топочу пходу (+1)-го элемента И четвертой группы, нулевой вход 1-го разряда регистра (11 в) подключен к выходу 1-го элемента И второй группы и к первому входу )-го элемента ИЛИ второй группы, второй вход которого подключен к выходу "го элемента задержки группы, вход которого подключен к выходу +1)-го Фв) элемента ИЛИ второй группы, выход в-го элемента И второй груп пы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу в-го разряда регистра 121.Недостатком известного устройства является то, что область его применения ограничена, поскольку устройство позволяет получить все сочетания иэ в элементов по и для фиксированного значения и. На практике часто возникает необходимость получения всех сочетаний из в элементов по и при произвольном изменении значения и отдо в;Цель изобретения - расширение области применения устройства за счет возможности задания произвольного значения и при получении сочетаний из в элементов по и как для фиксированных значений и, так и для и=1,в.45 Поставленная цель достигается тем, что устройство для перебора сочетаний, содержащее в-разрядный регистр, первую группу из (в) элементов И, вторую группу из в элементов И, третью группу из (в) элементов И, четвертую группу из (в) элементов И, первую группу иэ (в) элементов ИЛИ, вторую группу из (в) элементов ИЛИ группу из (в) элементов задержки, элемент И и триггер, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подклю чен к выходу элемента И, первый вход которого подключен к нулевому выходу триггера, второй вход элемента И подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход .которого подключен к единичному выходу триггера, второй вход 1-го элемента И второй группы ( 1 =1, 2в) подключен к единичному выходу -го разряда регистра и к первому входу-го эле" мента И четвертой группы ( = ,3,1 2 е), выход 1-го элемент И второй группы (1 Фц) подключен к первымвходам 1-ых элементов И и ИЛИ первых групп соответственцо (1=1,2 е), второй вход 1-го элемента ИЛИ первой группы подключен к выходу1-го элемента И третьей группы и к первому входу (1+1)"го элемента И третьей группы, второй вход 1 "го элемента И третьей группы подключен к нулевому выходу 1-го разряда регистра соответственно, который подключен к второму входу 1 -го элемента И первой группы,. выход которого подключен к первому единичному входу разряда регистра, второй единичный вход которого подключен к выходу )-го элемента И четвертой группы и к второму входу +1)-го элемента И четвертой группы, нулевой вход 1-го раз" ряда регистра (1 Фв) подключен к выходу 1-го элемента И второй группы и к первому входу )-го элемента ИЛИ второй группы, второй вход которого подключен к выходу ) "го. элемента задержки группы, вход которого подключен к выходу +1)"го ( Юе) элемента ИЛИ второй группы, выход в-го элемента И второй группы подключен к первому выходу окончания перебора сочетаний устройства и к нулевому входу в-го разряда регистра, дополнительно содержит (е)-ый ив-ый элементы И четвертой группы (в)-ый, е-ый и (е 1)-ый элементы ИЛИ второй группы, (в)-ый, в-ый и (е+1) -ый элементы задержки группы, причем первый вход (в"1)-го элемента И четвертой .группы соединен с выходом (в)-го элемента И четвертой группы, второй вход (е)-го элемента И четвертой группы соединен с единичным выходом (в)-го разряда регистра устройства, первый вход е-го элемента И четвертой группы соединен с выходом (в) -го элемента И четвертой группы, второй вход е-го элемента И четвертой группы соединен с единичным выходом (в)-го разряда регистра, выход в-го элемента И четвертой группы подключен к второму единичному входу в-го разряда регистра и к второму выходу окончания перебора сочетаний устройства, первый вход (в)-го элемен" 10 15 20 25 30 35 40 50 55та ИЛИ второй группы подключен к выходу (ш-)-го элемента И второй группы, а первые входы пт-га и (тяФ 1) -гоэлементов ИОт второй группы подключеньт к выходу пт-го элемента И второй 5группы, вторые входы тп-го и (гп)-гоэлеме ггов ИЛИ второй группы соединены с вьгходами гп-го и (тя)-го элесментов задержки группы соответственно, входя которых соединены с выхода- Оми (Ф+)-го и ят-го элементов ИЛИвторой группы саответстветтнот выход(пт" 1)-го элемента ИЛИ второй группысоединен с входом (пт)-га элементазадержки группы, второй вход (пт+1)"го 5элеь.ента Ит 1 И второй группы подключенк выходу (ге+1)-га элемента задержки,групць Бхсц которого подключен к выходу ю"га элемента И второи группы1 а ертеже представлена хеа пред лагаемаго устройства.устройство содержит регистр,образованный триггерами 1, ираспрецели ель импульсов образоваР:".тьцл элементами И 2 элементами И 3 элементами ИЛИ,4 элементатдл И 5, элементами И 6 элементаттизадержки элементамтт ИЛИ 8триггером 9, элементом И 10, шину11 входного импульса, шину 12 перБого сигнала Окончания переборашину 1 э второго сигнала ОкончаниЯперебора,При переборе сочетантлй каждоеочередное "остояние образуется из 35пре,цыдушего путем замены крайнейсправа комбинации 01" на "10" иттерегтистт всех ециниц,расположенных правее, Б крайние правые нозиции в При зтам Б первоначальном с ос Щтаянии все единицы должны располагаться в крайних справа позициях, Б последнем же состоянии Они переходятв крайние слеза позиции. Напримерпри ш=5 и п=3 устройством вырабатываютсясочетания: 00111 6 101012 01011 7 101 О3 01101 Б 110014 01110 9 11010 50 5 10011 1 О 11100Устройство может работать в двух реьчмах, В первом режиме обеспечивается перебор сочетаний из пт элементов по и для Фтлксированнога значения 55 и, а Бо втором - для п=1,Гп,В перБОМ режиме перед началом 1)а боты для перебора всех сочетаний из тп элементов по и производится установка всех триггеров 1 регистра в нулевое состояние, а затем запись. единиц в и крайние справа триггеры (и= =ф 1 у 2 ууттт 1)Каждый раз при поступлении входного импульса по шине .11 триггер 9 распределителя импульсов устанавливается в нулевое состояние, обеспечивая тем самым разрешающий потенциал на управляющем входе элемента И 10 и запрещающий - на управляющем входе элемента И 10 и на управляющем входе первого элемента И 6 четвертой группы, Этот же импульс поступает на информационные входы первого элемента И 3 второй группы и первого элемента И 5 третьей группы. При единичном состоянии триггеров 1 регистра на управляющих входах элементов И 3 и б второй и четвертой групп находятся разрешающие потенциалы, а на управляющих входах элементов И 2 и 5 - запрещающие потенциалы, при нулевом состоянии триггеров 1 регистра, наоборот, на управляющих входах элементов И 3 и б находятся запрещающие потенциалы, а на управляющих входах элементов И 2 и 5 - разрешающие. Если г (г=1,2пт) крайние справа триггеры 1 находятся в единичном состоянии, то входной импульс проходит последовательно элементы И 3 второй группы и ИЛИ 4 первой группы и устанавливает эти триггеры в нулевое состояние, а (г 1)-ьтй триггер 1 через открытый элемент И 2 первой группы - в единичное состояние и, кроме того, поступает на входы элементов ИЛИ 8 второй групгтьт, что обеспечивает Формирование на выходе первого элемента ИЛИ 8 второй группы серию из г импульсов (элементы 7 задержки обеспечивают временную растяжку серии импульсов необходимую для стабильности переходных процессов при дальнейшей работе), Первый импульс серии, пройдя через элемент И 10, устанав.ливает триггер 9 распределителя импульсов в единичное состояние, чем обеспечивается подача на управляющий вход первого элемента И 6 четвертой группы разрешающего потенциала. Второй импульс серии, пройдя первый элемент И бчетвертой группы, устанавливает первый триггер 1 регистра Б единичное состояние, чем обеспечивается прохождение третьего импуль1056205 40 Технико-экономический эффект от использования предлагаемого устройства состоит в расширении области применения, поскольку оно в отличие от йзвестного позволяет формировать сочетания нз в элементов по и не только для фиксированных значений и, но и для п=1,в,са серии через второй элемент И 6 четвертой группы и установка в единичное состояние второго. триггера 1 регистра, а с каждым очередным импульсом серии - установка очеред ного по порядку триггерарегистра включительно (г)"ый триггер. На . этом заканчивается такт фбрмирования очередного сочетания, которое снимается с единичных входов (а 4, О а;,ав) триггеров 1 регистра.Если г (г=1,2в-п) крайние правые триггеры 1 регистра находят" ся в нулевом состоянии, то входной ,импульс, пройдя г открытых элемен-. 5 ; тов И 5 третьей группы, поступает через г-ый элемент ИЗТИ 4 первой груп пы на открытый (г+1)"ый элемент И 3второй группы и в дальнейшем выпол :няет действия, аналогичные описанным. 20Если в текущем сочетании в крайней справа позиции имеется комбина" ция "О", то при формировании очередного сочетания она преобразуется в комбинацию "10", что соответствует 25 сдвигу единицы на один разряд влево. Если и крайние слева триггеры 1 ре" гистра находятся в единичном состоянии (последнее из формируемых сочетаний), то при поступлении очередного З 0 входного импульса с выхода послед него элемента И 3 второй группы выдается по шине 12 первого сигнала окончания перебора.Во втором режиме перед началом работы производится установка всех триггероврегистра в нулевое сос-, тояние а затем запись единицы в первый крайний справа триггер. В дальнейшем устройство работает ана- Флогично вышеописанному до перемещения единицы в крайний слева триггер регистра.Очередной входной импульс, поступивший по вине 11, пройдет все 45 открытые элементы И 5 третьей группы, (в"1)-ый элемент ИЛИ 4 первой группы и открытый (в"1)-ый элемент И 3 второй группы, с выхода которого он поступит на установку)в-готриггера регистра в ноль и на шину 12 (в данном режиме сигнал с шины 12 не воспринимается как сигнал окон. чания перебора), Одновременно этот сигнал поступает на первые входы в-го:и (в+1)-го элементов ИЛИ 8 второй группы, а также через элемент 7 задержки на второй вход (в+1)-го элемента ИЛИ 8 этой же группы. Последнее обеспечивает формирование на выходе первого элемента ИЛИ второй группы серии из трех сигналов первый из которых установит в единичное состояние триггер 9, а последующие - в единичное состояние первый и второй крайние справа триггеры 1 регистра. Пооле этого начинается цикл формирования сочетаний из в элементов по и при п=2.В дальнейшем каждый раз при поступлении входного сигнала, когда ,1 крайние слева триггеры 1 регистра находятся в единичном состоянии, эти триггеры сбрасываются в нулевое состояние, а на выходе первого элемента ИЛИ 8 второй группы формируется серия из2 импульсов, которые Обеспечивают вышеописанньпл об разом установку в единичное состояние 1 +1 крайних справа триггеров регистра, Если все триггеры 1 регистра окажутся в единичном состоянии (последнее из формируемых сочетание) то при поступлении очередного входного импульса с выхода.последнего элемента И 6 четвертой груп пы выдается по шине 3 сигнал, который для данного режима является сигналом окончания перебора.056205 Составитель В,КайдановТехред ТМаточка едактор А,Козо рректо мокосов аз 9308/43 наб. Патент", г, Ужгород, ул. Проектная, 4 Филиал Тираж ВНИИПИ Госуд по делам из 035, Москва, 706рствеиного кбретений и оН(-35, Раушск Подписноитета СССРрытий