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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(51)М. Кл. С 06 Р 15/20 с присоединением заявки М Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 1507.80(72) Авторы изобретения С. Н. Борисов, О, В. Викторов, Л. Н. Минина и А. М. Романкевич Киевский ордена Ленина политехнический институтимени 50-летия Великой Октябрьской социалистическойеволю ии(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК Изобретение относится к области автоматики и вычислительной техники, предназначено для получения всех о 1 перестановок из о величин и может использоваться для решения комби наторных задач, а также в системах контроля для генерации кодовых последовательностей.Известно устройство для перебора перестановок, содержащее счетчики, схемы ИЛИ и И (11 .Недостатком его является большая сложность.Наиболее близким по своей технической сущности к данному изобрете нию является устройство для перебора сочетаний, содержащее в каждом из и разрядов регистр, элементы И, ИЛИ, элемент задержки, причем вход первого элемента И соединен с тактовым 20 входом устройства, а выход его подключен к тактовому входу регистратого же разряда, информационный вход которого соединен с первым входом второго элемента И того же разряда 25 и с выходом элемента ИЛИ следующего разряда, выход регистра каждого разряда соединен с первым входом третьего элемента И того же разряда, выход которого соединен с первым входом 30. 2элемента ИЛИ того же разряда, второйвход которого подключен к выходувторого элемента И того же разряда,устройство содержит, кроме того,дополнительный регистр, тактовыйвход которого является тактовымвходом устройства, информационныйвход которого подключен к выходуэлемента ИЛИ первого разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда 21 .Устройство содержит, кроме того,ключи, мультивибратор, блок регистрации. Недостатком его является низкое быстродействие.Целью изобретения является повышение быстродействия,Цель достигается тем, что каждый-тый (= 1, . и ) разряд устр;йства содержит счетчик по модулю 1 + 2и четвертый элемент И, первый и второй инверсные входы которого соеди.нены с выходами счетчика соответственно последующего и предыдущегоразрядов, третий выход четвертого элемента И каждого разряда через соответствующий элемент задержки подклюиен к тактовому входу устройства,высод счетчика каждого разряда соединен4841 со вторым инверсным входом первого цтретьего элементов И и со вторымвходом второго элемента И того жеразряда, причем выходы счетчиков первого и последнего разрядов и разрядные выходы регистров являютсявыходами устройства.На чертеже представлено устройствб для перебора перестановок (дляп=4)Устройство содержит регистр 1,элемент И 2, элемент ИЛИ 3, элемент И 4, счетчик 5, элемент И б,тактовый вход 7, элемент 8 задержки, элемент И 9, разрядные выходы 10регистров, выходы 11 счетчика последнего разряда, выход 12 счетчикапервого разряда, вспомогательный регистр 13,Устройство работае следующимбразом.Перед началом работы но все пятьрегистров 1 заносятся коды переставляемых величин, счетчики 5 сбрасываются н состояние О, вследствие чегооткрываются элементы И 2 и И б, запираются элементы И 4 и выходы регистров 1 подключаются ко входам соседних слева регистров 1, причем выходы первого регистра 1 подключаютсяко входам пятого регистра 1, запираются элементы И 9 и на нходы счетчиков по модулю 5, 4, 3 тактойые импульсы не поступают.Работа устройства начинается сподачей на вход 7 серии тактовыхсигналов.Величины задержек элементон задержки, подключенных соответственнок счетчикам 5 по модулю б, 5, 4,выбираются таким образом, чтобы ониудовлетворяли соотношению: тт М: т.6 5 4) , )О, вследствие чего на счетчик 5по модулю б тактовые импульсы начинают поступать с запаздыванием наС=п(где:п(4,е - длительность тактового импульса)При поступлении тактовых сигналон на регистры 1 коды, записанные 4н них через элементы И 2 и ИЛИ 3,сдвигаются в соседние слева регистры 1, причем из первого регистра 1сдвиг происходит н пятый регистр.После поступления на счетчик 5по модулю 5 пяти тактовых импульсов на его выходе появляется единичный сигнал, который запрещает считыго т о 30ни ет пу 35 осле поступления д льсов на вход счет ,на его выходе поя сигнал, Этот сигнал ледующего тактовог чик 5 по модулю 4, подключенный к ег соответствующие э рает соответствующ дстние чего коды с вух тактовыхчика 5 по модунляется единичзапрещает подао сигнала назапирая элементо входу; запилементы И 2,ий элемент И 4,выходов первоимпу лю ы ный О чу с счет И 9,5 рает отпи нсление кодов из регистра 1, открывает элемент И 9 и на его счетчик 5 пб модулю 5 проходит 1 тактовый импульс, запирает соответствующие элементы И 2 и И б, отпирает соответствующие элементы И 4, вследствие чего цепь из пяти регистров зам кается в обходпятогорегистра 1.С приходом шестого тактового имгульса йасчетчик 5 по модулю б, если нет запрета с выхода счетчика по модулю 5, счетчик сбрасынаетсяв состояние О, закрывая при этом элемент И 9, подключенный ко входусчетчика 5 по модулю 5.Когда на вход счетчика 5 по модулю 5 поступит 4 тактовых импульса,на выходе этого счетчика, появитсяединичный сигнал. Этот сигнал запрещает подачу следующего тактовогосигнала на счетчик 5 по модулю бзапирая схему И 9, подключенную к евходу, разрешает подачу следующеготактового сигнала на счетчик 5 помодулю 4, элемент И 9, подключенныйк его входу, открывает, запираетсоответствующие элементы И 2 и,И ботпирает соответствующие элементыИ 4, вследствие чего цепь из пяти15 регистров 1 замыкается в обход пятого и четвертого регистров 1, выходной сигнал со счетчика 5 по модулю б запрещает считывание кодоврегистров 1.20 С приходом следующего тактовогоимпульса на счетчик 5 по модулю 5,если нет запрета с выхода счетчика 5 по модулю 4, счетчик сбрасывается в состояние О, открывая приэтом элемент И 9, подключенный ковходу счетчика 5 по модулю б, исчетчик 5 по модулю б сбрасываетсяв состояние О..После поступления на счетчик 5модулю 4 трех тактовых импульв на его выходе появляется едичный сигнал. Этот сигнал запрещаподачу следующего тактового имльса на счетчик 5 по модулю 5,пирая элемент И 9, подключенныйего входу, разрешает подачу следующего тактового сигнала на счетчик5 по модулю З,открывая элемент И 9,подключенный к его входу; запираетсоответствующие элемента И 2 и И б,О отпирает соответствующие элементыИ 4, вследствие чего цепь иэ пяти реристров 1 замыкается в обход пятого,четвертого и третьего регистров 1,выходной сигнал со счетчика 5 по модулю б запрещает считывание кодов иэрегистров 1,С приходом следующего тактовогоимпульса на счетчик 5 по модулю 4, еслинет запрета с выхода счетчика по модулю 3, он сбрасывается в состояниеО, открывая элемент И 9, подклюЧенныйко нходу счЕтчика 5 по модулю 5. После этого сбрасываются в состояниеО счетчик 5 по модулю 5 и счетчик 55по модулю б.2 2 4 2 2 5 1 2 3 0 0 2 3 1 2 3 2 2 3 3 2 3 4 2 3 5 2 4 5 Э 4 5 0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 4 1 5 1 5 1 0 1 0 0 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 2 0 0 2 1 0 2 2 0 2 3 0 2 4 О 2 5 О 3 0 0 3 1 1 1 ,1 1 1 1 1 1 1 0 3 2 0 3 3 0 3 4 0 3 5 0 4 5 1 0 0 1 0 1 1 0 2 1 0 3 1 0 4 1 0 5 1 1 0 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 2 0 1 2 1 1 2 2 1 2 3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 2 4 1 2 5 1 3 0 1 3 1 1 3 2 1 3 3 1 3 4 го регистра 1 передаются на их жевходы,Кроме того, сигнал с выхода счетчика 5 по модулю 3 поступает на выход 12.Работа устройства поясняется примером перестановки пяти кодов.Ниже даны состояния соответственнопервого, второго пятого регистров1, счетчиков 5 по модулям 3, 4, 5, б,выхода 11, запрещающего считывание цкодов из регистров на каждом такте.0 1 2 3 4 5 0 0 0 0 01 2 3 4 5 1 0 О 0 1 02 3 4 5 1 2 0 0 0 2 03 4 5 1. 2 3 0 0 0 3 О451234000405 1 2 3 4 5 0 0 0 5 1б 2 3 4 1 5 0 0 1 0 0734152001108 4 1 5 2 3 0 0 1 2 09 1 5 2 3 4 О О 1 3 О 2010 52 3 4 1 0 0 1 4 011234150015112341250020013 41 2 5 3 0 0 2 1 014 12 5 3 4 0 0 2 2 015 25 3 4 1 0 0 2 3 016 53 4 1 2 0 0 2 4 017 34 1 2 5 0 0 2 5 118 41 2 3 5 0 0 3 0 019 1 2 3 5 4 0 0 3 1 О ЗО20 23 5 4 1 0 0 3 2 021354120033022541230034023 41 2 3 5 0 0 3 5 124 1 2 3 4 5 0 0 4 5 13525 2 3 1 4 5 0 1 0 0 026 31 4 5 2 0 1 0 1 027 14 5 2 3 0 1 0 2 028 45 2 3 1 0 1 0 3 029 52 3 1 4 0 1 0 4 030 2 3 1 4 5 0 1 0 5 131 31 4 2 5 0 1 1 О 032142530111033 42 5 3 1 0 1 1 2 034 25 3 1 4 0 1 1 3 035531420114036 31 4 2 5 0 1 1 5 137 14 2 3 5 0 1 2 0 038423510121039235140122040351420123041 5 1 4 2 3 О. 1 2 4 042 14 2 3 5 0 1 2 5143 32 3 1 5 0 1 3 О 044 23 1 5 4 0 1 3 1 045 3 1 5 4 2 0 1 3 2 0 5546 15 4 2 3 0 1 3 3 047 54 2 3 1 0 1 3 4 048 42 3 1 5 0 1 3 5 149231450145150 3 1 2 4 5 0 2 0 0 О, 6051 12 4 5 3 0 2 0 1 052 2 4 5 3 1 0 2 0 2 053453120203054 5 3 1 2 4 0 2 0 4 055 3 1 2 4 5 0 2 0 5 1 65 56 1,2 57 24 58 43 59 35 60. 51 61 12 62 24 63 43 64 31 65 15 66 52 67 24 .68 4369 31 70 12 71 25 72 54 73 43 74 31 75 12 76 21 77 13 78 34 79 45 80 52 81 21 82 13 83 34 84 42 85 25 86 51 87 13 88 34 89 4 2 90 21 91 15 92 53 93 34 94 42 95 21 96 13 97 35 98 54 99 42 100 2 1 101 1 Э 102 3 2 103 2 4 104 4 5 105 5 1 106 1 3 107 3 2 108 2 4 109 4 1110 1 5 111 5 3 112 3 2113 2 4 114 4 1 115 1 3 116 3 5 117 5 2 118 2 4119 4 1 120 1 3 121 3 2 122 2 5 123 5 4 4 3 3 5 5 1 1 2 2 4 4 3 3 1 1 5 5 2 2 4 4 3 3 1 1 2 2 5 5 4 4 3 3 1 1 2 2 4 3 4 3 4 4 5 5 2 2 1 1 3 3 4 4 2 2 5 5 1 1 3 3 4 4 2 2 1 1 5 5 3 3 4 4 2 2 1 1 3 3 5 5 4 4 2 2 .1 1 3 3 4 2 4.4 5 5 1 1 3 3 2 2 4 4 1 1 5 5 3 3 2 2 4 4 1 1 3 3 5 5 2 2 4 4 1 1 3 3 2 2 5 5 4 4 1 1 3Прототип предлагаемого изобретения обеспечивает перебор всех о перестановок из п кодов затактов (в случае для 5 чисел - 3125 тактов). По сравнению с прототипом, предлагаемое устройство обеспечивает перебор всех о перестановок из о кодов за ,Х.11 тактов (в случае для 5 чисел - 153 такта). Формула изобретения Устройство для перебора перестановок, содержащее вспомогательный регистр, и также в каждом из о разрядов регистр, элементы И, ИЛИ, элемент 124 4 125 1 126 3 127 2 128 1 129 4 130 5 131 . 3 132 2 133 134 4 135 3 136 5 137 . 2 138 139 4 140 3141 2 142 5 143 1 144 4 145 3 146 2 147 1 148 5 149 4 150 3 151 2 152 1 153 1 1 3 3 2 г 1 4 4 5 5 3 3 2 1 1 4 4 3 3 55 2 2 1 1 4 4 3 3 2 2 5 5 1 1 4 4 3 3 2 2 1 1 5 5 4 4 3 3 2 2 1 1 3 2 3 2 3 2 5 1 1 4 5 1 1 4 5 1 2 5 3 1 2 3 2 1 2 2 1 1 2 1 4 1 2 4 5 1 2 3 5 1 5 2 1 2 2 1 1 2 1 4 1 2 4 3 1 2 3 5 1 2 2 5 1 2 5 1 1 2 1 4 1 2 4 3 1 2 3 2 1 2 2 5 1 2 1 5 1 2 5 4 1 2 4 3 1 2 3 2 1 2 2 1 1 2 1 5 1 2 4 5 1 2 4 5 1 3 4 5 2 3 4 5 0 0 3 5 1 4 5 1 о о о О 1 О О 2 0 О 3 О О 4 О О 5 1О О 1 1. О 1 2 03 О 1 4 0 1 5 1.2 0 0 2 1 0 2 2 О 2 3 0 2 4 0 2 5 1 3 О О 3 1 О 3 2 0 3 3 О 3 4 О 3 5 1.5 г 4 5 1 4 5 1 о о о задержки, причем первый вход первогоэлемента И каждого разряда соединенс тактовым входом устройства, а выходподключен к тактовому входу регистратого же разряда, информационный входкоторого соединен с первым входомвторого элемента И того же разряда ис выходом элемента ИЛИ следующегоразряда, выход регистра каждого разряда соединен с первым входом третьего элемента И того же разряда, выходкоторого соединен с первым входомэлемента ИЛИ того же разряда, второйвход которого подключен к выходувторого элемента И того же разряда,тактовый вход вспомогательного регистра является тактовым входом устройства, информационный вход которого подключен к выходу элемента ИЛИпервого разряда, а выход дополнительного регистра соединен с первым20 входом второго элемента И последнегоразряда, отличающийсятем, что, с целью повышения быстродействия, каждый-тый ( = 1,д)разряд устройства содержитсчетчик помодулю+ 2, четвертый элемент И,первый и второй инверсные входы которого соединены с выходами счетчика соответственно последующего и предыдущего разрядов, третий выход четвертого элемента Й каждого разрядачерез соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого раз)ряда соединен со вторым инверснымвходом первого и третьего элементовИ и со вторым вЛдом второго элемента И того же разряда, причем выходысчетчиков первого и последнего разрядов и разрядные выходы регистровявляются выходами устройства.Источники информации,принятые во внимание при экспертизе74841 б Составитель Е.,Пупыдактор Т. Лошкарева Техред А.Щепанская ректор М. Коста одписное Зак иал ППП "Патент", г. Ужгород, ул. Проектная,41/37цНИИПИ Государпо делам изо35, Москва, Х51комитета СССРи открытийая наб д, 4/ Тираж твенног ретений Раушс