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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКРЕСПУБЛИК 09) (11) 38 А 06 Р 15/20 0 ПИСАНИК ИЗ 0 ВЕКТЬН А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ 2 ательност послнияние ль рете асшир остей упрошение устроиства и о функциональных возмо жны ра о блава уппы воз рестяет оист ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(561 Авторское свидетельство СССРМ 1180917, кл. С 06 Е 15/20, 198.Авторское свидетельство СССРВ 1410056, кл. С 06 Е 15/20, 987.(57) Изобретение относится к автоматике и вычислительной технике иможет быть использовано при решениикомбинаторных задач, а также в систмах контроля для генерации кодовых эа счет формирования всех возм перестановок. Устройство содер делитель 1, счетчики 2, 3, деш тор 4, регистры 5, 6, элементь Ипи 7-4, НЕ 15, И 16-20, 22, ки 23-25, группы 21 элементов Упрощение устройства достигнут подаря исключению иэ его соста Б- делителей, сумматоров и гр регистров, При этом обеспечена можность формирования любых пе новок иэ 1 элементов, что рас функциональные воэможности уст 1 ил., 1 табл.15 А, А, А; " епс(А /(Б-, д 2, , Б;А - целое число в интервале от 0 до Б -1;Фр Р, Р "1, 2, ,Б, Р Р;,/р, =2, , Б. Изобретение относится к автоматике и вычислительной технике и может быть использовано при решении комбинаторных задач, а также в системах контроля для генерации кодовых последонательностей.Целью изобретения является упрощение устройства и расширение его функциональных возможностей за счет формирования всех возможных перестановок.На чертеже представлена функциональная схема устройства.Устройство содержит делитель 1, счетчики 2 и 3, дешифратор 4, регистры 5 и 6, элементы ИЛИ 7-14, элемент НЕ 15, элементы И 16-20, группы Устройство для перебора перестановок работает следующим образом.Перед началом работы 2 устанавливается в нулевое состояние, в счетчик 3 заносится код числа Б сигналом с входа 26 "Начальная установка" По сигналу с шины 27 "Пуск" регистры 5-, -30 5-Б устанавливаются в начальное состояние, а именно: в регистр 5-1 заносится код числа единицы, н регистр 5-. код числа , в регистр 5-Б - код числа Б. Содержимое счетчика 2 через 35 элементы И 17-1 - 17-К и элементы ИЛИ 10-1 - ) 0-К (где К = 3 1 од (Б - 1) ) подается на первую группу входов делителя 1, являющуюся входом делимого числа, На вторую группу входов делителя подано содержимое счетчика 3. По сигналу с выхода элемента 23 задержки через элемент ИЛИ 9 и элемент И 22 начинается выполнение операции деления числа поданного на первую группу входов45 делителя,на число, поданное на вторую группу входов, По окончании операции деления по сигналу с выхода делителя "1 нец операции" остаток от деления поступает на вход дешифратора 4, а50 целая часть от деления через элементы И 19-1 - 19-К и элементы ИЛИ 10-1 10-К - на первую группу входов делителя 1, По сигналу с выхода, соответствующего величине остатка, дешифратора 4 содержимое соответствующего регистра 5-1 - 5-Б передается через соответствующую группу элементов И 21 элементов И, элемент И 22, элементы 3-25 задержки, установочный вход 26, пусковой вход 27, последовательный 28 н параллельный 29 информационные выходы и выход 30 окончания перебора.Принцип действия устройства основывается на том, что все возможные перестановки из 11 чисел можно получить, применив Б-шаговую вычислительную процедуру: -й элемент пере,становки ( 1, 2, , Б) определя 21-1 - 21-Б и через элементы ИЛИ 12-1 12-К (где К3 1 о 8 т(Б на регистр 6-1. С выходов элементов ИЛИ 12-1 12-В. выдаются перестановки в последовательном коде. Импульсы с выхода дешифратора 4 задерживаются в соо тветствующем элементе 25-1 - 25-Б, через элемент ИЛИ 13 содержимое регистров 6- - 6-Б сдвигается на К разрядов вправо, и через соответствующие элементы ИЛИ 11-1 - 11-Б содержимое регистров 5-1 - 5-Б, начиная с номера рег истра, с которого произошла передача информации в регистр 6-1, сдвигается иа К разрядов влево.П окончании операции сигнал с выхода элемента И 18 уменьшает содержимое счетчика 3 на единицу и через элемент 24 задержки, элемент ИЛИ 9 и элемент И 22 поступает на вход "Начало операции" делителя, Выполняется операция деления целой части отпервого деления на величину Б.Дальнейшая работа устройства происхо-дит аналогично. После Б-го деления(т,е. деления на число 1) на регистрах 6-1 - 6-Б будет находиться сформи"рованная перестановка. Когда состоя.ние счетчика 3 равно единице, то навыходе элемента ИЛИ 14 - нулевойсигнал, который запрещает прохождениесигнала "Конец операциин через элемент И 18, через элемент НЕ 15 увеличивает состояние счетчика 2 наединицу, заносит в счетчик 3 код чис5 1512038 ла 14 и через эл менты 1 ЛИ 8 и задержки 23 запускает схему на получениеперестановки, соответствующей новому состоянию счетчика 2. Если содержи 5 мое счетчика 2 равно числу Н тона выходе элемента И 16 появляетсясигнал "Конец работы", к торый запрещает прохождение сигналов на входНачало операции делителя, 1 ОТаким образом, изменяя содержимое счетчика 2 от О до И - 1, получают все возможные перестановки из Н чисел.Рассмотрим работу устройствапри получении всех возможных пере ь становок из трех чисел (М3). 3этом случае К =1 од.5= 3; К =3 1 оц,З2. вСостояние основных элементов н устройства и возможные г;ерестановки в приведены в таблице. и Устройство для перебора перестановок, содержащее дье группы регистров, делитель, дешифратор, четыре элемента ИЛИ, два элемента задержки, группу элементов задержки, причем выходы регистров первой группы являются параллельным информационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и расширения его функциональных возможностей за счет формирования всех возможных перестановок, оно содержит два счетчика, пятый элемент ИЛИ, три элемента И, элемент НЕ, три группы элементов ИЛИ, 3+И групп элементов И (где Б - число элементов в перестановках, причем первый вход первого элемента ИЛИ является пусковым входом устройства, выход первого элемента ИЛИ через первый элемент задержки подключен к входам начальной установки всех регистров второй группы, к первому входу второго элемента ИЛИ и к первым входам всех элементов И первой группы 1-й разрядный выход первого счетчика (1 = 1,К, где К =1 од (Б 1-1 подключен к 1-му входу первого элемента И и к второму входу -го элемента И первой группы, выход ь-го элемента И первой группы подключен к первому входу -го элемента ИЛИ первой группы, выходы элементов ИЛ первой группы соединены с соответствующими разрядными входами делимого делителя,формула изобретения 20 25 30 35 40 45 1 50 55 разрядные .выходы в горого счетчика соединены с соответствующими разрядными входами делителя, ь-й разрядный выход целой части результата делителя подключен к первому входу ь-го элемени И второй группы, выход которогоодключен к второму входу -го элемента11 первой группы, -й разрядный выход гстатка от деления делителя подключен к первому входу -го элемента И третьей группы, разрядные выходы второго -етчика, кроме выхода старшего разряда, подключены к соответствующим прягым входам третьего элемента ИЛИ, инверсный вход которого соединен со старшим разрядным выходом вгорого счетчика,ыход третьего элемента ИЛИ подключенпервому входу второго элемента И и кходу элемента НЕ, выход элемента НЕодключен к второму входу первого элемента ИЛИ, к суммирующему счетному входу первого счетчика и к первому в:оду четвертого элемента ИЛИ, выход которого подключен к входу начальной установки второго счетчика, второй вход четвертого элемента ИЛИ соединен с входом начальной установки первого счетчика и является установочным входом устройства, выход второго элемента И подключен к вычитающему счетному входу второго счетчика, к вторым входам всех элементов И второй и третьей групп и через второй элемент задержки к второму входу второго элемента 1 ЛИ, выход которого подключен к прямому входу третьего элемента И, выход первого элемента И является выходом окончания перебора устройства и подключен к инверсному входу третьего элемента И, выход третьего элемента И подключен к входу начала операции делителя, выход конца операции делителя подключен к второму входу второго элемента И, выходы элементов И третьей группы подключены к соответствующим входам дешифратора 1-й выход дешифратора ( = 1,11) подключен к первым входам всех элементов И (1+3)-йгруппы и к входу 1-го элемента задержки группы, выход 1-го элемента задержки группы подключен к 3-му входу с 1-го по И-й элементов ИЛИ второй группы, выход 3-го элемента ИЛИ второй группы подключен к сдвигающему входу 1-го регистра второй группы, выходы элементов задержки группы подключены к соответствующим входам пятого элемент ИЛИ, выход к торого подключен1517038 к сдвигающему входу каждого регистрапервой группы, разрядные выходы 1 го регистра второй группы (12,0)подключены к соответствующим разряднымвходам (1-1)-го регистра второйгруппы, ш-й разрядный выход (ш1,К, где К1 од Б) 1-го регистравторой группы подключен к второмувходу ш-го элемента И (3+3)"й группы, 10выход ш-го элемента И (3+3)-,й группыподключен к 1-му входу ш-го элемента Перестановка Состояние счетчиков Состояние регистров Номерделения 5-2 5-3 6-3 5-1 6-1 6-2 2 3 О 10 0 1 2 О 2 1 О 2 Э О 3 2 1 3 0Составитель В. БайковТехред П,Олийнык Корректор В. Гирняк Редактор О.Юрковецкая Заказ 6392/52 Тираж 668 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-Э 5, Раушская наб., д, 4/5Производственно-издательский комбинат "Патент", г,ужгород, ул. Гагарина,10 Число нпервойгруппевыходовделител1 ИЛИ третьей группы, выходы элементовИЛИ третьей труппы являются последовательными разрядными выходами устройства и соединены с соответствующими разрядными входами первого регистра первой группы, разрядные выходы1-го регистра первой группы, кромеН-го регистра, подключены к соответствующим разрядным вхЬдам (1+1)-горегистра первой группы.