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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН аВ C 06 15/31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и

СР

Ю

Об

l 4

)475

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 3349976/18-24. (22 ) 02. 1 1.81 (46) 30.03 .83. Бюл. ¹ 1.2 (72) С. П. Присяжнюк, В. С. Михеенко, Л. С. Соколов и В. С. Таискин (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

No.634285, кл. G 06 F 15/32, 1975.

2. Авторское свидетельство СССР

No 525948, кл. G 06 F 7/00, 1973.

3. Авторское свидетельство СССР

N 374606, кл. G 06 F 15/32, 1970 (прототип ). (54) (57) УСТРОЙ).ТВО,ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, содержащее первый распределитель импульсов, генератор такто вых импульсов, четыре группы элементов

И-, о т л и ч а ю ш е е с я тем, что, с целью упрощения, оно содержит два накапливающих сумматора, второй распределитель импульсов, два триггера, группу элементов ИЛИ, три элемента НЕ, три элемента И, два элемента ИЛИ, формирователь импульсов, причем выход генератора тактовых импульсов соединен с информационным входом первого распределителя импульсов и первыми входами первого и второго элементов И, выходы первого распределителя импульсов соединены соответственно с первыми входами элементов

И первой и второй групп: вторые входы которых соединены соответственно с выходами разрядов первого и второго накапливающих сумматоров, входы разрядов которых соединены соответственно с выхода ми элементов И второй группы и элемен- . тов ИЛИ первой группы, первые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И третьей группы и соответствующими вхо„„ЯЦ„„1008750 дами первого элемента ИЛИ, выход которого соединен с единичным входом первого триггера, нулевой вход которого соединен с последним выходом первого распре делителя импульсов, выход первого триггера соединен с первым входом третьего элемента И, второй вход которого соединен с входом первого элемента НЕ, вторым входом второго элемента И и выходом второго триггера, нулевой и единичный входы которого соединены соответсз» венно с последним выходом первого распределителя импульсов и выходом первого элемента И, второй вход которого соединен с выходом второго элемента HE„ вход которого соединен с выходам второго элемента ИЛИ и первыми входами элементов И третьей группы, вторые входы которых соединены соответственно с вы-. .ходами второго распределителя, вход которого соединен с выходом второго элемента И, входы сброса первого и второго распределителей импульсов соединены с выходом формирователя импульсов, вход которого соединен с выходом третьего элемента И, третьими BxbllBMH элементов

И второй группы и входом третьего эле мента НЕ, выход которого соединен с третьими входами элементов И первой и третьей групп, вторые входы элементов

ИЛИ первой группы соединены соответственно с выходами элементов И четвертой группы первые входы которых соединены соответственно с выходами элементов И четвертой группы: первые входы которых соединены соответственно с выходами элементов И первой группы и соответствуюшими входами второго элемента ИЛИ вторые входы элементов И четвертой группы соединены с выходом первого элемента HE.

780 2 пульсов, генератор тактовых импульсов, четыре группы элементов И, содержит два накапливакяцих сумматора, второй рас пределитель импульсов, два триггера, группу элементов ИЛИ, три элемента НЕ, три элемента И, два элемента ИЛИ, формирователь импульсов, причем выход генератора тактовых импульсов соединен с информационным входом первого распределителя импульсов и первыми входами первого и второго элементов И, выходы первого распределителя импульсов соединены соответственно с первыми входами элементов И первой и второй групп, вторые входы которых соединены соответственно с выходами разрядов первого и второго накапливающих сумматоров, входы разрядов которых соединены соответственно с выходами элементов И второй группы и элементов ИЛИ первой группы, первые входы элементов ИЛИ первой груп пы соединены соответственно с выходами элементов И третьей группы и соответствукицими входами первого элементов ИЛИ, выход которого соединен с единичным входом первого, триггера, нулевой вход кото рого соединен с последним выходом первого распределителя импульсов, выход первого триггера соединен с первым входом третьего элемента И, второй ахоа которого соединен с входом первого элемента НЕ, вторым входом второго элемента И и выходом второго триггера, нулевой и единичный входы которого coei динены соответственно с последним,выхо1 дом первого распределителя импульсов и выходом первого элемента И, второй вход которого соединен с выходом второго элемента НЕ, вход которого соединен с выходом второго элемента ИЛИ и первыми входами элементов И третьей группы, вторые входы которых соединены соответственно с выходами второго распределителя, вход которого соединен с выходом второго элемента И, входы сброса первого и второ о распределителей импульсов соединены с выходом формирователя им пульсов, вход которой соединен с выходом третьего элемента И, третьими входами элементов И второй группы и входом третьего элемента НЕ, выход которого соединен с третьими входами элементов И первой и третьей группы, вторые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И четвертой группы, первые входы которых соединены соответственно с выходами элементов И первой группы и соответствукщими входами второго эле1 1008

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

Известно устройство для перебора сочетаний, содержащее регистры сдвига, распределитель импульсов, дешифратор, триггер, элементы И, элементы задержки, 1ц счетчик 1).

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

Известно устройство для перебора со- l5 четаний, содержашее распределитель им- . пульсов, генератор тактовых импульсов блок .памяти, два блока перестановок, триггер, элементы И, элементы задержки г).

Недостатком данного устройства является сложность.

Наиболее близким к предлагаемому является устройство для перебора сочетаной, содержащее распределитель импульсов. 5 генератор тактовых импульсов, И счетчиков, (n-1) группу элементов И, (й+2) элемента ИЛИ, И элементов запрета 2(И-1) элементов задержки, причем выход переноса 1 -ro счетчика, кроме последнего, через . i -й элемент запрета и первый (1+1)-й элемент ИЛИ соединены с входом (1+1)-го счетчика, а также с соответствуюшим входом распределителя импульсов и через второй < -й элемент ИЛИ и первый -й элемент задержки с первыми входами элементов И i -й группы, вторые входы которых соединены соответственно с выходами 1 -ro счетчика, а выходы — с входами (i+1)-го счетчика, выход первого 1-го элемента задержки через второй 1-й элемент задержки и первый 1 -й элемент ИЛИ соединены с входом 1-го счетчика, а через второй (i-1)-й элемент ИЛИ вЂ” входом перво45

ro (-1)-го элемента задержки, выход переноса последнего счетчика соединен с входом установки распределителя импульсов, вход первого счетчика через первый элемент запрета и первый элемент

ИЛИ подклЬчен к выходу генератора тактовых импул.ьсов (1=1-И) (3 j.

Недостатком данного устройства является его сложность при больших М и М

Цель изобретения — упрощение устройства для перебора сочетаний.

Поставленная цель достигается тем, что устройство для перебора сочетаний, содержащее первый распределитель им750 .4

3 1008 мента ИЛИ, втррые входы элементов И четвертой группы соединены с выходом первого элемента HE.

На чертеже представлена схема устройства для перебора сочетаний.

Устройство для перебора сочетаний со держит сумматор 1, группу элементов И

2, группу элементов И 3, группу элементов ИЛИ 4, сумматор 5, элемент ИЛИ 6, элемент HE 7, элемент И 8, триггер 9, 10 распределитель 10 импульсов(генератор

11 тактовых импульсов, элемент И 12, распределитель 13 импульсов, элемент

ИЛИ 14, триггер 15, элемент И 16, элемент НЕ 17, группу элементов И 18, 1$ формирователь импульсов 19, элемент

НЕ 20 и элементы И 21.

Перебор сочетаний иэ М по Ч производится следующим образом.

Исходным сочетанием является со 20 четание,в котором N единиц записано в правых (младших) разрядах, Йпя получения -очередного сочетания подсчитывается число L подряд стоящих нулей в младших разрядах, начиная с нулевого до 2$ первой единиць1 и число .k подряд стоя-щих единиц после нулей справа до первого нуля в ста шеу разряде, Вычисляется число = 2 +2 -1, где р-„K 1, и находится сумма P>ph где Д,„- преды - З0 дущее сочетание, тем . самым определяется очередное -сочетание. Перебор про— допжается до появления подряд единиц -в левых (старших) разрядах.

Рассмотрим на примере перебор сочетаний из "5 по «2". Число сочетаний будет

С см Р(ЙиТ "«

Исходное сочетание А и 00011,здесь

Ь О, К=2, следовательно, Ь = 2 или в двоичной системе 00010". суммируя ис- . ходную комбинацию и получаем очередную комбинацию "00101 .

Д =ОООО1 Д = ОО110

Д =ООО11 A4 = 01001

4$

b4 = 00001 А = 01010, &5"- 00010 А6 = 01100

h,6= 00101 Д = 10001

Д = ОООО1 Ая = 10010

Ьй= 00010 Аф = 10100

Qq= 00100 А1 = 11000

Таким образом, научены все десять очетаний.

Для перебора всех- сочетаний из М по М,где Й изменяется or (М-1) до 1, на$$ до взять исходную комбинацию у которой во всех разрядах записаны единицы. Возьмем М= М=5, т.е. A„=11111, 6 «10000

Д =01.111. Йалее перебор осуществляется как в вышеописанном примере, т.е. перебор из "5 по,"4 . После окончания

I перебора иэ 5 по 4 получается комбинация "11110 . Лля этой комбинации

Ь =01001 и новое сочетание 11110 +

01001 = 003.11. Далее осуществляется перебор из 5 по 3 и т. д. до поаучения комбинации 10000 . Зля нее Ь

=10000.и следующее сочетание 10000+

+10000=00000, т.е. наличие во всех разрядах нулей. говорит о конце перебора всех сочетаний.

Устройство пля перебора сочетаний ра-! ботает следукяпим образом.

В исходном состоянии триггеры .9 и

15 находятся в нулевом состоянии,. в пер- вом сумматоре записано исходное соче». тание, у которого Я единиц записаны в младших, крайних правых разрядах. Так как триггеры 9 и 15 находятся в нулевом состоянии, то на выходе элемента И

16 нулевой потенциал, следовательно, нулевой потенциал и на первых входах элементов И 18, на выходе элемента HE

17 единичный потенциал, который приложен к первым. входам элементов И 2 и

3. На выходе элемента HE 20 единичный потенциал, который подается на все вторые входы элементов И 21, От распределителя 10 импульсов последователь. но подаются импульсы на третьи входы, элементов И 2, .вторые входы которых

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

5, При нахождении первой единицы после нулей в сумматоре 1 в соответствующий разряд сумматора S запишется нуль..

Таким образом в сумматоре 5 будет записано число 4. 4 что равно 2 -1 °

Нулевой потенци с выхода соответствующего элемента И 2 подается на вход элемента ИЛИ 6, на выходе которого бу» дет нулевой потенциал, на выходе эле. мента НЕ 7 - единичный потенциал. Этот единичный импульс, воздействуя на единичный вход триггера 9, переводит его в единичное состояние, тем самым на первом входе элемента И 12 будет единичный потенциал и через элемент станут проходить тактовые импульсы от генера-. тора импульсов, которые запускают распределитель 13 импульсов. Кроме того, 5 1008 на выходе элемента HE 20 будет нулевой потенциал, который подается на все вторые входы элемента И 21. Следовательно, информация с сумматора 1 не будет подаваться через элементы И 21 иа сумматор 5, Под воздействием импульсов вырабаты.аемых распределителем 10 им- пульсов, будет нродопжаться опрос состо-яний разрядов сумматора 1, Начинается подсчет числа единиц после Ь нулей и вычисление числа 2 =..2." - Заметим, что к- . nepsas единица у нас использовалась для вычисления. 2 -1, следовательно, число

4 подсчнтываемых единиц будет уже на одну меньше, Так как используются инверс- >> ные выходы разрядов сумматора 1, то через элемент ИЛИ 6 последовательно во времени прч помощи распределителя 13 . импульсов и через элементы И 3, ИЛИ

4 ссстояния разрядов сумматора 1, взя- 20 тые с инверсных. выходов будут записываться в сумматор 5, начиная с младшего разряда, тем самым в сумматоре 5 будет происходит суммирование. Qonycтим после 1 нулей шло К единиц, так 2$ как одна единица уже пропущена, то к числу, записанному в сумматор, будет прибавляться число „, после К еди00 "0 ниц в сумматоре 1 отыскивается первый нуль, ннвертируется и в сумматор запи- Зп сывается единица. Следовательно, в сумматоре 5 к числу (2 -1 ) прибавляется

4 число Р,а это и есть ни что иное как

100.. о

2(, Таким образом, в счмматоре 5 выполняется операция (2"+2 -1). При об- наружении первого нуля после К единиц этот инвертированный нуль (т. е. единица) через элемент ИЛИ 14 воздействует на единичный вход тригтера 15. Оба триг.

750 d .гера 15 и 9 находятся в единичном сос стоянии. На выходе элемента И 16 поя:— вится единичный потенциал, который переводит через формирователь импульсов 19 распределители импульсов 10 и 13 в исходное состояние((закрывает элементы И

j2 и 3 и открывает элемент И 18. Импульсы с распределителя 10 импульсов воздействуют на третьи входы элементов

И 18 и тем самым информация иэ сумматора 5 подается последовательно, начиная с младшего разряда, на входы сумматора 1, в котором осуществляется сложение содержимого сумматора 5, т.е. величины Ь с содержимым сумматора 1, т.е, с предыдущим сочетанием. Таким образом, в сумматоре 1 формируется очередное сочетание. При появлении импульса на последнем выходе распределителя

10 импульсов заканчивается процесс суммирования. Этот импульс переводит триг геры 9 и 1 5 и нулевое состояние и начинается новый цикл вычисления следующего сочетания. Сигналом о переборе всех сочетаний является появление N единиц подряд в старших разрядах сумматора 1.

Лля перебора всех сочетаний из M no где Й меняется от N до 1 необходимо в сумматор. записать исходную комбинацию -" -. Полный перебор эаканчиваетя

М м при появлении в сумматоре 1 всех нулей.

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

Составитель А. Клюев

Редактор Е. Папп Техред M. Tenep

Корректор О. Билак

Филиал ППП Патент, г, Ужгород, ул. Проектная, 4

Заказ 2340/60 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений,и открытий

113035, Москва, Ж-35, Раушская наб., д, 4/5