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

(64) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

1

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

Известно устройство для перебора сочетаний, содержащее основной регистр, ЭЕШоминающий регистр, вспомогательный регистр, блок ущзавления, триггеры, элементы И и ИЛИ, элементы задержки СИ

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

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

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

10 первого регистра сдвига и выходом устройства, первый выход первого регистра сдвига соединен с первым входом второго элемента И, третий вход первого регистра сдвига соединен с выходом втоISрого элемента задержки, первый выход первого регистра сдвига соединен с пер-; вым входом второго элемента И, второй вход которого подключен к нулевому выходу триггера, выход элемента И

30 второй элемент задержки подключен к единичному входу триггера, нулевой вход которого подключен к первому входу дешифратора, второй вход которого подклю« 3903 чен к второму входу второго элемента И, третий вход дешифратора подключен к третьему входу первого .регистра сдвига, четвертый вход дешифратора подключен к выходу первого элемента И ,2. Недостатком этого устройства является его сложность, обусловленная наличием двух регистров сдвига, дешифратора, счетчика (скоэффициентом пересчетаvn ), распределителя импульсов, выполненного в виде регистра сдвига. Вследствие этого устройство обладает невысоким быстродей ствием и низкой приспособленностью к схемным изменениям при изменении величины VV1. Цель изобретения упрощение устройства. Поставленная цепь достигается тем, что устройство для перебора сочетаний, содержащее m -разрядный регистр, группу из ( т-2) элементов задержки, элемент И и триггер, нулевой выход которого подключен к первому входу элемента И, содержит первую группу из { vn - 1) элементов И, вторую группу из элементов И, третью группу из (m-i) элементов И, четвертую группу из ( w, - 2) элементов И, первую группу из ( wi -l) элементов ИЛИ, вторую группу из ( ил 2) элементов ИЛИ, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу 35 элемента И, второй вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу « триггера, второй вход г -го элемента И второй группы ( i 1, 2,...,v,) подключен к единичному выходу i -го разряда регистра и к первому входу j -го элемента И четвертой группы ( j 2, 3 « -2), выход t -го элемента И второй группы ( ) подключен к первым входам -X элементов И и ИЛИ первых групп соответственно ( i 1, 2,.,., ы1), второй вход i -го элемента ИЛИ . 50 первой группы подключен к выходу t -го элемента И третьей группы и к первому входу ( . + 1 )-го элемента И третьей группы, второй вход i -го элемента И третьей группы подключен к нулевому 55 выХЬд i -го разряда регистра соответственно, который геодключен ко второму входу -го элемента И первой труппы, 4. выход которого подключен к первому единичному входу разряда регистра, вто-. рой единичный вход которого подключен к выходу j -го элемента И четвертой группы и ко второму входу ( j + 1) элемента И четвертой группы, нулевой вход I -го разряда регистра ( i w ) подключен к выходу i -го элемента И второй группы и к первому входу j -го элемента ИЛИ второй группы, второй вход котор, подключен к выходу -го элемента задержки группы, вход которого подключен к выходу j (j tn-З) элемента ИЛИ второй группы, выход -ro элемента И второй группы подключен к выходу окончанияперебора сочетаний устройства и к нулевому входу ки-го разряда регистра, вход ( «о 2)-го элемента задержки группы подключен к нулевому входу ( уу - 1)-го регистра. На чертеже представлена схема устройства. Устройство содержит регистр, образованный триггерами 1, и распределитель импульсов, образованный элементами И 2, элементами И 3, элементами ИЛИ 4, элементами И 5, элементами И 6, элемента jj 7 задержки, элементами ИЛИ 8, триггером 9, элементом И 1О, шину Ц входного импульса, шину 12 сигнала окончания перебора. При переборе сочетаний каждое очередное состояние образуется из предыдуще™ У замены крайней справа комби««««« Ol на Ю и переписи всех единиц, расположенных правее, в край«« правые позиции. При этом в первоначальном состоянии все единины должны располагаться в крайних справа позициях, последнем же состоянии они переходят крайние слева позиции. Например, при S и 3 устройством вырабатываются сочетания OOI11 Перед началом работы для перебора всех сочетаний из wi элементов по и хфоизводится установка всех триггеров 1 регистра в нулевое состояние, а затем запись единиц в v крайние справа триггеры i и 1, 2,,.., ил - 1). Каждый раз при поступлении входного импульса по шине Ц триггер 9 рас хфеделителя импульЬов устанавливается в нулевое состояние, обеспечивая тем . самым разрешающий потенциал на управ ляющем входе элемента И 10 и запрещаю щий - на управляющем входе первого элемента И 6 четвертой группы. Этот же импульс поступает на информационные входы первого элемента И 3 второй группы и пе вого элемента И 5 третьей группы. При единичном состоянии триггеров 1 регист ра на управляющих входах элементов И 3 и И 6 второй и четвертой групп находятся разрешающие потенциалы, управляющих входах элементов И 2 и И 5 запрещающие потенциалы, при нулевом состоянии триггеров 1 регистра, наоборот, на управляющих входах элементов И 3 и И 6 находятся запрещающие потенциалы, а на управляющих входах элементов И 2 и И 5 - разрещающие. Если y ( Г i, 2,..., у ) крайние справа триггеры 1 находятся в единичном состоянии, то входной импульс проходит последовательно элементы И 3 второй группы и ИЛИ 4 первой группы и устанавливает эти триггеры в нулевое со стояние, а (и +1)-ый триггер 1 через от крытый элемент И 2 первой группы - в единичное состояние и, кроме того посту пает на входы элементов ИЛИ 8 второй группы, что обеспечивает формирование на выходе первого элемента ИЛИ 8 второй группы серию из 1 импульсов (элементы 7 задержки обеспечивают временную растяжку серии импульсов, необходимую для стабильности переходных процессов при дальнейшей работе). Первый импульс серии, пройдя через элемент И 10, устанавливает триггер 9 распределителя импульсов в единичное состояние, чем обеспечивается подача на управляющий вход первого элемента И 6 четвертой группы разрешающего потенциала. Второй импульс серии, пройдя первый элемент И 6 четвертой группы, устанавливает первый триггер, 1 регистра в единичное состояние, чем обеспечивается прохождение третьего импульса серии через второй элемент И 6 четвертой группы и установка в единичное состояние второго триггера 1 регистра, а с каждым очередным импульсом серии установка очередного по порядку триггера 1 регистра включительно ( ir - l)-ый триггер. На этом заканчивается такт формировани очередного сочетания, которое снимается С единичных входов ( а, , а O-rv, триггеров 11 регистра. ./ Если 1 ( 1,2,..., м-и ) крайние правые триггеры 1 .регистра находятся в нулевом состоянии, то входной импульс, пройдя t открытых элементов И 5 третьей группы, поступает через г -ый элемент ИЛИ 4 первой группы на открытый I Г + 1)-ый элемент И 3 второй группы и в дальнейшем выполняет действия, аналогичные описанным. Если в текущем сочетании в крайней справа позиции имеется комбинация О1, то при формировании очередного сочетания она преобразуется в комбинацию 10, что соответствует сдвигу единицы на одни разряд влево. Если и крайние слева триггеры 1 регистра находятся в единичном состоянии {последнее из формируемых сочетаний), то при поступлении очередного входного импульса с выхода последнего элемента И 3 второй группы выдается по шине 12 сигнал окончания перебора. Технико-экономический эффект от использования данного устройства состоит в упрощении технической реализации устройства и повышении его надежности за счет сокращения количества элементов (околб ЗО%), а также в повышении его быстродействия за счет исключения регистров сдвига и необходимости переписи кодов из регистра в регистр. Кроме того, конструкция устройства может быть представлена в виде соединенных последовательно tn ячеек, каждая из которых содержит триггер 1, четыре элемента И (2.3,5 и 6), два элемента ИЛИ (4 и 8) и один элемент 7 задержки. Такое построение обеспечивает простоту схемного изменения устройства - при увели- чении (уменьшении) значения y в устройство включается (исключается) соответствующее количество ячеек. формула изобретения Устройство для перебора сочетаний, содержащее vvi -разрядный регистр, группу из ( К1 - 2)элементов задержки, эле мент И и триггер, нулевой выход котоого подключен к первому входу элемента И, отличающееся тем, что, с целью упрощения устройства, оно содержит первую группу из ( VM -l) элементов И, вторую группу из элементов И, третью группу из ( m - l) элементов И, четвертую группу из ( i -2) элементов И/первую группу из ( гм - 1) элементов ИЛИ, вторую .группу из l w 2) элементов ИЛИ, гфичем вход устройства подключен к первому входу первого элемента И второй группы, .к первому ; входу первого элемента И третьей группы н к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, второй вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход i -го элемента И второй группы ( 4. 1,2,..., И) подключен к единичному выходу Ч -гр разряда регистра и к первому . входу -го элемента И четвертой rpyi пы V 2, 3,..., и -т 2),. выход i -г элемента И второй группы () подключен к первым входам I -к элемен - тов И и ИЛИ первых групп соответственно ( I 3,, 2,..., уп - l), BtqpoS вход -го элемента ИЛИ первой группы подключен к выходу -го элемента И третьей группы и к первому входу (-С + fi)-ro элемента И третьей группы, второй вход i -го элемента И третьей группы подключен к нулевому выходу t -го разряда регистра соответственно 9 91 который подключен ко второму входу го элемента И первой группы, выход которого подключен к первому единичному входу разряда регистра, второй единичный вход которого подключен к выходу J -го элемента И четвертой гругапы и ко второму входу I j + 1) элемента И четвертой группы, нулевой вход i -го регистра ( t ч н) подключен к выходу t го элемента И второй группы в к первому входу J элемента ИЛИ второй группу:, второчи вход которого подключен к выходу -го элемента задержки группы, вход которого подключен к выходу j + l-ro ( Уп -З) элемента ИЛИ второй группы, выход -го элемента И второй группы подклкэчен к выходу окончания перебора сочетаний устройства и к нуле- вому входу ш -го разрзда .регистра, вход ( w - 2)-го элемента задержки группы подключен к нулевому входу ( ш - I )-го регистра. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 514295. кл. G Об F 15/2О, 1973. 2.Авторское свидетельство СССР № 634285, кл. (3 06 F 15/32, 1974 ( прототйп).