Устройство для перебора соединений Советский патент 1983 года по МПК G06F7/08 

вход.-.синхронизации первого регистра сдвига соединен с первыми входами элементов Н четвертой группы, второй вход k-ro (,,.., n-1) элемента Н которой соединен с предпоследним выхдом и входом установки первого разряда в единичное состояние (k-l)-ro регистра сдвига, входы си1гхронизации которых, кроме первого, соединены с выходами соответствующего элемента И четвертой груплы, инверсные выходы последних разрядов регистров сдвига соединены соответственно . с контактами с второго ро п-й переключателя, управляющий вход устройства соединен с перншми управляющиъсн входами запоминающих элементов, втор управляющие входы которых соединены с выходом первого элемента задержки, вторые входы запоминающих элементов ,соедин п 1 с «вторым, входом устройства, третьи управляющие входы запоминающих элементов соединены соответственно для первого запоминающего элмента с выходами элемен ов И первой группы, для остальных запоминающих элементов - с вторыми входами элементов И соответствующих подгрупп третьей группы.

2. Устройство по п. 1,,о т л и- . чающееся тем, что запоминающий элемент содержит два триггера, три элемента И, элемент ШШ и два элемента НЕ, причем первый вход запоминающего элемента соединен с синхронным единичным входом первого триггера и входом первого элемента НЕ, выход которого соединен с синхронным нулевымВХОДОМ первого триггера, единичный вход которого соединен с выходом первого элемента И,первый вход которого соединен с вторым входом запоминающего элемента, а втор вход - с первым управляющим входом запоминающего элемента, второй управляющий вход которого соединен с синхровходом первого триггера и- .входом второго элемента НЕ, в|.1ход которого соединен с первыми входами второго и третьего элементов И, вторые входы которых соединены соответственно с единичным и нулевым выходами первого триггера, третьи входы второго и трет его элементов И соединены с выходом элемента ИЛИ, входы которого соединены с третьим управляющим входом запоминающего элемента, выходы второго и третьего элементов И соединены соответственно с асинхронными единичным и нулевым входами второго триггера, единичный выход которого соединен с выходом запоьданающего элемента.

I. УСТРОЙСТВО Д11Я ПЕРЕБОРА СОЕДИНЕНШ, содержащее элемент И, первую и вторую группы элементов ИЛИ, первый элемент задержки , п запоминаю1цих элементов (где п - число, переставляемых кодов), первую, вторую третью и четвертую группы элементов И, переключатель, причем выходы запоминающих элементов, начиная с второго, додключены к первым входам соответствующих элементов И первой группы, первые входы элементов И второй группы соединены с выходами соответствующих запоминаюпщх элементов первый контакт перекшочателя соединен с первым входом первого элемента И, второй вход которого подключен к первому входу устройства, выходами устройства являются выходы элементов И второй группы, птличающеес я Тем, что, с целью повышения быстродействия, оно содерхсит (п-1) регистров сдвига, второй элемент за.держки, причем выходы, кроме первого и последнего, четных регистров сдвига соединены с входами соответствующг1.ч элементов ИЛИ первой группы, выходы которых соединены с вторыми входами соответствующих четных элементов И первой группы, вторые входы нечетных элементов И которой соедннею с вторыми выходами соответствующих нечетных регистров сдвига, выход первого запоминающего элемента соединен с первыми входами первых элементов И всех подгрупп третьей группы, второй вход первого элемента И 1-й подгруппы третьей группы (,2,..., п-1) соединен с вторым входом i-ro элемента И первой группы, выход j-ro (j 4,6,8,...) запоминающего элемента соединен с первыми входами соответртвующих элементов И всех 1-х (Kj) (Л подгрупп третьей группы, вторые входы которых соединены с соответствующими выходами, начиная с третьего, ()-го регистра сдвига и с первыми входами соответствующих элементов И j-й подгруппы третьей, группы, вторые входы которых соединены с выходами СП со ел ьо соответствующих 1-х запоминающих элементов, кроме первого, первые входы запоминающих элементов соединены с выходами соответствующих элементов ИЛИ второй группы, входы первого элемента ИЛИ которой соединены соответственно, с выходами элементов И первой группы, входы осталышх элемен- тов HIM второй группы соединены соот ветственно с выходами элементов И соответствующих подгрупп третьей группы вход первого элемента задержки соединен с входом синхронизации первого регистра сдвига и выходом второго элемента задержки, вход которого соединен с выходом злементА И и вторыми входами элементов И второй группы.

Изобретение относится к цифровой вычислительной технике и может быть применено в вычислительных устройствах, решающих комбинаторные задачи.

Известно устройство для перебора сочетаний, содержащее (п-1) счетчиков с коэффициентами пересчета, изменяющи мися на.единицу, элементы передачи информации, элементы задержки, логические элементы и распределитель импульсов 11 .

Однако с помощью устройства невозможно реализовать перестановки кодов,

Наиболее близким к предлагаемому по вехнической сущности является устройство для перебора соединений, содержащее первый и второй элементы Й, первую и вторую группы элементов ,элементы задержки, п ; ппоминающи элементов, (где п - число переставляемых кодов, первую, вторую,третью, содержащую ) подгрупп, и четвертую группы элементов И, переключатель (п-1) счетчиков, группу элементов ШШ-НЕ, элемент ИЛИ-НЕ, причем выходы запоминаюш 1х элементов, кроме первого, подключены к первым входам соотвествующих элементов И первой группы, первые входы элементов И второй группы соединены с выходами -соответствующих запоминазощих элементов, переключатель соединен с первым входом первого элемента И, второй вход которого подключен к входу устройства, выходам устройства являются выходы элементов И второй группы, выход переноса i-ro счетчика (1 1,2,... ,п-1), кроме последиего, соединен с входом (i+1)-ro счетчика, вход первого счетчика подключен к выходу второго элемента И, информационные входы запоминающи элементов подключены к выходам элементов И третьей группы, первый вход первого элемента И которой подключен к -выходам элементов И первой группы, первые входы остальных элементов И третьей группы подключены к выходам (i-l)-ro запоминающего элемента а первые входы j-ых элементов Ш1И первой группы (,..., п-1), второй вход () го соединены с вторыми входами К-х (,...,п) элементов И первой гру пы и через i-е элементы И четвертой группы - с выходами i-х элементов ИЛИ второй группы, подключенными к прямым выходам разрядов соответствующих счетчиков, вторые входы i-х элементов .ИЛИ первой группы подключены к выходам + 1)-x элементов ИЛ первой группы и к вторым входам К-х элементов И третьей группы, выход первого элемента ИЛИ первой группы .подключен к вторым входам первого и второго элементов И третьей группы инверсные выходы первых разрядов и прямые выходы остальных разрядов сч чиков подключены к входам элементов ИГШ-НЕ, выходы которых подключены к первым входам элементов И пятой группы, выходы которых подключены через элемент задержки к инверсным входам элементов И второй группы, выходы переноса счетчиков, кроме первого, соединены через элемент ИЛИ-НЕ с первым вх.одом второго элемента И и через переключатель - с первым входом первого элемента И, выходы переноса счетчиков, кроме последнего, соединены с вторыми вхо дами соответствующих элементов И четвертой и пятой групп, остальные которых соединеш с вторым входом второго элемента И, с входом синхронизации счетчиков и инверсным выходом первого элемента . . Однако быстродействие устройства невелико из-за наличия в алгоритме функционирования вспомогательных состояний. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство для перебора с динений, содержащее элемент И, пер вую и вторую группы элементов ИЛИ, первый элемент задержки, п запоминшощих элементов (где п - число пер |Ставляемых кодов), первую, вторую. третью, содержащую (п-1) подгрупп, и четвертую группу элементов И, переключатель, причем выходы запоминающих элементов, начиная с второго, подключены к первым входам соответствующих элементов И первой группы, первые входы элементов И второй группы соединены с выходами соответствующих запоминающих элементов, первый контакт переключателя соединен с первым входом первого элемента И, второй вход которого подключен к первому входу устройства, выходами ycтpoЙJCTвa явля ются выходы элементов И второй группы, содержит (п-1) регистров сдвига, .второй элемент задержки, пирчем выходы, кроме первого и последнего , четных регистров сдвига соединены соответственно с входами соответствующих элементов ИЛИ первой группы, выходы которых соединены с вторыми входами соответствующих четных элементов И первой группы, вторые входы нечетных элементов И которой соединены с вторыми выходами соответствукмцих нечетных регистров сдвига, выход первого зсчюминающего элемента соединен с первьми входами первых элементов И всех подгрупп третьей группы, второй вход первого элемента И i-и подгруппы третьей группы (,2,...,п-1) соединен с вторым входам i-ro элемента И первой группы, выход j-ro (,6, 8,...) запоминающего элемента соединен с первыми входами соответствующих элементов И всех 1-х U j) подгрупп третьей группы, вторые входы которых соединены с соответствукмцимн выходами,начиная с третьего, (j-l)-ro регистра сдвига и С первыми входами соответствующих элементов И j-й подгруппы третьей группы, вторые входы которых соединены с выходами соответствующих 1-х запоминаницих элементов, кроме первого, первые входы запоминающих элементов .соединены с выходами соответствующих элементов И1Ш второй группы, входы первого элемента ИЛИ которой соединены соответственно с выходами элементов И первой группы,входы остальных элементов ИЛИ второй группы соединены соответственно с выходами элементов И соответствующих подгрупп третьей группы, вход первого элемента задержки соединен с входом синхронизации первого регистра сдвига и выходом второго элемента задержки, вход которого соединен с выходом элемента И и вторыми входами элементов И второй группы, вход синхронизации первого регистра сдвига соединен с первыми, входами элементов И четвертой группы, второй вход К-го -(,.., п-1) элемента И которой соединен с предпоследним i выходом и входом установки первого разряда в единичное состояние (К-1)-г регистра сдвига, входы синхрониза;дии которых, кроме первого, соединены с в№содами соответствующего элемента И четвертой груцпы, инверсные выходы последних разрядов регис ров сдвига соединены соответственно с контактами с второго по п-й пе. реключателя, управлякицмй вход устрой ства соединен с первыми ynpa.BnHtas tei входами .запоминакнцих элементов, вто.рые управляняцне зу.ор}л которых соединены с выходом первого элемента задержки, вторые входы запоминаювщх элементов соединены с вторым входом устройства,.третьи управляющие входы запоминающих элементов соедине : соо ветственно для первого з,aпo шнaющero элемента с выходами элементов И пер вой группы, для осталышх запоминающих элементов - с вторьош входами элементов И соответствующих подгрупп третьей группы. Запогшнающий элемент содержит два триггера, три элемента И, элемент ШШ и два элемента НЕ, причем, первый вход запоминахщего элемента соединен с синхронным единичнш4 входом первого триггера и входом первого элеме та НЕ, -выход которого соединен с син ронным нулевым входом первого триггера, единичный вход которого соединен с выходом первого элемента И, первый вход которого соеданен с вторым входом згшоминающего элемента, а второй вход - с первым управляющим входом запомина1одего элемента, второ управляющий вход которого соединен с синхровходом первого триггера ,и входом второго элемента НЕ, выход котор го соединен с первыми входами второго и третьего элементов И, втсфые входы; которых соединены соответствен . но с единичным и нулевым выходами napBolO триггера, третьи входы второ го и третьего элементов И соединены с выходом элемента ШШ, -входа которого соединены с третьим управляющим входом запоминакщего элемента , выходы второго и третьего элементов: И соединены соответственно :с асинхронными единичным и нулевым входами второго триггера , единичный выход которого соединен с выходом запс в}нающего элемента.| На черт(1же представлена схема устройства для перебора соединений. Устройство для перебора соедине1шй содержит элемент И 1, первую 2 и вторую 3 группы элементов ШМ, первый 4 и второй 5 элементы задержки, п запоминаюпа1х элементов 6, имекицие информационные входы 7 и выходы 8, первую 9, вторую 10, третью 11, содерж.ащую fri-l) подгрупп, и четвертую 12 группы элементов И,переключатель 13, первый вход 14 и выход 15 устройства, (rt-1) регистров 16 сдвига с количеством разрядов, изме кццимся на один, начиная с трех до ), управляющий в1сод 1.7 устройства. Запом11нающий элемент 6 содержит,, триггеры 18 и 19, три элемента И 2022, элемент ИЛИ 23, два элемента НЕ 24 и 25, второй вход 26 и первый 27, второй 28 и третий 29 управляющие входы. Заноьшнающие элементы 6 представляют собой регистры двухступенчатого действия. 11ереставляе а.1е коды заносятся в запоминающие элементы 6 через вторые информационные входы 26 с помощью первых элементов И 20. Синхронизация приема кода осуществляется через управляюи01й вход 17 устройства. Разрядность переставляемых кодов и соответственно запоминающих элементов 6 зависит от количества переставляемых кодов и определяется nq pмуле Н }l од-nf. Синхронизация первой ступен запоминающего элемента 6 осуществляется сигналом, который поступает с выходом первого элемента 4 задер:кки, через второй управляющий вход 28 на синхровход первого триггера.Синхронизация второй ступени осуществляется не только общим для всех з.апоминающих элементов 6 сигналов с выхода первого элемента 4 задержки, но и от сигналов, которые поступает на вторые входы элементов И первой 9 и третьей 11 групп. Во время отсутствия синхросигнала на выходе первого элемента задержки 4 И наличия единицы на J-M выходе () соответств:1пощего регистра 16 сдвига единицы и, следовательно, на одном из третьих управляющих входов 29 и входов элемента ШШ 23, открыв лютея второй-и третий 22 элементы И и проис- t ходит перепись содержимого первого 71 триггера 18 во второй триггер 19. Та ким образом, во всех остальных элеме тах 6, не участвующих в обмене, во время наличия синхросигнала на выходе первого элемента 4 задержки проис ходит обнуление только первой ступени, а вторая ступень (после прекраще ния синхросигнала на выходе первого элемента задержки ) не обнуляется так как в это время отсутствуют сигн лы разрешения переписи от соответствующих регистров 16 сдвига. Регистры 16 сдвига однотактные,по роенные по двухступенчатому принципу. Во время начальной установки в первых разрядах регистров 16 сдвига записываются единицы , а в остальных разрядах - нули. При наличии импульса на входе синхронизации регистра 16 сдвига единица пере содит из 1-го (1 + 1)-й разряд, а i-й разряд устанавливается в нулевое состояние.Во всех регистрах 16 сдвига выход предпоследнего разряда связан с установочным входом первого разряда И во время подачи очередного импульса единица из предпоедеднего разряда пе реписывается в первый и последний разряды, а предпоследний разряд уста навливается в нулевое состояние. Принцип работы устройства основывается на :положении, гласящем, что каждую следующую перестановку можно получить из предыдущей, поменяв мест ми какие-либо два символа (не обязательно стоящие рядом), оставляя при этом все остальные символы на ме ..те. Устройство для перебора соединени работает следующим образом. Перед началом работы регистры 16 сдвига устанавливаются в начальные состояния, а в запоминающие элементы 6 записываются переставляемые коды. С помощью переключателя 13 задается количество переставляемых кодов,при этом количество регистров 16 сдвига подключенных через переключатель 13, Должно быть на единицу меньше числа переставляеьфых кодов. Каждая транспозиция реализуется путем обмена переставляемых кодов ме ду двумя запоминающими .элементами 6 с помощью логических элементов И пер вой 9 и третьей 11 групп. Выбор запо минаюощх. элементов, участвующих в об мене, осуществляется с помощью регистров. 16 сдвига. 2 Регистры 16 сдвига соединены между собой и с запоминающими элементами 6 так, чтобы осуществить циклический процесс обмена кодов между двумя запоминающими элементами 6. Например,первый регистр 16 сдвига осуществляет обмен между вторым и первым запоминающими элементами 6, второй - между третьим и первым, а третий регистр 16 сдвига управляет обменами.четвертого запоминшощего элемента 6 с другими и т.д. При вьфаботке всех п перестановок при п переставляемых кодов задаваемый переключателем 13 низкий потенциал, подаваемый с инверсного выхода последнего разряда (п-1)го регистра 16 сдвига, производит остановку устройства, так как подача тактовых импульсов через элемент И 1 прекращается. Рассмотрим несколько тактов работы устройства. Пусть в запомииаюсще эле менты записаны коды (1,2,3,4,5) в двоМчНом коде. При поступлении первого тактового импульса производится задача содержимого запоминаюш 1Х элементов 6, т.е. кодов (1,2,3,4,5). Через время задержки на элементе 5 задержки производится сдвиг единиицы в первом регистре 16 сдвига, а через время задержки на элементах 4 и 5 задержки откроются первые элементы И первой группы 9 и первой подгруппы третьей группы 1 1 и обменяютс:я первый и второй запоминающие элементы 6. Во втором такте также выдазотся коды (1,2,3, 4,5) и через время задержки на элементе 5 задеряжи опять производится сдвиг в первом регистре 16 сдвига. Единица с предпоследнего разряда первого регистра 16 сдвига через первый Элемент И четвертой группы 12 подается на вход синхронизации второго регистра 16 сдвига и происходит сдвиг. Через время задержки на злементах 4 и 5 задержки откроется второй элемент И первой группы и первый элемент И второй подгруппы третьей группы 11 и обменяются первый и третий запоминающие элементы 6. В следующем такте выдаются коды (3,1,2,4,5), опять происходит сдвиг в первом регистре 16 сдвига и т.д., циклы повторяются. Предлагаемый при1щцп работы устройства достаточен для получеш1я всех п перестановок кодов.

Устройство для перевода соединеттй (позводяет получить технический эффект, заключающийся в значительном увеличении быстродействия по срав/V

о73

11

нению с прототипом, вследствие исключения из алгоритма функционирования вспомогательных состояний.

15

Ю

W

10