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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК ц 5 6 06 Г 15/20 РЕТЕНИ- расширение функтей за счет автомаия перестановок в и последовательнохема устройст СУДАРСТВЕННОЕ ПАТЕНТНОДОМСТВО СССРОСПАТЕНТ СССР) ПИСАНИЕ К АВТОРСКОМУ СВИДЕТЕЛЬСТ(72) А,А.Бабаев, С,М.Кашин и Н.И.Ячкула (56) Авторское свидетельство СССР М 1383381, кл. 6 06 Р 15/20, 1988.Авторское свидетельство СССР М 1410056, кл. 6 06 Р 15/20, 1988, (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК(57) Изобретение относится к вычислительной технике, предназначено для формирования в определяемой пользователем последовательности перестановок и элементов,и может быть использовано в специализированных устройствах решения комбинаторных задач, в аппаратном обеспечении систем автоматизированного проектирования, а также в системах контроля Изобретение относится к вычислительной технике, предназначено для формирования в определяемой пользователем последовательности перестановок иэ Н величин и может быть использовано в специалиэи рова кных обрабатывающих устройствах для решения комбинаторных задач. Цель изобретения циональных возможно тического формирова заранее определяемо сти.функциональная с ведена на чертеже,для генерации кодовых последовательностей. Цель изобретения - расширение функциональных возможностей за счет автоматического формирования перестановок в заранее определяемой последовательности. Устройство содержит блок управлекия, который содержит группу регистров. группу ключей, блок выбора минимального числа, дешифратор, блок декодирования, содержащий две группы регистров, сумматоры, элементы ИЛИ, блоки деления, сумматоры, элементы задержки и ключи, блок памяти, счетчик, регистр, дешифратор и два элемента задержки, Устройство обеспечивает последовательный выбор из блока памяти номеров перестановок гг, (Ои) ( и) и преобразование значений е в однозначно соответствующие им перестановки, 1 ил,Устройство содержит блок 1 управления, блок 2 декодирования, блок 3 памяти, счетчик 4, регистр 5, дешифратор 6, первый 7 и второй 8 элементы задержки, вход запуска устройства 9, информационные выходы 10 а, а = 1,2.Н и приэнаковый выход 11 (Н - число переставляемых элементов),Блок 1 предназначен для формирования определяющего множества чисел в соответствии с шагом работы устройства, выбора минимального числа иэ этого мкожества и подачи его на вход блока декодирования. Блок 1 содержит схему выбора минимального числа 12, дешифратор 13, регистры 14 а, ключи 15 а, элемент задержки 16 (а = 1,2., Н).Блок 2 предназначен для преобразования чисел, поступающих на его информационный вход и блок 3 памяти, в соответствующие им перестановки. Блок 2 содержит регистры 17, 18 а, 19 а, блоки деления 20 а, сумматоры 21 а, элементы ИЛИ 22, 23, элементы задержки 24 а, 25 а и ключи 26 а (а 1,2.Н);Блок памяти 3 предназначен для хранения и выдачи в процессе работы устройства номеров перестановок в соответствии с определяемой пользователем последовательностью перестановок. Блок может представлять собой ОЗУ с произвольным доступом (см., например, Цифровая и вычислительная техника, под ред. З.В.Евреинова, - М.: Радио и связь, с. 206-213).Работа устройства основана на реализации процедуры преобразования заранее определенной последовательности чисел М (О,МН 1), в соответствующую последовательность перестановок из Н элементов,Перед работой счетчик 4 обнуляется, в ячейки блока 3 заносятся числа М (О "- "МН 1) в последовательности определяемой пользователем, а в регистры 14 а блока 1 вносятся числа исходного определяющего множества Ао = (1,2 Н, причем число К (К (= А 0) вносится в регистр 14, Работа формирователя начинается подачей импульса на вход запуска устройства 9, При этом импульс поступает на счетный вход счетчика 4 и вход элемента задержки 7. Содержимое счетчика увеличивается и на первом шаге устройства становится равным единице. Код единицы с выходов счетчика парафазно поступает на входы регистра 5. Через время задержки г 1, определяемое элементом 7, импульс с его выхода поступает на вход элемента задержки 8 и на вход записи регистра 5 и код единицы поступает с его выходов на вход дешифратора 6. При этом сигнал единичного, уровня с первого выхода дешифратора поступает на считывающий вход первой ячейки памяти блока 3 и число М. соответствующее номеру первой перестановки в последовательности перестановок, определенной пользователем, поступает с информационного выхода блока 3 на информационные входы регистра 17 блока 2 декодирования, Через время г 2 сигнал с выхода элемента задержки 8 поступает на тактовый вход блока 2 декодирования и начинается работа устройства по формированию перестановки, соответствующей первому значению числа М. При этом импульс с тактового входа блока 2 поступает на вход считывания регистра 17, управляющий вход блока деления 20 и вход элемента задержки 24. Число М с информационноговыхода регистра 17 поступает на вход блокаделения на постоянный модуль 20блоки деления 20 а осуществляют деле 5 ние числа. поступающего на их вход, на модуль Ра = Н - а + 1. При этом с первоговыхода схемы деления выдается целая частьот деления поступающего на ее вход числбна соответствующий данной схеме постоян 10 ный модуль, а со второго - остаток от деления. Поэтому при поступлении науправляющий вход блока 20 импульса анем осуществляется деление числа М, поступившего на его вход с информационного15 выходарегистра 17, начислоР, Целаячастьотделения поступает с первого выхода блока 20 на вход блока деления 20-1, а остатокот деления со второго выхода 20 поступаетна информационный вход регистра 18, Че 20 рез время гз, большее чем время работысхемы 20 а, импульс с выхода элемента задержки 24 н поступает на управляющий входблока деления 20-1 и вход элемента задержки 24-1.Далее аналогичным образом, последовательно через интервалы времени гз блоками 20 а, а = Н - 1,1 осуществляетсявыделение целой части и остатка отделенияна постоянный модуль чисел, поступающих30 с первых выходов блоков деления 20 в,В = Н, 2 соответственно, В результате чегоостатки от процедур деления записываются в регистры 18 а, а = 1,Н. Через времяТ 1 = Н гз+ г+ г 2 от момента подачи импуль 35 са на тактовый вход устройства 9 импульс свыхода элемента задержки 241 поступает навход элемента задержки 25, считывающийвход регистра 181, управляющий вход ключа261 и один из входов элемента ИЛИ 22, С40 выхода элемента ИЛИ 22 сигнал уровня логической единицы поступает на вход разрешения считывания регистров 14 а блока 1управления (а = 1,Й). Число исходного определяющего множества Ао с информацион 45 ных выходов этих: регистров черезсоответствующие ключи 15 а, а = 1,Н посту-.пает на входы схемы выбора минимальногочисла 12,В схеме 12 осуществляется выбор мини 50 мального числа и его код с выхода схемы 12поступает на входы ключей 26 а, а1,Н. Таккак при этом сигнал высокого уровня присутствует только на управляющем входеключа 261, то код минимального числа исходного определяющего множества А через его информационную цепь поступает на вход сумматора 21, на другой вход которого поступает число с регистра 181. В сумматоре 21 осуществляется сложение чисел, поступивших на его входы и код суммы поступаетна информационный вход регистра 191 и вход элемента ИЛИ 23, С выхода элемента ИЛИ 23 код суммы поступает на вход элемента задержки 16 блока 1 управления. Через время задержки г 4. большее длительности импульса запуска, код суммы через элемент задержки поступает на вход дешифратора, где он дешифрируется и сигнал с соответствующего выхода поступает на вход одного из ключей 15 а, в = 1,Н (величина суммы на выходе сумматоров 21 а, а,Н принадлежит множеству первых Н чисел натурального ряда). К этому моменту сигнал высокого уровня уже снят со считывающих входов регистров 14 а, а = 1,Н и управляющего входа ключа 26, Через время задержки г 5г 4 сигнал высокого уровня поступает с выхода элемента задержки 25 на считывающий вход регистра 182. управляющий вход ключа 262, вход элемента задержки 252 и соответствующий вход элемента ИЛИ 22, С выхода элемента ИЛИ 22 сигнал поступает на входы разрешения считывания регистров 14 а блока 1. Однако теперь, когда на управляющем входе одного из ключей 15 а, а = 1,Н присутствует сигнал высокого уровня, на входы схемы выбора минимального числа 12 не поступает число исходного определяющего множества равное сумме, полученной в сумматоре 21.Дальнейшая работа схемы будет аналогична, и через время Т 2 = Т + Н г 5 от момента подачи импульса запуска сигнал высокого уровня с выхода элемента задержки 25 н поступает на входы разрешения считывания регистров 19 а, а = 1,Н и признаковый выход 11, Числа, соответствующие сгенерированной перестановке. поступают с регистров 19 а, а = 1,Н на информационные выходы устройства 10 а, а = 1,Н. Поступление импульса на приэнаковый выход устройства 11 сигнализирует с готовности устройства к формированию очередной перестаноаки из последовательности перестановок заданной пользователем. Работа устройства при этом будет аналогична.Таким образом предлагаемое устройство для перебора перестановок позволяет автоматически, формировать любую заранее определенную пользователем последо-. вательность перестановок Формула изобретения Устройстводля перебора перестановок, содержащее первый регистр, первую, вторую и третью группы из и регистров (и - длина перестановок), первую и вторую группы ключей, первую и вторую группу элементов задержки. два элемента ИЛИ, блок выбора минимального числа, первый де 55 и два элемента задержки, причем вход запуска устройства соединен с входом второго элемента задержки и счетным входом счетчика, выход разрядов которого соединен с информационными входами второго регистра, вход записи котсрого объединен с выхо 10 15 20 25 30 35 40 шифратор. первый элемент задержки, и блоков деления и и сумматоров, выход 1-го регистра первой группы соединен с информационным входом 1-го ключа первой группы (1 = 1,п). управляющий вход которого соединен с соответствующим выходом дешифратора, информационный вход которого соединен с выходом первого элемента задержки, выход 1-го ключа первой группы соединен с 1-и входом блока выбора минимального числа, выход которого соединен с объединенными входами ключей второй группы, информационный вход )-го блока деления / = 1(п - 1) соединен с первым выходом (1+1)-го блока деления, тактовый вход )-го блока деления соединен с входом )-го элемента задержки первой группы и с выходом(1+1)-го элемента задержки первой группы, второй выход 1-го блока деления соединен с информационным входом 1-го регистра второй группы (1 = 1,п), выход первого регистра соединен с информационным входом и-го блока деления, тактовый вход которого соединен с входом и-го элемента задержки первой группы, с входом разрешения считывания первого регистра, вход разрешения считывания 1-го регистра второй группы соединен с выходом (1 - 1)-го элемента задержки второй группы, с входом 1-го элемента задержки второй группы, с управляющим входом 1-го ключа второй группы и с 1-м входом первого элемента ИЛИ, выход 1-го регистра второй группы соединен с первым входом 1-го сумматора группы, второй вход которого соединен с выходом 1-го ключа второй группы, выход 1-го сумматора группы соединен с информационным входом 1-го регистра третьей группы и с 1-м входом второго элемента ИЛИ, выход которого соединен с входом элемента задержки, выход первого элемента ИЛИ соединен с обьединенными входами разрешения считывания регистров первой группы, выходы разрешения считывания регистровтретьей группы соединены с выходом п-гоэлемента задержки второй группы, выход 1-го регистра третьей группы является 1-минформационным выходом устройстг а, о т лича ющееся тем, что, с цельюрасширения функциональных возможностей за счет автоматического формирования перес"ановок в заранее определенной последовательности, в него введены блок памяти, дешифратор, второй регистр, счетчик1820394 Составитель А. БабаевКулакова Техред М.Моргентал Корректор Н. Король Редакт аказ 2031 ВНИИПИ Тираж арственного комитета 113035, Москва; Жроизводственно-издательский комбинат "Пате жгород, ул,Гагарина, 1 дом второго элемента задержки и с входом третьего элемента задержки, а выходы соединены с соответствующими входами дешифратора, выходы де шифратора соединены с адресными входами блока памяти, выходы которого соединены с информационными входами второго регистра, вход разрешения считывания которого соединен с выходом третьего элемента задержки, выход п-го элемента задержки второй 5 группы соединен с выходом конца работыустройства. Подписноеизобретениям и открытиям при ГКНТ СССР