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

 

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

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

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

РЕСПУБЛИК (19) (11) (511 4 (06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ гб; гвму

2Áö

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А STOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4169496/24-24 (22) 03. 11. 86 (46) 15. 07. 88. Бюл. 1(- 26 (72) О. Г.Алексеев, А.А.Бабаев и Н.И.Ячкула (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 1190388, кл. G 06 F 15/20, 1984.

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

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

Цель изобретения — повышение быстро действия устройства. за счет упрощения алгоритма перебора перестановок. Устройство содержит блок управления (БУ)

1 и блок декодирования (БД) 2. БУ содержит и регистров (Р) 3 и ключей (1() 6, дешифратор 4, элемент задержки 7 и схему выбора минимального числа 5. Входы БУ соединены с выходами

БД, а выход БУ соединен с входам БД.

Устройство реализует процедуру однозначного преобразования числа m (О

z m(n) в соответствующую ему-перестановку исходных величин, Данная процедура существенно упрощает управление очередностью следования перестановок; чем повышает удобства в эксплуатации устройства. 1 ил.

1410056 2

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

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

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

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

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

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

Работа устройства основана на реализации процедуры преобразования исходного числа m(0 m

Перед работой параллельным кодом в регистры 3, i=1,п блока 1 вносятся

1 числа исходного определяющего множества IО= 1,...,nj, причем число

К (1 E I ) вносится в регистр 3, а в

tC регистр 11 блока 2 вносится число 1ъ.

Работа устройства начинается подачей положительного импульса запуска на вход пуска устройства 18 блока 2.

При этом импульс запуска поступает на вход считывания регистра 11, управляющий вход блока деления на пос тоянный модуль 14 и вход элемента

:задержки 16>. Число m с информацион5

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

Блоки деления 14 - осуществляют

\ деленив числа, поступающего на их вход, на модуль r. =и-i+1.Ïðè этом с первого выхода схемы деления выдается целая часть от деления поступающего на ее вход числа на соответствующий данной схеме постоянный модуль, а с второго — остаток от деления., Поэтому при поступлении на управляющий вход блока 14 „ импульса в ней осуществляется деление числа, посту" пающего на ее вход с информационного выхода регистра 11, на число т„. Целая часть от деления поступает с первого выхода блока 14 на вход блока деления 14, а остаток от деления

il-1 с второго выхода блока 14„поступает на информационный вход регистра 121 .

Через времяТ,, большее чем время работы схемы 14., импульс с выхода

1 элемента задержки 1611 поступает на упфавляющий вход блока деления 14„, и вход элемента задержки 16

Далее аналогичным образом, последовательно через интервалы времени

7 блоками 14, j=n-1 1 осуществляется выделение целой части и остатка от деления на постоянный модуль чисел, поступающих с первого выхода блока деления 14;, i=n,2 соответственно. В результате чего остатки от процедур деления записываются в регистрах 12;, i=1,п. Через время

=n от момента подачи импульса за 4 пуска на вход пуска устройства 18 импульс с выхода элемента задержки

16 1 поступает на элемент задержки

17„, считывающий вход регистра 12 управляющий вход ключа 21„ и один из входов элемента ИЛИ 19. При этом содержимое регистра 12 1 с его информационного выхода поступает на вход сумматора 15,. С выхода элемента ИЛИ

19 сигнал уровня "1" через управляющий выход 23 блока 2 и управляющий вход 8 блока 1 поступает на вход разрешения считывания данных регистров

3., i=1 и. Числа исходного определяющего множества Х .с информационных выходов этих регистров через информационные пепи соответствующих ключей

6„, i=1,п поступают на входы схемы вйбора минимального числа 5. В схеме

5 осуществляется выбор минимального числа и код соответствующий этому з 141 числу с выхода схемы 5, через выход

10 блока 1, второй информационный вход 22 блока 2 поступает на информационные входы ключей 2 1;, i=i,"è. Так

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

13 и один из входов элемента ИЛИ 20, с выхода элемента ИЛИ код суммы через информационный выход 24 блока 2 и информационный вход 9 блока 1 поступает на вход элемента задержки 7.

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

15;, i=1,п принадлежит множеству первых и чисел натурального ряда). К этому моменту сигнал высокого уровня уже снят со считывающих входов реги-.. стров 3, i=1,п и управляющего входа ключа 21 ° Через время з держки lú ф

3 сигнал высокого уровня поступает с входа элемента задержки 17, на считывающий вход регистра 122 управляющий вход ключа 21, вход элемента задержки 17 и соответствующий-вход . элемента ИЛЙ 19. С входа элемента

ИЛИ 19 сигнал через управляющий выход 23 блока 2 и управляющий вход 8 блока 1 поступает на. входы разрешения считывания данных регистров 3

=1,п. Однако теперь, когда на управляющем входе одного из ключей 6>, =1,п присутствует сигнал высокого уровня, на входы схемы выбора мини,мального числа 5 не поступает число исходного определяющего множества I, рй равное сумме, полученной в сумматоре 15 . Дальнейшая работа схемы бу1 дет аналогична и через время t =t. + ф

+n а от момента подачи импульса за3. пуска сигнал высокого уровня с выхода элемента задержки 17 поступает на входы разрешения считывания данных регистров 13„, i=.1,п и числа, соот-. ветствующие полученной перестановке, пос гупают на их входы, являющиеся

0056

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

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

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

25 i-. го ключа первой группы (i 1,n), управляющие входы которых соединены с соответствующими выходами дешифратора, информационный вход которого соединен с выходом элемента задержки, З0 выход i-ro ключа первой группы соединен с i-м входом схемьь выбора минимального числа, информационный вход устройства соединен с инфорМационным входом регистра, выход которого соЕ .

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

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

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

50 группы соединен с выходом (1.— 1 )-го элемента задержки второй группы, с входом i-ro элемента задержки второй группы, с управляющим входом &го

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

Составитель С. Кошелев

Редактор О.Спесивых Техред А.Кравчук Корректор О. Кравцова

Заказ 3482/46 Тираж 704 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5.Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

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