Устройство для перебора сочетаний, размещений и перестановок

и 643883 Оиоа Советских Соцналнстнческнх РеспубликЗаявлено 10,0 нием э с присоедин (23) Прнорит ретвеией ввиатет СССР диан иМрвтеаб н еткрнтнй. И. Левин инский филиал Всесоюзного научно-исследов проектно-конструкторского института"пб ав редприятий промьииленности ст оительных материалов(71) Заявите стРойство для пе евою сочетлний,РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК в, элементы каочатепь, комвыходной реще Изобретение относится к области вы- иератор тактовых импульсочислительной техники и может быть ис-И, ИЛИ, триггеры, перепользовано в вычислительных устройст- мутатор, блок управления.вж и машинах, предназначенных для ре- гистр 2 .шения задаМ, основанных на переборе Недостатком извесгного устройствасочетаний, размещений и перестановок. 5 является его сложность. Наличие двухОдно нз известных устройств содер элементов задержки (одного на входежит последовательно соединенные коль сброса блоков перебора, другого на ув-яевые счетчики, узел блокировки, триг- равляющем входе распределителя) сугер, элементы ИЛИ и элементы задерж- щественно уменьшает быстродействие.ки 1 . 16 устройства,Наличие в устройстве большого коли- Целью изобретения является повычества кольцевых счетчиков, ведет к шение быстродействия я упро няе .устусложнению устройства, а использование ройства.элементов задержки снижает его быст- Поставленная пель достигается тем,род ействие. что неустройство, для перебора сочетаний, размещений и перестановок введеНаиболее, близким техническим решь- . ны блок формирователей и блок деления,нием к данному изобретению является причем пусковая шина устройсаа совустройство для перебора сочетаний, раз- динена спервым входом первбго. триьмещений и перестановок, содержашее за О гера, второй мод которого подключен кпоминакицуто матрнпу, упратципошие входы первому выходу реверсивного регистракоторой соединены с соответствувщими вы- сдвига, выход первого триггера подклзо.ходами реверсивного регистра сдвига ге- чен к первым модам элемента ИЛИ, второго триггера и первого элемента И,второй вход которого подключен к первому выходу Генератора импульсов, выход первбго элемента И подключен кпрямому входу рэтщстра сдвига, второй 5выход генератора импульсов подключенк первому входу второго элемента И, второй вход которого подключен к выходумФоготриггера и второму входу элемента ИДИ, выход которого подключен . Око входу генератора импульсов, третьивходы первого и второго триггеров через переключатель соединены с соответствующими входамя регистра сдвига, выход второго элемента И соединен с инверсным входом регистра сдвига, выходы зайоминакепей матрицы через последовательно соединенные блок формирователей, коммутатор и блок деления подключены к выходному регистру, выходыблока управленйя. соединены с упрквлякищими входами блока деления и коммутатора.Такое устройство не содержит элементов задержки, что позволяет осу-.25ществлять перебор сочетаний, размещений и лерестаноВок с щаышенным быстродействием. Кроме того, устройствохарактеризуется "простотой конструкт.Схема предлагаемого устройства пред-36ставлена на чертеже. Оно содержит запомиьакапую матриау 1 регистр сдвига2, элементы И 3 и 4,.триггеры 5 и 6,генератор тактовых импульсов 7; элемент ИЛИ 8, блок формирователей 9, вкоторых Формируются коды элементтовФ, вйходной регистр 10, переключатель 11, коммутатор 12, блок деления 13, блок управления 14. Вход триггера 5 соединен с пусковой шиной уст Оройства 18.Количество горизонтальных щин, аследовательно и количестворазрядов регистра сдвига равно . а ,. гдеи.е число элементови членах пьследоввтельности.Для перебора перестановок (такквк % в И ) все контакты коммутатора2 замкнуты,Для перебора размещений А исочетаний С, размыкаются 1- с .лконтактов коммутатора 3.2, начиная справоГь разряда,Соединении горизонтальных и вертикальных шин запоминающей матрицы,Х в узлах выполнены тМим образом,. что каадая последовательность комбивьторныхчленов высшего порядка випочает в себя последовательность низшегопорядка. Горизонтальные шины заломи"павшей матрицы 1 подюпочены к соот ветствуюшнм разрядам регис"тра сдвига2, а вертикальные шины - к входамблока формирователей 9. С выходов М 1разрядов реверсивного распределителя 2сделаны отводы, подключаемые черезпереключатель 11 (с помощью которогоустанавливается длина последовательности) к входам триггеров 5 и 6.Работает устройство следующим образом. В зависимости от типа решаемойзадачи, то есть перебора перестановок,размещений или сочетаний, в. блок деле ния 13 заносится соответственно одно из чисел 1" ( И-К ) или "%(И-с И, .В зависимости от размерности генери руемой устройством поспедовательности переключатель 11 устанавливается В положение В /2, а в коммутаторе 3.2 командой с блока управления 14 оФклвр чаютса разряды с номерами больше % При подаче пускового сигнала на шину 15 перебрасывается триггер Б, сигнал с его выхода подается на вход элемента И 3 и черезсхему ИЛИ 8 занускает генератор импульсов 7, импульсы йотюро го через элемент И 3 подавая на нрФмой вход регистра сдвига 2, вызываятем самым поочередное срабатывайиэ его разрядов- и появление на горизоатальных шинахзапоминающей матрицы 1 сигналов, которые йостунвют через соединения в узлах матрийы 1 и ее вер-.тикальные шины на соей ветствуюшие формирователи , блока Формирователей 9,.При срабатьщаний первого йбряда Ррегистра сдвига 2 сигнал с выхода этого разряда подтверждает сос тояние триггера 5, Одновременно этот же сигнап через первую вертикальиув шину запоминающей матрицы 1 посту пит на формирователь М блока фор- мирователей 9 и через коммутатор 12, соответствуюший элементу 43,4, ва подается в блок деления 13. Так как в режиме генерирования перестановок в блоке деления 13 записана Х, то код апроходит на вход выходного ре гистрв 10.При переключении второго, а затем третьего разрядов регистрами(щмпз 2 у аналогичным образом на вход вйходиого регистра 10 поступают зады элементе О иР 5Поскольку на чертеже показаны замкнутыми только те контакты коммутатора 12, которые соответствуют формирователям:Ю, О 0, то на выходном. регистре 10 за девать тактов переключения распределителя 2 зафиксируютсачлены О 4 д О 1 фа О 1 фью ОЙДОЭфвПри срабатывании девятого разрядерегистра сдвига 2 сигнал через переклю-чатель 11 перебросит триггер 5 в исходное состояние, снимая тем самымразрешаюший сигнал с элемента И 3 ипрекращая подачу импульсов на прямойвход регистра сдвига 2,Одновременно сигнал с переключателя 1511 перебросит триггер 6, с выхода которого. поступит разрешающий сигнал наэлемент И 4, и через элемент ИЛИ 8,подтвердится запуск генератора импульсов 7, Следовательно, импульсы с вы Охода генератора 7 через элемент И 4начнут посгупать на реверсивный эходрегистра сдвига 2. Переключение разрядов регистра сдвига 2 осушествлаетсапри этом в обратном порядке и согласно информации, записанной в матрице 1,на выходном регистре зафиксируютсячлены О И Ор фэ А о 2с ъ С а ф 4При срабатывании,первого р разряда регистра сдвига 2 триггер 5 перебрасывается в исходное состоанйе, перебрасывая своим выходом триггер 6.В резущлате чего снимаетсяразрешающий сигнал с элемента И 4 и нрекрвшаетса поступление импульсов с выходагенератора 7 на реверсивный вход регистра сдвига 2.Таким образом, на выходной регистрбудет выдана последовательность иэшести членов, авлаюшааса перестановкой 4 втрех элементов С 3, Оа, иАналэгйчно устройство работаетпри Й 3.В рекиме генерирования размешенийв блок делении 13 заносится число"( -Ж М.Работа устройства в этом режимеосушествляется аналогично вышеописан. ному. Однако на выходной регистр поступают не все и . членов генерируе-. 50мойпеествки", а только , такИкак А", - здесь испольэуетв-В)ся иэвест зависимость, то есть чисмло размещений А ф равно числупеРествновок, деленное на (и - )и 55В этом режиме работы устройствапропускбютса члены перестановки, невходяцае в данное рвзмешение. В режиме генерирования сочетанийв блок деления 13 заносится число1 ()"и по аналогии с режимомгенерирования размещений на выходной регистр выводятся не все И членов перестановок а толькото естьИии ф кчисло сочетаний иэ И элементов по кСп,Ф о р м у л а и з о б р е те н и яУстройство для перебора сочетаний,размещений и перестановок, содержащеезапоминаюшую матрицу, управляющиевходы которой соединены с союИетствуюшими выходами реверсивного регистра сдвига, генератор тактовых импульсов,элементы И, ИЛ, триггеры, переключатель, коммутатор, блок управления, выходной регистр, о т л и ч в ю ш е ес а тем, что, с целью повышения быстродействия и упрощении устройстваоно содержит блок формирователей, блокделения, причем пусковая 1 цина устройства соединена с первымвходом первоготриггера, второй вход которого подццочем к первому выходу реверсивного регистра сдвига, выход первого триггераподключен к первым входам элементаИЛИ, второго триггера и первого элемента И, второй вход которого подключен к первому выходу генератореимпульсов, выход первого элемента Иподключен к прямому входу регистрасдвига, второй выход генератора импульсов подключен к первому входу второго элеменга И, второй вход которогоподключен к выходу второго триггераи второму входу элемента ИЛИ, выходкоторого нодключен ко входу генератора импульсов, третьи входы первогои второго триггеров через переключвтель соединены с соответстувуюшимивходами регистра сдвига, выход второго элемента И соединен с инверсщлмвходом регистра сдвига, выходы запоминающей матрицы через последова-тельно соединенные блок формирователей, коммутатор и блок деления подключены к выходному региструвы-.ходы блока управления соединены суправшпащими входами блока деленияи коммутатора,Источники информации, принятые в 6внимание при экспертизе;1. Авторское свидетельство СССРХо 525100, кл. Я 06 Е 15/3225.12.74.2. Авторское свидетельство СССРЖ 525948, кл. б 06 Ф 7/ОО,03,09.73.643883 Составитель И, Нирман вили Текред Э, Чужик КорРед Д. Ме 02 3 ак илиал ППП "Патентф, г. Ужгород, ул. Проекта 7 ТЭ енногоретенийЖ,Ги ражКПИ Государст по делам изоб 038, Москва,Подписноеомнтета СССРи открытийаушская наб., д