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

 

Изобретение относится к вычислительной технике и предназначено для решения комбинаторных задач. Цель изобретения - повьппение быстродействия при формировании сочетаний и размещений . Оно содержит группу счетчиков , группу сзт маторов, группу элементов И, регистр сдвига, элементы ЗАПРЕТ, переключатель, генератор перестановок , регистры, два дешифратора , N групп элементов И, группу элементовРШИ, схему сравнения.„Устройство предназначено для генерации кодовых последовательностей, для построения специализированных вычислительных устройство 1 ил.-,2 табл.

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

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

РЕСПУБЛИК (ä1) 4 С 06 Р 15/20

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (57) Изобретение относится к вычислительной технике и предназначено для решения комбинаторных задач. Цель изобретения — повышение быстродействия при формировании сочетаний и размещений. Оно содержит группу счетчиков, группу сумматоров, группу элементов И, регистр сдвига, элементы

ЗАПРЕТ, переключатель, генератор перестановок, регистры, два дешифратора, N групп элементов И, группу элементов ИЛИ, схему сравнения..Устройство предназначено для генерации кодовых последовательностей, для построения специализированных вычислительных устройств. 1 ил.„ 2 табл.

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITVM (21) 4138809/24-24 (22) 22. 10. 86 (46) 07.06.88. Бюл. N - 21 (71) Таганрогский радиотехнический институт им.В;Д.Калмыкова (72) В.M,Ãëóøàíü, Ю.А.Згинник и Ю.А.Некрасов (53) 681.327 (088.8) .(56) Авторское свидетельство СССР

Ф 991432, кл. G 06 F 15/20, 1981.

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

У 1124319, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК

„.SUÄÄ 1401474 А1

1401474

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

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

Цель изобретения - повышение быстродействия при формировании сочетаний и размещений.

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

Устройство содержит группу счетчиков 1,..., 1„,, группу сумматоров

2,...,2„, образующих лестничную структуру, группу элементов И 3„. 20

3, регистр 4 сдвига, элементы ЗАПРЕТ

5 и 6, переключатель 7, генератор 8 перестановок, регистр 9, дешифратор

10 (кода Джонсона), N групп элементов И 1.1„,..., 11„, группу элементов 25

ИЛИ 12 „ ..., 12m дешифратор (N-позиционного кода). 13, регистр 14, схему

15 сравнения.

Дешифратор 10 реализует функцию — 30

Р (хну о о о ух,) — Е (хьюг ° ° ° ух ) у 1=ОЙ

$ -1 =е

1, если х 2 =j

F (x э ° ° ° эx )=

i=<

1-1

О, если,! х2 Hj- y5

1=.1

Устройство работает в трех режимах: генерации сочетаний (информация снимается с выходов сумматоров), перестановок (информация снимается с выхода генератора 8) и размещений (информация снимается с выхода дешифратора 13). Перестановки получаются в режиме генерации размещений при ш=п, так как А„=фЄ=Р„.

Работа устройства в режиме генерации сочетаний иллюстрируется табл.1, в которой представлены коды на выходах сумматоров для случая m=3, п=б.

В исходном состоянии счетчики

1,,...,1 устанавливаются в нулевое состояние, .в первый разряд регистра

4 записывается "1",.а во все остальные — "0", тактовая шина устройства через переключатель 7 соединяется с тактовым входом устройства. Так как в регистр 9 записано число m--3, то на счетные входы (V) счетчиков 1>,, 1 N- и 1н и на входы (II) переносов

40 сумматоров 2,„, 2,„, и .2 „, с дешифратора 10 подаются единичные сигналы.

Поэтому на выходе сумматора 2 устанавливается код "1", на выходе сумматора 2„, — код "2" и на выходе сумматора 2 ц — код "3".

По переднему фронту первого тактового импульса через открытый элемент

И 3 в счетчик 1 записывается "1".

Поэтому на выходе сумматора 2 установится код "4". Таким образом, по первому тактовому импульсу на выходах всех сумматоров устанавливается сочетание "124". Второй и третий тактовые импульсы поступают через открытый элемент И 3 на счетчик 1, устанавливая в нем последовательно коды "2" и "3". Соответственно этому на выходах сумматоров 2 „, 2 „,, и

2 устанавливаются сочетания "125" и "126". После установления на выходе сумматора 2 кода "6" в схеме 15 сравнения происходит сравнение кодов и на ее выходе появляется единичный сигнал. Поэтому элемент ЗАПРЕТ 6 открывается и по заднему фронту третьего тактового импульса, который посту.пает на вход синхронизации (с) регистра 4, происходит сдвиг "1" с первого выхода регистра 4 на второй.

В результате этого открываются элемент И 3 „и по переднему фронту четвертого тактового импульса счетчик 1 устанавливается в "0", а в счетчик 1ц „ записывается "1". Поэтому на выходах сумматоров 2, 2 и 2 устанавливается сочетание "134". Поскольку на выходе схемы 15 сравнения теперь единичного сигнала нет, то открывается элемент ЗАПРЕТ 5 и по заднему фронту четвертого тактового импульса, который поступает на вход регистра

4, происходит установка его в исходное состояние. Поэтому пятый и шестой тактовые импульсы вновь поступают через открытый элемент И 3„ на счетчик 1 . В результате на выходах сумматоров 2, 2 „и 2 последовательно устанавливаются сочетания

"135" и "136". Появление кода "б" на выходе сумматора 2> вызывает срабатывание схемы 15 сравнения и появление на ее выходе единичного сигнала. Поэтому через открытый элемент ЗАПРЕТ

6 по заднему фронту шестого тактового импульса проходит сдвиг "1" с первого выхода регистра 4 на второй.

1401474

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

3, и передним фронтом сбрасывает в "0" счетчик 1„, и добавляет "1" в

r> счетчике 1

В результате этого в счетчиках

1„,, 1„, и 1„.q соответственно запивыходах сумматоров устанавливается сочетание "145".

Задний фронт седьмого тактового импульса через открытый элемент 5 устанавливает по входу R регистр 4 в исходное состояние. Поэтому по вось-1 мому тактовому импульсу в счетчик 1 записывается "1", а на выходах сумматоров устанавливается сочетание

" 146". При этом срабатывает схема

15 сравнения, единичным сигналом с ее выхода открывается элемент 6 и по заднему фронту восьмого тактового импульса "1" с первого выхода регистра 4 сдвигается на второй его выход.

Девятый тактовый импульс проходит через открытый элемент И 3 „ и по переднему фронту сбрасывает в "0" счетчик 1 и добавляет "1" в счетчик

1,„,, в котором фиксируется код "3".

В результате этого на выходах сумматоров устанавливается сочетание

"156", на выходе схемы сравнения вырабатывается единичный сигнал и по заднему фронту тактового импульса, который поступает через открытый элемент ЗАПРЕТ 6 на вход синхронизации регистра 4, происходит сдвиг "1" с второго его выхода на третий. Поэтому десятый тактовый импульс теперь поступает через открытый элемент И

3 g и передним фронтом сбрасывает в "0" счетчик 1,„, и записывает "1" в счетчик 1 . На выходах сумматоров в результате устанавливается сочетание "234", а задний фронт десятого

45 импульса через открытый элемент 3АПРЕТ 5 регистр 4 по входу R устанавливает в исходное состояние.

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

1 „, 1 < фиксируются соответственно коды "0", "1", "2", на выходах сумматоров устанавливается сочетание

"356™ и "1" передвигается на третий выход регистра 4„ Передний фронт

19-го тактового импульса через открытый элемент И 3 сбрасывает в "0" счетчик 1 ., и к содержимому счетчика

1 добавляет "1" и в нем фиксируетМ-2 ся код "3". Поэтому на выходах сумматоров устанавливается сочетание "456", срабатывает схема 15 сравнения и по заднему фронту 19-го тактового импульса через открытый элемент ЗАПРЕТ

6 происходит сдвиг "1" с 3-го выхода регистра 4 на 4-й. Двадцатый импульс передним фронтом через открытый элемент И 3 сбрасывает в "0" счетчик

1,, а счетчик 1 единицу не записывает, так как на его разрешающем входе стоит нулевой потенциал. Поэтому на выходах сумматоров устанавливается сочетание "123". Задний фронт

20-го импульса через открытый элемент

ЗАПРЕТ 5 устанавливает регистр 4 в исходное состояние. После этого формирование сочетаний повторяется °

В режиме генерации размещений тактовая шина устройства через переключатель 7 подключается к выходу генератора 8 перестановок, а размещения снимаются с выходов дешифратора 13.

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

8 осуществляет полный перебор перестановок в пространственно-временной форме, т.е. при m=3 каждой серии из трех входных тактовых импульсов соответствует очередность появления импульсов на первых трех выходах генератора 8 перестановок.

Данная очередность импульсов представлена в табл.2.

Сигналы с выходов генератора 8 перестановок управляют работой элементов И 11„,...,11, выполняющих роль коммутаторов. Если, например, на выходах сумматоров 2,...,2 импульсом с выхода генератора перестановок установлено сочетание "136", то в соответствии с 1-й перестановкой к входам дешифратора 13 через элементы И 11, 11, и 11 последовательно подключены сумматоры 2»

2,, 2, а соответственно этому единичный сигнал последовательно появляется на 1-м, 3-м и 6-м выходах цешифратора 13. Затем на выходах генератора 8 формируется 2-я пере1401474

Состояния ия счетчиков сумматоров

N-2 N-1 N

N-2

N-3

1 0

2 0

3 0

0 1

1 2 4

1 2 5

1 2 6

1 3 4

0 становка, в соответствии с которой к входам дешифратора 13 последовательно подключаются сумматоры 2, 2, 2,, а единичный сигнал после5 довательно появляется на 1-м, 6-м и

3-м выходах. Так происходит до тех пор, пока не переберутся все перестановки. Сигнал об окончании перебора всех перестановок появляется на выходе генератора 8. По этому сигналу формируется новое сочетание и процесс перебора перестановок повторяется для данного сочетания до тех пор, пока не переберутся все сочетания и перестановки, что соответствует полному перебору размещений при заданных п и ш.

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

Устройство для перебора сочетаний, размещений и перестановок, содержащее группу счетчиков, первый регистр, первую группу элементов И, первый дешифратор, группу элементов ИЛИ и 25 схему сравнения, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия при формировании сочетаний и размещений, оно содержит второй регистр, два элемента ЗАПРЕТ, З0 группу сумматоров N групп элементов

И, генератор перестановок, регистр сдвига и второй дешифратор, причем тактовый вход устройства соединен с одноименным входом генератора перестановок и через переключатель с первыми входами элементов И первой группы и с инверсным входом первого элемента ЗАПРЕТ, с прямым входом второго элемента ЗАПРЕТ, выходы которых 40 соединены соответственно с входом сброса и тактовым входом регистра сдвига, выходы которого соединены с вторыми входами элементов И первой группы, выход i-ro элемента которой соединен с тактовым входом 3.-го счетчика группы (=1,N) и входом сброса (i+1)-ro счетчика группы, выходы Кго счетчика группы (К=2,N) соединены с входами первой группы К-го сумматора группы, входы второй группы которого соединены с выходами (К-1)-го сумматора группы и первыми входами элементов И j-й группы (j =2,N+1), выходы элементов И с второй по (N+

+ 1)-ю групп соединены с входами элементов ИЛИ группы, выходы которых и выход последнего элемента И (N+1)-й группы, соединены с входами первого дешифратора, выходы которого являются выходами размещений устройства, информационные входы первой группы которого соединены с входами первого регистра, выходы которого соединены с входами второго дешифратора и информационными входами генератора перестановок, тактовый выход которого соединен с переключателем, а i-й выход генератора перестановок соединен с вторыми входами элементов И j-й группы, К-й выход второго дешифратора соединен со счетным входом К-ro счетчика группы и входом переноса К-ro сумматора группы, входы второй группы первого сумматора группы соединены с первым выходом второго дешифратора, выходы последнего сумматора группы соединены с первыми входами элементов И (N+1) и группы и входами первой группы схемы сравнения, входы второй группы которой соединены с выходами второго регистра, входы которого соединены с информационными входами второй группы устройства, выход схемы сравнения соединен с прямым входом первого элемента ЗАПРЕТ и инверсным входом второго элемента ЗАПРЕТ.

3 аблица 1

1401474

Продолжение табл. 1

1 0

3 6

1 0

0 2 0

10

2 4 5

0 1

13 0

15

17

19

Таблица2

Выход

Перестановка (импульсы в серии) 1 13

1 1

0 3

0 0

1 0

2 0

1 1

0 2

0 0

1 0

0 1

0 0

1 2 3 1 2 3

1 4 5

1 4 6

1 5 6

2 3 4

2 3 5

2 3 6

2 4 6

2 5 6

3 4 5

3 4 6

3 5 6

4 5 6

1 2 3

3-я 4-я 5-я 6-я

1 2 3 1 2 3 1 2 3 1 2 3

1401474

Составитель О.Березикова

Техред M.ÕoäàíH÷

Редактор Н.Лазаренко

Корректор Л. Пилипенко

Заказ 278б/48

Тираж 704

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

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

Подписное

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