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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК 9) (11) 504 С 06 ГОСУДАРСТВЕННЫИ НОМИ ПО ДЕЛАМ ИЗОБРЕТЕНИЙ СССРНРЫТИЙ Я ОПИСАНИЕ ИЗОБРЕТН А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ 2(56) Авторское свидетельство СССР У 1190388, кл. С 06 Р 15/20, 1984.Авторское свидетельство СССР 1180917, кл. С 06 Р 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТА НОВОК(57) Изобретение относится к области вычислительной техники, предназначено для формирования в произвольной последовательности перестановок из и величин и может быть использовано для решения комбинаторных задач, а также в системах контроля для гене рации кодовых последовательностей.Цель изобретения - повышение быстродействия устройства. за счет упрощенияалгоритма перебора перестановок. Устройство содержит блок управления (БУ)1 и блок декодирования (БД) 2, БУ содержит и регистров (Р) 3 и ключей(К) 6, дешифратор 4, элемент задержки 7 и схему выбора минимального числа 5. Входы БУ соединены с выходамиБД, а выход БУ соединен с входам БД.Устройство реализует процедуру однозначного преобразования числа ш (Ош(п) в соответствующую ему"перестановку исходных величин. Данная процедура существенно упрощает управлениеочередностью следования перестановок;чем повышает удобства в эксплуатацииустройства, 1 ил.Изобретение относится к вычисли, тельной технике и может быть исполь зовано для решения комбинаторных задач, а также в системах контроля длягенерации кодовых последовательностей.Цель изобретения - повышение быстродействия устройства за счет упроще"ния алгоритма перебора перестановок.На чертеже приведена функциональная схема устройства.Устройство содержит блок 1 управления и блок 2 декодирования.Блок 1 предназначен для формирова"ния определяющего множества чисел всоответствии с выбранным вариантомперестановки и шагом работы устройства, выбора минимального числа изэтого множества и подачи его на входблока декодирования. Блок 1 содержитрегистры 3;, =1,п, дешифратор 4,схему выбора минимального числа 5,ключи б , х=1,п, элемент задержки 7,управляющий вход 8, информационныйвход 9 и 10.Блок 2 предназначен для преобразо- .вания заданного натурального числав соответствующую ему перестановку.Блок 2 содержит регистры 11, 12,13 , блоки деления 14;, сумматоры 15,элементы задержки 16;, 17;, вход пус ка устройства 18,элементы ИЛИ 19,20, ключи 21 второй информационныйвход 22, управляющий выход 23, ин формационный выход 24, информационный , вход устройства 25 и группу информа 1 ционных выходов устройства 26 (д= , =1,п).Работа устройства основана на реализации процедуры преобразования исходного числа ш(0 ш сп 1) в однозначно соответствующую ему перестановкуисходных, предварительно пронумеро- .ванных числами 1,2п, элементов.Перед работой параллельным кодомв регистры 3 1.=1,п блока 1 вносятсячисла исходного определяющего множеств а Хо = 1 п , причем число К ф б 1 ) вносится в регистр 3, а вК регистр 11 блока 2 вносится число 1 ъ,Работа устройства начинается подачейположительного импульса запуска навход пуска устройства 18 блока 2.При этом импульс запуска поступаетна вход считывания регистра 11, управляющий вход блока деления на пос тоянный модуль 14 1 и вход элемента :задержки 16, Число в с информацион 5 10 15 20 25 30 35 40 45 50 55 1 ного выхода регистра 11 поступает навход блока деления на постоянный модуль 14, .Блоки деления 14 осуществляют деленив числа, поступающего на их вход, на модуль г. =и-+1.При этом с первого выхода схемы деления выдается целаячасть от деления поступающего на ее вход числа на соответствующий данной схеме постоянный модуль, а с вторОго - остаток от деления., Поэтому при поступлении на управляющий вход блока 14 импульса в ней осуществляется деление числа, посту" пающего на ее вход с информационного выхода регистра 11, на число т. Це" лая часть от деления поступает с первого выхода блока 1411 на вход блока деления 14 , а остаток от деленияг1с второго выхода блока 14 поступает на информационный вход регистра 121 . Через времяТ, , большее чем время работы схемы 14., Импульс с выхода элемента задержки 161 поступает на управляющий вход блока деления 14, и вход элемента задержки 16Далее аналогичным образом, последовательно через интервалы времени 7 блоками 14 , 1=п,1 осуществляет" ся выделение целой части и остатка от деления на постоянный модуль чисел, поступающих с первого выхода блока деления 14;, х=п,2 соответственно, В результате чего остатки от процедур Деления записываются в регистрах 1211 1=11 п Через вре я Е 1= =и:1. от момента подачи импульса за 4пуска на вход пуска устройства 18 импульс с выхода элемента задержки 16поступает на элемент задержки 17, считывающий вход регистра 12 управляющий вход ключа 21 и один из входов элемента ИЛИ 19, При этом содержимое регистра 12с .его информационного выхода поступает на вход сумматора 15,. С выхода элемента ИЛИ 19 сигнал уровня "1" через управляющий выход 23 блока 2 и управляющий вход 8 блока 1 поступает на вход разрешения считывания данных регистров 3., =1 и. Числа исходного определяющего множества Х .с информационных выходов этих регистров через информационные цепи соответствующих ключей 6, =1,п поступают на входы схемы вйбора минимального числа 5. В схеме 5 осуществляется выбор минимального числа и код соответствующий этомуз 141 числу с выхода схемы 5, через выход 10 блока 1, второй информационный вход 22 блока 2 поступает на информационные входы ключей 2 1;, ь=д,и, Так как при этом сигнал высокого уровня минимального числа исходного определяющего множества через,его информационную цепь поступает на вход сумматора 151. В сумматоре,15 осуществляется сложение чисел, поступивших на его входы, и код их суммы поступает на информационный вход регистра 13 и один из входов элемента ИЛИ 20, с выхода элемента ИЛИ код суммы через информационный выход 24 блока 2 и информационный вход 9 блока 1 поступает на вход элемента задержки 7. Через время с большее длительности импульса запуска, код суммы через элемент задержки поступает на вход дешифратора 4, где он дешифруется и сигнал с соответствующего данной сумме выхода поступает на управляющий вход соответствующего ключа 6 1=1 и (Величина суммы на выходе сумматоров.15;, =1,п принадлежит множеству первых и чисел натурального ряда). К этому моменту сигнал высокого уровня уже снят со считывающих входов реги- стров 3 , =1,п и управляющего входа кл ча 21 Через время задержки с тала3 сигнал высокого уровня поступает с входа элемента задержки 17 , на считывающий вход регистра 12, управляющий вход ключа 21 , вход элемента задержки 17и соответствующий-вход . элемента ИЛЙ 19. С входа элемента ИЛИ 19 сигнал через управляющий выход 23 блока 2 и управляющий вход 8блока 1 поступает на. входы разрешения считывания данных регистров 3 1=1,п. Однако теперь, когда на управляющем входе одного из ключей 6;, =1,п присутствует сигнал высокого уровня, на входы схемы выбора мини,мального числа 5 не поступает число исходного определяющего множества 1,рЭ равное сумме, полученной в сумматоре 15 , Дальнейшая работа схемы будет аналогична и через время 1 =. +ф Фп от момента подачи импульса за 3пуска сигнал высокого уровня с выхода элемента задержки 17 поступает на входы разрешения считывания данных регистров 13, з.=.1 и и числа, соот-. ветствующие полученной перестановке, посгупают на их входы, являющиеся 00564группой информационных виходов устройства 26.формула изобретенияУстройство для перебора перестановок, содержащее первую группу изи регистров, первую группу из (и+1)ключей (и - длина перестановок), элемент задержки, первый и второй элементы ИЛИ, о т л и ч а ю щ е е с ятем, что, с целью .повышения быстродействия устройства за счет упрощенияалгоритма перебора перестановок, внего введены п-й ключ первой группы,дешифратор, схема выбора минимальногочисла, регистр, вторая и третья группы из п регистров, первая и втрраягруппы из п элементов задержки, вто рая группа из и ключей, группа из исумматоров и группа из и блоков Деления, выход -го регистра первой группы соединен с информационным входом 25 ь-. го ключа первой группы (1 1,п),управляющие входы которых соединеныс соответствующими выходами дешифратора, информационный вход которогосоединен с выходом элемента задержки, З 0 выход -го ключа первой группы соединен с 1-м входом схемьь выбора минимального числа, информационный входустройства соединен с инфорМационнымвходом регистра, выход которого соЕф;35динен с информационным входом и-гоблока деления, вход тактирования которога соединен с входом и-го элемента задержки первой группы и с входомразрешения считывания данных регистра, информационный вход -го блокаделения. соединен с первым выходом,(+1)-го блока деления, вход тактирования д-го блока деления соединен свходом.ь-го элемента задержки первой 45группы и с выходом (х+1)-го элементазадержки первой группы, второй выход-го блока деления соединен с информационным входом -го регистра второйгруппы (ь=1,й), вход.разрешения считывания данных -го регистра второй 50Вгруппы соединен с выходом (1-1)-гоэлемента задержки второй группы, свходом -го элемента задержки второйгруппы, с управляющим входом -го 55ключа второй группы и с -м входомпервого элемента ИЛИ, выход которогосоединен с входом разрешения считывания данных регистров первой группы,высод 1-го регистра второй группыЗаказ 3482/4 б Тираж 704 Подписное ВНИИПИ Государственного комитета СССР. по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5.Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4 5 14 соединен с первым входом 1.-го сумма - тора группы, второй вход которого соединен с выходом -го ключа второй группы, информационные входы ключей второй группы соединены с выходом схемы выбора минимального числа, выход х-го сумматора группы соединен с информационным входом -го регистра третьей группы .и с -м входом второго элемента ИЛИ, выход которого соединен с входом. элемента задержки, выход -го регистра третьей группы являет 10056 бся 1.-м информационным выходом устройства, входы разрешения считыванияданных регистров третьей группы соединены с выходом и-го элемента задержки второй группы, вход первогоэлемента задержки второй группы соединен с управляющим входом первогоключа второй группы, с входом разрешения считывания данных первого регистра второй группы, с первым входомпервого элемента ИЛИ и с выходом первого элемента задержки первой группы.