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

(57 бретениетехнике и ычисл носится коает исполмашинах,ель ьзоватьрешаюью изобя в вычислительных щих комбинаторнь ада ОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ДЛЯ ретения является расширение функщиональных возможностей за счет обеспечения формирования всех возможных сочетаний иэ ш элементов по п для заданных значений ш и п. Устройство для перебора сочетаний содерзит группу элеме .гон И 1, регистр 2, четыре группы элементов И 3-6, две группы элементов ИЛИ 7 и 8, группу 10 элементов задержки, элементы ИЛИ 9, элементы И 11, триггеры 2, элементы.И 13, триггеры 14-16, элементы И 17-23, элементы НЕ 24 и 25, элементы ИЛИ 26 и 27, элементы 28-31 задержки, переключатели 32, переключатель 33, пере- ср ключатель 39 режимов. 1 ил. фИзобретение относится к вычислительной технике и может быть использовано в пычислительньгк машинах, решающих комбинаторные задачи,Цель изобретения - расширение функциональных возможностей за счет обеспечения Формирования всех возможныхсочетаний из щ элементов по и длязаданных значений щ и и,На чертеже представлена схема ус 10тройства,Устройство содержит элементы И 1,регистр 2, элементы И 3, элементы И4, элементы ИЛИ 5, элементы И 6, элементы ИЛИ 7, элементы И 8, элементыИЛИ 9, элементы 10 задержки, элементы И 11, триггеры 12, элементы И 13,триггеры 14-16, элементы 17-23, элементы НЕ 24 и 25, элементы ИЛИ 26 и27, элементы 28-31 задержки, переключатели 32, двухсекционный переключатель 33, вход 34 начальной установки, вход 35 тактового сигнала, информацйонный выход 36, выход 37 сигналаокончания перебора, выход 38 сигнала25окончания перебора, переключатель 39режимовПри переборе сочетаний каждое очередное состояние образуется из предыдущего путем замены крайней справа ЗОкомбинаций "01" на "10" и переписивсех единиц, расположенных правее,в крайние правые позиции. При этом впервоначальном состоянии все единицыдолжны располагаться в крайних справа 31позициях. В последнем же состоянииони переходят в крайние слева позиции, Например, при щ = 5 и и = 3 устройством вырабатываются сочетания1. 00111 б, 10101 . 402, 01011 7, 101103, 01101 8, 110014. 01110 9. 110105, 10011 10. 1110045Устройство работает следующим образом.Перед началом работы для переборасочетаний из щ элементов по и переключатель 33 устанавливается в щ-ное положение. Замыкаются контакты переключателей 32, соответствующих щ младшим (правым) разрядам устройства, После этого на вход 34 подается сигнал, который устанавливает в нулевое состояние триггеры 14 и 12, а затем с задержкой на элементе 31 задержки через замкнутые контакты переключателя 32 устанавливает и крайние справа триггеры 12 в единичное состояние.Устройство может работать в двухрежимах. В первом режиме обеспечивается перебор сочетаний для данногоФиксированного значения и, при этомпереключатель 39 режимов устанавливается в положение, обеспечивающее соединение выхода элементов И 20 с выходом 37. Во втором режиме обеспечивается перебор всех сочетаний длязначений и = 1, щ. В этом случае переключатель 39 устанавливается в положение, обеспечивающее соединениевыхода элемента И 20 с входами элементов И 2 1 и 22,Устройство в первом режиме работает следующим образом.Первый сигнал, поступающий по входу 35, проходит через открытый элемент И 18, устанавливает триггер 14в единичное состояние и поступает навход элементов ИЛИ 27, Сигнал с выхода элементов ИЛИ 27 устанавливает внулевое состояние триггер 15 и триггеры регистра и с задержкой на элементе 30 через элементы И 11 и ИЛИ 7переписывает содержимое триггеров 12в триггеры регистра 2. Этот же сигнал, задержанный на элементе 29 задержки, поступает через элемент ИЛИ26 на входы элементов И 1 и выдаетна информационный выход 36 первое изФормулируемых сочетаний (элемент 29задержки обеспечивает задержку сигналов на время прохождения сигнала че-рез элемент задержки, элемент И 11,элемент ИПИ 7 и переходных процессовв триггере регистра 2).При поступлении очередного сигнала на вход 35 он проходит через открытый элемент И 17 и устанавливает триггер 16 в нулевое состояние, обеспечивая тем самым разрешающий потенциал на входе элемента И 23 и запрещающий - на входе первого элемента И 8, Этот же сигнал поступает на входы первого элемента И 4 и первого элемента И 6. При единичном состоянии триггеров регистра 2 на входах элементов И 4 и 8 находятся разрешающие потенциалы, а на входах элементов И 3 и 6 - запрещающие потенциалы, При нулевом состоянии триггеров регистра 2, наоборот, на входах элементов И 4 и 8 находятся запрещающие потенциалы, а на входах элементов И 3 и 6 - разрешающие,1264 Если г (г = 1, 2, , ш) крайниесправа триггеры регистра 2 находятсяв единичном состоянии, то тактовыйсигнал проходит последовательно элементы И 4 и ИЛИ 5 и устанавливает эти 5триггеры в нулевое состояние, аг+1-йтриггер регистра 2 через открытый элемент И 3 - в единичное состояние, и поступает на входы элементовИЛИ 9, что обеспечивает формированиена выкоде первого элемента ИЛИ 9 серии из г импульсов (элементы 10 задержки обеспечивают временную растяжку серии импульсов, необходимую длястабильности переходных процессов при 15дальнейшей работе),. Первый импульссерии, пройдя через элемент И 23, устанавливает триггер 16 в единичноесостояние, чем обеспечивается подачана вход первого элемента И 8 разреша. 20ющего потенциала. Второй импульс серии, пройдя первые элементы И 8 иИЛИ 7, устанавливает первый триггеррегистра 2 в единичное состояние, чемобеспечивается прохождение третьегоимпульса серии через второй элементИ 8 и установка в единичное состояние второго триггера регистра 2, а скаждым очередным импульсом серии установка очередного по порядку триггера регистра 2 по г-й триггер включительно. На этом заканчивается тактформирования очередного сочетания,которое снимается с единичных выходовтриггеров регистра 2 и выдается черезЗ 5элементы И 1 на информационный ныкодустройства этим же управляющим сигналом, задержанным к этому времени наэлементе 28 задержки и прошедшим через открытые элементы И 19 и ИЛИ 26.. Если (г = 1, 2, , ш-и) крайниеправые триггеры регистра 2 находятсяв нулевом состоянии, то тактовый сигнал, пройдя г открытых элементов И 6,.поступает через г-й элемент ИЛИ 5 иаоткрытый г+1-й элемент И 4.и в дальнейшем выполняет аналогичные действия.Если в текущем сочетании в крайнейсправа позиции имеется комбинация 50"01", то при формировании очередногосочетания она преобразуется в комбинацию "10",После того, как сформированы ивыданы все сочетания из ш элементов 55по и для данного значения и (приш ( ш , ) очередным тактовым сигналом будет сформировано следующее со 197четание, при котором ш+1-й триггеррегистра 2 находится в единичном состоянии, Сигнал из этого триггера через замкнутые клеммы соответствующейсекции переключателя 33 поступает навход элемента И 20 и через элементНЕ 24 - на вход элемента И 19, чемобеспечивается запрет прохождения задержанного на элементе 28 задержкисигнала через элемент И 19 и разрешение его прохождения через элемент И20, С выхода элемента И 20 сигнал подается через замкнутые контакты переключателя 39 на выход 37, сигнализируя тем самым об окончании работы устройства в данном режиме,Во втором режиме устройство до появления сигнала на выходе элемента И20 работает аналогично. Начиная сэтого момента сигнал с выхода элемента И 20 поступает на входы элементовИ 21 и 22,Так .как обычно и ( ш, то с единичного выхода ш-го триггера 12 череззамкнутые контакты соответствующейсекции переключателя 33 на вход элемента И 21 подается запрещающий потенциал, а на вход элемента И 22 через элемент НЕ 25 - разрешающийпотенциал. Сигнал проходит через элемент И 22 и поступает на входы элементов И 13 и вход элемента ИЛИ 27.Поскольку первые и справа триггеры 12находятся в единичном состоянии, тона входах первых и справа элементовИ 13 находятся разрешающие потенциалы. Поэтому сигнал, поступающий навходы элементов И 13, устанавливаетв единичное состояние и+1-й триггер12 и подтверждает единичные состоянияпредьдущих триггеров 12, чем обеспечивается увеличение значения и наединицу, Этот же сигнал проходит элемент ИЛИ 27 и с его выхода обеспечивает выполнение действий, аналогичныхдля первого режима работы, В дальнейшем процесс повторяется.После того, как сформировано и выдано последнее из формируемых сочетаний, т.е, когда значение и станет равным а, на входе элемента И 21 находится разрешающий потенциал, а на,входе элемента И 2 - запрещающий.Поэтому сигнал с выхода элемента И20 через элемент И 21 поступает навыход 38, сигнализируя тем самьж обокончании работы устройства в данномрежиме.5Для обеих режимов в случае, когда шш, и п крайние слева триггеры регистра 2 находятся в единичном сос.тоянии (последнее из формируемых сочетаний при данном и) при поступлении очередного тактового сигнала на выходе последнего элемента И 4 появляется сигнал, который устанавливает триггер 15 н единичное состояние, потенциал с единичного выхода которого 10 подается через замкнутые контакты переключателя 33 на элементы И 19 и 20, управляя их работой.15Формула изобретенияУстройство для перебора сочетаний,содержащее регистр, первую группушэлементов И, вторую группу ш эле ментов И, третью группу шэлементов И, четвертую группу шэлементовИ, первую группу шэлементов ИПИвторую группу шэлементов ИЛИ,группу шэлементов задержки, первый 25элемент И и первый триггер, единичныйвход которого подключен к выходу первого элемента И, первый вход которогоподключен к выходу первого элементаИЛИ второй группы и к первому входупервого элемента И четвертой группы,второй вход которого подключен к единичному выходу первого триггера, первый вход -го элемента И второй группы (х = 1, 2, , ш) подключен кединичному выходу д-го разряда регис 35тра и к первому входу 1-го элементаИ четвертой группы (1 = 2, 3,ш), выход -го элемента И второйгруппы (х Ф ш) подключен к первым40входам 1-х элементов И и ИЛИ первыхгрупп соответственно (1 = 1, 2,ш), второй вход 1-го элемента ИЛИпервой группы подключен к выходу 1-гоэлемента И третьей группы и к первому45входу 1+1-го элемента И третьей группы, второй вход 1-го элемента И третьей группы подключен к нулевому выходу х-го разряда регистра и к второму входу 1-го элемента И первойгруппы, выход которого подключен к50единичному входу первого разряда регистра, нулевой вход д-го разряда ре", гистра (хш) подключен к выходу1-го элемента И второй группы и кпервому входу 3-го элемента ИЛИ вто рой группы, второй вход которогоподключен к выходу 1-го элемента за-.держки группы, вход которого подключен к выходу 1+1-го (1 4 ш) элемента ИЛИ второй группы, выход ш-го элемента И второй группы подключен к нулевому входу ш-го разряда регистра,вход ш-го элемента задержки группы подключен.к нулевому входу ш-го разряда регистра, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей за счет обеспечения формирования всех возможных сочетаний из ш элементов по п для заданных значений ш и п, в него введены группа триггеров, пятая группа шэлементов И, шестая и седьмая группы ш элементов И, третья группа шэлементов ИЛИ, второй, третий четвертый, пятый, шестой и седьмой элементы И, первый и второй элементы ИЛИ, второй и третий триггеры, первый и второй элементы НЕ, первый, второй, третий и четвертый элементы задержки, группа ш переключателей, переключатель режимов, двухсекционный переключатель, причем входы переключателей группы соединены с первыми единичными входами триггеров группы, единичные выходы которых, кроме ш-го соответственно, соединены с первыми входами элементов И пятой группы и с первыми входами элементов И шестой группы, выходы .1-х элементов И четвертой группы (д = 1, 2, , ш) соединены с вторыми входами 1+1-х элементов И четвертой группы и с первыми входами -х элементов ИЛИ третьей группы, вторые входы х-х элементов ИЛИ третьей группы соединены с выходами 1-х элементов И шестой группы, выходы элементов ИЛИ третьей группы соединены с вторыми единичными входами х-х разрядов регистра выходы ш-го и ш-го элементов И шестой группы соединены соответственнос информационными входами разрядоврегистра, первые входы элементов Иседьмой группы соединены соотнетственно с единичными выходами разрядоврегистра, выходы элементов И седьмойгруппы являются информационным выходом устройства, входы первой секциидвухсекционного переключателя в порядке возрастания ньмеров соединенысоответственно с единичными выходамитриггеров группы, начиная с первоготриггера, выход первой секции двухсекционного переключателя соединен свходом первого элемента НЕ и с первымвходом третьего.элемента И, входы. ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5,Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 второй секции двухсекционного переключателя в порядке возрастания йомеров соединены соответственно с единичными выходами разрядов регистра, начиная со второго разряда, ш-й вход 5второй секции двухсекционного переключателя соединен с единичным выходом второго триггера, а выход соединен с входом второго элемента НЕ ис первым входом четвертого элемента И,выход первого элемента НЕ соединен спервым входом второго элемента, И, выход второго элемента НЕ соединен спервым входом пятого элемента И, первые входы шестого и седьмого элементов И соединены с входом тактовыхсигналов устройства,.второй вход шестого элемента И соединен с нулевымвыходом третьего триггера, второйвход седьмого элемента И соединен сединичным выходом третьего триггера,выход шестого элемента И соединен сединичным входом третьего триггера ис первым входом первого элемента ИЛИ,выход которого соединен с нулевым 2 Бвходом триггера, с входами сбросаразрядов регистра, через первый элемент задержки - с вторыми входамиэлементов И шестой группы и черезвторой элемент задержки - с первымвходом второго элемента ИЛИ, выходкоторого соединен с вторыми входами элементов И седьмой группы, вход начальной установки устройства соединен с нулевым входом третьего триггера, с нулевыми входами триггеровгруппы и через третий элемент задержки - с входами переключателей группы, выход седьмого элемента И соединен с вторым входом первого элементаИ второй группы, с первым входом первого элемента И третьей группы, с нулевым входом первого триггера и черезчетвертый элемент задержки - с вторыми входами четвертого и пятого элементов И, выход второго элемента Исоединен с вторым входом первого элемента ИЛИ и с вторыми входами элементов И пятой группы, выходы -х эле-.ментов И пятой группы ( = 1,2,ш) соединены соответственно с информационными входами +1-х триггеРов группы,. выход четвертого элементаИ соединен с входом переключателя режимов, первый выход которого соединенс первым выходом окончания перебораустройства, второй выход соединен свторыми входами второго и третьегоэлементов И, выход пятого элемента Исоединен с вторым входом второго элемента ИЛИ, выход третьего элемента И является вторым выходом окончания .перебора устройства.