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

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

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

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

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

21 элементов И, элемент И 22, элементы 23-25 задержки, установочный вход 26, пусковой вход 27, П1)следователь- ный 28 и параллельный 29 информационные выходы и выход 30 окончания перебора.

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

Х;Р

где j - rest(A./(N-i+l)) 1;

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

А, А% А; - ent(A ;., /(N-i)), i 2, ..., N; A - целое число в интервале от О до N -1; pj Р , Р 1, 2, ..о, N}. Р , - ,.., /р J- ,

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

Перед началом работы 2 устанавливается в нулевое состояние, в счетчик 3 заносится код числа N сигналом с входа 26 Начальная установка. По

25

21-1 - 21-N и через элементы ИЛИ 12-1 12-R (где К log()) на регист 6-1. С выходов элементов ИЛИ 12-1 - 12-R выдаются перестановки в последов тельном коде. Импульсы с выхода дешифратора 4 задерживаются в соответ6-1 - 6-N сдвигается на R разрядов вправо, и Через соответствуюш 1е элементы ШШ 11-1 - 11-N содержимое реги CTpt B 5-1 - 5-N, начиная с номера регчстра, с которого произошла передача информации в регистр 6-1, сдви- 1 ается на R разрядов влево.

По окончании операции сигнал с

сигналу с шины 27 Пуск регистры ствующем элементе 25-1 - 25-N, через 5-N устанавливаются в начальное состо- элемент Ш1И 13 содержимое регистров яние, а именно: в регистр 5-1 заносится код числа единицы, в регистр 5-i код числа i, в регистр 5-N - код числа N. Содержимое счетчика 2 через 35 элементы И 17-1 - 17-К и элементы ИЛИ

10-1 - 10-К (где К log(Nl-l)) подается на первую группу входив AejiHтеля 1, являющуюся входом делимого

числа. На вторую группу входов дели- выхода элемента И 18 уменьшает содертеля подано содержимое счетчика 3. жимое счетчика 3 на единицу и через

По сигналу с выхода элемента 23 за- -держки через элемент 9 и элемент И 22

начинается выполнение операции деления

числа поданного на первую группу плодов

делителя,на число,поданное на вторую

группу входов. По окончании операции

деления по сигналу с выхода делителя

операции остаток от деления

поступает на вход дешифратора 4, а

45

50

элемент 24 задержки, элемент ИЛИ 9 и элемент И 22 поступает на вход Начало операции делителя. Вьтолняется операция деления целой части от первого деления на величину N-1, Дальнейшая работа устройства происходит аналогично. После N-ro деления (т.е. деления на число 1) на регистрах 6-1 - 6-N будет находиться сформи рованная перестановка. Когда состоя- лие счетчика 3 равно единице, то на выходе элемента ИЛИ 14 - нулевой сигнал, который запрещает прохождение

целая часть от деления через элементы И 19-1 - 19-К и элементы ИЛИ 10-1 - 10-К - на первую группу входов делите ля 1, По сигналу с выхода, соответэлемент 24 задержки, элемент ИЛИ 9 и элемент И 22 поступает на вход Начало операции делителя. Вьтолняется операция деления целой части от первого деления на величину N-1, Дальнейшая работа устройства происходит аналогично. После N-ro деления (т.е. деления на число 1) на регистрах 6-1 - 6-N будет находиться сформи рованная перестановка. Когда состоя- лие счетчика 3 равно единице, то на выходе элемента ИЛИ 14 - нулевой сигнал, который запрещает прохождение

ствующего величине остатка, дешифра-55 сигнала Конец операции через эле- тора 4 содержимое соответствующего мент И 18, через элемент НЕ 13 уве- регистра 5-1 - 5-N передается через личивает состояние счетчика 2 на соответствующую группу элементов И единицу, заносит в счетчик 3 код чис2,

N.

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

6-1 - 6-N сдвигается на R разрядов вправо, и Через соответствуюш 1е элементы ШШ 11-1 - 11-N содержимое реги CTpt B 5-1 - 5-N, начиная с номера регчстра, с которого произошла передача информации в регистр 6-1, сдви- 1 ается на R разрядов влево.

По окончании операции сигнал с

ствующем элементе 25-1 - 25-N, через элемент Ш1И 13 содержимое регистров

выхода элемента И 18 уменьшает содер

элемент 24 задержки, элемент ИЛИ 9 и элемент И 22 поступает на вход Начало операции делителя. Вьтолняется операция деления целой части от первого деления на величину N-1, Дальнейшая работа устройства происхоt дит аналогично. После N-ro деления (т.е. деления на число 1) на регистрах 6-1 - 6-N будет находиться сформированная перестановка. Когда состоя- лие счетчика 3 равно единице, то на выходе элемента ИЛИ 14 - нулевой сигнал, который запрещает прохождение

сигнала Конец операции через эле- мент И 18, через элемент НЕ 13 уве- личивает состояние счетчика 2 на единицу, заносит в счетчик 3 код чис515

jia N и через элеме ты ИЛИ 8 и задержки 23 запускает схему на получение перестановки, соответствующей новому состоянию счетчика 2. Если содержимое счетчика 2 равно числу N ,, то на выходе элемента И 16 появляется сигнал Конец работы, киторьв запрещает прохождение сигналов на вход Начало операции делителя.

Таким образом, изменяя содержимое счетчика 2 от О до N1-1, получают вс возможные перестановки из N чисел.

Рассмотрим работу устройства при получении всех возможных перестановок из трех чисел (N 3), 3 этом случае К log,5 t 3; R Iogj3 С 2.

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

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

Устройство для перебора перестановок, содержащее две группы регистров, делитель, дешифратор, четыре элемента ИЛИ, два элемента задержки. Группу элементов задержки, причем выходы регистров первой группы являются параллельным информационным выходом устройства, отличающееся тем, что, с целью упрощения устройства и расширения его функциональных возможностей за счет формирования всех возможных перестановок, оно содержит два счетчика, пятый элемент ИЛИ, три элемента И, элемент НЕ, три группы элементов ИЛИ 3+N групп элементов И (где N - число элементов в перестановках), причем, первый вход первого элемента ИЛИ является пусковым входом устройства, выход первого элемента ИШ1 через первый элемент задержки подключен к входам начальной установки всех регистров второй группы, к первому входу второго элемента ИЛИ и к первым входам всех элементов И первой группы i-й разрядный выход первого счетчика (i 1,К,где К 1 log()t) под- ключен к i-му входу первого элемента И и к второму входу i-ro элемента И первой группы, выход i-ro элемента И первой группы подключен к первому входу i-го элемента ИЛИ первой группы, выходы элeмeнт(JЦ ИЛИ первой группы соединены с соитветствующими раз-i рядными входами делимс1го делителя.

86

разрядные -выходы BTopoi o счетчика соединены с соответствующими разрядными Бх -)дами делителя, i-й разрядньи выход целой части результата делителя подключен к первому входу i-ro элемента И второй группы, выход которого подключен к второму входу i-ro элемента Ш первой группы, i-й разрядный выход

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

входу элемента НЕ, выход элемента НЕ подключен к второму входу первого элемента ИЛИ, к суммирующему счетному входу первого счетчика и к первому в/оду четвертого элемента ИЛИ, выход

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

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

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

и подключен к инверсному входу третьего элемента И, выход третьего элемента И подключен к входу начала операции делителя, выход конца операции делителя подключен к второму входу

второго элемента И, выходы элементов И третьей группы подключены к соответ- ствуюцщм в ходам дешифратора j-й выход дешифратора (j 1,Н) подключен к первым входам всех элементов И(j +3)-й|

группы и к входу j-ro элемента задержки группы, выход j-ro элемента задержки группы подключен к j-му вхо- ДУ с j-ro по N-Й элементов ИЛИ второй группы, выход j-ro элемента ИЛИ второй

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

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

ИЛИ третьей группы, выходы элементов ИЛИ третьей Группы являются последовательными разрядными выходами устройства и соединены с соответствующими раэрядными входами первого регистра первой группы, разрядные выходы j-ro регистра первой группы, кроме N-ro регистра, подключены к соответствующим разрядным вхбдам (j+O-ro регистра первой группы.