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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ1) 54295 Союз Советских Социалистических Ресоублик(51) М Кч в С 06 Г 15,2 осударственныи комит Совета Министров СС 3) УД 1 681,14(088,8 оо делам изобретении и открытий) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ в - с созаписи, а дами пер Изобретение относится к устройствам, осуществляющим перебор сочетаний из Л 4 элементов по У.Известные устройства для перебора сочетаний из М элементов по Л содержат блок уп равления, блок перезапсси, группы элементов И, регистры, триггеры, элементы задержки и элементы И и ИЛИ. Недостатком известных устройств является то, что при значениях У, достигающих величины (М - 1), 10 объем оборудования становится значительным и возрастает пропорционально величине Л 1.Цель изобретения заключается в упрощении устройства при,переборах сочетаний из большого числа элементов. В описываемом 15 устройстве это достигается тем, что единичный выход триггера перезаписи соединен с управляющими входами первой группы элементов И, информационные входы которых связаны со вторыми входами основного регистра 20 и выходами блока управления, а выходы - с установочными входами запоминающего регистра, выход старшего разряда которого через третий элемент задержки соединен с нулевым входом разрешающего триггера, еди ничным входом триггера перезаписи и нулевым входом триггера фиксации двойного пересчета, выходы остальных разрядоответствуюшими входами блока переуправляющий вход - с первыми вхо вого и второго элементов И, с нулевым входом дополнительного триггера, с управляющим входом вспомогательного регистра п выходом четвертого элемента И, пмпульсньш вход которого связан с шиной тактовых импульсов, а управляющий вход - с едпни шым Выходов разрешаОщего триггера, единичный вход которого соединен с выходом пятого элемента И, первым входом элемента И 1 И, 1 пр а Вля Ощ 11 ъ 1 Входа ми Втор 011 Грпп ы зле. ментов И и через второй элсмепг задержки - с единичным Входом триггера фиксации пересчета, нулевой вход которого связан с нулевым входом триггера перезаписи, с первым входом пятого элемента И и через первый элемент задержки - с шиной входпого импульса, первым входом третьего элемента И и импу.1 ьсным Входох Олока упраВ;1 епия, управляющий вход которого связан с шиной окончание перебора, а установочные входы - с пулевыми выходами основного регистра, единичный Выход старшего разряда которого соединен с информационным входом соответствующего элемента И второй группы, со вторым входом пятого элемента И и третьим входом третьего элемента И, а остальные выходы - с инфорхационными входами блока управления и информационными входами соответствующих элематов И второй группы, выходы которых связаны с ипформациимпульс 3-й импульс онными входами вспомогательного регистра, нулевой выход старшего разряда которого связан со вторым входом первого элемента И, а единичный выход старшего разряда - со вторым входом элемента ИЛИ, выход которого соединен с единичным входом дополнительного триггера, нулевой выход которого связан со вторым входом второго элемента И, третий вход которого соединен с единичным выходом триггера фиксации двойного пересчета, а выход - с установочным входом управляющего триггера и выходом первого элемента И, третий вход которого соединен с нулевым выходом триггера фиксации двойного пересчета, единичный вход которого связали с выходом третьего элемента И, второй вход которого соединен с единичным выходом триггера фиксации пересчета, единичный выход управляющего триггера соединен с управляющим входом блока перезаписи, выходы которого связаны с первыми входами основного регистра.На чертеже представлена функциональная схема устройства,Устройство содержит триггер 1 перезаписи, первую группу элементов И 2, запоминающий регистр 3, блок 4 пврезаписи, управляющий триггер 5, основной регистр 6, вторую группу элементов И 7, блок 8 управления, вспомогательный регистр 9, первый элемент задержки 10, второй элемент задержки 11, триггер 12 фиксац 1 ии двойного пересчета, триггер 13 фиксации пересчета, третий элемент И 14, первый элемент И 15, второй элемент И 16, четвертый элемент И 17, третий элемент задержки 18, разрешающий триггер 19, пятый элемент И 20, дополнительный триггер 21, элемент ИЛИ 22, шину 23 тактовых импульсов, шину 24 окончания перебора и шину 25 входного импульса.Первоначально происходит установка в исходное состояние всех триггеров устройства. В исходном состоянии в единичном положении находится только триггер 1 перезаписи. Остальные триггеры находятся в нулевом положении. Для перебора всех сочетаний из М элементов по У производится запись единиц в первые У разрядов основного регистра б. Дальнейшая работа устройства происходит по тактам Ть Т и Тз. В такте Т 1 с выходов основного регистра б считывается очередное сочетание из М элементов по У и устанавливается в нулевое положение управляющий триггер 5. В такте Т 2 по шине 25 поступает входной импульс. Импульс с шины 25 поступает на вход первого элемента задержки 10, на первый вход третьего элемента И 14 и на импульсный вход блока 8 управления. Так как на втором входе третьего элемента И 14 нет сигнала (триггер 13 фиксации пересчета находится в нулевом положении), то триггер 12 фиксации двойного пересчета остается в нулевом положении. Блок управления 8 определяет первый старший разрядосновногорегистра 6, который содержит единицу при усло 5 10 15 20 25 30 35 40 45 50 55 60 65 вии, что следующий за ним разряд содержитноль. В данном случае это Л-й разряд. НаЛ-м выходе блока управления 8 появляетсяимпульс, который через Лт-й элемент И 2первой группы осущсствляет запись единицыв Лт-й разряд запоминающего регистра 3 и перезапись единицы из Лт-го разряда основногорегистра б в (Л+1)-й разряд основного регистра 6. После этого импульс с выхода первого элемента задержки 10 переводит в нулевое положение триггер 1 перезаписи и подтверждает нулевое положение триггера 13фиксации пересчета. Если последний разрядосновного регистра 6 находится в единичномположении, то импульс с выхода первого элемента 3 задержки 10 через пятый элемент И20 переводит в единичное положение разрешающий триггер 19. Так как в данном случаесчитаем, что в последнем разряде основногорегистра б единица отсутствует, то послепервого импульса, поступившего по шине 25,разрешающий триггер 19 останется в нулевом положении.Таким образом, после первого импульса, поступившего по шине 25, основной регистр 6находится в состоянииив1111 1 0100ОО,а в запоминающем регистре 3 в Ж-м разрядехранится единица. В этом случае такт Тзможет быть пропущен.При поступлении второго, третьего и другихимпульсов до (М - У) -го импульса в тактахТ, по шине 25 все триггеры устройства находятся в нулевом положении, и по каждомупоступающему по шине 25 импульсу осуществляется продвижение последней единицы восновном регистре 6 на один разряд вправо.Таким образом, после (М - Ж) импульсов,поступивших по шине 25, основной регистр 6имеет следующие состояния;и1 1 11 100000 - исходное состояние;м111 , 10100000 - поступил 1-й импульспо шине 25;11110010000 - поступил 2-йпо шине 25;11110001000 - поступилпо шине 25;11110000010 - поступил (М - У - 1)импульс по шине 25;111 . 10000001 - поступил (М - М) импульс по шине 25.В каждом такте Т 1 считывается предыдущеЕположение основного регистра 6. Такты Тз приэтом могут быть опущены.Затем в очередном такте Тд считывается сочетание из М элементов по У, которое 1 находится в основном регистре б. В данном случаесочетание 11111000001 в такте Та во.аИступает импульс по шине 25. Опять блоком управления 8 осуществляется сдвиг единицы из первого старшего разряда основного регистра 6, следуощий разряд после которого находится в нулевом положении. В данном случае основной регистр б находится в состоянииП 1 10100 01.В отличие от предыдущих случаев на втором входе пятого элемента И 20 имеется сигнал, так как последний разряд основного регистра 6 наход 1 ится в единичном положении.Следовательно, импульс с выхода первого элемента задержки 10, поступив на первый вход пятого элемента И 20, переводит в сединичное положение разрешающий триггер 19 и дополнительный триггер 21 (через элемент ИЛИ 22) и осуществляет перезапись содержимого основного регистра 6 (кроме первого разряда) через вторую группу элементов И 7 во вспомогательный регистр 9, Кроме того, на вход второго элемента задержки 11 поступает импульс, который, после задержки, перебрасывает в единичное положение триггер 13 фиксации пересчета.В такте Тз по шине 23 поступает серия из М вспомогательных тактовых импульсов (81 - Ьлл), которые через четвертый элемент И 17 поступают на продвижение запоминающего регистра 3 и вспомогательного регистра 9. Кроме того, в каждом такте (11 - 1) осуществляется перевод в нулевое положение дополнительного триггера 21 и опрос первого элемента И 15 и второго элемента И 16. При продвижении ссединицы в запоминающем регистре 3 осуществляется запись единицы или нуля в соответствующий разряд основного регистра 6 в зависимости от состояния блока 4 перезаписи 2 управление которым происходит управляющим триггером 5. Если управляющий триггер 5 находится в снулевом положении, то в разряды основного регист 1 ра 6 записываются единицы и наоборот. Так как первоначально управляющий триггер 5 находится в нулевом положении, то по первому такту 11 происходит запись единицы в основной репистр 6 (в данном случае в (К+1) разряд, так как в Л-м разпяде запоминающего регистра 3 записана единица). Триггер 12 фиксации двойного пересчета находится в нулевом положении и пазрешает сборк первого элемента И 15. Как только в последнем разряде вспомогательного регистра 9 появляется ноль, очередным тактовым импульсом 1; через первый элемент И 15 управляюций триггер 5 перебрасывается в единичное полокение, и уже прц продгцжспии запоминающего регистра 3 импульсом 1 происходит запись нуля в очередной разряд основного регистра 6. В последующие разряды основного регистра 6 по тактам (;+1 - м)45 50 55 00 65 10 15 20 25 30 35 40 записываются нули. В данцом случае единица записывается в основной регистр 6 только в (У+1) разряд, а в остальные последующие разряды только нули, В результате получим сочетаниелл - 2И 11101100 ОО.лсВ следующем такте Т 1 (еслц в последующем разряде основного регистра б находится ноль) импульсом с выхода первого элемента задержки 10 происходит переброс триггера 13 фиксации пересчета в нулевое положение, и дальнейшая работа устройства происходит аналогично.Если перед очередным тактом Т, триггер 13 фиксации пересчета находится в сединичном полохсе 11 ии и в последнем разряде основного регистпа 6 находится единица. то прц поступлении импульса в такте Т по шине 25 пеоебрасывается в единичное полохсение тпиггер 12 фиксации двойного пересчета. Тогда переключение управляющего трцггепа 5 в единичное положение осуц 1 ествляется посредством сборки второго элемента И 16, который собирается на олин тактпозже, чем собирался бы первый элемент И 15. Это необходимо для ппедотвоашения потери одной ссединипы в основном регистре 6, когда в двух подряд поллченных сочетаниях в последнем разояде имеется единица. Рассмотрим это на поимепе, когда в основном пегистре 6 было сочетаниеЛ - 2111 1 ОО 0101.После очередных тактов Т 1, Т., Т., триггер 13 фиксации пересчета перебпасывается в единичное положе 2 гие. Основной регцсто 6 имеет сочетание, в котором последний разряд1 Ч 2 содержит единицу 1111100 0011, В резизультате этого оказывается подготовлен к срабатыванию третий элемент 1 Л 14. В очепелном такте Т. пост 2 пает имп 12 льс по шине 25 и спабатывает третин элемент И 14, Тпиггео 12 фиксации лвойного пересчета перебрасывается в елиничное положечце и подготавливает к работе второй элемент И 16. Блок управления 8 осуществляет сдвиг елиницы цз (У - 2) разряда основного регистра 6 в О - 1) разряд и записывается единица в (У - 2) разряд запомц 1.а ошсго регистра 3. Основной регистр 6 находится в состояниию - з111110100.011.1 Лмпульс с выхода первогоз 1элемента задержки 10 через пятый элемент И 20 перебрасывает в единичное положение разрешающий триггер 19 и дополнительный триггер 21 и осуществляет перезапись со 514295держимого основного регистра 6 во вспомогательный регистр 9. В такте Тз начинается продвижение содержимого запоминающего регистра 3 и содержимого вспомогательного регистра 9. Если бы управляющий триггер 5 перебрасывался бы с помощью первого элемента И 15, то в основном регистре 6 потерялась бы одна единица за счет того, что из запоминающего регистра 3 было бы разрешено записать две единицы (вспомогательный регистр 9 в старших разрядах содержит подряд две единицы) в (У - 1) -й и У-й разряды основного регистра 6, в то время как необходимо записать единицы в У-й и (Л+1)-й разряды основного регистра, так как в (1 х - 1)-м разряде уже имеется единица, Запись единиц в Л-й и 1 Л+1)-й разряды основного регистра 6 осуществляется в ре. зультате того, что триггер 12 фиксации двойного пересчета подготавливает,к срабатыванию второй элемент И 16, который еще упр авляется нулевым выходом дополнительного триггера 21. Дополнительный триггер 21 перебрасывается в нулевое положение при опросе второго элемента И 16 на один такт 1 позже того момента, когда в последнем разряде вспомогательного регистра 9 появится ноль. Вследствие этого в основной регистр 6 записывается дополнительная единица, и тем самым общее число единиц в основном регистре 6 равно Ж, а состояние его будетм - зш11 ошоооо.мВ дальнейшем работа устройства происходит аналогично.Окончание работы устройства происходит, когда все единицы располагаются в старших разрядах основного регистра 6, т, е.оооооош 111. мВ этом случае в очередном такте Т, происходит считывание этого сочетания. В такте Т импульс поступает с шины 25 на вход блока управления 8. Так как в основном регистре 6 нет ни одной единицы после которой находится ссноль, то на шине 24 появляется импульс, который свидетельствует об окончаниии перебора,Формула изобретенияУстройство для перебора сочетаний, содержащее блок управления, блок перезаписи, группы элементов И, регистры, триггеры, элементы задержки и элементы И и ИЛИ, отличающееся тем, что, с целью упрощения устройства, единичный выход триггера перезаписи соединен с управляющими входами первой группы элементов И, информационные входы которых связаны со вторыми 5 10 15 20 25 30 35 40 45 50 55 60 входамн основного регистра и выходами блока управления, а выходы - с установочными входами запоминающего регистра, выход старшего разряда которого через третни элемент залсргккп соединен с нулевым входом разрешающего триггера, единичным входом триггера перезаписи и нулевым входом триггера фиксации двойного пересчета, выходы остальных разрядов - с соответствующими входами блока перезаписи, а управляющий вход - с первыми входами первого,и второго элементов И, с нулевым входом дополнительного триггера, с управляющим входом вспомогательного регистра и выходом четвертого элемента И, импульсный вход которого связан с шиной тактовых импульсов, а управляющий вход - с единичным выходом разрешающего триггера, единичный вход которого соединен с выходом пятого элемента И, первым входом элемента ИЛИ, управляющими входами второй группы элементов И и через второй элемент задержки - с единичным входом триггера фиксации пересчета, нулевой вход которого связан с нулевым входом триггера перезаписи, с первым входом пятого элемента И и через первый элемент задержки - с шиной входного импульса, первым входом третьего элемента И и импульсным входом блока управления, управляющий вход которого связан с шиной окончание перебора, а установочные входы - с нулевыми выходами основного регистра, единичный выход старшего разряда которого соединен с информационным входом соответствующего элемента И второй группы, со вторым входом пятого элемента И и третьим входом третьего элемента И, а остальные выходы - с информапионными входами блока управления и информационными входами соответствующих элементов И второй пруппы, выходы которых связаны с информационными входами вспомогательного регистра, нулевой выход старшего разряда которого связан со вторым входом первого элемента сИ, а единичный выход старшего разряда - со вторым входом элемента ссИЛИ, выход которого соединен с единичным входом дополнительного триггера, нулевой выход которого связан со вторым входом второго элемента ссИ, третий вход которого соединен с единичным выходом триггера фиксации двойного пересчета, а выход - с установочным входом управляющего триггера и выходом первого элемента И, третий вход которого соединен с нулевым выходом триггера фиксации двойного пересчета, единичный вход которого связан с выходом третьего элемента И, второй вход которого соединен с единичным выходом триггера фиксасии пересчета, единичный выход управляющего триггера соединен с управляющим входом блока перезаписи, выходы которого связаны с первыми входами основного регистра.Редактор Л. Тюрина Корректор О, Тюрина Типография, пр. Сапунова, 2 Заказ 1848,О Изд. Лз 1343 Тираж 864 Полписнсе ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж.35, Раушская наб д. 4/5