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

1 а Ать".Л бкбляотмй ф 0 11 И С А Н И Е (11)525948ИЗОБРЕТЕНИЯ Ссокоз Советскии Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ олнительное к авт, свид-ву 1 956682/2 09,73 2) Заявле 51)Ю, К 406 0 с присоединением заявки сударственный колите авета Министров СССР ос делаи изобретенийи открытий) Автор из обре В. Епихц) Заявит 54) УОТРОИОТВО 1 ЛЯ ПЕРЕЙРА ООЧЕТАНИ 2 И", оди выходо блок-схема п ертеже да л блок к пеим вх ем, чт о вход которо редепит Зто достигается перебора соединены элемента "И", выход ко входу сброса рас т элемент задержки ко перебора, управляющ которых подключен к 2 ам рвогоключе го 8,10 ии вановля через блоков о из о о и вход пер выходу вт вог 25 э Изобретение относится к области автоматики и вычислительной техники и можетбыть использовано при реализации технических средств дискретной автоматизациии вычислительных машин.Известны устройства дпя перебора сочетаний, содержащие спок памяти, управляющие входы которого связаны с выходами распределителя, а выходы подключенык соответствующим входам двух блоков перебооа, элементы "И", элементы задеряки и триггер.Известные устройства обладают низкимбыстродействием и не позволяют осуществить выдачу очередного сочетания в каждом такте его работы,Цель изобретения - повьгщение быстро -действия,ментан из входов которого соединен с м второго блока перебора, а другой вход - с его управляющим входом и с выходом третьего элемента "И", один из входов которого соединен с выходом второго олока перебора, а другой вход- с его управляющим входом и с выходом третьего элемента "И", один из входов которого и один из входов четвертого элемента фИ" подключены к лине тактовых сигналов, а нх другие входы сое. - ,.иены с соответствующими выходами триггера, входы которого подключены к выходу пе 1 ового элемента "И" и через другой эле,:ент задержки к у.правляюшему входу распределителя и к выходу четвертого элемен//1 х Рта йНа на ред агаемого устроиства.Оно содержит блок памяти 1, блребора 2 с выходами 3 и управляюдом 4, блок перебора 5 с выходамиуправляющим входом 7, элемент "Иэлемент задержки 9, элементы "И"11, триггер 12 со входом установкединичное состояние 13, входом уст= 2 111 = 3 111 = 4 001111010111 = 4 40 011011 011111 = 5 111111 = 6 Для М = 5 00000 = 0 00001 = 1 00101001110101101111 411111 = 5Для любых значенибазовые сочетания покомбинаций соответсттаний, например, дляответствуют следующи( й =5,Т=7):11111 100000011110 110000011110 1010000 й М двоичныепутем всехбазовых сочеиМ=12 со- у ые сочетания чают щих = 6 е базо 11000 1111000 11000 1110100 11000 1110010 ки в нулевое состояние 14, прямым выходом 15 и инверсным выходом 16, элементфИ" 17, элемент задержки 18, распределитель 19, шину 20 тактовых импульсов,шину 21 установки и шину 22 окончанияработы.Устройство работает следующим образом,Перебор сочетания из М элементов пой заменяется перебором двух сочетаний,каждое из которых в качестве исходныхимеет полное базовое сочетание, Полнымбазовым сочетанием называется такое сочетание, из которого можно получить М(включая исходное) различных сочетанийблагодаря циклическому сдвигу исходногосочетания, Например, из сочетанияМ 111 11000.,0020 можно получить еще Мсочетаний благодаря его циклическому сдвигу.Базовые сочетания подбираются по опре деленным правилам. Для некоторых значеИ ний М и значений М (от 0 до Й ) все базовые сочетания будут равны;Для М = 3 ЧляМ=6 ООО = 0 000000 = 0 001 = 1 000001 = 1 011 = 2 00001130 111 = 3 000101 = 2001001 411110 1001000 11000 110110011100 1110000 11000 110101011100 1101000 10100 111100011100 1100100 10100 111010011100 1010100 10100 110110011010 1110000 10100 110101010000 111110011010 1100100 10000 111101011010 1100010 10000 111011011010 1010100 00000 1111110Таким образом, каждое сочетание из двенадцати по шести можно представить в виде комбинации двух базовых сочетаний (двЫных базовых сочетаний),При этом исходные базовые сочетанияимеют разрядность Й и Т ( Й + Т = М).Максимальное количество сочетаний, которое можно получить из двойного базового, равно ЙТ (включая само двойное базовое сочетание).Порядок получения всех сочетаний издвойных базовых следующий.Сначала сдвигается циклически одно изсоставляющих сочетаний; если оно содержит Т разрядов, то сдвигается (Т) раз,и после этого осуществляется одновременный циклический сдвиг первого и второгосоставляющих сочетаний. Такая процедураповторяется Й раз.Рассмотрим работу устройства на примере перебора сочетаний при М = 12, Й == 6, В = 5 и Т = 7. Перед началом работы устройство устанавливают в исходное состояние по шине 20, При этом триггер 12 устанавливается в единичное состояние, распределитель 19 в первое положение, а блоки перебора 2 и 5 - в нулевое состояние, Блок перебора 2 имеет пять разрядов и первые тить выходов блока памяти 1 подключены к его входам. Блок перебора 5 имеет семь разрядов, и к его входам подключены семь последних выходов блока памяти 1. Далее по шине 20 начинают поступать тактовые импульсы. Так как перед поступлением первого тактового импульса триггер 12 находится в единичном состоянии, открыт элемент "И" 17, и первый тактовый импульс через элемент "Иф 17 поступает на продвижение распределителя 19. Распределитель 19 переводится во второе положение, при этом на его первом выходе появляется импульс, который производит считывание первой строки из блока памяти 1. Содержимое первой строки из блока памяти 1 записывается в блоках перебора 2 и 5.В результате этого в блоке перебора 2имеется базовое сочетание 11111, а вблохе перебора 5 - базовое сочетание1000000,Блоки перебора 2 и 5 осуществляют Ьциклический сдвиг их содержимого. Сигнал на управляющих входах 4 или 7 блоков перебора 2 или 5 появляется в случае если на все разряды блока перебораподаны из блоха памяти 1 все единицыили все нули, а также в том случае, еслисодержимое блока циклически сдвигаетсяна величину равную разрядности блоха,уменьшенную на единицу, т.е. для блокаперебора 2 после четырех сдвигов, а дляблоха перебора 5 - после шести сдвигов.На выходах 3 и 6 блоков перебора 2и 5 появляются сочетания двенадцати элементов по шесть. После первого тактовогоимпульса на выходах 3 и 6 блоков пере 20бора 2 и 5 будет первое сочетание111111000000,Так как импульс с выхода элемента "И"17 поступил на вход элемента задержкиМ18, перед приходом второго тактового импульса триггер 12 находится в нулевомсостоянии и открыт элемент "И"1.Последующие шесть тахтовых импульсов,поступивших по шине 20, пройдут. черезэлемент "И" 11 на продвижение блока перебора 5и на вход элемента "И" 10. Элемент фИф10 открыт, если на управляющем входе 7блока перебора 5 имеется сигнал.Таким образом, по шести последующимтактовым импульсам получим следующиесочетаниЯ: 111110100000111110010000111110001000111110000100 40111110000010111110000001Таким образом, произошло шесть циклических сдвигов содержимого блока перебора 5. После этого на управляющем входе 7 блока перебора 5 появляется сигнал, Тах как и на управляющем входе 4 блока 2 имеется сигнал, собирается элемент фИф 8, и по переднему фронту сигнала с его ЬО выхода перебрасывается триггер 12 в единичное положение и сбрасываются блоки перебора 2 и 5 в нулевое положение через первый элемент задержки 9, Следующий тактовый импульс через элемент фИ" 17 пере- ЬЬ ведет распределитель 19 в третье положение, и происходит считывание второй строки блока памяти 1, В результате на выходах 3 и 6 блоков перебора 2 и 5 имеется сочетание 111101100000, 60 Триггер 12 импульсом с элемента задержки 18 перебрасывается в нулевое состояние и открывается элемент фИф 11.Следующие шесть тахтовых импульсов поступят на продвижение блока перебора 5, в результате чего получим следующие сочетания:111100110000111100011000111100001100111100000110111100000011111101000001Так как содержимое блока перебора 5 сдвигалось шесть раз, на управляющем входе 7 появляется сигнал, который открывает элемент фИ" 10, Следующий тактовый импульс осуществит циклический сдвиг содержимого блока перебора 2 и содержимого блока перебора 5. При этом на управляющем входе 7 блока перебора 5 пропадает сигнал и сдвиг этим тактовым импульсом не входит в подсчет импульсов сдвига для выдачи сигнала на управляющем входе 7. В результате получаем очередное сочетание 011111100000,Последующие шесть тактовых импульсов поступят на продвижение только блока перебора 5 и в результате получим еше шесть из двенадцати по шесть:011110110000011110011000011110001100011110000110011110000011011110000001 Далее опять происходит одновременный циклический сдвиг содержимого блоков перебора 2 и 5 при поступлении очередного тактового импульса. Последующие шесть тактовых импульсов циклически сдвигают только содержимое блока перебора 5 и т,д. до тех пор, пока на управляющих входах 4 и 7 одновременно появятся сигналы, После этого происходит сброс содержимого блоков перебора 2 и 5 и очередной так - товый импульс, поступивший по шине 20, продвинет распределитель 19 в следующее положение и произойдет считывание очередной строки блока памяти 1 в блоки перебора 2 и 5. Далее опять продолжается циклический сдвиг содержимого блоков перебора 2 и 5. Этот процесс повторяется до тех пор, пока не будут считаны все стр- ки блока памяти 1 и на шине 22 (последний выход распределителя 19) не появится импульс, сигнализируюший об окончании перебора сочетаний.Формула и з обретения Устройство для перебора сочетаний, содержащее блок памяти, управляющие входы которого связаны с выходами распределителя, а выходы подключены к соответствующим входам двух блоков перебора, элементыИ", элементы задержки и триггер, о т л и ч а ю ш е е с я тем, что, с целью повышения быстродействия, входы блоков перебора соединены со входами первого элемента И", выход которого подключен ко входу сброса распределителя и через элемнет задержки ко входу сброса блоков перебора, управляющий вход первого из которых подключен к выходу второго элемента "И, один из входов которого соединен с выходом второго блока перебора, а другой вход - с его управляющимвходом и с выходом третьего элемента "И,один из входов которого и один из входовчетвертого элементаИ" подключены к шине тактовых сигналов, а их другие входыЯ соединены с соответствующими выходамитриггера, входы которого подключены к вы-.ходу первого элементаИ и через другойэлемент задержки к управляющему входураспределителя и к выходу четвертого элемента "И,525948 Составитель В, БелкинДанилович Техред М. Левицкая Корректор Т. Чаброва Типаж 8 исноеистров СССР ного комитетаиюбретений и от ау а, Жлиал ППП Патент", г. Ужгород, ул, Проектная,аз 5450/204ЦНИИПИ Государствепо делам113035,Мос Пвета Мрытийая наб