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

ик,ский адиотех алмыков видетельство СССРР 15/20, 1978.идетельство СССРР 15/20, 1980.детельство СССРР 15/20, 1977(54 ЧЕТ сод бло тв ОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ДЕЛАМ. ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ВТОРСНОМУ СВИДЕТЕЛЬСТВ)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОАНИЙ, РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК,ержащее первую группу регистров,к управления, генератор тактовых импульсов, переключатель, коммутатор, выходнои регистр, элемент ИЛИ, причем группа информапионных входов коммутатора соединена с выходами регистров первой группы, выход выходно го регистра является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения количес а оборудования, оно содержитвторую группу регистров, две группы:элементов И, две группы элементов ИЛИгруппу элементов сравнения, счетчик,дешифратор, делитель, три элементазадержки, причем блок управления содержит группу регистров сдвига, группу триггеров, группу элементов И,группу элементов ИЛИ, группу элементов запрета, элемент ИЛИ, причемуправляющие входы коммутатора соединены соответственно с выходом первого регистра сдвига, выходами элементов запрета группы, выходом предпоследнего регистра сдвига блока управления и выходом первого элемента,задержки, вход которого соединен с выходом делителя, входами размещения приема регистров первой группы и входом первого регистра сдвига блбка управления, первые входы элементов ИЛИ группы которого соединены с первым входом элемента ИЛИ, входом установки последнего регистра сдвига блока управления и входом начальной установки устройства, который соединен с входом установки счетчика, тактовый вход которого соединен свходом делителя и выходом генератора тактовых импульсов, управляющие входы коммутатора, начиная с второго, соединены соответственно с группой входов переключателя, группа выходов Я которого соединена с соответствующими входами элементов ИЛИ первой груп-: пы, выходы которых соединены с первыми входами элементов И первой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, а выходы являются выходами сочетаний устройства, входы 1 с-го элемента ИЛИ второй группы соединены соответственно с Ос)-м выходом первой группы, к-м выходом второй группы, В+1)-м выходом третьей группы коммутатора и 1-м входом. р, устройства, (где 1 с=1, , и, и - количество элементов перебора), выходы элементов ИЛИ второй группы соединены с входами. соответствующих регистров второй группы, выходы которых соединены с информационными входами соответствующих регистров пер 1 вой группы, первыми входами соответ,ствующих элементов сравнения группы и первыми входами соответствующих элементов И второй группы, выходы которых соединены с соответствующими входами элемента ИЛИ, выход которого соединен с входом выходного регистра, выход счетчика соединен. с входом дешифратора, выходы которого соединены с вторыми входами соответствующих элементов второй группы, выходы перестановок устройства соединены с выходами элементов сравнения группы, вторые входы которых соединены с выходом счетчика, выход первого элемента задержки соединен с входом второго элемента задержки, выход которого соединен с входом третьего элемента задержкии первьйи входами элементов И группы блока управления, выход третьего элемента задержки соединен с вторым входом 124319элемента ИЛИ блока управления, причем в блоке управления выход элемен та ИЛИ соединен с. нулевыми входами триггеров группы, выходы которых соединены с вторыми входами соответ.ствующнх элементов И группы, выходы которых соединены с вторики входами соответствующих элементов ИЛИ группы, выходы которых соединены с установочными входами соответствующих соединенных последовательно регистров сдвига группы единичными входами соответствующих триггеров груп пы и информационными входами соответствующих элементов запрета группыуправляющие входы которых соединены соответственно с выходами всех регистров сдвига с большими номерами , кроме последнего , выход которого соединен с выходом окончания, генерирования устройстваИзобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, преФ назначенных для решения задач автоматизированного конструирования радио 5 .электронной и вычислительной аппара"., туры.Известно устройство для перебора перестановок, содержащее в каждом разряде регистр, счетчик, элемент И%1, четыре элемента И, элемент задержки и один вспомогательный регистр на все устройство и .Однако это устройство характеризуется низким быстродействием. Кроме того, оно не позволяет получать размещения и сочетания.Известно устройство для перебора . перестановок, содержащее первую и вторую группы циклически соединенных регистров, первую группу элемен" тов И, через которые каждый регистр первой группы соединен с соответствующим регистром второй группы, элемент запрета, группу элементов запрета, группу элементов ИЛИ и вторую группу элементов И, через которые осуществляется связь между регистрами первой группы по длинным либо короткимциклам, последовательно соединенные,счетчики, дешифратор, соединенный свыходами первого счетчика, элементы И, соединенные с выходами дешифратора и с выходами последующихсчетчиков, элементы.ИЛИ, соединенныес одним из выходов дешифратора и выходами упомянутых элементов И, третьюгруппу элементов И, каждый из которыхвходами соединен с выходами генера,тора тактовых импульсов и с выходом1соответствующего элемента ИЛИ, авыходом - с входом соответствующегорегистра первой группы 2 .Недостатками известного устройства являются низкая функциональнаянадежность и невозможность получениясочетаний и размещений,Наиболее близким к предлагаемому:по технической сущности являетсяустройство для перебора сочетаний,размещений и перестановок, содержащее запоминающую матрицу, регистрсдвига, два элемента И, два тригге11243 50 55 ра, генератор тактовых импульсов, элемент ИЛИ, блок регистров, выходной регистр, переключатель, коммутатор, блок деления и блок управления, причем горизонтальные шины запоминающей матрицы соединены с выходами регистра сдвига, а ее вертикальные шины через последовательно соединенные блок регистров, коммутатор и блок деления подключены к выходно О му регистру, выходы блока управления соединены с управляющими входами блока деления и коммутатора, вход запуска устройства соединен с первым входом первого триггера, второй вход которого подключен к первому выходу регистра сдвига, выход первого триггера подключен к первым входам второго триггера, элемента ИЛИ и первого элемента И, второй вход которого подклю чен к первому выходу генератора импульсов, выход .первого элемента И подключен к прямому входу регистра сдвига, второй выход генератора импульсов подключен к первому входу р 5 второго элемента И, второй вход которого подключен к выходу второго триг- . гера и второму входу элемента ИЛИ, выход которого подключен к входу генератора импульсов, третьи входы первого и второго триггеров через переключатель соединены с соответствующими входами регистра сдвига, выход второго элемента И соединен с инверсным входом регистра сдвига Я .Недостатком этого устройства явля 35 ется сложность его реализации, а при числе элементов, участвующих в перестановках, больше шести оно оказывается практически нереализуемым.40 Это вызвано тем, что число разрядов регистра сдвига и соответственно число горизонтальных шин запоминаюпп 1 щей матрицЫ представляют величину в ,45 где п - число элементов в перестановках. Цель изобретения - сокращение количества оборудования.Поставленная цель достигается тем, что устройство для перебора сочетаний, размещений и перестановок, содержащее первую группу регистров, блок управления, генератор тактовых импульсов, переключатель, коммутатор, выходной регистр, элемент ИЛИ, причем группа информационных входов коммутатора соединена с выходами ре 19гистров первой группы, выход выходного регистра является выходом устройства, включает в себя вторую группу регистров,. две группы элементов И,две группы элементов ИЛИ, группуэлементов сравнения, счетчик, дешифратор, делитель, три элементазадержки, причем блок управлениясодержит группу регистров сдвига,группу триггеров, группу элементовИ, группу элементов ИЛИ, группу элементов запрета и элемент ИЛИ, причемуправляющие входы коммутатора соединены. соответственно с выходом пер вого регистра сдвига, выходами эле,ментов запрета группы, выходом пред-.последнего регистра сдвига блокауправления и выходом первого элемента задержки, вход которого соединен с выходом делителя, входами размещения приема регистров первой группы и входом первого регистра сдвига блокауправления, первые входы элементовИЛИ группы которого соединены спервым входом элемента ИЛИ, входомустановки последнего регистра сдвигаблока управления и входом начальнойустановки устройства, который соединен с входом установки счетчика, тактовый вход которого соединен с входом делителя и выходом генераторатактовых импульсов, управляющие входы коммутатора, начиная с второго,соединены соответственно с группойвходов переключателя, группа входовкоторого соединена. с соответствующими входами элементов ИЛИ первой группы, выходы которых соединены с первыми входами элементов И первойгруппы, вторые входы которых соединены с выходами соответствующихрегистров первой группы, а выходыявляются выходами сочетаний устройства, входы 1-го элемента ИЛИ второйгруппы соединены соответственно с Ь)-м выходом первой группы, К-м выходом второй группы, Ь+1)-м выхо.дом третьей группы коммутатора и 1 с-м входом устройства (где 1 с=1,и, п - количество элементов перебора), выходы элементов ИЛИ второй группы соединены с входами соответст вующих регистров второй группы, выходы которых соединены с информацион ными входами соответствующих регистров первой группы, первыми входами соответствующих элементов сравнения группы и первыми входами соответст 1124319вующих элементов И второй группы,выходы которых соединены с соответствующими входами элемента ИЛИ, выходкоторого соединен с входом выходногорегистра, выход счетчика соединен с 5входом дешифратора, выходы которогосоединены с вторыми входами соответствующих элементов И второй группы, выходы перестановок устройствасоединены с выходами элементов сравнения группы, вторые входы которыхсоединены с выходом счетчика, выходпервого элемента задержки соединенс входом второго элемента задержки,выход которого соединен с входомтретьего элемента задержки и пер, вымивходами элементов И группы блока управления, выход третьего элемента задержки соединен с вторымвходом элемента ИЛИ блока управлений, 20причем в блоке управления выход эле-,мента ИЛИ соединен с нулевыми входами триггеров группы, выходы которыхсоединены с вторыми входами соответствующих элементов И группы, выходыкоторых соединены с вторыми входамисоответствующих элементов ИЛИ группы, выходы которых соединены с установочными входами соответствующихпоследовательно соединеннЫх регист- З 0ров сдвига группы, единичными входами соответствующих триггеров группыи информационными входами соответствующих элементов запрета группы, ук- .равляющие входы которых соединены З 5соответственно с выходами всех регистров сдвига с большими номерами, кроме последнего, выход которого соединен .с выходом окончания генерирования устройства. 40На фиг. 1 приведена структурнаясхема предлагаемого устройства дляперебора сочетаний, размещений и пе"рестановок для случая пяти переставляемых.элементов; на фиг, 2 - струк Ф 5турная схема блока управления,Устройство для перебора сочетаний, размещений н перестановок содержит первую группу 11-15 регистров, комму" татор 2, состоящий из групп 31"3 элементов И и групп 41-4 элементов ИЛИ, блок 5 управления, блок 6переключателей, первую группу 71 -7 элементов ИЛИ, первую группу 81-84 элементов И, вторую группу 91-9 д элементов ИЛИ с входами 101-105, вторую группу 111 -115 регистров, вторую группу 121-125 элементов И, групп,13-13 у элементов сравнения с выходами 14 -14 , счетчик 15, дешифратор 16, элемент ИЛИ 17, выходной регистр 18, генератор 19 тактовых импульсов, делитель 20, элементы 21, 22 и 23 задержки, вход 24 установки исходного состояния, выход 25 окончания генерирования.Блок 5 управления содержит последовательно соединенные регистры 261 264 сдвига, триггеры 271-27, элементы 281-28 запрета, элементы И 291-29, элементы ИЛИ 301-30 и ИЛИ 31, причем число разрядов в ре" гистре 261 сдвига равно двум, а в каждом последующем на единицу больше, чем в предыдущем. (входы и выходы блока 5 управления на фиг. 2 расположены в строгом соответствии с их расположением на фиг. 1)Устройство для перебора сочетаний, размещений и перестановок может работать в трех режимах: генерирование перестановок генерирование раз" мещений и генерирование сочетаний.Для генерирования перестановок по входам 10 в регистре 11 записываются исходные элементы, например. числа 1, 2, 3, 4, 5, причем запись этих чисел в регистре 1 может производиться в.любом порядке. Для удобства будем считать, что эти числа записаны в возрастающем порядке, начиная с верхнего регистра 11. На вход 24 подается сигнал установки висходное состояние блока 5 и счетчика 15.Ъ Первый тактовый импульс с выходаделителя 20 производит перепись элементов, т.е. чисел 1, 2, 3, 4 и 5,из регистров 11 в соответствующие регистры 1 и одновременно устанавливает единицу на первом выходе блока 5, Благодаря этому задержанный элементом 21 первый тактовый импульс, поступая на входы всех групп 31 -3 элементов И коммутатора 2, переписывает числа из регистра 11 в регистр 11 , из регистра 1 в регистр 111, из регистра 1 в регистр 11, из регистра 11,.в регистр 111 и из регистра 15 в регистр 11 у. Задержанный элементами 22 и 23 первый тактовый импульс, поступая на.второй и третий входы блоков 5никаких изменений ке производит.Тактовые импульсы с генератора 19 тактовых импульсов, частота которых в и раз выше, чем с выхода делителя 20 (и - число элементов в перестановках), поступая на счетчик 15,суммируются. Так как выходы счетчика 15 соединены со всеми элементами13 сравнения, то при поступлениикаждого тактового импульса на этотсчетчик, в одном из элементов 13сравнения проис;.эдит сравнение кодовсчетчика 15 и соответствующего регистра 11. На выходе 14 той схемы13 сравнения, где произошло сравнение, появляется сигнал. Кроме того,производится перепись содержимогосоответствующего регистра 11 через 5элементы И 12 и ИЛИ 17 на выходнойрегистр 18.После этого ка выходе делителя 20появляется второй импульс, которыйпереписывает числа из регистров 114 в 2011 в регистры 11-15 соответственно,Этот же импульс проходит на выход .регистра 261 блока 5 и появляется навтором его выходе, переводит в единичное состояние триггер 274 и чоступает с выхода регистра 261 на входрегистра 262.В соответствии с этим задержанныйвторой импульс с выхода элемента 21переписывает числа 2, 3, 1, 4, 5 изрегистров 1 -15 в регистр 111-115соответственно. Этот же импульс,пройдя через элемент 22 задержки,поступает на второй вход блока 5и через открытый элемент И 291 и элемент ИЛИ 304 сбрасывает регистр 261в исходное состояние, а пройдя черезэлемент 23 задержки, поступает натретий вход блока 5 и через элементИЛИ 31 устанавливает в исходноегсостояние триггер 271,, Далее, аналогичным образом по тактовым импульсам генератора 19 нач 11 нается сравнение чисел в элементах 13 -13 сравнения и сигнал пос 45 ледовательно появляется на выходах 14, 14 14, 14 и 14. Одновременно по сигналам с дешифратора 16 переписываются числа 2, 3, 1, 4, 5 из регистров 111 -115 в регистр 18. Таким образом, параллельная форма представления перестановок в регистрах 11 - 11 преобразуется в последовательную форму в регистре 18 и пространственно-временную форму последовательности появления сигналов на выходах 141- 145 элементов 13 -13 срав 5 нения.. После перебора всех 120 перестановок на выходе 25 регистра 26 появляется сигнал, который является сигналом окончания работы в режиме генерирования перестановок.При генерировании размещений работа не отличается от режима генерирования перестановок. Различие заключается лишь в том, что перед началом работы числа, отличные от нуля, нужно занести не во все регистры 11, а лишь в некоторые. Так, например,при генерировании размеще. ний из 5 по 2 в л бые два регистра необходимо . записать числа, отличные от нуля. Сравнение чисел происходит лишь в тех элементах 13 сравнения, на которые поступают.из регистров 11 не нулевые числа. Поэтому за каждый цикл пересчета счетчиком 15 тактовых импульсов с генератора 19 сигнал появляется на выходах только двух схем 13 сравнения из пяти. Но поскольку числа в регистрах 11 в каждом цикле меняются, то к моменту появления сигнала конца работы устройства (на выходе 25 блока 5) перебираются всевозможные комбинации пар элементов 13 сравнения, в которых происходит сравнение чисел, и на соотве 1 ствующих выходах 14 появляются сигналы. Все эти комбинации пар элементов сравнения являются размещениями из 5 по 2. Таким образом, получаем все размещения из 5 по 2 в форме пространственно- временной последовательности появления сигналов на выходах 14.В режиме генерирования сочетаний информация снимается с выходов элементов И 84-84. Исходная установка такая же, как и в режиме генериро/вания перестановок. Переключателем б задается число элементов из общего числа, которые должны участвовать в формировании сочетаний. Так, если замкнут первьп контакт переклю-. чателя 6, то Формируются сочетания из 5 по 4, если второй - из 5 по 3, если третий - из 5 по 2.Принцип формирования сочетаний основан на периодическом исключении из перестановок лишних комбинаций. Так, при замкнутом третьем контакте переключателя 6 на выходах элементов И 84 и 8 появляются через одну комбинацию все сочетания элементов из 5 по 2. При замкнутом втором контакте9 1124 ка выходе элементов И 81, 8, 8 появляются через шесть комбинаций все сочетания иэ 5 по 3 и т.д.Таким образом, предлагаемое устройство для перебора сочетаний, раэ мещений и перестановок позволяет генерировать перестановки, размещения и сочетания, причем перестановки представляются в форме не только парал 319 10лельных но и последовательных кодов,Фформе пространственно-временной пос. ледовательности появления сигналов на выходах элементов сравнения. Исключение из устройства сдвигового регистра., запоминающей матрицы, бло. ка деления и замена их группамиэлементов И, ИЛИ, обуславливает сокращение количества оборудования.1124319 ие Составитель; А. Клюеексеенко Техред А.Бабинец рректор Г. Огар едактор писное ПП "Патент", г. Укгорог, ул. Проектная,ал 2/39 Тирах 698 По ВНИИПИ Государственного комитета .СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д.