Устройство для генерирования перестановок и сочетаний Советский патент 1987 года по МПК G06F17/10 

1

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

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

На фиг.1 показана блок-схема устройства для N 4, К 2,3; на фиг.2 функциональная схема блока управления .

Устройство содержит (фиг.1) два регистра 1 и 2 сдвига, регистры 3 числа, реверсивньй кольцевой регистр 4 сдвига, ключи 5, элементы ИЛИ 6, генератор 7 тактовых импульсов, элемент 8 задержки, блок 9 управления, первую группу 10 переключателей, вторую группу 11 переключателей,дополнительные элементы ИЛИ 12, группы 13 элементов И.

-. Устройство имеет выходы 14 перестановки, выходы 15 сочетания, вход 16 начальной установки, выход 17 признака окончания работы.

Блок 9 управления содержит регистры 18 сдвига, группу 19 триггеров, группу 20 элементов запрета, группу 21 элементов И, группу 22 элементов ИЛИ, два элемента 23,24 задержки и элемент ИЛИ 25.

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

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

Генерирование перестановок. Переставляемые числа находятся в регистрах 3 числа и считываются по выходам 14. Передача чисел от одного регистра к другому производятся через ключи 5. При наличие сигнала на первом (втором) управляющем входе ключа он пропускает на выход число с первого (в.торого) информационного входа.

Генерирование перестановок может происходить в двух режимах: первый режим - задание произвольного чередования перестановок (замкнут первый переключатель группы второй режим - автоматически производится полный перебор всех возможных перестано3

IF

20

25

;|Q 632392

вок из N (замкнут второй переключа - тель Группы 1)о

Режим 1 .Все ключи управляются си1- налами с выходов реверсивного регистра 4 сдвига. При этом в реверсивном кольцевом регистре 4 сдвига содержится только одна 1, т.е. сигнал су-, ществует только на одном из выходов реверсивного кольцевого регистра 4 сдвига. Для рассматриваемого случая, когда N 4, используется трехразрядный реверсивный кольцевой регистр 4 сдвига.

При наличии сигнала на первом выходе реверсивного кольцевого регистра 4 сдвига все ключи 5 открыты по первому управляющему входу и из регистров 3 числа образуется кольцо, которое обозначим К.

При наличии сигнала на втором выходе реверсивного кольцевого регистра 4 сдвига первый ключ 5 закрыт, второй ключ 5 открыт по второму управляющему входу, третий ключ 5 открыт по первому управляющему входу. Вследствие этого из регистра 3 числа образуется кольцо, которое обозначим К2.

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

35 разуется кольцо, которое обозначим КЗ.

Выбирая то или иное кольцо, т„е. . формируя сигнал на том или инЪм выходе реверсивного кольцевого регист40 ра 4 сдвига, можно осуществлять заданную перестановку чиселс

Управление реверсивным кольцевым регистром 4 сдвига осуществляется кодами, заносимыми в регистры 1 и 2

45 сдвига. Эти коды задают характер перестановок. В качестве примера в таблице приведена частная последовательность перестановок, соответствующая ей последовательность состоя50 НИИ реверсивного кольцевого регистра 4 сдвига и первоначальных кодов в регистрах 1 и 2 сдвига.

Режим 2. Все ключи управляются сигналами с выходов блока 9 управле55 ния. Если необходим полный перебор всех перестановок, а также при большом значении N задание частной последовательности перестановок кодами регистров 1 и 2 сдвига трудоемко, за-:

30

мыкание второго переключателя второй группы 11 задает автоматический режим.

Предварительно по входу 29 начальной установки в блоке 9 управления происходит сброс в о регистров 18 сдвига и триггеров 19.

Первый тактовый импульс поступает на вход первого регистра 18 сдвига и появляется на первом выходе блока ключа 5. Происходит-перестановка КК

Второй и третий тактовые импульсы производят аналогичные действия.

Четвертый тактовый импульс проходит на выход первого регистра 18 сдвига (так как для случая N 4

1234 1423 1432 2143 2314 4231 4123 4132 2412 2341 2134 .4213 4321 4312 2431 1243 3124 3412

первый регистрсдвига имеет четыре разряда), на вход второго регистра 18 сдвига, устанавливает в 1 первый триггер 19 и, пройдя через элементы И 21 и ИЛИ 22, устанавливает в О первый регистр 18 сдвига.

Четвертый тактовый импульс, пройдя через элементы 23 и 24 задержки и элемент ИЛИ группы 22 устанавливает в О первый триггер 19.

Сигнал, появившийся на втором выходе блока 9 управления, соединенном с вторым входом третьего ключа 5, производит перестановку КЗ.

Пример частной последовательности перестановок

010 010 001 100 010 100 010 001 100 010 010 100 010 001 100 100 100 010

Пятый, шестой и седьмой тактовые импульсы производят перестановку К1 (аналогично первому, второму и третьему тактовым импульсам)«

Восьмой тактовый импульс с выхода второго регистра 18 сдвига, имеющего два разряда, проходит на вход третье г о регистра 18 сдвига, появляется на третьем выходе блока 9 управления и производит перестановку К2. Через элемент запрета группы 20 сигнал с второго выхода блока 9 управления устанавливает 1 второй триггер 19, сигнал с выхода которого через вторые элементы И и ИЛИ групп 21 и 22 устанавливает в О второй регистр 18 сдвига.

Восьмой тактовый импульсj пройдя через элементы 23 задержки и первые элементы И и ИЛИ групп 21 и 22, устанавливает в О первый регистр 18 сдвига, а пройдя через элементы 24 задержки и 22 ИЛИ, сбрасьшает первый триггер 19 в О,

Последующие тактовые импульсы повторяют работу, описанную выше.

Двадцать четвертый тактовый импульс появляется на выходе 17 признака окончания работы, так как в данном случае количество всех перестановок при N 4 равно N( - 2k,

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

формировании сочетаний. Например, если замкнут первый переключатель первой группы 10, то формируются сочетания 2 и 4, если замкнут второй, то формируются сочетания 3 и 4.

Режим работы задается переключателями второй группы 11, как и при формировании перестановок. В автоматическом режиме перебора все сочетания из N по К, где К N - 1, формируются за N тактов работыо

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

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

/1363239

выход которого соединен с информационным входом (i + O-rn регистра числа, выход (N-l)-ro регистра числа подключен к информацинному входу N-ro регистра числа, выход которого соединен с вторыми информационными входами с второго по (N-l)-ft ключей и с информационным входом первого ключа, выход которого подключен к

If

20

30

10

информационному входу первого регистра числа, выход j-ro элемента ИЛИ (j 1, N-З) подключен к первому управляющему входу (j + 2) -ro ключа и к первому входу (j+1 )-го элемента ИЛИ, второй вход которого подключен к (j4-2)-My выходу реверсивного кольцевого регистра сдвига, выход (N-З)- г6 элемента ИЖ соединен с первым управляющим входом (N-2)-ro ключа, (+1)-й выход реверсивного кольцевого , регистра сдвига подключен к второму управляющему входу (1+1)-го ключа, выходы регистров числа являются оответствующими выходами перестановки 25 стройства, отличающееся тем, что, с целью ресширения функциональных возможностей устройства путем обеспечения формирования сочетаний из N элементов по К, где , а также возможности задания автоматического режима полного перебора всех Nj перестановок, устройство содержит блок управления, две группы переключателей, (К -1) дополнительных элементов ИЛИ и К групп элементов И, причем входы переключателей первой группы соединены с выходом эле- , ента задержки, выход {К-1)-го переключателя первой группы соеинен с первыми входами элементов И К-й группы и с первым ходом (K-l)-ro дополнительного элеента ИЛИ, выход (К-2)-г6 переключателя первой группы подключен к второ- 45 у входу (к-1)-го дополнительного элемента ИЛИ, выход которого соединен с первыми входами элементов И (К-1)й группы и с первым входом (К-З)-го ополнительного элемента ИЛИ, выход первого переключателя первой группы соединен с вторым входом первого доолнительного элемента ИЛИ, выход оторого соединен с первыми входами элементов И первой и второй групп, вторые входы элементов И групп подлючены к выходам соответствующих разрядов первых К регистров числа соответственно, а выходы элементов

55 (

35

40

50

8

f

0

0

5 5

И 1-й группы {1-К) являются соответствующими 1-го выхода сочетания устройства, выход генератора тактовых импульсов подключен к входам переключателей второй группы, выход первого переключателя второй группы подключен к входам сдвига регистров сдвига, выход второго переключателя второй группы - к входу элемента задержки и к тактовому входу блока управления, вход начальной установки которого является входом установки устройства, первый выход блока управления подключен к управляющему входу первого ключа, а выходы с второго по (М-1)-й блока управления подключены соответственно к вторым управляющим входам ключей с (N-l)-ro по второй, N-й выход блока управления является выходом признака окончания работы устройства.

2. Устройство по п.I, отличающееся тем, что блок управления содержит (N-I) регистров сдвига, группу из (N-2) триггеров, группу из (М-З) элементов запрета, группу из (N-2) элементов И, группу из (N-2) элементов ИЛИ, два элемента задержки и элемент RHH, причем первый регистр сдвига содержит N разрядов, а каждый следующий - на единицу меньше, тактовый вход блока подключен к входу сдвига первого регистра сдвига, выход i-ro регистра сдвига (i-l,N- 2) соединен с входом сдвига (i+l)-ro регистра сдвига, выход (N-l)-ro регистра сдвига является N-M выходом блока, вход начальной установки блока управления подключен к первому входу элемента ИЛИ, первым входам элементов- ИЛИ группы и входу установки в О()го регистра сдвига, выход первого разряда первого регистра сдвига является первым выходом блока, выход i-ro регистра сдвига (i-1, N-З) соединен с входом установки в 1 1-го триггера группы и первым входом i-ro элемента запрета пыГ входы с второго по К-й которого (Уде i + К N - 1) подключены к входам соответственно с (1 + 1)-го по (i+K-l)-й регистров сдвига, выход I-го элемента запрета является 5 (itl)-M выходом блока, выход (М-2)-го регистра сдвига соединен с входом установки в 1 (N-2)-ro триггера группы и является (N-l)-M выходом блока, прямой выход 1-го триггера (i-l,N-2)

5

0

0

913632

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

Фиг. 2

Редактор А.Маковская

Составитель И.Захаревич Техред М.Дидык

Заказ 6364/42 Тираж 671

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

9

10

динен с вторыми входами элементов И группы и входом второго элемента задержки, выход КОТОРОГО соединен с вторым входом элемента ИЛИ, выход которого соединен с входами установки в О триггеров группы.

Корректор М.Пожо

Подписное

Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач при построении специализированньгх вычислительных устройств. Цель изобретения - расширение функциональных возможностей путем формирования сочетаний из N элементов по К, где , и задания автоматического режима полного перебора всех N перестановок. Указанная цель достигается тем, что в устройство, содержащее два регистра 1,2 сдвига N регистров 3 чисел, где N - количество элементов перестановок, реверсивный кольцевой регистр 4 сдвига, N-1 ключей 5, N-3 элементов ИЛИ 14, генератор 7 тактовьгх импульсов и элемент 8 задержки, введены бЛок 9 управления, две группы переключателей 10, 11, К-1 элементов ИЛИ 12 и К групп элементов И 13. 1 з.п. ф-лы, 2 ил., 1 табл. с S сл со о со ьо 00 со