Устройство для перебора перестановок Советский патент 1993 года по МПК G06F15/20 

Изобретение относится к вычислительной технике, предназначено для формирования в определяемой пользователем последовательности перестановок из Н величин и может быть использовано в специ- ализировакных обрабатывающих устройствах для решения комбинаторных задач.

Цель изобретения - расширение функциональных возможностей за счет автоматического формирования перестановок в заранее определяемой последовательности.

Функциональная схема устройства приведена на чертеже.

Устройство содержит блок 1 управления, блок 2 декодирования, блок 3 памяти, счетчик 4, регистр 5, дешифратор б, первый 7 и второй 8 элементы задержки, вход запуска устройства 9, информационные выходы 10а, а 1,2,..,,Н и признаковый выход 11 (Н - число переставляемых элементов).

Блок 1 предназначен для формирования определяющего множества чисел в соответствии с шагом работы устройства, выбора минимального числа из этого множества и подачи его на вход блока декодирования. Блок 1 содержит схему выбора минимального числа 12, дешифратор 13, регистры 14а, ключи 15а, элемент задержки 16 (а 1,2„..,Н).

00

ю о со ю

Јь

Блок 2 предназначен для преобразования чисел, поступающих на его информационный вход и блок 3 памяти, в соответствующие им перестановки. Блок 2 содержит регистры 17.18а. 19а. блоки деления 20а. сумматоры 21 а, элементы ИЛИ 22. 23, элементы задержки 24а, 25а и ключи 2ба (а - 1,2„...Н);

Блок памяти 3 предназначен для хранения и выдачи в процессе работы устройства номеров перестановок в соответствии с определяемой пользователем последовательностью перестановок. Блок может представлять собой ОЗУ с произвольным доступом (см., например, Цифровая и оы- . числительная техника/под ред. Э.В.Евре- инова,.-- М.: Радио и связь, с. 206-213).

Работа устройства основана на реализации процедуры преобразования заранее определенной последовательности чисел М (0. М HI), в соответствующую последовательность перестановок из Н элементов.

Перед работой счетчик 4 обнуляется, в ячейки блока 3 заносятся числа М (0 М Н|) в последовательности определяемой пользователем, а в регистры 14а блока 1 вносятся числа исходного определяющего множества АО {1,2,...,Н}, причем число К (К Ј АО) вносится в регистр 14К. Работа формирователя начинается подачей импульса на вход запуска устройства 9. При этом импульс поступает на счетный вход счетчика 4 и вход элемента задержки 7. Содержимое счетчика увеличивается и на первом шаге устройства становится равным единице. Код единицы с выходов счетчика парафазно поступает на входы регистра 5. Через время задержки п, определяемое элементом 7, импульс с его выхода поступает на вход элемента задержки 8 и на вход записи регистра 5 и код единицы поступает с его выходов на вход дешифратора 6. При этом сигнал единичного уровня с первого выхода дешифратора поступает на считывающий вход первой ячейки памяти блока 3 и число М. соответствующее номеру первой перестановки в последовательности перестановок, определенной пользователем, поступает с информационного выхода блока 3 на информационные входы регистра 17 блока 2 декодирования. Через время Г2 сигнал с выхода элемента задержки 8 поступает на тактовый вход блока 2 декодирования и начинается работа устройства по формированию перестановки, соответствующей первому значению числа М. При этом импульс с тактового входа блока 2 поступает на вход считывания регистра 17, управляющий вход блока деления 20м и. вход элемента

задержки 24Н. Число М с информационного выхода регистра 17 поступает на вход блока деления на постоянный модуль 20н.

Блоки деления 20а осуществляют деление чис/ia, поступающего на их вход, на модуль Ра Н - а + 1. При этом с первоги выхода схемы деления выдается целая часть от деления поступающего на ее вход числи на соответствующий данной схеме постоякн

ный модуль, а со второго - остаток от деления. Поэтому при поступлении ни управляющий вход блока 2Он импульса в нем осуществляется деление числа М, поступившего на его вход с информационного

5 выхода регистра 17, на число Рн. Целая часть от деления поступает с первого выхода блока 20ц на вход блока деления 20н-1. а остаток от деления со второго выхода 20н поступает на информационный вход регистра 18н. Че0 рез время гз, большее чем время работы схемы 20а, импульс с выхода элемента задержки 24н поступает на управляющий вход блока деления 20н-1 и вход элемента задержки 24н-1.

5 Далее аналогичным образом, последо- . вательно через интервалы времени гз блоками 20а, а Н - 1,1 осуществляется выделение целой части и остатка от деления на постоянный модуль чисел, поступающих

0 е первых выходов блоков деления 20в, В Н, 2 соответственно. В результате чего остатки от процедур делен ия записываются в регистры 18а, а Т.Н. Через время Тг Н гз + п + га от момента подачи импуль5 са на тактовый вход устройства 9 импульс с выхода элемента задержки 24i поступает на вход элемента задержки 25i, считывающий вход регистра 18i, управляющий вход ключа 261 и один из входов элемента ИЛИ 22, С

0 выхода элемента ИЛИ 22 сигнал уровня логической единицы поступает на вход разрешения считывания регистров 14а блока 1 . управления (а - 1 ,Н). Число исходного определяющего множества АО с икформацион5 ных выходов этих : регистро в через соответствующие ключи 15а, а 1.Н поступает на входы схемы выбора минимального числа 12.

В схеме 12 осуществляется выбор мини0 мального числа и его код с выхода схемы 12 поступает на входы ключей 26э, а 1,Н. Так как при этом сигнал высокого уровня присутствует только на управляющем входе ключа 26ч, то код минимального числа ис5 ходного определяющего множества АО через его информационную цепь поступает на вход сумматора 2.11, на другой вход которого поступает число с регистра 18i. В сумматоре 211 осуществляется сложение чисел, посту- пивших на его входы и код суммы поступает

на информационный вход регистра 191 и вход элемента ИЛИ 23. С выхода элемента ИЛИ 23 код суммы поступает на вход элемента задержки 16 блока 1 управления. Через время задержки п, большее длительности импульса запуска, код суммы через элемент задержки поступает на вход дешифратора, где он дешифрируется и сигнал с соответствующего выхода поступает на вход одного из ключей 15а, а 1 ,Н (величина суммы на выходе сумматоров 21а, а 1,Н принадлежит множеству первых Н чисел натурального ряда). К этому моменту сигнал высокого уровня уже снят со считывающих входов регистров 14а, а 1,Н и управляющего входа ключа 26i. Через время задержки rs ГА сигнал высокого уровня поступает с выхода элемента задержки 25i на считывающий вход регистра 182. управляющий вход ключа 262. вход элемента задержки 252 и соответствующий вход элемента ИЛИ 22. С выхода элемента ИЛИ 22 сигнал поступает на входы разрешения считывания регистров 14а блока 1. Однако теперь, когда на управляющем входеодного из ключей 15э, а 1,Н присутствует сигнал высокого уровня, на входы схемы выбора минимального числа 12 не поступает число исходного определяющего множества равное сумме, полученной в сумматоре 21i.

Дапьнейшэя работа схемы будет аналогична, и через время Та Ti + Н -rs от момента подачи импульса запуска сигнал высокого уровня с выхода элемента задержки 25Н поступает на входы разрешения считывания регистров 19а, а 1,Н и признаковый выход 11. Числа, соответствующие сгенерированной перестановке, поступают с регистров 19а,а 1,Н на информационные выходы устройства Юз, а 1,Н. Поступление импульса на признаковый выход устройства 11 сигнализирует с готовности устройства к формированию очередной пе- рестанозки из последовательности перестановок заданной пользователем. Работа устройства при этом будет аналогична.

Таким образом предлагаемое устройство для перебора перестановок позволяет автоматически, формировать любую заранее определенную пользователем последо-. вательность перестановок..

Формула изобретения Устройство для перебора перестановок, содержащее первый регистр, первую, вторую и третью группы из п регистров (п - длина перестановок), первую и вторую группы ключей, первую и вторую группу элементов задержки, два элемента ИЛИ, блок выбора минимального числа, первый дешифратор, первый элемент задержки, п блоков деления и п сумматоров, выход 1-го регистра первой группы соединен с информационным входом 1-го ключа первой 5 группы (t 1,п). управляющий вход которого соединен с соответствующим выходом дешифратора, информационный вход которого соединен с выходом первого элемента задержки, выход 1-го ключа первой группы 0 соединен с 1-м входом блока выбора минимального числа, выход которого соединен с объединенными входами ключей второй группы, информационный вход j-ro блока деления j 1...(п-1) соединен с первым вы- 5 ходом 0+1)-го блока деления, тактовый вход J-ro блока деления соединен с входом j-ro элемента задержки первой группы и с выходом (j+1)-ro элемента задержки первой группы, второй выход i-ro блока деления

0 соединен с информационным входом 1-го регистра второй группы (i 1,n), выход первого регистра соединен с информационным входом n-го блока деления, тактовый вход которого соединен с входом n-го элемента

5 задержки первой группы, с входом разрешения считывания первого регистра, вход разрешения считывания 1-го регистра второй группы соединен с выходом (i-1)-ro элемента задержки второй группы, с входом

0 1-го элемента задержки второй группы, с управляющим входом 1-го ключа второй группы и с 1-м входом первого элемента ИЛИ, выход 1-го регистра второй группы соединен с первым входом 1-го сумматора

5 группы, второй вход которого соединен с выходом 1-го ключа второй группы, выход 1-го сумматора группы соединен с информационным входом i-ro регистра третьей группы и с i-м входом второго элемента ИЛИ,

0 выход которого соединен с входом элемента задержки, выход первого элемента ИЛИ соединен с объединенными входами разрешения считывания регистров первой группы, выходы разрешения считывания регистров

5 третьей группы соединены с выходом п-го элемента задержки второй группы, выход 1-го регистра третьей группы является 1-м информационным выходом устройст- г а, отличающееся тем, что, с целью

0 расширения функциональных возможностей за счет автоматического формирования перестановок, в заранее определенной последовательности, в него введены блок памяти, дешифратор, второй регистр, счетчик

5 и два элемента задержки, причем вход запуска устройства соединен с входом второго элемента задержки и счетным входом счетчика, выход разрядов которого соединен с информационными входами второго регистра, вход записи которого объединен с выходом второго элемента задержки и с входом третьего элемента задержки, а выходы соединены с соответствующими входами дешифратора, выходы дешифратора соединены с адресными входами блока памяти, выходы которого соединены с информационными входами второго регистра, вход разрешения считывания которого соединен с выходом .третьего элемента задержки, выход п-го элемента задержки второй группы соединен с выходом конца работы устройства.

Изобретение относится к вычислительной технике, предназначено для формирования в определяемой пользователем последовательности перестановок п элементов, и может быть использовано в специализированных устройствах решения комбинаторных задач, в аппаратном обеспечении систем автоматизированного проектирования, а также в системах контроля для генерации кодовых последовательностей. Цель изобретения - расширение функциональных возможностей за счет автоматического формирования перестановок в заранее определяемой последователь- ности. Устройство содержит блок управления, который содержит группу регистров, группу ключей, блок выбора минимального числа, дешифратор, блок декодирования, содержащий две группы регистров, сумматоры, элементы ИЛИ, блоки деления, сумматоры, элементы задержки и ключи, блок памяти, счетчик, регистр, дешифратор и два элемента задержки. Устройство обеспечивает последовательный выбор из блока памяти номеров перестановок гг. (О m h ) и преобразоаание значений т в однозначно соответствующие им перестановки. 1 ил.

3 -+11