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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)э G 06 F 15/20

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ, (21) 4954320/24 (22) 17.06.91 (46) 07.06.93, Бюл. N. 21 (72) А,А.Бабаев, С,М.Кашин и Н.И.Ячкула (56) Авторское свидетельство СССР

М 1383381, кл. G 06 F 15/20, 1988.

Авторское свидетельство СССР

N 1410056, кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК (57) Изобретение относится к вычислительной технике, предназначено для формирования в определяемой пользователем последовательности перестановок и элементов, и может быть использовано в специализированных устройствах решения комбинаторных задач, в аппаратном обеспечении систем автоматизированного проектирования, а также в системах контроля

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

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

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

„„Я2 „„1820394 А1 для генерации кодовых последовательностей. Цель изобретения — расширение функциональных возможностей за счет автоматического формирования перестановок в заранее определяемой последовательности. Устройство содержит блок управления, который содержит группу регистров. группу ключей, блок выбора минимального числа, дешифратор, блок декодирования, содержащий две группы регистров, сумматоры, элементы ИЛИ, блоки деления, сумматоры, элементы задержки и ключи, блок памяти, счетчик, регистр, дешифратор и два элемента задержки. Устройство обеспечивает последовательный выбор из блока памяти номеров перестановок гг, (О и) h!) и преобразование значений m в однозначно соответствующие им перестановки. 1 ил, Устройство содержит блок 1 управления, блок 2 декодирования, блок 3 памяти, счетчик 4, регистр 5, дешифратор 6, первый

7 и второй 8 элементы задержки, вход запуска устройства 9, информационные выходы

10а, а = 1,2...„Н и приэнаковый выход 11 (Н вЂ” число переставляемых элементов), Блок 1 предназначен для формирования определяющего множества чисел в соответствии с шагом работы устройства, выбора минимального числа иэ этого множества и подачи его на вход блока декодирования.

Блок 1 содержит схему выбора минимального числа 12, дешифратор 13, регистры 14а, ключи 15а, элемент задержки 16 (а =

1,2„., Н).

1820394

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

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

Работа устройства основана на реализации процедуры преобразования заранее определенной последовательности чисел М (О, М < Hl), в соответствующую последовательность перестановок из Н элементов, Перед работой счетчик 4 обнуляется, в ячейки блока 3 заносятся числа

M (О "- "М < Hl) в последовательности определяемой пользователем, а в регистры 14а блока 1 вносятся числа исходного определяющего множества Ао = (1,2,...,Н}, причем число К (К =„ Ао) вносится в регистр 14», Работа формирователя начинается подачей импульса на вход запуска устройства 9. При этом импульс поступает на счетный вход счетчика 4 и вход элемента задержки 7. Содержимое счетчика увеличивается и на первом шаге устройства становится равным единице. Код единицы с выходов счетчика парафазно поступает на входы регистра 5.

Через время задержки г1, определяемое элементом 7, импульс с его выхода поступает на вход элемента задержки 8 и на вход записи регистра 5 и код единицы поступает с его выходов на вход дешифратора 6. При этом сигнал единичного .уровня с первого выхода дешифратора поступает на считывающий вход первой ячейки памяти блока 3 и число M. соответствующее номеру первой перестановки в последовательности перестановок, определенной пользователем, поступает с информационного выхода блока 3 на информационные входы регистра 17 блока 2 декодирования. Через время г2 сигнал с выхода элемента задержки 8 поступает на тактовый вход блока 2 декодирования и начинается работа устройства по формированию перестановки, соответствующей первому значению числа M. При этом импульс с тактового входа блока 2 поступает на вход считывания регистра 17, управляющий вход блока деления 20» и вход элемента задержки 24 . Число М с информационного выхода регистра 17 поступает на вход блока деления на постоянный модуль 20н..

Блоки деления 20а осуществляют деле5 ние чистка. поступающего на их вход, на модуль Pa= Н вЂ” а + 1. При этом с первого выхода схемы деления выдается целая часть от деления поступающего на ее вход числ@ на соответствующий данной схеме постоян10 ный модуль, а со второго — остаток от деления. Поэтому при поступлении нв управляющий вход блока 20>< импульса а нем осуществляется деление числа М, п0ступившего на его вход с информационногб

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

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

30 с первых выходов блоков деления 20а, В = H, 2 соответственно, В результате чего остатки от процедур деления записываются в регистры 18а, а = 1,Н. Через время

Т> = Н гз+ г1 + гг от момента подачи импуль35 са на тактовый вход устройства 9 импульс с выхода элемента задержки 24> поступает на вход элемента задержки 251, считывающий вход регистра 181, управляющий вход ключа

26> и один из входов элемента ИЛИ 22, С

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

В схеме 12 осуществляется выбор мини50 мального числа и его код с выхода схемы 12 поступает на входы ключей 26а, а 1.Н. Так как при этом сигнал высокого уровня присутствует только на управляющем входе ключа 261, то код минимального числа исходного определяющего множества Ао через его информационную цепь поступает на вход сумматора 21, на другой вход которого поступаетчисло с регистра 181. В сумматоре

211 осуществляется сложение чисел, поступивших на его входы и код суммы поступает

1820394 на информационный вход регистра 191 и вход элемента ИЛИ 23. С выхода элемента

ИЛИ 23 код суммы поступает на вход элемента задержки 16 блока 1 управления. Через время задержки г4. большее длительности импульса запуска, код суммы через элемент задержки поступает на вход дешифратора, где он дешифрируется и сигнал с соответствующего выхода поступает на вход одного из ключей 15а, в = 1,Н (величина суммы на выходе сумматоров 21а, а I,Н принадлежит множеству первых Н чисел натурального ряда). К этому моменту сигнал высокого уровня уже снят со считывающих входов регистров 14а, а = 1,Н и управляющего входа ключа 26 . Через время задержки г5 > г4 сигнал высокого уровня поступает с выхода элемента задержки 25 на считывающий вход регистра 182. управляющий вход ключа 262, вход элемента задержки 252 и соответствующий вход элемента WIN 22. С выхода элемента ИЛИ

22 сигнал поступает на входы разрешения считывания регистров 14а блока 1. Однако теперь, когда на управляющем входе одного из ключей 15а, а = 1,Н присутствует сигнал высокого уровня, на входы схемы выбора минимального числа 12 не поступает число исходного определяющего множества равное сумме, полученной в сумматоре 21>.

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

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

Формула изобретения

Устройстводля перебора перестановок, содержащее первый регистр, первую. вторую и третью группы из и регистров (n — длина перестановок), первую и вторую группы ключей, первую и вторую группу элементов задержки. два элемента ИЛИ, блок выбора минимального числа, первый де55 и два элемента задержки, причем вход запуска устройства соединен с входом второго элемента задержки и счетным входом счетчика, выход разрядов которого соединен с информационными входами второго регистра, вход записи котсрого объединен с выхо10

40 шифратор. первый элемент задержки, и блоков деления и п сумматоров, выход i-го регистра первой группы соединен с информационным входом I-го ключа первой группы (i = 1,п). управляющий вход которого соединен с соответствующим выходом дешифратора, информационный вход которого соединен с выходом первого элемента задержки, выход 1-го ключа первой группы соединен с i-и входом блока выбора минимального числа, выход которого соединен с объединенными входами ключей второй группы, информационный вход J-ro блока деления / = 1...(n — 1) соединен с первым выходом (1+1)-го блока деления, тактовый вход

J-ro блока деления соединен с входом J-го элемента задержки первой группы и с выходом (J+1)-го элемента задержки первой группы, второй выход 1-ro блока деления соединен с информационным входом 1-го регистра второй группы (i =- 1,n), выход первого регистра соединен с информационным входом и-го блока деления, тактовый вход которого соединен с входом и-го элемента задержки первой группы, с входом разрешения считывания первого регистра, вход разрешения считывания 1-го регистра второй группы соединен с выходом (1 — 1)-го элемента задержки второй группы, с входом

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

ИЛИ, выход i ãî регистра второй группы соединен с первым входом 1-го сумматора группы, второй вход которого соединен с выходом I-ro ключа второй груг пы, выход

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

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

1820394

Составитель А. Бабаев

Редактор С. Кулакова Техред M.Mîðãåí Tàë Корректор Н. Король

Заказ 2031 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж 35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 дом второго элемента задержки и с входом третьего элемента задержки, а выходы соединены с соответствующими входами дешифратора, выходы дешифратора соединены с адресными входами блока памяти, выходы которого соединены с информационными входами второго регистра, вход разрешения считывания которого соединен с выходом третьего элемента задержки, выход n-ro элемента задержки второй

5 группы соединен с выходом конца работы устройства.