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

110O Изобретение относится к вычислительной технике и может быть использовано в специализированных моделирующих усгройствах для решения задач синтеза сетей связи, транспортных сетей, вычисления характеристик графов. Известно устройство для nepeSopia сочетаний, содержащее регистры сдвига, распределитель импульсов, дешифратор. триггер, элементы И, элементы задержки, счетчик 1. Недостатками данного устройства является сложность и низкое быстродействие. Известно устройство для перебора сочетаний, содержащее распределитель им- . пульсов, генератор тактовьк Ямпульсов блок .памяти, два блока перестановок, триггер, элементы И, элементы задержки 2J. Недостатком данного устройства является сложность. Наиболее близким к предлагаемому является устройство для перебора сочетаной, содержащее распределитель импульсов 25 генератор такторых импульсов, п счетчикав, (И-1) группу элементов И, (И+2) эле мента ИЛИ, и элементов запрета 2(м-1) элементов задержки, причем выход переноса 1 -го счетчика, кроме последнего, через i -if элемент запрета и первый (i-H)-u элемент ИЛИ соединены с входом (i+l)-ro счетчика, а также с соответствующим входом распределителя импульсов и через второй i -и элемент ИЛИ и первый -i-и элемент задержки с первыми входами элементов И i -и группы, вторые входы которых соединены соотве ственно с выходами 1 -го счетчика, а выходы - с входами (т +1 )-го счетчика, выход первого i -го элемента задержки через второй ч-й элемент задержки и первый i -и элемент ИЛИ соединены с входом 1 -го счётчика, а через второй (1-1)-й элемент ИЛИ - входом первого (i-l)-ro элемента задержки, выход переноса последнего счетчика соединен с входом установки распределителя импульсов, вход первого счетчика через первый элемент запрета и первый элемен ИЛИ подкл1очен к выходу генератора так товых импульсов () fsj. Недостатком данного устройства явля ется его сложность при больших М и NЦель изобретения - упрощение устрой ства для перебора сочетаний. Поставленная цель достигается тем, что устройство для перебора сочетаний, содержащее первый распределитель им20SO2 пульсов, генератор тактовых импульсов, четыре группы элементов И, содержит два накапливакщих сумматора, второй рас пределитель импульсов, два триггера, группу элементов ИЛИ, три элемента НЕ, три элемента И, два элемента ИЛИ, формирователь импульсов, причем выход генератора тактовых импульсов соединен с информационным входом первого распределителя импульсов и первыми входами первого и второго элементов И, выходы первого распределителя импульсов соедииены соответственно с первыми входами элементов И первой и второй групп, вто- рые входы которых соединены соответствённо с выходами разрядов первого и второго накапливагацих сумматоров, входы разрядов которых соединены соответственно с выходами элементов И второй rpyraibi и элементов ИЛИ первой группы, первые входы элементов ИЛИ первой группы соединены соогветственно с выходами элементов И третьей группы и соответствуюишми входами первого элементов ИЛИ, выход которого соединен с единичным входом первого, триггера, нулевой вход кото рого соединен с последним выходом первого распределителя импульсов, выход первого триггера соединен с первым входом третьего элемента И, второй вход которого соединен с входом первого элемента НЕ, вторым входом второго элемента И и выходом второго триггера, нулевой и единичный входы которого соединены соответственно с последним,выходом первого распределителя импульсов и выходом первого элемента И, второй вход которого соединен с вь1ходом второго элемента НЕ, вход которого соединен с выходом второго элемента ИЛИ и первыми, входами элементов И третьей группы, вторые входь которых соединены соответственно с выходами второго распределителя, вход которого соединен с выходом второго элемента И« входы сброса первого и второго распределителей импульсов fсоединены с выходом формирователя импульсов, вход которой соединен с выхо- дом третьего элемента И, третьими входами элементов И второй группы и входом третьего элемента НЕ, выход которого соединен с третьими входами элементов И первой и третьей группы, вторые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И четвертой группы , первые входы которых соединены соответственно с выходами элементов И первой группы и соответствующими входами второго элемента ИЛИ, втррые йходы элементов И четвертой группь: соединены с выходом первого элемента НЕ. На чертеже представлена схема устройства для перебора сочетаний. Устройство Для перебора сочетаний с держит сумматор 1, группу элементов И 2, группу элементов И 3, группу элемен тов ИЛИ 4, сумматор 5, элемент ИЛИ 6 элемент НЕ 7, элемент И 8, триггер 9, распределитель 1О импульсовугенератор 11 тактовых импульсов, элемент И 12, распределитель 13 импульсов, элемент ИЛИ 14, триггер 15, элемент И 16, элемент НЕ 17, группу элементов И 18 формирователь импульсов 19, элемент НЕ 20 и элементы И 21. Перебор сочетаний из М по N производится следующим образом. Исходным сочетанием является со четанйе,в котором N единиц записано в праВ:ЫХ (младших) разрядах. Для получе, очередного сочетания подсчитывается число Ь подряд стоящих нулей в младших разрядах, начиная с нулевого д первой единицы и число К подряд стоя.щих единиц после нулей справа до перво го нуля в старшем разряде. Вычисляется число А i 2+2f-l, где Р::: К -1, И находится сумма А,М,где Ау,- предыдущее сочетание, тем .-самым определя ется очередное сочетание. Перебор про догакается до появления подряд единиц в левых (старших) разрядах. Рассмотрим на примере перебор сочетаний из 5 по 2. Число сочетаний будет. rN- /У М N(M-N) Исходное сочетание Avi ОРО11, здес , , следовательно, или в двоичной системе 00010. суммируя ис ходную комбинацию и А получаем очередную комбинацию 00101. uji-OOOOlAj ОО11О Дз 00011А4 01ОО1 &4 OOOO1Aj 01010 Д.5 00010At 01100 Лб-OOlOl AT 10001 Uk-, 00001 Ag 10010 Ae 00010 A9 10100 Aq 00100 A o-llOOO Такцм образом, п случены все десять сочетаний. Лля перебора всех сочетаний из М по М,где N изменяется от (М-1) до 1, на до взять исход ю комбинацию у которюй во всех разрядах записаны единицы. Воз мем N , т.е. А -11111, ЛЧОООО A,j 01111. Далее перебор ос.уществляется как в вышеописанном примере, т.е. перебор из 5 по 4. После окончания перебора из 5 по 4 получается комбинация 11110. Лля этой комбинации ik 01001 и новое сочетание 11110 О1ОО1 OOill. Далее осуществляется перебор из 5 по 3 и т. д. до пояучения комбянвпкк 1ОООО, Для нее Д 1ОООО.и следующее сочетание 1.ОООО+ +10ООО ООООО, т.е. наличие во всех разрядах нулей говорит о конце перебора всех сочетаний. Устройство я перебора сочетаний работает следующим образом.Г В исходном состоянии триггеры. 9 и 15находятся в нулевом состоянии,, в первом сумматоре записано исходное сочё-. тание, у которого h единиц записаны в ; младших, крайних правых разрядах. Так как триггеры 9 и 15 находятся в нулевом состоянии, то на выходе элемента И 16нулевой потенциал, следовательно, нулевой потенциал и на первых входах элементов И 18, на выходе элемента НЕ 17единичный потенциал, кото1Я 1Й приложен к первым входам элементов И 2 и 3. На выходе элемента НЕ 2О единичный потенциал, который подается на все вторые входы элементов И 21, От распределителя 1О импульсов последоватепы но подаются импульсы на третьи входы . элементов И 2, вторые входы которых подключены к нулевым выходам разрядов сумматора 1, где записано исходное со-., четанйе. Если в некоторых младших р взрядах, начиная с нулевого, последовательно было записано | нулей, то еданвцы (так как выходы инверсные) через элементы И 21, ИЛИ 4 перепишутся в соответствующие младшие разряды сумматоре 5. При нахождении первой единицы после L нулей в сумматоре 1 в соответствующий разряд суммато| 1а 5 запишетсяГнуль. Таким образом в сумматоре 5 будет записано число P...J что равно 2-1, Нулевой потешщЗп с выхода соответствующего элемента И 2 подается на вход элемента ИЛИ 6, на выходе которого будет нулевой потенциал, на выходе злемента НЕ 7 - единичный потенциал. Этот единичный импульс, воздействуя на единичный вход триггера 9, перевбдит его в единичное состояние, тем самым на первом входе элемента И 12 будет единичный потенциал и через элемент станут проходить тактовые импульсы от генера-. тора импульсов, которые запускают расщэеделитель 13 импульсов. Кроме того.

йа выходе элемента НЕ 20 будет нулевой потенциал, который подается на все вторые входы элемента И 21, Следокагопьио, информация с сумметора 1 не будет Подаваться через элементы И 21 на сумматор 5, Под воздействием импульсов вырабатььлаемь|Х распределителем Ю импульсов, будет продспжа1ъся опрос состояний разрядов сумматора 1, Начинается подсчет числа еДиниц после U нулей и вычисление Числа -Заметим, что . первая единица у нас использовалась для вычисления , следовательно, число подсчитываемых единиц будет уже на одну меньше, Так как используются инверсные выходы разрядов сумматора 1, то через элемент ИЛИ 6 последовательно вб времени пр помощи распределителя 13 импульсов и через элементы И 3, ИЛИ 4 состояния разрядов сумматора 1, взяTbte с инверсных выходов будут записы.ваться в сумматор 5, начиная с младшего разряда, тем самым в сумматоре 5 будет происходит суммирование. Допустим после L нулей шло К единиц, так как одна единица уже прсжушена, то к мслу, записанному в сумматор, будет прибавляться число 2; после К единиц в сумматоре 1 отыскивается первый нуль, инвертируется и в сумматор запи- сывается единица. Следовательно, в сумматоре 5 к числу () прибавляется чкспо это н есть ни что иное как 2 , Таким образом, в сумматоре 5 выполняется операция ( -1). При обнаружении первого нуля после К единиц этот инвертированный нуль (т, е. единица) через элемент ИЛИ 14 воздействует на единичный вход трнпера 15, Оба триггера 15 и 9 находятся в единичном состоянии. На выходе элемента И 16 поя единичный потенциал, который переводит через формирователь импульсов 19 распределители импульсов 10 и 13 и исходное состояние /закрывает элементы И 12 и 3 и открывает элемент И 18, Импульсы с распределителя 10 импульсов воздействуют на третьи входы элементов И 18 и тем самым информация из сумматора 5 подается последовательно, начиная с младшего разряда, на входы cyMMiaTOpa 1, в котором осушествляется сложение содержимого сумматора 5, т,е, величины Л с содержимым сумматора 1, т,е, с предыдущим сочетанием. Таким образом, в сумматоре 1 формируется очередное сочетание. При появлении импульса на последнем выходе распределителя 1О импульсов заканчивается процесс суммирования. Этот импульс переводит триггеры 9 и 15 в нулевое состояние и начинается новый цикл вычисления следующего сочетания. Сигналом о переборе все сочетаний является появление N единиц подряд в старших разрядах сумматора 1. Для перебора всех сочетаний из М по N где N меняется от М до 1 необходимо в сумматор- записать исходную комбинацию11и, Полный перебор заканчиваетя при появлении в сумматоре 1 всех нулей.

Данное устройство значительно проще, содержит меньше элементов по сравнению с прототипом, особенно при больших М и М. Меньшее количество элементов требуется уже при М 4 (под типовым элементом понимаем одну интегральную сборку: триггер, элемент И и элемент ИЛИ).

УСТРОЙрТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, содержащее первый распределитель импульсов, генератор тактовых импульсов, четыре группы элементов И, отличающееся тем, что, с целью упрощения, оно содержит два накапливающих сумматора, второй распределитель импульсов, два триггера, группу элементов ИЛИ, три элемента НЕ, три элемента И, два элемента ИЛИ, формирователь импульсов, причем выход генератора тактовых импульсов соединен с информационным входом первого распределителя импульсов и первыми входами первого и второго элементов И, выходы первого распределителя импульсов соединень соответственно с первыми входами элементов И первой и второй групп: вторые входы которых соединены соответственно с выходами разрядов первого и второго накапливающих сумматоров, входы разрядов которыхСоединены соответственно с выходами элементов И второй группы и элементов ИЛИ первой группы, первые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И третьей группы и соответствующими входами первого элемента ИЛИ, выход которого соединен с единичным входом первого триггера, нулевой вход которого соединен с последним выходом первого распределителя импульсов, выход первого триггера соединен с первым входом третьего элемента И, второй вход которого соединен с входом первого элемента НЕ, вторым входом второго элемента И и выходом второго триггера, нулевой и единичный входы которого соединены соответственно с последним выходом первого распределителя импульсов и выходом первого элемента И, второй вход которого соединен с выходом второго элемента НЕ, вход которого соединен с выходом второго элемента ИЛИ и первыми входами элементов И третьей группы, вторью входы которых соединены соответственно с вы-. ходами второго распределителя, вход которого соединен с выходом второго элемента И, входы сброса первого и второго распределителей импульсов соеПивеиы с выходом фс мирователя импульсов, вход которого соединен с выходом третьего элемента И, третьими входами элементов 00 И второй группы и входом третьего эле мента НЕ, выход которого соединен с «ч третьими входами элементов И первой и ел третьей групп, вторые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И четвертой группы первые входы которых соединены соответственно с выходами элементов И четвертой группы: первые входы которых соединены соответственно с выходами элементов И первой группы и соответствующими входами второго элемента ИЛИ вторые входы элементов И четвертой группы соединены с выходом первого элемента НЕ.