Устройство для перебора сочетаний, размещений и перестановок
Иллюстрации
Показать всеРеферат
Изобретение относится к вычислительной технике и предназначено для решения комбинаторных задач. Цель изобретения - повьппение быстродействия при формировании сочетаний и размещений . Оно содержит группу счетчиков , группу сзт маторов, группу элементов И, регистр сдвига, элементы ЗАПРЕТ, переключатель, генератор перестановок , регистры, два дешифратора , 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