Устройство для перебора соединений
I. УСТРОЙСТВО Д11Я ПЕРЕБОРА СОЕДИНЕНШ, содержащее элемент И, первую и вторую группы элементов ИЛИ, первый элемент задержки , п запоминаю1цих элементов (где п - число, переставляемых кодов), первую, вторую третью и четвертую группы элементов И, переключатель, причем выходы запоминающих элементов, начиная с второго , додключены к первым входам соответствующих элементов И первой группы , первые входы элементов И второй группы соединены с выходами соответствующих запоминаюпщх элементов первый контакт перекшочателя соединен с первым входом первого элемента И, второй вход которого подключен к первому входу устройства, выходами устройства являются выходы элементов И второй группы, птличающеес я Тем, что, с целью повышения быстродействия , оно содерхсит (п-1) регистров сдвига, второй элемент за .держки, причем выходы, кроме первого и последнего, четных регистров сдвига соединены с входами соответствующг1.ч элементов ИЛИ первой группы, выходы которых соединены с вторыми входами соответствующих четных элементов И первой группы, вторые входы нечетных элементов И которой соедннею с вторыми выходами соответствующих нечетных регистров сдвига, выход первого запоминающего элемента соединен с первыми входами первых элементов И всех подгрупп третьей группы, второй вход первого элемента И 1-й подгруппы третьей группы (,2,..., п-1) соединен с вторым входом i-ro элемента И первой группы, выход j-ro (j 4,6,8,...) запоминающего элемента соединен с первыми входами соответртвующих элементов И всех 1-х (Kj) (Л подгрупп третьей группы, вторые входы которых соединены с соответствующими выходами, начиная с третьего, ()-го регистра сдвига и с первыми входами соответствующих элементов И j-й подгруппы третьей, группы, вторые входы которых соединены с выходами СП со ел ьо соответствующих 1-х запоминающих элементов, кроме первого, первые входы запоминающих элементов соединены с выходами соответствующих элементов ИЛИ второй группы, входы первого элемента ИЛИ которой соединены соответственно , с выходами элементов И первой группы, входы осталышх элементов HIM второй группы соединены соот ветственно с выходами элементов И соответствующих подгрупп третьей группы вход первого элемента задержки соединен с входом синхронизации первого регистра сдвига и выходом второго элемента задержки, вход которого соединен с выходом злементА И и вторыми входами элементов И второй группы.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК .
3 @ С 06 F 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГПФ (21) 3492654/ 18-24 (22) 20.09.82 46) 30.11.83. Бюл. В 44 (72) Г. С. Цирамуа, Л. Ш. Имнаишвнли, С. Г. Цирамуа и И.. П. Чхитунидзе (71). Грузинский ордена Ленина и ордена Трудового Красного Знамени поли« технический институт им. В. И. Ленина (53) б81.33 (088.8) (56) 1.Авторское свидетельство СССР
Р 374б06, кл. G 06 F 15/32, 1970;
2. Авторское свидетельство СССР
Р 911535, кл. G 06 F 15/26, 1978 (прототип).
Ь4) (57) 1. УСТРОЙСТВО ДЛЯ IIEPESOPA
СОЕДИНЕНИЙ, содержащее элемент И, первую и вторую группы элементов
ИЛИ, первый элемент задержки, и запоминающих элементов (где n " .число переставляемых кодов), первую, вторую третью и четвертую группы элементов
И, переключатель, причем выходы запоминающих элементов, начиная с второго, подключены к первым входам соответствующих элементов И первой группы, первые входы элементов И второй группы соединены с выходами соответствующих запоминающих элементов," первый контакт переклв>чателя соединен с первым входом первого элемента И, второй вход которого подключен к первому входу устройства, выходами устройства являются выходы элементов
И второй группы, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия,оно содержит (n-1) регистров сдвига, второй элемент за:держки, причем выходы, кроме первого и последнего, четных регистров сдвига соединены с входами соответствующих
„„SU„„1057952 А элементов ИЛИ первой группы, выходы которых соединены с вторыми входами соответствующих четных элементов И первой группы, вторые входы нечетных элементов И которой соединены с вторыми выходами соответствующих нечет-. ных регистров сдвига, выход первого запоминающего элемента соединен с первыми входами первых элементов И всех подгрупп третьей группы, второй вход первого элемента И l-й подгруппы третьей группы (1 1,2,..., и-1) соединен с вторым входом l-го элемента И первой группы, выход J""го (j 4,6,8,...) запоминающего элемента соединен с первыми входами соответст вующих элементов И всех l-х (i j-й подгруппы третьей. группы, вторые входы которых соединены с выходами соответствующих 1-х запоминающих элементов, кроме первого, первые входы запоминающих элементов соединены с выходами соответствующих элементов HJIH второй группы, входы первого элемента ИЛИ которой соединены соответственно ° с выходами элементов И первой группы, входы осталь 1ых элементов IUIH второй группы соединены соответственно с выходами элементов И соответствующих подгрупп третьей группы вход. первого эЛемента задержки соединен с входом синхронизации первого регистра сдвига и выходом второго элемента задержали, вход которого соединен с выходом элемента И и вторыми входами элементов И второй группы, 1057952 вход. синхронизации первого регистра сдвига соединен с первыми входами элементов И четвертой группы, второй вход k-го (k 2 и-1) элемента И которой соединен с предпоследним выходом и входом установки первого разряда в единичное состояние (к-1)-го регистра сдвига, входы синхронизации которых, кроме первого, соединены с выходами соответствующего элемента И четвертой груплы, инверсные выходы последних разрядов регистров сдвига соединены соответственно с контактами с второго go n-й переключателя, управляющий вход устройства соединен с первшми управляющими входами запоминающих элементов, вторые управляющие входы которых соединены с выходом первого элемента задержки, вторые входы запоминающих элементов. ,соединены с вторым входом устройства, третьи управляющие входы запоминающих элементов соединены соответственно для первого эапомИнающего элемента с выЖодами элементов И первой группы, для остальных запоминающих элементов — с вторыми входами элементов И соответствующих подгрупп третьей группы. 2. Устройство по п. I о т л и- . ч а ю щ е е с я тем, что запоминаюИзобретение относится к цифровой вычислительной технике и может быть применено в вычислительных устройствах, решающих комбинат орные задачи. Известно устройство для перебора сочетаний, содержащее (n-1) счетчиков с коэффициентами пересчета, изменяющи мися на.единицу, элементы передачи информации, элементы задержки, логические элементы и распределитель им" пульсов (1 ). Однако с помощью устройства невозможно реализовать перестановки кодов. Наиболее близким к предлагаемому по технической сущности является 15 устройство для перебора соединений,. с здержащее первый и второй элементы И, первую и вторую группы элементов ИЛИ,элементы задержки, и запоминающих элементов, (где n " число перестав- 20 1 щий элемент содержит два триггера, три элемента И, элемент ШШ и два элемента ПЕ, причем первый вход запоминающего элемента соединен с синхронным единичным входом первого триггера н входом первого элемента НЕ, выход которого соединен с синхронным нулевым.1входом первого триггера, единичный вход которого соединен с выходом первого элемента И,первый вход которого соединен с вторым входом запоминающего элемента, а второй вход - с первым управляющим входом запоминающего элемента, второй управляющий вход которого соединен с синхровходом первого триггера и .входом второго элемента НЕ, выход которого соединен с первыми входами второго и третьего элементов И, вторые входы которых соединены соответственно с единичным и нулевым выходами первого триггера, третьи входы второго и треть его элементов И соединены с выходом элемента ИЛИ, входы которого соединены с третьим управляющим входом запоминающего элемента, выходы второго и третьего элементов И соединены соответственно с асинхронными единичным и нулевым входами второго триггера, единичный выход которого соединен с выходом запоминающего элемента. ляемых кодов), первую, вторую, третью, содержащую (р-1) подгрупп, и четвертую группы элементов И, переключатель, (n-1) счетчиков, группу элементов ИЯ-НЕ, элемент ИЛИ-НЕ, причем выходы запоминающих элементов, кроме первого, подключены к первым входам соответствующих элементов И первой группы, первые входы элементов И второй группы соединены с выходами соответствующих запоминающих элементов, переключатель соединен с первым входом первого элемента И, второй вход которого подключен к входу устройства, выходами устройства являются выходы элементов . И второй группы, выход переноса i-го счетчика P=1,2,...,ï-1), кроме пос-. леднего, соединен с входом (i+1)-го счетчика, вход первого счетчика подключен к выходу второго элемента третью, содержащую (и-1) подгрупп, и четвертую группу элементов И, переключатель, причем выходы запомина- ющих элементов, начиная с второго, подключены к первым входам соответствующих элементов il первой группы, первые входы элементов И второй группы соединены с выходами соответствующих 1 запоминающих элементов, первый контакт переключателя соединен с первым входом первого элемента И, второй вход которого подключен к первому входу устройства, выходами устройства являются выходы элементов И второй группы, содержит (n-1) регистров сдвига, второй элемент задержки, пирчем выхо. ды, кроме первого и последнего,: четных регистров сдвига соединены соответственно с входами соответствующих элементов ИЛИ первой группы, выходы которых соединены с вторыми входами соответствующих четных элементов И первой группы, вторые входы нечетных элементов И которой соединены с вторыми выходами соответствующих нечетных регистров сдвига, выход первого з;поминающего элемента соединен с первыми входами первых элементов И всех подгрупп третьей группы, второй вход первого элемента И i-й подгруппы третьей группы (i=1,2,...,n-1) соединен с вторым входам 1-го элемента И первой группы, выход j-го ()=4,6, 8,...) запоминающего элемента соединен с первыми входами соответствующих элементов И всех i-х (i (j) подгрупп третьей группы, вторые входы -..оторых соединены с соответствующими выходами, начиная с третьего, (j-1)-го регистра .сдвига и с первыми входами соответствующих элементов И 1-й подгруппы третьей группы, вторые входы которых соединены с выходами соответствующих i õ запоминаюцих элементов, кроме первого, первые входы запоминающих элементов .соединены с выходами соответствующих элементов ИЛИ второй группы, входы первого элемента ИЛИ которой соединены соответственно с выходами элементов И первой группы, входы остальных элементов ИЛИ второй группы соединены соответственно с выходами элементов И соот- ветствующих подгрупп третьей группы, вход первого элемента задержки соединен с входом синхронизации первого регистра сдвига и выходом второго эле. мента задержки, вход которого соединен с выходом элемента И и вторыми 3 1057952 4 И, информационные входы запоминающих эле11ентов подключены к выходам элеI ментов И третьей группы, первый вход первого элемента И которой подключен к -выходам элементов И первой группы, первые входы остальных элементов И третьей группы подключены к выходам (i"1)-ro запоминающего элемента а первые входы j-ых элементов ИЛИ первой группы 1О (j=2,..., n-1), второй вход (и-1)го соединены с вторыми входами К-х (К=1,...,n) элементов И первой группы и через i å элементы И четвертой группы — с выходами 1-х элементов ИЛИ второй группы, подключенными к прямым выходам разрядов соответствующих счетчиков, вторые входы i-x элементов,ИЛИ первой группы подключены к выходам (1+1)-х элементов ИЛИ ро первой группы и к вторым входам К-х 1 элементов И третьс .й группы, выход первоГо элемента ИЛИ первой группы .подключен к вторым входам первого и второго элементов И третьей группы, инверсные выходы первых разрядов и прямые выходы остальных разрядов счетчиков подключены к входам элементов ИЛИ-НЕ, выходы которых подключены к первым входам элементов И пятой группы, выходы которых подключены через элемент задержки к инверсным входам элементов И второй группы, выходы переноса счетчиков, кроме первого, соединены через элемент ИЛИ-НЕ с первым входом второго элемента И и через переключатель — с первым входом первого элемента И, выходы переноса счетчиков, кроме последнего, соединены с вторыми входами соответствующих элементов И четвертой и пятой групп, остальные входы которых соединены с вторым входом второго элемента И, с входом синхронизации счетчиков и инверсным 45 выходом первого элемента И(2 3. Однако быстродействие устройства невелико из-за наличия в алгоритме функционирования вспомогательных состояний. Цель изобретения — повышение 50 быстродействия устройства. Поставленная цель достигается тем, что устройство для перебора соединений, содержащее элемент И, первую и вторую группы элементов ИЛИ, 55 первый элемент задержки, и запомийающих элементов (где и — число пере, ставляемых кодов), первую, вторую, 1057952 входами элементов И второй группы, вход синхронизации первого регистра сдвига соединен с первыми. входами элементов И четвертой группы, второй вход К-го .(К2.. . и-1) элемента И которой соединен с предпоследним . выходом и .входом установки первого разряда в единичное состояние (K-1) -ro регистра сдвига, входы синхронизации которых. кроме первого, соедиие- 10 ны с выходами соответствующего элемента И четвертой груцпы, инверсные выходы последних разрядов регистров сдвига соединены соответственно с контактами с второго по й"й пе. реключателя, управляющмй вход устройства соединен с первыми управляющими входами .запоминающих элементов, вто.рые управляющие входы которых соеЬ динены с выходом первого элемента задержки, вторые входы запоминающих элементов соединены с вторым входом устройства,,третьи управляющие входы запоминающих элементов соединены соотг ветственно для первого запоминающего элемента с выходами элементов И пер- вой группы, для остальных запоминающих элементов — с вторыми входами элементов И соответствующих подгрупп третьей группы. Запоминающий элемент содержит дватриггера, три элемента И, элемент ИДИ и два элемента НЕ, причем первый . вход запоминающего элемента соединен с синхронным единичным входом первого триггера и входом первого элемен35 та НЕ, выход котсрого соединен с синхронным нулевым .входом первого триггера, единичный вход которого соединен с выходом первого элемента И, первый вход которого соединен с вторым входом запоминающего элемента, а второй вход - с первым управляющим входом запоминающего элемента, второй управляющий вход которого соединен с 45 сннхравходом первого триггера,и входом второго элемента НЕ, выход которого соединен с первыми входами второго и третьего элементов И, вторые входы: которых соединены соответственно с единичным и нудевым выходами первого триггера, третьи входы второго и третьего элементов И соединены с выходом элемента ИЛИ, входы которого соединены с третьим управляющим входом запоминающего элемента, выходы второго и третьего элементов", И соединены соответственно :с асинхронными единичным и нулевым входаФ ми второго триггера, единичнъ и выход которого соединен с выходом запс минающего элемента.1 На чертеже представлена схема устройства для перебора соединений. Устройство для перебора соединений содержит элемент И 1, первую 2 и вторую 3 группы элементов ИЛИ, первый 4 и второй 5 элементы задержки, и запоминающих элементов 6, именнцие информационные входы 7 и выходы 8, первую 9, вторую 10, третью 11, содержащую (n-1) подгрупп, и четвертую 12 группы элементов И,переключатель 13. первый вход 14 н выход 15 устройства, (й-1) регистров 16 сдвига с количеством разрядов, изменяющимся на один, начиная с трех до @+1), управляющий вход 1.7 устройства. Запоминающий элемент 6 содержит„ триггеры 18 и 19, три элемента И 2022, элемент ИЛИ 23, два элемента НЕ 24 и 25,второй вход 26 и первый 27, второй 28 и третий 29 управляющие входы. Запоминающие элементы 6 представляют собой регистры двухступенчатого действия. Переставляемые коды заносятся в запомиианнцие элементы 6 через вторые информационные входы 26 с помощью первых элементов И 20. Синхронизация приема кода осуществляется через управляющий вход 17 устройства. Разрядность переставляемых кодов и соответственно запоминающих элементов 6 зависит от количества переставляемых кодов и,определяется пс1формуле И )1од2п I. Синхронизация первой ступени запоминающего элемента 6 осуществляется сигналом, который поступает с выходом первого элемента 4 задержки, через второй управляющий вход 28 на синхровход первого триггера. Синхронизация второй ступени осуществляется не только общим дпя всех запоминающих элементов 6 сигналов с выхода первого элемента 4 задержки, но и от сигналов, которые поступает на вторые входы элементов И первой 9 и третьей 11 групп. Во время отсутствия сннхросигнала на выходе первого элемента задержки 4 и наличия единицы на j-м выходе (j>i2) соответствующего регистра 16 сдвига единицы и, следовательно, на одном из третьих управляющих входов 29 и входов элемента ИЛИ 23,открываются вто-рой .и третий 22 элементы И и происходит перепись содержимого первого 7 1057952 8 триггера 18 во второй триггер 19. Таким образом, во всех остальных элемен. так 6, не участвующих в обмене, во время наличия синхросигнала на выходе первого элемента 4 задержки происходит обнуление только первой ступе-, ни а вторая ступень (после прекращения синхросигнала на выходе первого элемента задержки ) не обнуляется так как в это время отсутствуют сигна- lp лы разрешения переписи от соответствующих регистров 16 сдвига. Регистры 16 сдвига однотактные,посп роенные по двухступенчатому принципу. Во время начальной установки в 15 первых разрядах регистров 16 сдвига записываются единицы, а в остальных разрядах — нули. При наличии импульса на входе синхронизации регистра 16 сдвига единица переходит из i-го. в 2О (i+1)-й разряд, à i-й разряд устанавливается в нулевое состояние.Во всех регистрах 16 сдвига выход предпоследнего разряда связан с установочным входом первого разряда и во 25 время подачи очередного импульса единица из предпоследнего разряда переписывается в первый и последний разряды, а предпоследний разряд устанавливается в нулевое состояние. 30 Принцип работы устройства основывается на:положении, гласящем, что каждую следующую перестановку можно получить из предыдущей, поменяв местами какие-либо два символа (не обяза35 тельно стоящие рядом), оставляя при этом все остальные символы на мес. ..те. Устройство для перебора соединений работает следующим образом. Перед началом работы регистры 16 сдвига устанавливаются в начальные состояния, а в запоминающие элементы 6 записываются переставляемые коды. С помощью переключателя 13 задается количество переставляемых кодов,при этом количество регистров 16 сдвига подключенных через переключатель 13, Должно быть на единицу меньше числа переставляемых кодов. Каждая транспозиция реализуется путем обмена переставляемых кодов между двумя запоминающими элементами 6 с помощью логических элементов И первой 9 и третьей 11 групп. Выбор запоминающих. элементов, участвующих в обмене, осуществляется с помощью регистров,16 сдвига. Регистры 16 сдвига соединены между собой и с запоминающими элементами Ь так, чтобы осуществить циклический процесс обмена кодов между двумя sanoминающими элементами 6. Например,первый регистр 16 сдвига осуществляет обмен между вторым и первым запоминающими элементами 6, второй — между третьим и первым, а третий регистр 16 сдвига управляет обменами. четвертого запоминающего элемента 6 с другими н т.д. При выработке всех nl перестановок при и переставляемых кодов задаваемый переключателем 13 низкий потенциал, подаваемый с инверсного выхода последнего разряда (и-1)-го регистра 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 задержки опять производится сдвиг в первом регистре 16 сдвига. Единица с предпоследнего разряда первого регистра 16 сдвига через первый элемент И четвертой группы 12 подается на вход синхронизации второго регистра 16 сдвига и происходит сдвиг. Через время задержки на элементах 4 и 5 задержки откроется второй элемент И первой группы и первый элемент И второй подгруппы третьей группы ll и обменяются первый и третий запоминающие элементы 6. В следующем такте выдаются коды (3,1,2,4,5), опять происходит сдвиг в первом регистре 16 сдвига и т.д., циклы повторяются. Предлагаемый принцип работы устройства достаточен для получения всех п1 перестановок кодов. 9 1057952 I0 Устройство для перевода соединений нению с прототипом, вследствие iпозволяет получить технический эффект, исключения из алгоритма функцизаключающийся в значительном уве-- онирования вспомогательньж состоличении быстродействия по срав- яний. Составитель А. Клюев Техред.Т.Фанта Корректор Г. Решетник Редактор С. Юско Заказ 9465/52 - Тираж 706 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий I13Î35, Москва, Ж-35, Раушская наб.„ д. 4/5 Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4
