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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при решении комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Цель изобретения - упрощение устройства и расширение его функциональных возможностей за счет формирования всех возможных перестановок. Устройство содержит делитель 1, счетчики 2, 3, дешифратор 4, регистры 5, 6, элементы ИЛИ 7-14, НЕ 15, И 16-20, 22, задержки 23-25, группы 21 элементов И. Упрощение устройства достигнуто благодаря исключению из его состава N-1 делителей, сумматоров и группы регистров. При этом обеспечена возможность формирования любых перестановок из N элементов, что расширяет функциональные возможности устройства. 1 ил., 1 табл.

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

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

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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4413551/24-24 (22) 09.02.88 (46) 23. 10.89. Бюл. N 39 (72) A.А.Бабаев, В.Д.Киселев, Г.П.Иировицкий и H.À.Ðóñàíîâ (53) 681 ° 3(088.8) (561 Авторское свидетельство СССР

ll 1180917, кл. G 06 F 15/20, 1981 °

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

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

„„SU„„1517038 А1 последовательностей. Цель изобретения - упрошение устройства и расширение его функциональных возможностей за счет формирования всех возможных перестановок. Устройство содержит делитель 1, счетчики 2, 3, дешифратор 4, регистры 5, 6, элементы

ИЛИ 7-14, НЕ 15, И 16-20, 22, задержки 23-25, группы 21 элементов И.

Упрошение устройства достигнуто благодаря исключению иэ его состава

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

1 ил., 1 табл.

1517038

10 ется из выражения

> х;р., где j rest(А /(N-i+1)} + 1;

А, А, А; ent(A;, /(N-i)), i 2, ..., N;

А — целое число в интервале от 0 до М -1;

ФPl P, P 11» 2» ..., Nf» P> Р;, /P„. » i = 2» ..., N °

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

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

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

Устройство содержит делитель 1, счетчики 2 и 3, дешифратор 4, регистры 5 и 6, элементы ИЛИ 7-14, элемент

НЕ 15, элементы И 16-20, группы

Устройство для перебора перестановок работает следующим образом.

Перед началом работы 2 устанавливается в нулевое состояние, в счетчик 3 заносится код числа N сигналом с входа 26 "Начальная установка"„ По сигналу с шины 27 "Пуск" регистры 5-! -30

5-N устанавливаются в начальное состояние, а именно: в регистр 5-1 заносится код числа единицы, н регистр 5-) код числа i в регистр 5-N — код числа N. Содержимое счетчика 2 через 35 элементы И 17-1 — 17-K и элементы И>1И

10-1 — 10-К (где K = 7 log>(N l — l )() подается на первую группу входов делителя 1, являющуюся входом делимог.> числа, На вторую группу входов делителя подано содержимое счетчика 3.

11v сигналу с выхода элемента 23 за-держки через элемент ViJIIi 9 и элемент И 22 начинается выполнение операции деления числа поданного на первую группу входов

45 1 делителя,на число, поданное на вторую группу входов. По окончании операции деления по сигналу с выхода делителя

"1 >нец операции" остаток от деления поступает на вход дешифратора 4, а

50 целая часть от деления через элементы

И 19-1 — 19-К и элементы ИЛИ 10-1

10-К вЂ” на первую группу входов делителя 1. По сигналу с выхода, соответствующего величине остатка, дешифратора 4 содержимое соответствующего регистра 5-1 — 5-N передается через соответствующую группу элементов И

21 элементов И, элемент И 22, элементы ?3-25 задержки, установочный вход

26, пу> коной вход 27, последовательный 28 и параллельный 29 информационные ныходь> и выход 30 окончания перебора.

Принцип действия устройства основывается на том, что все возможные перестановки из Н чисел можно получить, применив И-шаговую вычислительную процедуру: i-й элемент пере,становки (i 1, 2, ..., N) определя21-1 — 21-1>1 и через элементы ИЛИ 12-1

12-R (где К 7 log g(N!-1)() на регистр

6-1. С выходов элементов ИЛИ 12-1

12-R выдаются перестановки в последовательном коде. Импульсы с выхода дешифратора 4 задерживаются в соо тветствующем элементе 25-1 — 25-N, через элеме>нт ИЛИ 13 содержимое регистров

6-1 — 6-N сдвигается íà R разрядов вправо, и через соответствующие элементы ИЛИ ll — i — ll-N содержимое регистр>..в 5-1 — 5-N, начиная с номера рег истра, с которого произошла передача информации в регистр 6-1, сдвигается иа R разрядов влево.

II<> окончании операции сигнал с выхода элемента И 18 уменьшает содержимое счетчика 3 на единицу и через элемент 24 задержки, элемент ИЛИ 9 и элемент И 22 поступает на вход "Начало операции" делителя. Выполняется операция деления целой части от первого деления на величину N-l.

Дальнейшая работа устройства происхо-> дит аналогично. После N-го деления (т.е. деления на число 1) на регистрах 6-1 — 6-N будет находиться сформи" рованная перестановка. Когда состоя.ние счетчика 3 равно единице, то на выходе элемента ИЛИ 14 — нулевой сигнал, который запрещает прохождение сигнала "Конец операции" через элемент И 18, через элемент НЕ 15 увеличивает состояние счетчика ? на единицу, заносит в счетчик 3 код чис5 1512!!3Я ла N и через эл менты 1!ЛИ 8 и задержки 23 запускает схему на получение перестановки, соответствующей новому состоянию счетчика 2. Если содержи5 мое счетчика 2 равно числу И,, то на выходе элемента И 16 появляется сигнал "Конец рабс ты", к< торый запрещает прохождение сигналов на вход Начало операции делителя. 10

Таким образом, vçìåèÿÿ содержимое счетчика 2 от О до N! -1, получают все возможные перестановки из N чисел.

Рассмотрим работу устройства 1 при получении всех возможных пере- 15 становок из трех чисел (N 3). 3 этом случае К = 1 log.5 (= 3; R =

) 1од 3 2. в

Состояние основных элементов н устройства и возможные перестановки в приведены в таблице. п

Устройство для перебора перестановок, содержащее дье группы регистров, делитель, дешифратор, четыре элемента ИЛИ, два элемента задержки, группу элементов задержки, причем выходы регистров первой группы являются параллельным информационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и расширения его функциональных возможностей за счет формирования всех возможных перестановок, оно содержит два счетчика, пятый элемент ИЛИ, три элемента И, элемент НЕ, три группы элементов ИЛИ, 3+N групп элементов И (где N — число элементов в перестановках>, причем первый вход первого элемента ИЛИ является пусковым входом устройства, выход первого элемента ИЛИ через первый элемент задержки подключен к входам начальной установки всех регистров второй группы, к первому входу второго элемента ИЛИ и к первым входам всех элементов И первой группы

i-й разрядный выход первого счетчика (i = 1,k, где К = ) log (N 1-1)() подключен к -му входу первого элемента

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

55 разрядные -выходы в горого счетчика соединены с соответствующими разрядными входами делителя, ь-й разрядный выход целой части результата делителя подключен к первому входу ь-го элемен.а И второй группы, выход которого одключен к второму входу i-го элемента !!!!! первой группы, i-й разрядный выход достатка от деления делителя подключен к первому входу i-го элемента И третьей группы, разрядные выходы второго eò÷èêà, кроме выхода старшего разряда, подключены к соответствующим пряым входам третьего элемента ИЛИ, инверсный вход которого соединен со старшим разрядным выходом вгорого счетчика, ыход третьего элемента ИЛИ подключен первому входу второго элемента И и к ходу элемента НЕ, выход элемента HE одключен к второму входу первого элемента ИЛИ, к суммирующему счетному входу первого счетчика и к первому в оду четвертого элемента ИЛИ, выход кот >рого подключен к входу начальной установки второго счетчика, второй вход четвертого элемента ИЛИ соединен с входом начальной установки первого счетчика и является установочным входом устройства, выход второго элемента И подключен к вычитающему счетному входу второго счетчика, к вторым входам всех элементов И второй и третьей групп и через второй элемент задержки к второму входу второго элемента HJIH, выход которого подключен к прямому входу третьего элемента И, выход первого элемента И является выходом окончания перебора устройства и подключен к инверсному входу третьего элемента И, выход третьего элемента И подключен к входу начала операции делителя, выход конца операции делителя подключен к второму входу второго элемента И, выходы элементов

И третьей группы подключены к соответствующим входам дешифратора 3-й выход дешифратора (j 1,1!) подключен к первым входам всех элементов И (3+3)-й группы и к входу j --ro элемента задержки группы, выход !-го элемента задержки группы подключен к j-му входу с j -го по N-й элементов ИЛИ второй группы, выход j-ro элемента ИЛИ второй группы подключен к сдвигающему входу

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

1517038 к сдвигающему входу каждого регистра первой группы, разрядные выходы 1го регистра второй группы (1 2,N) подключены к соответствующим разрядным входам (1-1)-ro регистра второй группы, ш-й разрядный выход (m

1,К, где R ) log N() j-го регистра второй группы подключен к второму входу m-ro элемента И (j+3) "й группы, !0 выход m-ro элемента И (j+3)-.é группы подключен к j-му входу m-го элемента

Перестановка

Состояние счетчиков

Состояние регистров

Номер деления

6-3 5-1 5-2 5-3

6-1 6-2

2 3

0 1 0 О 1 2

0 2 1 0 2 3

0 3 2 1 3 О

,0 3

3

О

0 Первая

0 2 0 О 1 2

0 1 2 О . 3

0 3 2 3 О

О

0 Вторая

1 3

0 3 О О i 2

О 1 3 0 2

0 2 1 3 2 0

О

О Третья

2 3.2

3 3

1! О 0 1 2

3 1 0 2 3

2 3 1 2 О

О

О Четвертая

0

2 О 0 1 2

3 2 0 3

1 3 2 1 О

4 3

3

О

О Пятая

2

3 О 0 1 2

2 3 О 1 2

1 2 3 1 О

О

О Шестая

5 3

Составитель В. Байков

Техред J1,0ëèèíbtê Корректор В. Гирняк

Редактор О.Юрковецкая

Заказ 6392/52

Тираж 668

Подписное

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

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

Производственно-издательский ком(гниат "1!атент", г.ужгород, ул. Гагарина,101

Число н первой группе выходов делител

ИЛИ третьей группы, выходы элементов

ИЛИ третьей группы являются последовательными разрядными выходами устройства и соединены с соответствующими разрядными входами первого регистра первой группы, разрядные выходы

)-го регистра первой группы, кроме

N-го регистра, подключены к соответствующим разрядным вхЬдам (j +1)-го регистра первой группы.