Устройство для перебора перестановок

(57) Ислителпользоных зад об ой ч СУДАРСТВЕННЫЙ КОМИТЕТО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТ АНИЕ ИЗОБр У СВИДЕТЕЛЬСТВ(56) Авторское свидУ 995093, кл. С 06Авторское свиде1190388, кл. С 0 ТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАение относится к вычи ехнике и может быть и для решения комбинатор и автоматизированном конструировании радиоэлектронной ивычислительной аппаратуры. Цельизобретения - упрощение устройства,При п=5 устройство содержит группусчетчиков 1) - 1, группу элементовИ 2, - 2 з, группу элементов ЗАПРЕТ3- 3, группу элементов И 4, - 4,группу регистров 5, - 5 сдвига, ком"мутаторы 6-10, элемент НЕ 11, триггер 12, элемент И 13, счетчик 14,"выходы 15-19, тактовый вход 20, выход 21 признака окончания перебора21, выход 22 признака окончания выдачи одной перестановки, вход 23 ус"тановки исходного состояния, группутриггеров 24 1- 24. Устройство реа"лизует перебор всех перестановок иэлементов перебора. 1 ил.1418733 7. 3142 8. 1342 91432 10. 4132 18. 4231 19. 2413 20.4213 21. 4123 22. 1 4 2 3 23. 1 2 4 3 10 11. 4 3 1 2 50 2.2134 3, 2314 4.3214 13. 4 3 2 1 14,3421 15.324 г 1 б. 2 3 4 1 5.3124 6. 1324 17, 2 А 3 1 Изобретение относится к вычислительной технике и может быть испольэовано для решения задач автоматизированного конструирования радио 5электронной и вычислительной аппаратуры.Целью изобретения является упрощение и повышение быстродействияустройства,На чертеже представлена схемаустройства для и=5 переставляемыхэлементов.Устройство содержит группу счетчиков 1 - 1, группу элементов И 152, - 2 з, группу элементов запрет3, - 3, группу элементов ИЛИ 4, -4, группу регистров 5, - 5 сдвига,коммутаторы б, элемент НЕ 11,триггер 12, элемент И 13, счетчик14, выходы 15-19 устройства, тактовыйвход 20, выхоц 21 признака окончанияперебора, выход 22 признака окончаниявыдачи одной перестановки, вход 23установки исходного состояния, группу 2524- 24 триггеров, модуль счетчика1, равен двум, у каждого последующегосчетчика - на единицу больше. Принцип работы устройства состоит 30в том, что при помощи управляющихсигналов с устройства управленияпроисходит попарное включение соответствующих коммутаторов, которыепересоединяют выходы сдвиговых регистров 5 на их входы таким образом,что в течение и (и - число переставляемых. элементов) тактов происходитобмен содержимым соседних регистров.При этом информация в соседних регистрах сохраняетсяПоследовательность обменов в соответствии с используемым алгоритмомдля случая 4-х переставляемых элементов (элемент представлен числомв десятичной системе, а пары разрядов, между которыми происходит обменэлементами, указаны дугами) имеет вид1. 1 2 3 4 12. 3 4 1 2 24. 2143Устройство работает в двух режимах: в режиме выдачи паралельногокода перестановок и в режиме пространственно-временной формы последовательности появления сигнала на выходах устройства.,В режиме пространственно-временной формы представления перестановокпо сигналу, поступающему на вход 23,счетчики 1, - 1, триггер 12 и триггеры 24- 24 устанавливаются в,нулевое состояние, триггер 24 первый разряд регистра 5 сдвига, второй разряд регистра 5 сдвига, третий разряд регистра 5 сдвига, четвертый разряд регистра 5 сдвига ипятый разряд регистра 5 сдвигаустанавливаются в единичные состояния. При этом на выходах 15 появляется код 10000,означающий,чтопервая цифра первой перестайовкинаходится на первой позиции, Передний фронт тактового импульса не изменяет состояния устройства, так какэлемент И 13 закрыт, а триггер 12срабатывает по переднему фронту импульса. По заднему фронту первоготактового импульса через открытыйэлемент НЕ 11 триггер 12 переходитв единичное состояние и открываетэлемент И 13 для прохождения следующих тактовых импульсов на регистры5, - 5. Таким образом, первому тактовому импульсу соответствует код 10000на выходах 15.На втором выходе счетчика 14 появляется каждый и-й тактовый импульс, а на первом выходе - второй икаждый (и+2)-й импульс, где = 1,2 Второй тактовый импульс проходит через открытый элемент И 13 и поступает на синхровходы регистров 5 сдвига, а также через счетчик 14 - на счетные входы счетчиков 1 , 1, в результате чего счетчик 1, пере 1418733ходит в единичное состояние, сигнал с выхода которого, пройдя через открытые элементы 3, и 4, появляется на входе триггера 24 . Так как триггер 24, находится в единичном состоянии, коммутаторы 7 пересоединяют выход регистра 5 сдвига на вход регистра 5, сдвига, а выход 5, на вход 5 и по приходу тактового импульса единица из последнего разряда 5 переписывается в первый разряд 5, а ноль иэ последнего разряда регистра 5 " в первый разряд регистра 5, При этом на выходах 15 появляется код 01000, Так как после пяти первых тактовых импульсов состояния триггеров 24 - 24не изменяется, то регистры 5, и 5 сдвига полностью обменяются содержимым, а содержимое регистров 5 з - 5 з будет таким же как и в исходном состоянии, причем после прихода каждого тактового импульса на выходах 15 появляются коды расположения очередной цифры первой пере-г 5 становки. По приходу пятого тактового импульса одновременно с перезаписью состояний регистров 5 сдвига появляется сигнал на выходе счетчика 14, а в результате чего триггер 24 переходит в единичное состояние, а триггер 24, обнуляется.Под действием сигнала на выходе триггера 24 коммутаторы 7 и 8 соединяют выход регистра 5 сдвига со вхо 235 дом регистра 5 сдвига и выход регист ра 5 с входом регистра 5 , выходы остальных регистров будут соединены со своими же входами.После прихода очередных 6-10 так 0 товых импульсов поменяются содержимым регистры 5 и 5, а содержимое остальных регистров станет таким же как после прихода 5-го тактового импульса. Причем после прихода каждого .из этих импульсов на выходах 15 будут 45 появляться коды расположения очередной цифры второй перестановки.1После прихода каждого (1 и)-го импульса состояния триггеров 24 изменя ются таким образом, что генерация перестановок происходит по вьппеупомянутому алгоритму, Достигается это тем, что после прихода каждого импульса с первого выхода счетчика 14 на инверсном и прямом выходах счетчика 11, импульсы появляются по очереди, на выходах И 2, после каждого шестого, на выходе элемента И 2 после каждого 24-го, на выходе элемен" та И 2 после каждого 120-го импульса. Элементы И 3 , И 3 пропускают импульсы только.со старших разрядов регистров 1, а элементы ИЛИ 4, 4одновременно пропускают импульсы на входы триггеров 24 младших разрядов, совпадающих по четности со старшими еРабота устройства в режиме форми" рования перестановок в форме параллельного кода отличается только тем, что параллельные коды снимаются с выходов, 15-19 после каждого (ж)-го импульса, а код первой перестановки после импульса установки каждого состояния.Кроме того, в устройстве на выходах 15-19 можно получить информацию одновременно о положении и единиц генерируемой последовательности перестановок.Формула изобретенияУстройство для перебора перестановок, содержащее группу из исчетчиков (и - количество элементов перебора), группу элементов ЗАПРЕТ, группу элементов ИЛИ и группу из итриггеров, о т л и ч а ю щ ее с я тем, что, с целью упрощения и повьппения быстрод йствия, оно со- держит группу из иэлементов И, и и-разрядных регистров сдвига, счетчик по модулю и, триггер, элемент Й, эле" мент НЕ, и коммутаторов, причем выход -го коммутатора, (1=1, и) соединен с информационным входом.-го регистра сдвига, выход 1-го регистра сдвига Ц= 1,, , и) соеди" нен с первым информационным входом 3-го коммутатора, с вторым информационным входом (3-1)-го коммутатора и с третьим информационным входом Ц+1)-го коммутатора, выход (и)- го регистра сдвига соединен с пер вым информационным входом (и)-гс коммутатора, с вторым информационным входом (и)-го коммутатора и с вторым информационным входом и-го ком" мутатора, выход и-го регистра сдвига соединен с вторым информационным входом (и)-го и первым информационным входом и-го коммутаторов, выход 1-го триггера группы соединен с. первым инверсным и первым прямым управляющими входами 1-го коммутатора, втором1418733 с и в -) соединен с соответствующими 21 входами всех четных элементов ИЛИ, начиная с второго и до (2 р)-го, а выход каждого (2 р)-го элемента ЗАПРЕТ соединен с входами всех нечетных элементов ИЛИ группы, выход последнего элемента И группы соединен с выходом признака окончания перебора устройства, информационные выходы которого соединены с выходами.регистров сдвига. Составитель М. ГоряиновТехред А.Кравчук Корректор И. Эрдейи Редактор Г. Волкова Тираж 704 Заказ 4155/47 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж, Раушская наб д, 4/5 Яроизводственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4 инверсным и вторым прямым управляющим входами Я+1)-го коммутатора, выход (п)-го триггера группы соединен с первым инверсным и первым пря 5 мым управляющими входами (и)-го и и-го коммутаторов, единичный вход К-го триггера группы (к=1,п) соединен с выходом соответствующего элемента ИЛИ группы, единичный вход 1 О (п-г)-го триггера группы соединен с выходом (и)-го элемента ЗАПРЕТ группы, а единичный вход (п)-го триггера группы соединен с выходом (и)-го элемента И группы и первым входом (п)-го элемента ИЛИ группы, синхровходы всех триггеров соединены с первым информационным выходом счетчика, второй информационный выХод которого соединен со счетными входами всех счетчиков группы и выходом признака окончания выдачи одной перестановки устройства, счетНый вход счетчика соединен с тактовым входом устройства и с первым 25 входом элемента И, второй вход которого соединен с выходом триггера, единичный вход и вход установки начального состояния которого соединены соответственно с выходом элемента НЕ и входом установки начального состояния устройства, соединенного с одноименными входами всех счетчи-,ков группы, триггеров группы и регистров сдвига, синхровходы которых соединены с выходом элемента И, выходы1-го элемента И группы соединены свыходами с первого по (3+1)-й счетчиков группы, инверсный выход первого счетчика группы соединен с первым входом первого элемента ИЛИ группы, а прямой выход первого сЧетчикагруппы соединен с синхровходом второго счетчика группы, с прямым входомпервого элемента ЗАПРЕТ группы, выход к-го элемента И группы соединенс синхровходом (к+2)-го счетчика ис соответствующими входами всех элементов ЗАПРЕТ группы, выход (2 р)го элемента ЗАПРЕТ группы (р=1,