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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК . С 06 С 1 У ОП Е ИЗ ЕНИ СВИДЕТЕЛЬСТВ Н АВТОРСН ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(7). Грузинский ордена Ленина и ордна Трудового Красного Знамени поли"технический институт им. В. И. Лени(53) б 81 33 (088 8)6) 1.Авторское свидетельство СССРР 374 б 06, кл. С 06 Г 15/32, 1970;2. Авторское свидетельство СССРР 911535, кл. С 06 Г 15/26, 1978(прототип). Ь 4) 67) 1 е УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЕДИНЕНИЙ, содержащее элемент И, первую и вторую группы элементов ИЛИ, первый элемент задержки , и запоминающих элементов (где и " .число переставляемых кодов), первую, вторую третью и четвертую группы элементов И, переключатель, причем выходы за.поминающих элементов, начиная с второго, подключены к первым входам соответствующих элементов И первой группы, первые входы элементов И второй группы соединены с выходами соответствующих запоминающих элементов," первый контакт переклвчателя соединен с первым входом первого элемента И, второй вход которого подключен к первому входу устройства, выходами устройства являются выходы элементов И второй группы, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия,оно содержит Ь) регистров сдвига, второй элемент за;держки, причем выходы, кроме первого и последнего, четных регистров сдвига соединены с входами соответствующих 801057952 элементов ИЛИ первой группы, выходыкоторых соединены с вторыми входамисоответствующих четных элементов Ипервой группы, вторые входы нечетныхэлементов И которой соединены с вторыми выходами соответствующих нечет-.ных регистров сдвига, выход первогозапоминающего элемента соединен спервыми входами первых элементов Ивсех подгрупп третьей группы, второй вход первого элемента И 1-йподгруппы третьей группы (11,2и"1) соединен с вторым входом 1-гоэлемента И первой группы, выход )"го(1=4,6,8,) запоминающего элементасоединен с первыми входами соответст евующих элементов И всех 1-х (1 С 1)подгрупп третьей группы, вторые входы которых соединены с соответствующими выходами, начиная с третьего,(1)-го регистра сдвига и с первымивходами соответствующих элементов И-й подгруппы третьей. группы, вторые фффффвходы которых соединены с выходами 4,)соответствующих 1-х запоминающих фЧэлементов, кроме первого, первые вхо- еДды запоминающих элементов соединены с 1выходами соответствующих элементов р1 Ц 1 И второй группы, входы первого элемента ИЛИ которой соединены соответственно с выходами элементов И первой группы, входы остальных элементов ИЛИ второй группы соединены соответственно с выходами элементов И соответствующих подгрупп третьей группы ффвход. первого эЛемента задержки соединен с входом синхронизации первогорегистра сдвига и выходом второгоэлемента задержали, вход которого соединен с выходом элемента И и вторымивходами элементов И второй группы,1057952 входсинхронизации первого регистра сдвига соединен с первыми входами элементов И четвертой группы, второй вход М"го (1 с 2 п) элемента И которой соединен с предпоследним выхо. дом и входом установки первого разряда в единичное состояние (к)-го регистра сдвига, входы синхронизации которых, кроме первого, соединены с выходами соответствующего элемента И четвертой груплы, инверсные выходы последних разрядов регистров сдвига соединены соответственно с контактами с второго ро и-й переключателя, управляющий вход устройства соединен с первюми управляющими входами запоминающих элементов, вторые управляющие входы которых соединены с выходом первого элемента задержки, вторые входы запоминающих элементов. ,соединены с пнторым входом устройства, третьи управляющие входы запоминающих элементов соединены соответственно для первого эапомИнающего элемента с выЖодами элементов И первой группы, для остальных запоминающих элементов - с вторыми входами элементов И соответствующих подгрупп третьей группы.2. Устройство по и. 1, о т л и- . ч а ю щ е е с я тем, что запоминаюИзобретение относится к цифровой вычислительной технике и может быть применено в вычислительных устройствах, решающих комбинаторные задачи,Известно устройство для перебора сочетаний, содержащее (и) счетчиков с коэффициентами пересчета, изменяющи мися на.единицу, элементы передачи информации, элементы задержки, логические элементы и распределитель им" 10пульсов 11 1.Однако с помощью устройства невозможно реализовать перестановки кодов.Наиболее близким к предлагаемому по технической сущности является 15 устройство для перебора соединений, с держащее первый и второй элементы И, первую ивторую группы элементов ИЛИ ,элементы задержки, и запоминающих элементов, (где и " число перестав щий элемент содержит два триггера,три элемента И, элемент ШШ и дваэлемента ПЕ, причем первый вход запоминающего элемента соединен с сикх.ронным единичным входом первого триггера н входом первого элементаНЕ, выход которого соединен с синхронным нулевым 1 входом первого триггера, единичный вход которого соединен с выходом первого элемента И,первый вход которого соединен с вторымвходом запоминающего элемента, а второйвход - с первым управляющим входомзапоминающего элемента, второй управляющий вход которого соединен с синхровходом первого триггера и .входомвторого элемента НЕ, вьход которогосоединен с первыми входами второго итретьего элементов И, вторые входыкоторых соединены соответственно сединичным и нулевым выходами первоготриггера, третьи входы второго и третьего элементов И соединены с выходомэлемента ИЛИ, входы которого соединены с третьим управляющим входом запоминающего элемента, выходы второго и третьего элементов И соединенысоответственно с асинхронными единичным и нулевым входами второго триггера, единичный выход которого соединен с выходом запоминающего элемента. ляемых кодов), первую, вторую, третью,содержащую Ь) подгрупп, и четвертую группы элементов И, переключатель,(и) счетчиков, группу элементовИЛИ-НЕ, элемент ИЛИ-НЕ, причем выходызапоминающих элементов, кроме первого, подключены к первым входам соответствующих элементов И первой группы,первые входы элементов И второй группы соединены с выходами соответствующих запоминающих элементов, переключатель соединен с первым входом первого элемента И, второй вход которогоподключен к входу устройства, выходамиустройства являются выходы элементов .И второй группы, выход переноса 1-госчетчика 1 1,2п), кроме постледнего, соединен с входом (1+1)-госчетчика, вход первого счетчика подключен к выходу второго элементатретью, содержащую (и) подгрупп,и четвертую группу элементов И, переключатель, причем выходы запомина-ющих элементов, начиная с второго,подключены к первым входам соответствующих элементов И первой группы, пер.вые входы элементов И второй группысоединены с выходами соответствующих1запоминающих элементов, первый контактпереключателя соединен с первым входом первого элемента И, второй входкоторого подключен к первому входуустройства, выходами устройства являются выходы элементов И второй группы, содержит Ь) регистров сдвига,.второй элемент задержки, пирчем выхо.ды, кроме первого и последнего,: чет.ных регистров сдвига соединены соответственно с входами соответствующих элементов ИЛИ первой группы, выходы которых соединены с вторымивходами соответствующих четных элементов И первой группы, вторые входынечетных элементов И которой соедине-ны с вторыми выходами соответствующихнечетных регистров сдвига, выход первого з;поминающего элемента соединенс первыми входами первых элементовИ всех подгрупп третьей группы, второй вход первого элемента И 1-й подгруппы третьей группы (1=1,2п)соединен с вторым входом 1"го элементаИ первой группы, выход )-го (3=4,6,8) запоминающего элемента соединен с первыми входами соответствующих элементов И всех 1-х Ц ( ) подгрупп третьей группы, вторые входы-оторых соединены с соответствующимивыходами, начиная с третьего, (1-1)-горегистра .сдвига и с первыми входами соответствующих элементов И 1"йподгруппы третьей группы, вторыевходы которых соединены с выходамисоответствующих 1-х запоминаюцихэлементов, кроме первого, первые вхо.ды запоминающих элементов .соединеныс выходами соответствующих элементовИЛИ второй группы, входы первого элемента ИЛИ которой соединены соответственно с выходами элементов И первой группы, входы остальных элементовИЛИ второй группы соединены соответственно с выходами элементов И соот-ветствующих подгрупп третьей группы,вход первого элемента задержки соединен с входом синхронизации первогорегистра сдвига и выходом второго элемента задержки, вход которого соединен с выходом элемента И и вторыми 3 1057952 4И, информационные входы запоминающихэлементов подключены к выходам эле 1ментов И третьей группы, первыйвход первого элемента И которойподключен к -выходам элементов Ипервой группы, первые входы остальных элементов И третьей группы подключены к выходам (1"1)-го запоминающего элемента а первые входы-ых элементов ИЛИ первой группы 1 ОЦ =2 п), второй вход Ь)- го соединены с вторыми входами К-х(К=1п) элементов И первой группы и через 1-е элементы И четвертойгруппы - с выходами 1-х элементов 15ИЛИ второй группы, подключенными кпрямым выходам разрядов соответствующих счетчиков, вторые входы 1-хэлементов,ИЛИ первой группы подключены к выходам 0+1)-х элементов ИЛИ рОпервой группы и к вторым входам К-хэлементов И третьей группы, выходпервого элемента ИЛИ первой группы.подключен к вторым входам первого ивторого элементов И третьей группы, 25инверсные выходы первых разрядов ипрямые выходы остальных разрядов счетчиков подключены к входам элементовИЛИ-НЕ, выходы которых подключены кпервым входам элементов И пятойгруппы, выходы которых подключенычерез элемент задержки к инверснымвходам элементов И второй группы,выходы переноса счетчиков, кромепервого, соединены через элемент35ИЛИ-НЕ с первым входом второго элемента И и через переключатель - спервым входом первого элемента И,выходы переноса счетчиков, кромепоследнего, соединены с вторыми входами соответствующих элементов Ичетвертой и пятой групп, остальныевходы которых соединены с вторымвходом второго элемента И, с входомсинхронизации счетчиков и инверсным45выходом первого элемента И 2 3,Однако быстродействие устройстваневелико из-за наличия в алгоритмеФункционирования вспомогательныхсостояний.Цель изобретения - повышение50быстродействия устройства.Поставленная цель достигаетсятем, что устройство для перебора соединений, содержащее элемент И, первую и вторую группы элементов ИЛИ,55первый элемент задержки, и запомийающих элементов где и - число перевходами элементов И второй группы, вход синхронизации первого регистра сдвига соединен с первыми. входами элементов И четвертой группы, второй .вход К-го .(К=2 . и) элемента И которой соединен с предпоследним . выходом и .входом установки первого разряда в единичное состояние (К)-го регистра сдвига, входы синхронизации которых. кроме первого, соедиие ны с выходами соответствующего элемента И четвертой груцпы, инверсные выходы последних разрядов регистров сдвига соединены соответственно с контактами с второго по и"й пе. реключателя, управляющмй вход устройства соединен с первыми управляющими входами .запоминающих элементов, вто,рые управляющие входы которых соединены с выходом первого элемента задержки, вторые входы запоминающихэлементов соединены с вторым входом устройстватретьи управляющие входы запоминающих элементов соединены соотг ветственно для первого запоминающего элемента с выходами элементов И пер-вой группы, для остальных запоминающих элементов - с вторыми входами элементов И соответствующих подгрупп третьей группы.30Запоминающий элемент содержит дватриггера, три элемента И, элемент ИДИ и два элемента НЕ, причем первый . вход запоминаощегв элемента соединен с синхронным единичным входом первого триггера и входом первого элемен 35 та НЕ, выход котсрого соединен с синхронным нулевым .входом первого триггера, единичный вход которого соединен с выходом первого элемента И, первый вход которого соединен с вторым входом запоминаощего элемента, а второй вход - с первым управляющим входом запоминающего элемента, второй управляющий вход которого соединен с45 сннхравходом первого триггера,и вхо" дом второго элемента НЕ, выход которого соединен с первыми входами второго и третьего элементов И, вторые входы: которых соединены соответственно с единичным и нудевым выходами первого триггера, третьи входы второго и третьего элементовИ соединены с выходом элемента ИЛИ, входы которого соединены с третьим управляющим входом запоминающего элемента , выходы второго и третьего элементов", И соединены соответственно :с асинхронными единичным и нулевым входа- Ф ми второго триггера , единичнъй выход которого соединен с выходом запс 1 щнающего элемента.1На чертеже представлена схема устройства для перебора соединений.Устройство для перебора соединений содержит элемент И 1, первую 2 и вторую 3 группы элементов ИЛИ, первый 4 и второй 5 элементы задержки, и запоминающих элементов 6, имеющие информационные входы 7 и выходы 8, первую 9, вторую 10, третью 11, содержацую (и) подгрупп, и четвертую 12 группы элементов И,переключатель 3, первый вход 14 н выход 15 устройства, (й) регистров 16 сдвига с количеством разрядов, изменяющимся на один, начиная с трех до Ь+1), управляющий ввод 1.7 устройства. Запоминающий элемент 6 содержит триггеры 18 и 19, три элемента И 20- 22, элемент ИЛИ 23, два элемента НЕ 24 и 25,второй вход 26 и первый 27, второй 28 и третий 29 управляющие входы.Запоминающие элементы 6 представляют собой регистры двухступенчатого действия. Переставляемые коды заносятся в запомииаощие элементы 6 через вторые информационные входы 26 с помощью первых элементов И 20. Синхронизация приема кода осуществляется через управляющий вход 17 устройства. Разрядность переставляемых кодов и соответственно запоминающих элементов 6 зависит от количества переставляемых кодов и,определяется па формуле И 11 о 9 и 1. Синхронизация первой ступени запоминающего элемента 6 осуществляется сигналом, который поступает с выходом первого элемента 4 задержки, через второй управляющий вход 28 на синхровход первого триггера, Синхронизация второй ступени осуществляется не только общим дпя всех запоминающих элементов 6 сигналов с выхода первого элемента 4 задержки, но и от сигналов, которые поступает на вторые входы элементов И первой 9 и третьей 11 групп.Во время отсутствия сннхросигнала на выходе первого элемента задержки 4 и наличия единицы на 1-м выходе Ц 2) соответствующего регистра 16 сдвига единицы и, следовательно, на одном из третьих управляющих входов 29 и входов элемента ИЛИ 23,открывзотся вто" рой и третий 22 элементы И и происходит перепись содержимого первого1057952 8триггера 18 во второй триггер 19. Таким образом, во всех остальных элемен1 тах 6, не участвующих в обмене, вовремя наличия синхросигнала на выходе первого элемента 4 задержки происходит обнуление только первой ступе-,ни а вторая ступень ( после прекращения синхросигнала на выходе первогоэлемента задержки ) не обнуляетсятак как в это время отсутствуют сигна-Олы разрешения переписи от соответствующих регистров 16 сдвига.Регистры 16 сдвига однотактные,поспроенные по двухступенчатому принципу. Во время начальной установки в дпервых разрядах регистров 16 сдвигазаписываются единицы , а в остальныхразрядах - нули. При наличии импульса на входе синхронизации регистра16 сдвига единица переходит из 1"го. в 20(1+1)"й разряд, а 1-й разряд устанавливается в нулевое состояние.Вовсех регистрах 16 сдвига выход предпоследнего разряда связан с установочным входом первого разряда и во 25время подачи очередного импульсаединица из предпоследнего разряда переписывается в первый и последнийразряды, а предпоследний разряд устанавливается в нулевое состояние. 30Принцип работы устройства основывается на положении, гласящем, чтокаждую следующую перестановку можнополучить из предыдущей, поменяв местами какие-либо два символа (не обяза 35тельно стоящие рядом), оставляяпри этом все остальные символы на мес,.те.Устройство для перебора соединенийработает следующим образом.Перед началом работы регистры 16сдвига устанавливаются в начальныесостояния, а в запоминающие элементы6 записываются переставляемые коды.С помощью переключателя 13 задаетсяколичество переставляемых кодов,приэтом количество регистров 16 сдвигаподключенных через переключатель 13,Должно быть на единицу меньше числапереставляемых кодов. Каждая транспозиция реализуется путем обмена переставляемых кодов между двумя запоминающими элементами 6 с помощью логических элементов И первой 9 и третьей 11 групп. Выбор запоминающих. элементов, участвующих в обмене, осуществляется с помощью регистров,16 сдвига. Регистры 6 сдвига соединены между собой н с запоминающими элементами Ь так, чтобы осуществить циклический процесс обмена кодов между двумя запо. минающими элементами 6, Например,первый регистр 16 сдвига осуществляет обмен между вторым и первым запоминающими элементами 6, второй - между третьим и первым, а третий регистр 16 сдвига управляет обменами. четвертого запоминающего элемента 6 с другими н т,д.При выработке всех и 1 перестановок при и переставляемых кодов задаваемый переключателем 13 низкий потенциал, подаваемый с инверсного выхода последнего разряда (и)-го регистра 16 сдвига, производит остановку устройства, так как подача тактовых импульсов через элемент И 1 прекращается. Рассмотрим несколько тактов работыустройства, Пусть в запоминающие злементы записаны коды (1,2,3,4,5) в двоичном коде. При поступлении первого .тактового импульса производится выдача содержимого запоминающих элементов6, т.е. кодов (1,2,3,4,5), Черезвремя задержки на элементе 5 задержки производится сдвиг единицы в первом регистре 16 сдвига, а через времязадержки на элементах 4 и 5 задержкиоткроются первые элементы И первойгруппы 9 и первой подгруппы третьейгруппы 11 и обменяются первый и второй запоминающие элементы 6. Во втором такте также выдаются коды (1,2,3,4,5) и через время задержки на элементе 5 задержки опять производитсясдвиг в первом регистре 6 сдвига,Единица с предпоследнего разрядапервого регистра 16 сдвига черезпервый элемент И четвертой группы 12подается на вход синхронизации второго регистра 16 сдвига и происходитсдвиг. Через время задержки на элементах 4 и 5 задержки откроется второй элемент И первой группы и первыйэлемент И второй подгруппы третьей группы 11 и обменяются первый и третий запоминающие элементы 6, В следующем такте выдаются коды (3,1,2,4,5), опять происходит сдвиг в первом регистре 16 сдвига и т.д., циклы повторяются.Предлагаемый принцип работы устройства достаточен для получения всех и. перестановок кодов.9 1057952 1 ОУстройство для перевода соединений нению с прототипом, вследствие позволяет получить технический эфФект, исключения из алгоритма функцизаключающийся в значительном уве онирования вспомогательньж состоличении быстродействия по срав- яний.у Составитель А. Клюев едактор С. Юско Техред Т.Фанта Корректор Г. Решетниказ 9465/52 Тираж 706 ВНИИПИ Государственного комитет по делам изобретений и откр 113035, Москва, Ж, Раушская