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

Оп ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик р 11995093(22) Заявлено 11.0881 21) 3331309/18-24 с присоединением заявки Йо Государственный комитет СССР по делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК Изобретение относится к автоматйке и вычислительной технике и может использоваться для решения комбинаторных задач, а также в системах конт роля для генерации кодовых последова" тельностей.Известно устройство для выбора перестановок, содержащее кольцевые регистры, линии зацержки, пороговые элементы, генератор импульсов и блок логики, в состав которого входят сумматор, импликатор и ждущий мультивибратор (1). Недостатком известного устройстваявляется низкое быстродействие (перебор всех и, перестановок из и кодовобеспечивается за и"тактов),Наиболее близким по техническойсущности к предлагаемому является устройство для перебора перестановок-,содержащее вспомогательный регистр,а также в каждом 1-м (1 = 1,2 и)разряде регистр, элементы И, ИЛИ, счетчик по модулю (1 + 2), элемент задержки, причем первый вход первогоэлемента И каждого разряда соединенс тактовым входом устройства, а выходподключен к тактовому входу регистратого же разряда, информационный -вход ЗО скоторого соединен с первым входом второго элемента И того же разряда и с выходом элемента ИЛИ следующего разряда, выход регистра каждого разряда соединен с первым входом третьего элемента И того же разряда, выход которого соединен с первьи входом элемента ИЛИ того же разряда, второй вход которого подключен к выходу второго элемента И того же разряда, тактовый вход вспомогательного регистра является тактовым входом устройства, информационный вход которого подключен к выходу элемента ИЛИ первого,разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда, первый и второй инверсный входы четвертого элемента И соединены с выходами счетчика соответственно последующего и предыдущего разрядов, третий выход четвертого элемента И каждого Разряд через соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого раз" ряда соединен с вторым инверсными входом первого и третьего элементов И и с вторьм входом второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов иразрядные выходы регистров являютсявыходами устройства 21.Недостатком известного устройстваявляется низкое быстродействие (перебор всех и перестановок из и кодов5осуществляется за с 1 тактов),Цель изобретения - повышение быстродействия устройства.Поставленная цель достигается тем,1 то устройство для перебора перестановок,содержащее (в)счетчиков с коэффи-, циентами пересчета 2,3,исоответственно,регистр(я) групп элементов И иИЛИ, причем выход первого счетчикаподключен к первому входу первого элемента И первой группы, выход р-госчетчика (Р = 2,3 и) подключен к первому входу первого элементаИ р-й группы, выход которого подключен к счетному входу (р+1) -го счетчика, выход первого элемента И первой группы подключен к счетному входу второго счетчика, введены (и)групп элементов И-ИЛИ и дешифраторы, причем каждая Ь-я группа элементовИ-ИЛИ (Ь = 1,2 и) содержит Ьэлементов 2 Й-ЙЛи .и один элемент(Ь+1) И-ИЛИ, первый вход устройства соединен с первыми входами первых элементов И первой группы элемента ЗО 2 И-ИЛИ, А-й вход устройства (1 2,3 и) соединен с первым входом 1-го элемента И элемента 1 И"ИЛИ(1-1)-й группы и с первыми входами вторых элементов И элементов 2 И-ИЛИ 35(1+1)-й группы, выходы элементов 2 ИИЛИ первой группы соединены с первыми входами первых элементов И второй группы элементов 2 И"ИЛИ соответственно и с первыми входами элементов И Щ элемента ЗИ-ИЛИ второй группы соответственновыходы )-й группы элементов 2 И-ИЛИ и элемента ( 1 +1) И-ИЛИщ 12п) соединены с первыми входами перв эл ентов И (+1)-й 45 группы элементов 2 И-ИЛИ соответственно и с первыми входами элементов И элемента (+2) И-ИЛИ (+1)"й группы соответственно, выходы (и"1)-й группы элементов 2 И-ИЛИ и элемента пИ-ИЛИ о соединены с выходами устройства соответственно, первый выход первого дешифратора соединен с вторым входом второго элемента И второго элемента 2 И-ИЛИ первой группы, второй выход первого дешифратора соединен с вторым входом первого элемента И второго элемента 2 И-ИЛИ первой группы и с вторыми входами элементов И первого элемента 2 И-ИЛИ первой группы, первый вы", ход Х-го дешифратора (2 - 2,3, . 60 6 ;, 1) соединен с вторым входом (3+1)- го элемента И элемента (2+1) И-ИЛИ й-й группы, к-й выход 2-го дешифратора (к - 2,3 . 1+1) соединен с вторьм входом (Р - к + 2)-го элемента И 65 элемента (2+1) И-ИЛИ Й-й группы и с вторыми входами элементов И (2-к+2)-го элемента 2 И-ИЛИ Й-й группы, входы дешифраторов соединены с выходами счетчиков соответственно, вход тактовых импульсов устройства соединен со счетным входом первого счетчика, выход которого подключен к первому входу второго элемента И первой группы, выход которого подключен к первому входу элемента ИЛИ, вторые входы элементов И первой группы подключены к первому выходу п-го дешифратора, выход В-го счетчика (Р Ф и) подключен к первому входу второгоэлемента И р-й Группы, выход которого подключен к р-му входу элемента ИЛИ, вторые входы элементов И р-й группы подключены к р-му выходу и-го дешифратора, выход (и) -го счетчика подключен к (п) -му входу элемента ИЛИ, выход которого подключен к шине конца работы устройства, выходы регистра подключены к входам п-го дешифратора соответственно.На чертеже представлена блок-схема предлагаемого устройства.Устройство содержит счетчики 1-1 1 с коэффициентами пересчета 2, 3, 4,и, дешифраторы 2-2 , 3, ре-гистр 4, элементы 2 И-ИЛИ 5"-5" " ЗИи-ф ИЛИ 6, 4 И-ИЛИ 7 пИ-ИЛИ 8, элементы И 9-9 2, 10-10 2, элемент ИЛИ 11, входы 12-12, 13, выходы 14- .14, выходную шину 15 конца работы,Первый вход 12соединен с первыми входами первых элементов И первой группы элементов 2 И-ИЛИ 5-5, 1-й вход 12; (1 = 2,3 и) соединен с первым входом 1-го элемента И элемента 1 И-ИЛИ и с первыми входами вторых элементов И (1-1)-й группы элементов ,2 И-ИЛИ 51" -5; 1, и-й вход 12 п соединен с первым входом и-го элемента И элемента пИ-ИЛИ 8 и с первьми входами вторых элементов И (и"й) -й группы элементов 2 И-ИЛИ 5 - 5 пвыходы перИ 1 вой группы элементов 2 И-ИЛИ 5- 5 д соединены с первыми входами элементов И второй группы соответствующих элементов 2 И-ИЛИ 5 - 5 и с первыми входами соответствующих элементов И элемента. ЗИ-ИЛИ б, выходы ,-й группы элементов 2 И-ИЛИ 5 - 5 и элемента ( ) +1) И-ИЛИ ( 1: 1, 2п) соединены с первыки входами первых элементов И соответствукщих элементов 2 И-ИЛИ 5)+ -5+" и с первыми входами соответствующйх элементов И элемента ( ) +2) И-ИЛИ, выходы (и)-й группы элементов 2 И-ИЛИ 51 "- 5" и элемента пИ-ИЛИ 8 соединены с соответствующими выходами 14 - 14 , первый выход первого дешифратора 2 соединен с вторым входом второго элемента И элемента 2 И-ИЛИ 5 1, второй выход первого дешифратора соединен с вторью входом первого элемента И элемента995093 1234 2134 1324 2314 3214 3124 1243 0 О0 3 0 0 О 2 И-ИЛИ 5" и с вторым входом второго открытый элемент И 10 и элемент ИЛИ элемента И и вторьи инверсньм входом соединен с выходной шиной 15 конца первого элемента И элемента 2 И-ИЛИ 51, работы. первый выход В-го дешифратора (2.-2, 3 п.-1) соединен с вторив входом Счетчики 1 - 1 находятся в нуле(У+1) элемента И элемента (2+1)И-ИЛИ, вом состоянии, на первых выходах дек-й выход Ю-го .дещифратора (к - 2, шифраторов 2- 2 1 - высокие потен"3,2+1) соединс:н с вторым входом циалы, которые поступают на З.-е эле- (3 - к+2) элемента И элемента (2+1)И- менты И элементов 1 И-ИЛИ, в злемен- ИЛИ, прямым входом второго элемента тах 2 И-ИЛИ открыты первые элементы И и инверсным входом первого элемен- О И, так как на инверсные входы не пота И элемента 2 И-ИЛИ 5 . входы дано высоких потенциалов. Следователь дешифраторов 21- 2соединены с вы- но, первый вход соединен с первма выходами соответствукщих счетчиков 11- ходом, второй - с вторыи, третий - с 1 . вход 13 тактовых импульсов .сое- третьим и т.,д. динен с входом счетчика 1, выход ко В зависимости от состояний счетчи" торого соединен с входами элементов ков 1., - 1 входы 12- 12 п будут И 9, И 10, выход элемента И 91 сое- подключаться через элементы И-ИЛИ к инеи с входом счетчика 1, выходы различным выходам 14- 14, Так, в лементов И 101 - И 10 соединены с зависймости от состояния счетчика 1, входами элемента ИЛИ 11, выход р-го 20,второй вход 122 может быть подключен счетчика соединен с входами элемен" к второму выходу 142. (состояние счеттов И 9 и И 10 , выход элемента И 9 чика 11 - О) и к первому выходу 14 соединен с входом (р+1) счетчика, вы-, а первйй вход 12- к второму:выходу ход (и) счетчика 1соединен с вхо- .14 2 (состояние счетчика 1., - 1 . В дом элемента ИЛИ 11, выход регистра 25 зависимости от состояния второго счет соединен с входами дешнфратора 3, чика 12 третий вход 12 з подключей к выходы дешифраторы 3 соединены соот- третьей выходной шине 143 (состояние ветственно с инверсньвжи входами эле- О), третий вход 12 з подключен к втоментов И 9 и с входами элементов И 10, рой; а второй вход 12 з - к третьему выход элемента ИЛИ 11 соединен с вы выходу (состояние 1), третий вход ходной шиной 15 конца работы, подключен к первому, а первый вход -устройство работает следукв 1 им об- к третьему выходу (состояние 2),. В разом. зависимости от состояния р-го счетчиВ.регистр 4 записывается число в, ка 1 Р (р+1) вход подключен к (р+1)-музначение которого равно числу. пере выходу (сЬстояние О), (р+1) вход под, станавливаемых чисел (а = 2,3 ключен к р-му выходу, а р-й вход - к п), Если в = и, то в регистр 4 чис- (р+1) выходу(состояние 1) и т.д., ло не записывается. (р+1) вход подключен к первому выходу,Для примера рассмотрим работу уст- а первый вход - к (Р+1-) выходу (сосройства для перестановки четырех чи-тояние р), сел. В регистр 4 записывается число Если на входы подать числа, то на 4. На третьем выходе дешифратора 3 выходах в зависимости от состояний высокий потенциал и элемент И 93 зак- счетчиков получат все возможные перерыт, элемент И 10 З открыт, а осталь- становки этих чисел. Возможные переные элементы И 9 открыты, элементы становки для четырех чисел представле- И 10 закрыты, выход счетчика 1 черезРы в таблице. эавиши ш шшиюаюеишшшш ее шшю Вашюшаишш ТИ, . Состояние счетчика Результат - УВ ш ш ш ш и и те ш аюшюЗФ таею ви1 а 1 Зиеш ееиавиаюювююююв юювииве иееатею ша таюишееРезультат 1 о 0 1 о 2 0 О 1 о О 1 12 13 15 О 2 1 б 17 18 О О При поступлении 24 тактового импульса счетчики 1 - 1 устанавливают-.45Эся в нулевое состояние, а импульс с выхода счетчика 1 З поступает через элемент И 10 З, элемент ИЛИ 11 на выходную шину 15 конца работы.За 24 такта работы обеспечивается перебор всех перестановок из четырех чисел. Если требуется обеспечить перебор перестановок 5 чисел, то в ре.- гистр 4 записывается число 5, элемент И. 10 открыт, а элемент И 9, закрыт и выход четвертого счетчика 14 соеди нен с выходной шиной 15 через элемен- ты И 10.4 и ИЛИ 11. После поступления 24 тактового импульса счетчики 1-1 Э устанавливаются в нулевое состояние, а счетчик 1 - в единичное и работа ЬО устройства продолжается до тех пор, пока не поступит 120 тактовый импульс, который установит счетчики 1 - 1 в нулевое состояние и импульс с выхода четвертого счетчика поступит через 45 2143 1 3 4 2 2341 3241 3 1 4 2 1 4 3 2 2431 14 23 2 4 1 3 3 4 1 2 3 4 2 1 4 2 3 1 4 1 3 2 4321 4 3 1 2 4 2 1 3 4123 1234 элементы И 104 и .ИЛИ 11 на выходнуюшину 15 конца работы,Аналогично устройство работает припереборе перестановок любого щ ( ичисла чисел,предлагаемое устройство для перебора перестановок по сравнению с устройством-прототипом имеет большее быстродействие за счет исключения повторяющихся перестановок, Предлагаемое устройство для и чисел обеспечивает все перестановки за и тактов работы,п а устройство-прототип за Е 1, чтоина, 1 тактов больше, чем в изобретенин. В предлагаемом устройстве исключены линии задержки, используемые в устройстве-прототипе. Это обеспечи" вает возможность дальнейшего увеличения быстродействия устройства засчет повышения частоты тактовых импульсов.Кроме того, устройство-прототип обеспечивает перебор перестановок только и чисел. Изобретение же позво-. ляет осуществлять перебор любого количества в чисел (ш = 2,3 п).за в, тактов работы, что также расширяет область его применения. формула изобретения 1 О Устройство для перебора перестановок, содержащее (и) счетчиков .с коэффициентами пересчета 2,3.и 15 :оответственно, регистр, (и) групп элементов И и ИЛИ, причем выход первого счетчика подключен к первому. входу первого элемента И первой груп-.пы, выход р-го счетчика (р : 2,3 2 О и) подключен к первому входу перво- . го элемента И р-й группы, выход которого подключен к счетному входу (р+1)- го счетчика, выход первого.элемента Иервой группы подключен .к счетномуходу второго счетчика, о т л и ч а ю щ е е с я тем, что, с целью повышения его быстродействия, в устройство введены (и) групп элементов И-ИЛИ и дешифраторы, причем каждая Ь-я груп 3 О па элементов И-ИЛИ (Ь = 1,2. п) содержит. Ь элементов 2 И-ИЛИ и одий элемент (Ь+1) И-ИЛИ, первый вход уст.-ройства соединен спервыми входами первых элементов И первой группы эле- З 5 мента 2 И-ИЛИ, 1-й вход устройства (Х 2,3 п).соединен с первым входом 1-го элемента И элемента 1 ИИЛИ (1-1)-й группы и с первыми входа ми вторых элементов И элементов 2 ИИЛИ (3.+1).-й группы, выходы элементов 2 И-ИЛИ первой групйы соединены с первыми входами первых элементов И второй группы элементов 2 И-ИЛИ соответственно и с первыми входами элементов И элемента ЗИ-ИЛИ второй группы соответственно, выходы 1-й группы элементов 2 И-ИЛИ и элемента ( +1). И-ИЛИ ( ) -1,2.и"2 соединены с первыми входами первых элементов И (+1)-й группы элементов 2 И-ИЛИ 50 соответственно и с первыми входамиэлементовИ элемента ( 1 +2) И-ИЛИ(+1)-й группы соответственно, эы"ходы (и) -и группы элементов 2 И-ИЛИи элемента пИ-ИЛИ соединены с выходами устройства соответственно, первыйвыход первого дешифратора соединен свторьм входом второго элемента И второго элемента 2 И-ИЛИ первой руппы,второй выход первого дешифратора соединен с вторыми входом первого элемен"та И второго элемента 2 Ч-ИЛИ первойгруппы и с вторыми входами элементовИ первого элемента 2 И-ИЛИ первой группы, первый выход В-го дешифратора(2+1) И-ИЛИ 1-й группы, к-й выходВ-го дешифратора (к : 2,3 2+1)соединен с вторьи входом (3 - к+2) -гоэлемента И элемента (2+1) И-ИЛИ В-йгруппы и с вторыми входами элементовИ (Р-к+2)-го элемента 2 И-ИЛИ 1-.й группы, входы дешифраторов соединены свыходами счетчиков соответственно,вход тактовых импульсов устройствасоединен -со счетным входом первогосчетчика, выход которого подключен кпервому входу второго элемента И пер"вой труппы, выход которого подключенк первому входу элемента ИЛИ; вторыевходы элементов И первой группы под"ключены к первому выходу пго дешиф-,ратора, выход К-го счетчика Я Ф п),подключен .к первому входу второго элемента И р-й группы, выход которогоподключен к р-му входу элемента ИЛИ,вторые входы элементов И р-й группыподключены к р-му выходу и-го дешифратора, выход (и)-го счетчика подключен к (и)-му входу элемента ИЛИ,выход которого подключен к шине конца работы;устройства, выходы регистра подключены к входам и-го дешифратора соответственно.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРВ 446057, кл. 6 06 Р 7/38, 1972,2. Авторское свидетельство СССРМ 748416, кл, 6 06 Р 15/20, 1978 (прототип).995093 оставитель В. Кайдановехред Ж,Кастелевич Корректор Г,Огар ич дактор А. Филиал ППП Патент, г. Ужгород, ул. Проект аказ Б 46/34 Тира ВНИИПИ Госу по.делам 113035, Москва704 арственног изобретени Ж, Рау Подписное омитета СССР открытий ая наб., д. 4