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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 19) (1 И 474 А 6 Г 15 51) АНИЕ ИЗОБРЕТЕНИЯ ЬСТ К АВТОРСК 4138809/2422. 10. 86 21) 22) 46) 71) 88. Бюл. У огский рад .В;Д.Калмьушань, Ю,Асов7 (088.8) Таганр тут и В.М,Г .Некр 681. 3 отехничесоваЗгинник(54) УСТРОЙСТВНИЙ, РАЗМЕЩЕНИЙ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ свидетельство СССР06 Р 15/20, 1981. идетельство СССР С 06 Г 15/20, 1983. ДЛЯ ПЕРЕБОРА СОЧЕТАИ ПЕРЕСТАНОВОК(57) Изобретение относится к вычислительной технике и предназначено длярешения комбинаторных задач. Цельизобретения - повышение быстродействия при формировании сочетаний и размещений, Оно содержит группу счетчиков, группу сумматоров, группу элементов И, регистр сдвига, элементыЗАПРЕТ, переключатель, генератор перестановок, регистры, два дешифратора, Х групп элементов И, группу элементов ИЛИ, схему сравненияУстройство предназначено для генерации кодовых последовательностей, для построения специализированных вычислительных устройств. 1 ил. 2 табл.Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения комбинаторных задач, для генерации кодовых последовательностей, а также для5 построения специализированных вычислительных устройств, предназначенных для автоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры.Цель изобретения - повьппение быстродействия при формировании сочетаний и размещений.На чертеже приведена структурная схема устройства.Устройство содержит группу счетчи" ков 1 1 группу сумматоров 22 образующих лестничную структуру, группу элементов И 3 20 3 регистр 4 сдвига, элементы ЗАПРЕТ 5 и 6, переключатель 7, генератор 8 перестановок, регистр 9, дешифратор 10 (кода Джонсона), М групп элементов И 1.1 11, группу элементов 25 ИЛИ 12, 12 дешифратор (И-позиционного кода). 13, регистр 14, схему 15 сравнения.Дешифратор 10 реализует функцию- 30 Рфхр о о ох,) =Р (хх) 1=0,-11, еслих 2 =1Г (х,х,) =Ь 1О, если, х 2 3 35=1 40 Устройство работает в трех режимах: генерации сочетаний (информация снимается с выходов сумматоров), перестановок (информация снимается с выхода генератора 8) и размещений (информация снимается с выхода дешифратора 13), Перестановки получаются в режиме генерации размещений приш=п, так как А=С"Р=Р.45Работа устройства в режиме генерации сочетаний иллюстрируется табл.1, в которой представлены коды на выходах сумматоров для случая ш=3, п=б.В исходном .состоянии счетчики 1,1 устанавливаются в нулевое состояние, .в первый разряд регистра 4 записывается "1",.а во все остальные - "0", тактовая шина устройства через переключатель 7 соединяется с тактовым входом устройства. Так как в регистр 9 записано число ш=3, то на счетные входы (Ч) счетчиков 1 , 1 ., и 1 н. и на входы (11) переносов сумматоров 2 2 и 2 , с деипфратора 10 подаются единичные сигналы. Поэтому на выходе сумматора 2устанавливается код "1", на выходе сумматора 2, - код "2" и на выходе сумматора 2 , - код "3".По переднему Фронту первого тактового импульса через открытый элемент И 3 в счетчик 1, записывается 1 Поэтому на выходе сумматора 2, установится код "4", Таким образом, по первому тактовому импульсу на выходах всех сумматоров устанавливается сочетание "124". Второй и третий тактовые импульсы поступают через открытый элемент И 3, на счетчик 1 устанавливая в нем последовательно коды "2" и "3". Соответственно этому на выходах сумматоров 22, и 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 на второй.Поэтому седьмой тактовый импульспроходит через открытый элемент И3, и передним фронтом сбрасываетв "О" счетчик 1, и добавляет "1" нсчетчике 1В результате этого в счетчиках1 1, и 1.2 соответственно запивыходах сумматоров устанавливаетсясочетание "145",Задний фронт седьмого тактовогоимпульса через открытый элемент 5устанавливает по входу К регистр 4в исходное состояние, Поэтому по вось мому тактовому импульсу в счетчик 1записывается "1", а на выходах сумматоров устанавливается сочетание" 146", При этом срабатывает схема15 сравнения, единичным сигналом сее выхода открывается элемент 6 ипо заднему фронту восьмого тактовогоимпульса "1" с первого выхода регистра 4 сдвигается на второй его выход,Девятый тактовый импульс проходитчерез открытый элемент И 3и попереднему фронту сбрасывает в "0"счетчик 1 ч и добавляет "1" в счетчик1, в котором фиксируется код "3".В результате этого на выходах сумматоров устанавливается сочетание"156", на выходе схемы сравнения вырабатывается единичный сигнал и позаднему фронту тактового импульса,который поступает через открытый элемент ЗАПРЕТ 6 на вход синхронизациирегистра 4, происходит сдвиг "1" свторого его выхода на третий. Поэтомудесятый тактовый импульс теперь поступает через открытый элемент И403.2 и передним фронтом сбрасываетв "О" счетчик 1 и записывает "1"в счетчик 1 .2 . На выходах сумматоровв результате устанавливается сочетание "234", а задний фронт десятого45импульса через открытый элемент ЗАПРЕТ 5 регистр 4 по входу К устанавливает в исходное состояние.Аналогичным образом устройство работает до поступления 18-го такто 50 ного импульса. При поступлении 18-го тактового импульса н счетчиках 1, 1, 1 ц 2 фиксируются соответственно коды "0", "1", "2", на выходах сумматоров устанавливается сочетание "356" и "1" передвигается на третий выход регистра 4 Передний фронт 19-го тактового импульса через открытый элемент И 3.2 сбрасывает в "0" счетчик 12., и к содержимому счетчика 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 осуществляет полный перебор перестановок в пространственно-временнойформе, т.е, при а=3 каждой серии изтрех входных тактовых импульсов соответствует очередность появления импульсов на первых трех выходах генератора 8 перестановок,Данная очередность импульсов представлена в табл.2,Сигналы с выходов генератора 8 перестановок управляют работой элементов И 1111, выполняющих роль коммутаторов. Если, например, на выходах сумматоров 222 импульсом с выхода генератора перестановок установлено сочетание "136", то в соответствии с 1-й перестановкой к входам дешифратора 13 через элементы И 112, 11 ., и 11 .2 последовательно подключены сумматоры 21, 2 2 2, а соответственно этому единичный сигнал последовательно появляется на 1-м, 3-м и 6-м выходах цешифратора 13, Затем на выходах генератора 8 формируется 2-я пере1401474 Состояния ия счетчиков сумматоровМИМ 1 О 2 О 3 О О 1 О 1 2 4 1 2 5 1 2 61 3 4 О О становка, в соответствии с которой к входам дешифратора 13 последовательно подключаются сумматоры 2, 2 , 2а единичный сигнал после 5 довательно появляется на 1-м, 6-м и 3-м выходах, Так происходит до тех пор, пока не переберутся все перестановки. Сигнал об окончании перебора всех перестановок появляется на выходе генератора 8. По этому сигналу формируется новое сочетание и процесс перебора перестановок повторяется для данного сочетания до тех пор, пока не переберутся все сочетания и перестановки, что соответствует полному перебору размещений при заданных и и ш. Формула изобретенияУстройство для перебора сочетаний, размещений и перестановок, содержащее группу счетчиков, первый регистр, первую группу элементов И, первый дешифратор, группу элементов ИЛИ и 25 схему сравнения, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия при формировании сочетаний и размещений, оно содержит второй регистр, два элемента ЗАПРЕТ, 30 группу сумматоров И групп элементов И, генератор перестановок, регистр сдвига и второй дешифратор, причем тактовый вход устройства соединен с одноименным входом генератора перестановок и через переключатель с первыми входами элементов И первой группы и с инверсным входом первого элемента ЗАПРЕТ, с прямым входом второго элемента ЗАПРЕТ, выходы которых 4 О соединены соответственно с входом сброса и тактовым входом регистра сдвига, выходы которого соединены с вторыми входами элементов И первой группы, выход х-го элемента которойсоединен с тактовым входом -го счетчика группы (=1,М) и входом сброса(.+1)-го счетчика группы, выходы Кго счетчика группы (К=2,И) соединеныс входами первой группы К-го сумматора группы, входы второй группы которого соединены с выходами (К)-госумматора группы и первыми входамиэлементов И 3-й группы (1=2,И+1),выходы элементов И с второй по (И+Ф 1)-ю групп соединены с входами элементов ИЛИ группы, выходы которых ивыход последнего элемента И (И+1)-йгруппы, соединены с входами первогодешифратора, выходы которого являются выходами размещений устройства,информационные входы первой группыкоторого соединены с входами первогорегистра, выходы которого соединеныс входами второго дешифратора и информационными входами генератора перестановок, тактовый выход которогосоединен с переключателем, а -й выход генератора перестановок соединенс вторыми входами элементов И 1-йгруппы, К-й выход второго дешифраторасоединен со счетным входом К-го счетчика группы и входом переноса К-госумматора группы, входы второй группыпервого сумматора группы соединеныс первым выходом второго дешифратора,выходы последнего сумматора группысоединены с первыми входами элементов И (И+1) -й группы и входами первойгруппы схемы сравнения, входы второйгруппы которой соединены с выходамивторого регистра, входы которого соединены с информационными входами второй группы устройства, выход схемысравнения соединен с прямым входомпервого элемента ЗАПРЕТ и инверснымвходом второго элемента ЗАПРЕТ.1аблица 11401474 Составитель О.БерезиковаТехред М.Ходанич едактор Н.Лазаренко ектор Л. Пилипенк Заказ 278 б/4 Подписно ко о кая 1 роиэводственно-полиграфическое предприятие, г. Ужгород, ул. Проект ВНИИПИ Госу по делам 113035, Москв