Устройство для генерирования перестановок и сочетаний

,136323 6 Г 15 5 И ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ИСАНИЕ ИЗОБРЕТЕНИЯА ВТОРСНОМУ СВИДЕТЕЛЬ(21) 40793 (22) 13.05 (46) 30,12 (71) Ленин кий инстит на)(72) Т.В.В В.С.Дудкин (53) 681,3 (56) Автор У 1124319,Авторск В 1180917, (54) УСТРО ПЕРЕСТАНОВ (57) Изобр лительной пользовано ных задач 4/24-248687. Бюл. У 48радский электротехничест им.В.И.Ульянова (Ленилченская, В.С,Князьков, и Д,П.Пуолокайнен 5 (088,8)кое свидетельство СССР кл, 0 06 Г 15/20, 1983, е свидетельство СССР кл, С 06 Г 15/20, 1983, СТВО ДЛЯ ГЕНЕРИРОВАНИЯ К И СОЧЕТАНИЙтение относится к вычисехнике и может быть исдля решения комбинаторри построении специализи рованных вычислительных устройств. Цель изобретения - расширение функциональных возможностей путем формирования сочетаний из М элементов по К, где К(М, и задания автоматического режима полного перебора всех М перестановок. Указанная цель достигается тем, что в устройство, содержащее два регистра 1,2 сдвига М регистров 3 чисел, где М - количество элементов перестановок, реверсивный кольцевой регистр 4 сдвига, Мключей 5, Мэлементов ИЛИ 14, генератор 7 тактовых импульсов и элемент 8 задержки,введены блок 9 управления, две группы переключателей 10, 11, с Кэлементов ИЛИ 12 и К групп элеФ ментов И 13. 1 з.п. ф-лы, 2 ил 1 табл.Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторныхзадач при построении специализирован 5ных вычислительных устройств.11 елью изобретения является расширение функциональных возможностейустройства путем обеспечения формирования сочетания из Й элементов поК, где КИ, и возможности задания автоматического режима полного перебора всех Мперестановок,На фиг,1 показана блок-схема устройства для И = 4, К = 2,3; на фиг,2 -1,функциональная схема блока управления.Устройство содержит (фиг,1) дварегистра 1 и 2 сдвига, регистры 3числа, реверсивный кольцевой регистр4 сдвига, ключи 5, элементы ИЛИ 6,генератор 7 тактовых импульсов, элемент 8 задержки, блок 9 управления,первую группу 10 переключателей,вторую группу 11 переключателей,дополнительные элементы ИЛИ 12, группы 13 элементов И.:. Устройство имеет выходы 14 перестановки, выходы 15 сочетания, вход16 начальной установки, выход 17 30признака окончания работы.Блок 9 управления содержит регистры 18 сдвига, группу 19 триггеров,группу 20 элементов запрета, группу21 элементов И, группу 22 элементовИЛИ, два элемента 23,24 задержки иэлемент ИЛИ 25,Блок 9 управления имеет тактовый26 вход, выход 27 признака окончанияработы, выходы 28, вход 29 начальной 40установки.Устройство работает следующим образом.Генерирование перестановок. Переставляемые числа находятся в регистрах 3 числа и считываются по выходам14, Передача чисел от одного регистра к другому производятся через ключи 5. При наличие сигнала на первом(втором) управляющем входе ключа 5 Оон пропускает на выход число с первого (второго) информационного входа.Генерирование перестановок можетпроисходить в двух режимах: первыйрежим - задание произвольного чередования перестановок (замкнут первыйпереключатель группы 11; второй режим - автоматически производится полный перебор всех возможных перестановок из Й (замкнут второй переключатель группы 11).Режим 1,Все ключи управляются сигналами с выходов реверсивного регистра 4 сдвига. При этом в реверсивномкольцевом регистре 4 сдвига содержится только одна "1", т.е, сигнал су-.ществует только на одном из выходовреверсивного кольцевого регистра 4сдвига. Для рассматриваемого случая,когда й = 4, используется трехразрядный реверсивный кольцевой регистр 4сдвига,При наличии сигнала на первом выходе реверсивного кольцевого регистра 4 сдвига все ключи 5 открыты попервому управляющему входу и из регистров 3 числа образуется кольцо,которое обозначим К 1.При наличии сигнала на второмвыходе реверсивного кольцевого регистра 4 сдвига первый ключ 5 закрыт,второй ключ 5 открыт по второму управляющему входу, третий ключ 5 открыт по первому управляющему входу.Вследствие этого из регистра 3 числаобразуется кольцо, которое обозначим К 2,При наличии сигнала на третьем выходе регистра 4 первый и второй ключи 5 закрыты, а третий ключ открытпо второму управляющему входу. Вследствие этого из регистров числа образуется кольцо, которое обозначим КЗ.Выбирая то или иное кольцо, т,е, . формируя сигнал на том или инэм выходе реверсивного кольцевого регистра 4 сдвига, можно осуществлять заданную перестановку чисел.Управление реверсивным кольцевым регистром 4 сдвига осуществляется кодами, заносимыми в регистры 1 и 2 сдвига. Эти коды задают характер перестановок, В качестве примера в таблице приведена частная последовательность перестановок, соответствующая ей последовательность состояний реверсивного кольцевого регистра4 сдвига и первоначальных кедов врегистрах 1 и 2 сдвига.Режим 2, Все ключи управляются сигналами с выходов блока 9 управления. Если необходим полный переборвсех перестановок, а также при большом значении М задание частной последовательности перестановок кодами регистров 1 и 2 сдвига трудоемко, за-.з 1363239 4мыкание второго переключателя второй - первый регистр. сдвига имеет четырегруппы 11 задает автоматический ре- разряда), на вход второго регистражиме 18 сдвига, устанавливает в пер 5Предварительно по входу 29 началь. вый триггер 19 и, пройдя через эленой установки в блоке 9 управления менты И 2 и ИЛИ 22, устанавливаетпроисходит сброс в "0" регистров 18 в "О" первый регистр 18 сдвига.сдвига и триггеров 19. Четвертый тактовый импульс, пройПервый тактовый импульс поступает дя через алементы 23 и 24 задержкина вход первого регистра 18 сдвига 1 О и элемент ИЛИ группы 22 устанавливаи появляется на первом выходе блока ет в "0" первый триггер 19.ключа 5, Происходит перестановка К 1, Сигнал, появившийся на втором выВторой.и третий тактовые импульсы ходе блока 9 управления, соединенномпроизводят аналогичные действия. с вторым входом третьего, ключа 5,Четвертый тактовый импульс прохо производит перестановку КЗ.дит на выход первого регистра 18 Пример частной последовательностисдвига (так как для случая й = 4 перестановок,Перестановка Состояние регистра 4 сдвига Код в регистрахЕ В1 2 1234 010 1423 010 0 001 1432 2143 100 0 2314 010 0 100 4231 4123 010 0 4132 001 0 2412 100 010 2341 2134 010 01363239 11 родоо;нптаблицы Код в регистрах Состояние регистрра 4 сдвига Перестановка 3421 1 0 001 3142 010 0 3214 010 0 3241 001 0 1324 100 О 1342 001 0 Пятый, шестой и седьмой тактовыеимпульсы производят перестановку К 1(аналогично первому, второму и третьему тактовым импульсам),Восьмой тактовый импульс с выходавторого регистра 18 сдвига, имеющегодва разряда, проходит на вход третьего регистра 18 сдвига, появляется натретьем выходе блока 9 управления ипроизводит перестановку К 2. Черезэлемент запрета группы 20 сигнал свторого выхода блока 9 управленияустанавливает "1" второй триггер 19,сигнал с выхода которого через вторые элементы И и ИЛИ групп 21 и 22устанавливает в "0" второй регистр18 сдвига.Восьмой тактовый импульс, пройдячерез элементы 23 задержки и первыеэлементы И и ИЛИ групп 21 и 22, устанавливает в "0" первый регистр 18сдвига, а пройдя через элементы 24задержки и 22 ИЛИ, сбрасывает первыйтриггер 19 в "0",Последующие тактовые импульсы повторяют работу, описанную, выше,Двадцать четвертый тактовый им-.пульс появляется на выходе 17 признака окончания работы, так как в данном случае количество всех перестановок при М = 4 равно М = 21.Генерирование сочетаний, При генерировании сочетаний информация считывается с выходов 15 сочетания. Исходная установка такая же, как и врежиме генерирования, перестановок.Переключателями 10 первой группы.задается число элементов из общегочисла, которые должны участвовать в формировании сочетаний, Например, если замкнут первый переключатель первой группы 10, то формируются сочетания 2 и 4, если замкнут второй, то формируются сочетания 3 и 4.Режим работы задается переключателями второй группы 11, как и при формировании перестановок, В автоматическом режиме перебора все сочетания из М .по К, где К = М - 1, формируются за М тактов работы. Формула изобретения 1.устройство для генерирования перестановок и сочетаний, содержащеедва регистра сдвига, М регистров числа (где М - количество элементов перестановок), реверсивный кольцевойрегистр сдвига, (М) ключей, (М)элементов ИЛИ, генератор тактовыхимпульсов и элемент задержки, причемвыходы первого и второго регистровсдвига подключены соответственно квходам сдвига вправо и влево реверсивного кольцевого регистра сдвига,первый выход которого подключен куправляющему входу первого ключа, кпервому управляющему входу второго 5ключа и к первому входу первого элемента ИЛИ, второй вход которого подключен к второму управляющему входувторого ключа и к второму выходуреверсивного кольцевого регистрасдвига, выход элемента задержки соединен с .синхровходами всех регистровчисла, выход 1-го регистра числа(1 1,М) подключен к первому информационному входу (1+1)-го ключа, 7 1 ЗЬ выход которого соединен с информационным входом (+1)-го регистра числа, выход (М)-го регистра числа подключен к информацинному входу .М-го регистра числа, выход которого соЕдинен с вторыми информационными входами с второго по (М) -й ключей и с информационным входом первого ключа, выход которого подключен к информационному входу первого регистра числа, выход -го элемента ИЛИ ( = 1, М) подключен к первому управляющему входу (1+2)-го ключа и к первому входу (1+1 )-го элемента ИЛИ, второй вход которого подключен к (1+2)-му выходу реверсивного кольцевого регистра сдвига, выход (М-З)" го элемента ИЛИ соединен с первым управляющим входом (М)-го ключа, (+1)-й выход реверсивного кольцевого регистра сдвига подключен к второму управляющему входу (+1)-го ключа, выходы регистров числа являются соответствующими выходамиперестановки устройства, о т л и ч а ю щ е е с я тем, что, с целью ресширения функциональных возможностей устройства путем обеспечения формирования сочетаний из М элементов по К, где КМ, а также возможности задания автоматического режима полного перебора всех Мперестановок, устройство содержит блок управления, две группы переключателей, (К =1) дополнительных элементов ИЛИ и К групп элементов И, причем входы переключателей первой группы соединены с выходом эле-, мента задержки, выход (К)-го переключателя первой группы соединен с первыми входами элементов И К-й группы и с первым входом (К)-го дополнительного элемента ИЛИ, выход (К)-го переключателя первой группы подключен к второму входу (К)-го дополнительного элемента ИЛИ, выход которого соединен с первыми входами элементов И (К)-й группы и с первым входом (К)-го дополнительного элемента ИЛИ, выход первого переключателя первой группы соединен с вторым входом первого дополнительного элемента ИЛИ, выход которого соединен с первыми входами элементов И первой и второй групп, вторые входы элементов И групп подключены к выходам соответствующих разрядов первых К регистров числа соответственно, а выходы элементов3239 8И 1-й группы (1-К) являются соответствующими 1-го выхода сочетания устройства, выход генератора тактовых 5импульсов подключен к входам переключателей второй группы, выход первого переключателя второй группы подключен к входам сдвига регистров сдвига, выход второго переключателя 10 второй группы - к входу элемента задержки и к тактовому входу блока 11 20 25 30 35 40 45 50 55 управления, вход начальной установкикоторого является входом установкиустройства, первый выход блока управления подключен к управляющему входупервого ключа, а выходы с второго по(М)-й блока управления подключенысоответственно к вторым управляющимвходам ключей с (М)-го по второй,М-й выход блока управления являетсявыходом признака окончания работыустройства,2, Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок управления содержит (М) регистров сдвига, группу из (М) триггеров, группу из (М) элементов запрета, группу из (М) элементов И, группу из(М) элементов ИЛИ, два элементазадержки и элемент ИЛИ, причем первыйрегистр сдвига содержит М разрядов,а каждый следующий - на единицуменьше, тактовый вход блока подключен к входу сдвига первого регистрасдвига, выход 1-го регистра сдвига(М)-го регистра сдвига являетсяМ-м выходом блока, вход начальнойустановки блока управления подключенк первому входу элемента ИЛИ, первымвходам элементов. ИЛИ группы и входуустановки в "0"(М)-го регистра сдвига, выход первого разряда первого регистра сдвига является первым выходомблока, выход 1-го регистра сдвига(где+ К = М - 1) подключены квходам соответственно с ( + 1)-гопо (+К)-й регистров сдвига, выход1-го элемента запрета являетсяставитель И.Захаревичхред М,Дидык Корректор М.П едактор А.Маковская ираж 671 аказ 6364 42 Подпис рственного комитета ССзобретений и открытийЖ, Раушская наб., д ВНИИ и 113035, Госуд делам осква,/5 изводственно-полиграфическое предприятие, г.ужгород роектная,9 1363239 10подключен к первому входу 1-го эле- динен с вторыми входами элементов мента И группы, выход которого соеди И группы и входом второго элемента нен с первым входом 1-го элемента задержки, выход которого соединен ;ИЛИ группы, выход которого подключен б с вторым входом элемента ИЛИ, к входу установки в "0" 1-го ре- выход которого соединен с вхогистра сдвига, тактовый вход блока дами установки в 0 триггеров ,через первый элемент задержки сое- группы.