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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ , РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК, содержащее первую группу регистров, блок управления, генератор тактовых импульсов, переключатель, коммутатор , выходной регистр, элемент ИЛИ, причем группа информационных входов коммутатора соединена с выходами регистров первой группы, выход выходного регистра является выходом устройства , отличающееся тем, что, с целью сокращения количества оборудования, оно содержит вторую группу регистров, две группы элементов И, две группы элементов ИЛИ, группу элементов сравнения, счетчик, дещифратор, делитель, три элемента задержки, причем блок управления содержит группу регистров сдвига, группу триггеров, группу элементов И, группу элементов ИЛИ, группу элементов запрета, элемент ИЛИ, причем управляющие входы коммутатора соединены соответственно с выходом первого регистра сдвига, выходами элементов запрета группы, выходом предпоследнего регистра сдвига блока управления и выходом первого элемента .задержки , вход которого соединен с выходом делителя, входами размещения приема регистров первой группы и входом первого регистра сдвига блока управления, первые входы элементов ИЛИ группы которого соединены с первым входом элемента ИЛИ, входом установки последнего регистра сдвига блока управления и входом начальной установки устройства, который соединен с входом установки счетчика, тактовый вход которого соединен с входом делителя и выходом генератора (Л тактовых импульсов, управляющие входы коммутатора, начиная с второго, соединены соответственно с группой входов переключателя, группа выходов которого соединена с соответствующими входами элементов ИЛИ первой груп-; пы, выходы которых соединены с первыми входами элементов И первой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, а выходы являются выходами сочетаний устройства, входы k-ro элемента ИЛИ второй группы соединены соответственно с (k-l)-M выходом первой группы, k-м выходом второй группы, (k+1)-M выходом третьей группы коммутатора и k-м входом устройства, (где , ..., п, п количество элементов перебора), выходы элементов ИЛИ второй группы соединены с входами.соответствующих регистров второй группы, выходы которых соединены с информационными входами соответствующих регистров пер

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

РЕСПУБЛИН ае oD

1 за С 06 F 15/20

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

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

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

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

I. : I (1 (21) 3630771/24-24 (22) 27.07.83 ,(46) 15.11.84. Бюп. В 42 (72) В.М. Глушань, В.М. Курейчик, М.И. Пупков и Л.И. Щербаков (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (53) 681.327(088.8) (56) 1. Авторское свидетельство СССР

Ф 748416, кл., С 06 F 15/20, -1978.

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

У 957215, кл. G 06 F 15/20, 1980.

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

У 643883, кл. G 06 F 15/20, 1977 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК, содержащее первую группу регистров, блок управления, генератор тактовых импульсов, переключатель, коммутатор, выходнои регистр, элемент ИЛИ, причем группа информапионных входов коммутатора соединена с выходами регистров первой группы, выход выходного регичтра является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения количества оборудования, оно содержит вторую группу регистров, две группы: элементов И, две группы элементов ИЛИ, группу элементов сравнения, счетчик, дешифратор, делитель, три элемента задержки, причем блок управления содержит группу регистров сдвига, группу триггеров, группу элементов И, группу элементов ИЛИ, группу элементов запрета, элемент ИЛИ, причем управляющие входы коммутатора соединены соответственно с выходом первоro регистра сдвига, выходами элементов запрета группы, выходом предпоследнего регистра сдвига блока управления и выходом первого элемента,задержки, вход которого соединен с выходом делителя, входами размещения приема регистров первой группы и входом первого регистра сдвига блбка управления, первые входы элементов

ИЛИ группы которого соединены с первым входом элемента ИЛИ, входом установки последнего регистра сдвига блока управления и входом начальной установки устройства, который соединен с входом установки счетчика, тактовый вход которого соединен с Я входом делителя и выходом генератора тактовых импульсов, управляющие входы коммутатора, начиная с второго, соединены соответственно с группой входов переключателя, группа выходов Я которого соединена с соответствующими входами элементов ИЛИ первой груп-, пы, выходы которых соединены с первыми входами элементов И первой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, а выходы являются выходами сочетаний устройства, входы k-го элемента ИЛИ второй группы соединены соответственно с (k-1)-м выходом первой группы, k-м выходом второй группы, (k+1)-м выходом третьей группы коммутатора и k-м входом. ), устройства, (где k=1 ..., n, n— количество элементов перебора), выходы элементов ИЛИ второй группы соединены с входами соответствующих регистров второй группы, выходы которых соединены с информационными входами соответствующих регистров пер1 вой группы, первыми входами соответ-.

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

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

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

Известно устройство для перебора перестановок, содержащее в каждом разряде регистр, счетчик, элемент ИЛМ, четыре элемента И, элемент задержки и один вспомогательный регистр на все устройство (1) .

Однако это устройство характеризуется низким быстродействием. Кроме того, оно не позволяет получать pasмещения и сочетания.

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

1 соответствующего элемента ИЛИ, а выходом - с входом соответствующего

:регистра первой группы f2) .

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

Наиболее близким к предлагаемому

:по технической сущности является устройство для перебора сочетаний, размещений и перестановок, содержащее запоминающую матрицу, регистр сдвига, два элемента И, два тригге11243

«О

55 ра, генератор тактовых импульсов, элемент ИЛИ, блок регистров, выходной регистр, переключатель, коммутатор, блок деления и блок управления, причем горизонтальные шины запоминающей матрицы соединены с выходами регистра сдвига, а ее вертикальные шины через последовательно соединенные блок регистров, коммутатор и блок деления подключены к выходно- 10 му регистру, выходы блока управления соединены с управляющими входами блока деления и коммутатора, вход запуска устройства соединен с первым входом первого триггера, второй вход которого подключен к первому выходу регистра сдвига, выход первого триггера подключен к первым входам второго триггера, элемента ИЛИ и первого элемента И, второй вход которого подклю- 0 чен к первому выходу генератора импульсов, выход .первого элемента И подключен к прямому входу регистра сдвига, второй выход генератора им пульсов подключен к первому входу д второго элемента И, второй вход которого подключен к выходу второго триг- . гера и второму входу элемента ИЛИ, выход которого подключен к входу генератора импульсов, третьи входы первого и второго триггеров через переключатель соединены с соответствующими входами регистра сдвига, выход второго элемента И соединен с инверсным входом регистра сдвига f3) .

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

Это вызвано тем, что число разрядов регистра сдвига и соответственно число горизонтальных шин запоминаюпп! .щей матрицЫ представляют величину в, 45 где п — число элементов в перестановках.

Цель изобретения — сокращение количества оборудования.

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

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

ИЛИ группы которого соединены с первым входом элемента ИЛИ, входом установки последнего регистра сдвига блока управления и входом начальной установки устройства, который соединен с входом установки счетчика, тактовый вход которого соединен с входом делителя и выходом генератора тактовых импульсов, управляющие входы коммутатора, начиная с второго, соединены соответственно с группой входов переключателя, группа входов которого соединена с соответствующими входами элементов ИЛИ первой группы, выходы которых соединены с первыми входами элементов И первой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, а выходы являются выходами сочетаний устройства, входы k-го элемента ИЛИ второй группы соединены соответственно с (k-1)-м выходом первой группы, k-u выходом второй группы, (k+1)-м выхо.дом третьей группы коммутатора и

k-м входом устройства (где k 1, и, п — количество элементов перебора), выходы элементов ИЛИ второй группы соединены с входами соответст. вующих регистров второй группы, выходы которых соединены с информациои. ными входами соответствующих регистров первой группы, первыми входами соответствующих элементов сравнения группы и первыми входами соответст1124319 вующих элементов И второй группы, выходы которых соединены с соответствующими входами элемента ИЛИ, выход которого соединен с входом выходного регистра, выход счетчика соединен с 5 входом дешифратора, выходы которого соединены с вторыми входами соответствующих элементов И второй группы, выходы перестановок устройства

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

На фиг. 1 приведена структурная схема предлагаемого устройства для перебора сочетаний, размещений и перестановок для случая пяти переставляемых.элементов; на фиг. 2 - струк 45 турная схема блока управления.

Устройство для перебора сочетаний, размещений н перестановок содержит первую группу 1 -15 регистров, комму" татор 2, состоящий из групп 31"Зя элементов И и групп 4 -4> элементов ИЛИ, блок 5 управления, блок 6 переключателей, первую группу 71 -7 элементов ИЛИ, первую группу 81 84 элементов И, вторую группу 91-9g элементов ИЛИ с входами 10<-10, вторую группу 111 -115 регистров, вторую группу 121-12 элементов И, групп, 13 -13> элементов сравнения с выходами 141 †1, счетчик 15, дешифратор 16, элемент ИЛИ 17, выходной регистр 18, генератор 19 тактовых импульсов, делитель 20, элементы 21, 22 и 23 задержки, вход 24 установки исходного состояния, выход 25 окончания генерирования.

Блок 5 управления содержит последовательно соединенные регистры 261

264 сдвига, триггеры 27(-2743, элементы 281-28 запрета, элементы И

291-29, элементы ИЛИ 301- 30 и

ИЛИ 31, причем число разрядов в регистре 261 сдвига равно двум, а в каждом последующем на единицу больше, чем в предыдущем. (входы и выходы блока 5 управления на фиг. 2 расположены в строгом соответствии с их расположением на фиг. 1).Устройство для перебора сочетаний, размещений и перестановок может работать в трех режимах: генерирование перестановок,, генерирование размещений и генерирование сочетаний.

Для генерирования перестановок по входам 10 в регистре t1 записываются исходные элементы, например. числа 1, 2, 3, 4, 5., причем запись этих чисел в регистре 1 может производиться в.любом порйдке. Для удобства будем считать, что эти числа записаны в возрастающем порядке, начиная с верхнего регистра 11. На вход 24 подается сигнал установки в исходное состояние блока 5 и счетчи. ка 15.

Ъ

Первый тактовый импульс с выхода делителя 20 производит перепись элементов, т.е. чисел 1, 2, 3, 4 и 5, из регистров 11 в соответствующие регистры и одновременно устанавливает единицу на первом выходе блока 5. Благодаря этому задержанный элементом 21 первый тактовый импульс, поступая на входы всех групп 3< -Зя элементов И коммутатора 2, переписывает числа из регистра 14 в регистр

11, из регистра 1 в регистр 11, из регистра 1 в регистр 11я, из регистра 1 .в регистр 111 и из регистра 1.5 в регистр 11я. Задержанный эле ментами 22 и 23 первый тактовый импульс, поступая на .второй и третий входы блоков 5 ° никаких изменений не производит.

Тактовые импульсы с генератора

19 тактовых импульсов, частота кото

1124319 8 рых в и раз выше, чем с выхода делителя 20 (и — число элементов в перестановках), поступая на счетчик 15, суммируются. Так как выходы счетчика 15 соединены со всеми элементами

13 сравнения, то при поступлении каждого тактового импульса на этот счетчик, в одном из элементов 13 сравнения проис;.эдит сравнение кодов счетчика 15 и соответствующего ре- 10 гистра 11. На выходе 14 той схемы

13 сравнения, где произошло сравнение, появляется сигнал. Кроме того, производится перепись содержимого соответствующего регистра 11 через 15 элементы И 12 и ИЛИ 17 на выходной регистр 18.

После этого на выходе делителя 20 появляется второй импульс, который переписывает числа из регистров 11 — 2п

11> в регистры 1»-1> соответственно.

Этот же импульс проходит на выход регистра 26 блока 5 и появляется на втором его выходе, переводит в еди ничное состояние триггер 274 и чос- 2S тупает с выхода регистра 26» на вход регистра 262.

В соответствии с этим задержанный второй импульс с выхода элемента 21 переписывает числа 2, 3, 1, 4, 5 из регистров 1< -1> В регистры 111 11 соответственно. Этот же импульс, пройдя через элемент 22 задержки, поступает на второй вхор, блока 5 и через открытый элемент И 29» и элемент ИЛИ 30» сбрасывает регистр 261 в исходное состояние, а пройдя через элемент 23 задержки, поступает на третий вход блока 5 и через элемент

ИЛИ 31 устанавливает в исходное состояние триггер 271 ., Далее, аналогичным образом,. по тактовым импульсам генератора 19 нач11нается сравнение чисел в элементах 13 -13 сравнения и сигнал пос45

4 ледовательно появляется на выходах

44, 14 » 1411 и 14 0дновремeH но по сигналам с дешифратора 16 переписываются числа 2, 3, 1, 4, 5 из регистров 11 -11> в регистр 18. Таким образом, параллельная форма представления перестановок в регистрах 11 —

111» преобразуется в последовательную форму в регистре 18 и пространственно-временную форму последовательности появления сигналов на выходах 14»- 14ч элементов 13 -13 срав5 нения.. После перебора всех 120 перестановок на выходе 25 регистра 264 появляется сигнал, который является сигналом окончания работы в режиме генерирования перестановок.

При генерировании размещений работа не отличается от режима генерирования перестановок. Различие заключается лишь в том, что перед началом работы числа, отличные от нуля, нужно занести не во все регистры 11, а лишь в некоторые. Так, например, при генерировании размещений из 5 по 2 в л бые два регистра необходимо . записать числа, отличные от нуля. Сравнение чисел происходит лишь в тех элементах 13 сравнения, на которые поступают.из регистров 11 не нулевые числа. Поэтому за каждый цикл пересчета счетчиком

15 тактовых импульсов с генератора

19 сигнал появляется на выходах . только двух схем 13 сравнения из пяти. Но поскольку числа в регистрах

11 в каждом цикле меняются, то к моменту появления сигнала конца работы устройства (на в1»1ходе 25 блока 5) перебираются всевозможные комбинации пар элементов 13 сравнения, в которых происходит сравнение чисел, и на соотвечствующих выходах 14 появляются сигналы. Все эти комбинации пар элементов сравнения являются размещениями из 5 по 2. Таким образом, получаем все размещения из 5 по 2 в форме пространственновременной последовательности появления сигналов на выходах 14.

В режиме генерирования сочетаний информация снимается с выходов элементов И 8 -8<. Исходная установка такая же, как и в режиме генериро/ вания перестановок. Переключателем б задается число элементов из общего числа, которые должны участвовать в формировании сочетаний. Так, если замкнут первьп1 контакт переклю-. чателя 6, то формируются сочетания из 5 по 4, если второй — из 5 по 3, если третий — из 5 по 2.

Принцип формирования сочетаний основан на периодическом исключении из перестановок лишних комбинаций.

Так, при замкнутом третьем контакте переключателя 6 на выходах элементов И 8» и 8» появляются через одну комбинацию все сочетания элементов из

5 по 2. При замкнутом втором контакте

1124319

Составитель; А. Клюев

Редактор Л. Алексеенко Техред А.Бабинец

Корректор Г. Огар

Филиал ППП "Патент", г. Укгорог, ул. Проектная, 4

Заказ 8282/39 Тирах 698 Подписное

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

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