Устройство для перебора перестановок Советский патент 1988 года по МПК G06F7/06 

/8

4

сл

Од

2S.

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

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

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

Устройство содержит блок 1 управления и блок 2 декодирования.

Блок 1 предназначен для формирования определяющего множества чисел в соответствии с выбранным вариантом перестановки и шагом работы устрой- . ств а, выбора минимального числа из этого множества и подачи его на вход блока де1 одирования. Блок 1 содержит регистры 3, ,п, дешифратор 4, схему выбора минимального числа 5, ключи 6., ,п, элемент задержки 7, управляющий вход 8, информационный вход 9 и 10.

Блок 2 предназначен для преобразования заданного натурального числа в соответствующую ему перестановку. Блок 2 содержит регистры 11, 12/, 13, блоки деления , сумматоры 15, элементы задержки 16 i ЗД пуска устройства 18, элементы ИЛИ 19 20, ключи 21-, второй информационный вход 22, управлякмций выход 23, ин- формационньй выход 24, информационный вход устройства 25 и группу информационных выходов устройства 26 (1 1,п).

Работа устройства основана на реализации процедуры преобразования ис- ходногс числа m() в однозначно соответствующую ему перестановку исходных, предварительно пронумерованных числами 1,2,...,п, элементов.

Перед работой параллельным кодом в регистры 3-, ,и блока 1 вносятся числа исходного определяющего множества ,... ,nj, причем число k (k IQ) вносится в регистр 3 , а в регистр 11 блока 2 вносится число т. Работа устройства начинается подачей положительного импульса запуска на вход пуска устройства 18 блока 2. При этом импульс запуска поступает на вход считывания регистра 11, управляющий вход блока деления на пос- тоянный модуль 14 и вход элемента задержки 16. Число m с информацион10

5

0

5

0

5

0

5

0

5

ного выхода регистра 11 поступает на вход блока деления на постоянный модуль .

Блоки деления 14- осуществляют деление числа, поступающего на их вход, на модуль г. .При этом с первого выхода схемы деления вьща- ется целая часть от деления поступающего на ее вход числа на соответствующий данной схеме постоянный модуль, а с вторбго - остаток от делелия.. Поэтому при поступлении на управляющий вход блока 14 импульса в ней осуществляется деление числа, поступающего на ее вход с информационного выхода регистра 11, на число г . Целая часть от деления поступает с первого выхода блока 14, на вход блока деления 14 , а остаток от деления с второго выхода блока 14 поступает на информационный вход регистра 12. Через время Т , большее чем время работы схемы 14- , импульс с выхода элемента задержки 16ц поступает на ущзавлятощий вход блока деления 14. и вход элемента задержки 16 ,

Далее аналогичным образом, последовательно через интервалы времени Т. блоками 14j,,1 осуществляется выделение целой части и остатка от деления на постоянный модуль чи- сел, поступающих с первого выхода блока деления 14, ,2 соответственно. В результате чего остатки от процедур Деления записываются в регистрах 12, ,п. Через время Ц п 6 от момента подачи импульса запуска на вход пуска устройства 18 импульс с выхода элемента задержки 16 поступает на элемент задержки 17, считывающий вход регистра 12, управляющий вход ключа 21 и один из входов элемента ИЛИ 19. При этом содержимое регистра 12 с его информационного выхода поступает на вход сумматора 15,. С выхода элемента ИЛИ 19 сигнал уровня 1 через управляющий выход 23 блока 2 и управляющий вход В блока 1 поступает на вход раз- решения считывания данных регистров 3:-, ,п. Числа исходного определяющего множества I с информационных выходов этих регистров через информа- ционные цепи соответствующих ключей 6-, ,п поступают на входы схемы выбора минимального числа 5. Вi схеме 5 осуществляется выбор минимального числа и код, соответствующий этому

числу с выхода схемы 5, через выход 10 блока 1, второй информационный вход 22 блока 2 поступает на ннформа- ционные входы ключей 21:, . Так как при этом сигнал высокого уровня минимального числа исходного определяющего множества-через, его информационную цепь поступает на вход сумматора 15,. В сумматоре,15 осуществГ

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

Устройство для перебора перестановок, содержащее первую группу из п регистров, первую группу из (п-«-1) ключей (п - длина перестановок), эл мент задержки, первый и второй элементы ИЛИ, от л и Ч а ю ц е е с я тем, что, с целью повышения быстродействия устройства за счет упрощ&н

с выхода элемента ИЛИ код суммы через 5 алгоритма перебора перестановок, в

информационный выход 24 блока 2 и информационный вход 9 блока 1 поступает на вход элемента задержки 7. Через время Т, ,, большее длительности импульса запуска, код суммы через элемент задержки поступает на вход дешифратора 4, где он дешифруется, , и сигнал с соответствующего дайной сумме выхода поступает на управляющий

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

вход соответствующего ключа

6.,.

,п

(величина суммы на выходе сумматоров 15, ,п принадлежит множеству первых п чисел натурального ряда). К этому моменту сигнал высокого уровня уже снят со считывающих входов региг стров 3j, ,n и управляющего входа ключа 21, Через время задержки t сигнал высокого уровня поступает с входа элемента задержки 17 на считывающий вход регистра 12, управляю21

вход элемента

щий вход ключа

задержки 172И соответствующий-вход элемента ИЛИ 19. С входа элемента ИЛИ 19 сигнал через управляющий выход 23 блока 2 и управляющий вход 8 блока 1 поступает на входы разрешени считывания/данных регистров 3(, 1

1,п. Однако теперь, когда на управляющем входе одного из ключей 6; ,

,п присутствует сигнал высокого уровня, на входы схемы выбора мини- .мального числа 5 не поступает число исходного определяющего множества 1 равное сумме, полученной в сумматоре 15. Дальнейшая работа схемы будет аналогична и через время t fn T .jOT момента подачи импульса запуска сигнал высокого уровня с выход элемента задержки 17 поступает на входы разрешения считывания данных регистров 13, .1.1,п и числа, соот-. ветСтвующие полученной перестановке, пос упают на их входы, являющиеся

группой информационных выходов устройства 26.

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

Устройство для перебора перестановок, содержащее первую группу из п регистров, первую группу из (п-«-1) ключей (п - длина перестановок), элемент задержки, первый и второй элементы ИЛИ, от л и Ч а ю ц е е с я тем, что, с целью повышения быстродействия устройства за счет упрощ&ния

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

,п 25 i-ro ключа первой группы (,п).

0

5

0

5

0

5

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

514100566

соединен с первым входом i-ro cy tMa-ся i-м информационным выходом устройтора группы, второй вход которого со-ства, входы разрешения считывания

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

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

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

с входом, элемента задержки, выходпервого элемента ИЛИ и с выходом перi-ro-регистра третьей группы являет-вого элемента задержки первой группы.

Изобретение относится к области вычислительной техники, предназначено для формирования в произвольной последовательности перестановок из п величин и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Цель изобретения - повышение быстродействия устройства.за счет упрощения алгоритма перебора перестановок. Устройство содержит блок управления (БУ) 1 и блок декодирования (БД) 2. зУ содержит п регистров (Р) 3 и ключей (К) 6, дешифратор 4, элемент задержки 7 и схему выбора минимального числа 5. Входы БУ соединены с выходами БД, а выход БУ соединен с входом БД. Устройство реализует процедуру однозначного преобразования числа 1П (0 m-tn) в соответствующую ему-.перестановку исходных величин. Данная проце- дура существенно упрощает управление очередностью следования перестановокj чем повышает удобства в эксплуатации устройства. 1 ил. с S