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

Изобретение относится к автоматике и Ьычислительной технике, предназначенс для получения всех п п естановок из п вепичкн и может использоваться для решения комбинаторных задач, а также Б системах контроля рля генерации кодовых последовательностей. Известно устройство для выбора перестановок, содержащее кольцевые регист ры, кшши задержки, пороговьв элементы, генератор импульсов и блок логики, в состав тготорюго входят сумматор, имппикатор и жщишй мультивибратор 11 J . Недостатком устройства является няэкое быстродействие (перебор всех п перестановок из п кодов обеспечивается за п тактов). Наиболее близким по тежической сущности к изобретению является устройство .ОЛЯ перебора перестановок, содержащее вспомогательный регистр, а также в каждом i-BOM ( - 1,2, ... ,п) разряде регистр, элементы И, ИЛИ, счетчик по модулю ( i + 2), элемент задержки, причем первьй вход первого элемента И каждого разряда соединен с тактовьп д входом устройства, а выход подключен к тактовому входу регистра того же разряда, информационный вход которсгю соединен с первым входом второго элемогга И того же разр51да и с выходе элемента ИЛИ сяедуюихего разряда, выход регистра каходого разряда соединен с первым входом третьего элемента И того же разряда, выход котсфого соедаиен с первьп входом элемента ИЛИ того же разряда, второй вход которого подключен к выходу второго элемента И того же разряда, тактовый вход вспомогательного регистра является тактовым входом устройства, информационный вход которсбго подключен к выходу элемента ИЛИ первого разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда, первый- и второй шшерсные входы четвертого элемента И соединеш) с выходами счетчика соответственно последующего и предьшущего разрядовр третий выход четверторо элемента И каждого разр$ща через соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого разряда соединен с вторым штерсным входом первого и третьего элементов И и с вторым входом второго элемента И того же разряда, причем выходы счетчиков первого и поелед11его разрядов и разрядные выходы регистров являются выходами устройства. Недостатком устройства является iffloKoe быстродействие (перебор всех г перестановок из п кодов осуществляется за У тактов).. . 1 -1 ; . Цель .Изобретения - повьпиение быстро действия устройства.. . Для достижения указанной цели устройство, содержащее п -1 счеТЧИков, п регистров, 2 п-5 элементов И, П-З элементов ИЛИ (п -3) групп элементов ИЛИ, п -3 групп элементов запрета, причем первые входы элементов И с первого по n-2-й подключены к тактовому входу устройства, а их выходы соединены с тактовыми входами регистров с второг по п -1-й соответственно, выход п -2ого элемента И подключен к тактовому входу п -ого регистра, выходы регистро с второго по п -2-й подключены к информшдионным входам элементов запрета с первой по п -3-тъю гругшы соответственно, выходы которых соединены с первы хш входами элементов ИЛИ с Первой по п -З-тьк группы соответственно подключенных своими выходами к информационным входам регистров с третьего по n-1-й соответственно, вторые вхолы которых соецинены с выходами элементов И с первой по п -3 -тью группу соответственно, первые входы которых соединены с выходами п -ого регистра, информационные входы которого подключены к выходам п -1-ого регистра, и пнформашюнными входами второго регистра, дополнительно содержит дещифра ТОР...элемент запрета, группы -элементов И с п -2-ой по 2п-3-тью, регистры с n + l-oro по 2п-и, причем первые входы элементов И с п -2-ой по 2 п -3-ть .группу соединены с выходами регистров с первого по п-и соответственно, вторые входы подключены к первому выходу дешифратора, третьи входы подключены к тактовому входу устройства, а выходы соединены с информационными входами регастров с п + 1-ого по 2 п -и, тактовые входы которых соединены с вы ХОДОМ элемента запрета, управляющий вход которого coeди eн с первым выходом дешифратора, а информационный- с тактовым входом устройства, выходы регистров с п +1-ОГО по 2п -и являются выходами устройства, кроме того, выходы предьщущего регистра соединены соответртвенно с информационными входами последующего, причем выходы 2п -ого регистра соединены с-информационными входами п+1-ОРО регистра, выход пре- . дыдущего счетчика соединен с одом последующего счетчика, вход первого счетчика соединен с тактовым входом устройства, выход п-1-ого счетчика соединен с выходом окончания работы устройства, входы дешифратора соединены р разрядньми выходами первого счетчика, а второй выход подключен к второму входу первого, элемента И и к первым входам элементов ИЛИ с первого по п -3-гй, выходы дешифратора с третьего по п -1-ый подключены к первым входам элементов И с, п -1-ого по 2 п.-5-й сосугветственно, остальные входы которых соединены с разрядными выходами счетчиков с второго по п -2-й соответственно и вьгходами всех предыдущих счетчиков, кроме первого, а выхо-; ды элементов И с п -1-ого по 2п -5-й соединены с -вторыми входами элементов ИЛИ с первого по п -3-и соответ ственно, остальные входы которых соединены с выходами всех предыдущих элементов И, кроме того, выходь элементов И с п -1-ога по 2п -5-й подключены к BTOpbnvi входам .групп элементов И с первой по п -3-тью соответственно и к управляющим входам групп элементов загфета с первой по п-3-тью соответственно, выходы элементов ИЛИ с первого по п -3-й подключены к вторым входам элементов И свторого по п соответственно. На чертеже представлена схема устройства для перебора перестановок (для п-5). Устройство содержит регистры , , группы элементов И , элемент запрета, группы элементов . запрета, группы элементов И 6,-6, элементы И , 8 и 9, группы элементов ИЛИ 1О,-1О, элементы ИЛИ 11 . и 12, -дешифратор 13, счетчики 14- . 17, вход 18 тактовых импульсов, выход 19 окончания работы устройства и ш:формационные выходы 20. При этом счетчик 14 работает по модулю 5, счетчик 15 - по модулю 4, счетчЕК 16 - по модулю 3, счетчик 17 по модулю 2. Когшчество элементов в группах и разрядность регистров соответствует ко личеству двоичных разрадов, необходимы для представления в двоичном коде максимального из переставляемых чисел. Устройство работает следующим обра зом. Перед началом работы в регистра . занесены кодь1 переставляемых величин, счетчики 14-17 находятся в состоянии О, элемент 4 запрета закрыт, а. элементы И г открыты. Ра бота устройства начинается с подачей на вход 18 тактовых импульсов. При посту лении Первого тактового импульса проис ходит перепись кодов из регистров l-i-l в соответствующие регистры , через элементы И , переключение счетчика 14 в состояние 1, по которо му закрываются элементы И и открывается элемент 4 запрета, разрешающий поступление тактовых импульсов на тактовые входы регистров 2 -2 с. Появляетсясигнал на втором выходе дешифратора Ii3, открывающий элемент И 7л элементы И V и 7 через элементы э ИЛИ 11 и 12 и разрешающий поступление второго тактового импульса на тактовые входы регистров 1,,-1 г. При поступлении тактовых импульсов с второго по четвертый коды, записанные в регист рах , сдвигаются при каждом тактовом импульсе в соседние справа ре- гистрьх, причем из регистра. 2 j сдвиг происходит в регистр 2, а состояние счетчика 14 изменяется от 2 до 4. Кроме этого, одновременно при посгуп- лении второго тактового импульса коды, записанные в регистрах In-lc сдвигают ся в соседние с.права регистры через открытл1е элементы за11рета и элементы ИЛИ lOj-10, причем из регистра Ig сдвиг происходит в регистр 1. При поступлении пятого тактового импуль са гфоисходит сдвиг кодов в регистрах 2/1 2 2 в соседние справа регистры, счет- . чик 14 переключается в О, ссютветствекно счетчих 15 в состояние 1, т.е. усганав.-л1вается исходное состояние счет чика 14 и рхабота устройства повторяется до тех пор, пока счетчик 14 не будет в состоянии 1, а счетч1Ж 15 - в соСТОЯНИИ 3. При поступлении 17-го тактового импульса происходит сдвиг в соседдов в регистрах ние справа регистры, счетчик 14 пере- на выходе ключается в состояние элемента И 8 появляется сигнал, эакры веющий элемент запрета 5- и открывах щий элемент И 6 и элементы И 7 Я 7 через элеметы ИЛИ 11 и 12. При поступлении 18-го тактового импульса происходит сдвиг кодов в регистрах 2,,2 5 и 1з 5 открытые элементы И 6j, запрета 5 и элементы ИЛИ lOjЮд в соседние справа регистры „счетчик 14переключается в состояние 3; открываетря элемент запрета 5,, а элемент 6j закрьгоается. При поступлении 19-го тактового импульса происходит сдвиг кодов в регистрах 2 ,,-25 . счетчик 14 переключается в состояние 4. При поступлении 20-го тактового импульса коды в регистрах г сдвигаются, счетчики 14 и 15 переключаются в О, а счетчик 16. - в , т.е. устанавливается исходное состояние счетчиков 14 и 15и работа устройства повторяется сна-чала аналогично описанной. При поступлении 58-го тактового импульса устройство работает также как при поступлеиш 18-го Тактового импульса, кроме этого, появляется сигнал на выходе элемента И 9, так как счетчики 14, 15 в состоянии З, а счетчик 16 в состоянии 2, закрывающий элемент запрета 54 и открывающий элемент И 6 и элемент И 7 через элемент ИЛИ 12. При поступлении 5У-ГО тактового импульса происходит сдвиг кодов в регистрах в соседние справа регистры и в регистрах через открьггый элемент И 64 и элемент ИЛИ 10. При поступлешш 6О-го тажтового импульса происходит сдвиг кодов в регистрах , счетчики 14-16 переключаются в О, счетчик 17 - в 1, т.е. устанавливается исходное состояние счетчиков 14-16 и работа устройства повторяется сначала аналогично описанной. При поступлении последнего 12О-го тактового импульса происходит сдвЕСг кодов в регистрах 2-,2, счетчики 14-17 п)еключаются в О и на выходе устройства 19 появляется сигнал об окоичании перебора перестановок, т.е. об окончании работы устройства. Технико кономический эффект заключается в , чта предлагаемое устройство обладает большим быстродействием по сравнению с известным. Количество тактов для перестановки п чисел в пред- п-1 агаемом устройстве уменьшено на i о сравнению с прототипом и равно .. fOMG этого, в предлагаемс устройстве исключены n -1 гаший задержки, используемых в известном устройстве. Это обеспечивает возможность дальнейшего увеличения быстродействия устройства за счет повьшения частоты тактовых импульсов. Формула изобретения Устройство для перебора перестановок содержащее n -1 счетчиков, n-регист-. ров, 2п-5 элементов И, n -3 элементов ИЛИ, групп элементов И,п -3 групп элементов ИЛИ, n -3 групп элегментов запрета, причем первые входы элементов И с первого по n -2-й подключены к тактовому входу устройства, а их выходы соединены с тактовыми входами регистров с второго по n -1-й соответственно, выход n -2-огЬ элеме та И подключен к входу п ого регистра, выходы регистров с второго по n -2-й подключены к информационным входам элементов запрета с первой по n -3-тью группы соответственно, выходы которых соединены с первым входаьш элементов ИЛИ с первой по n -3-тью грутшы соогвегсгвенно, подключенных своими выходами к информационным входам регистров с третьего, по г 1-й соответственно, вторые входы ко торых соединены с выходами элементов И с первой но n -3-тью группу соответ ственно, первые входы которых соединены с выходами n -ого регистра, информациошше входы которого подключены к выходам n -1-ого регистра, и информа 1ШОННЫМИ входами второго регистра, от личающееся тем, что, с целью повышения быстродействия, оно содержит дешифратор, элемент запрета, группы элементов Иол 2-ой по 2 n -3-тью, регистры с п+1-ого по 2п-й, хфичем «ервые Входы элементов И с n -2-ой по 2п -3-тью группу соединены с выходами регистров с первого по n -и соответств но, вторые входы подключены к первому выходу дешифратора, третьи .входы подключены к тактовому входу устройства, а выходы соединены с информапионными входами регистров с n + 1-ого по 2п актовые входы которых соединены с выодом элемента запрета, управляющий ход которого соединен с первым выхоом дешифратора, а информационный .- с актовым входомустройства, выходу Рв йстров с n + 1-ого по Зп-й являются ыходами устройства, кроме того, выходы редыдущего регистра соединены соответтвенно с информационными входами последующего, хфичем выходы 2п-ого регистра соединены с информационньаш ходами n + 1-ого регистра, выход предьщущего счетчика соединен с входом оследующего счетчика, вход первого счетчика соединен с тактовым входом устройства, выход n -1-ого счетчика соединен с выходом окончания работы устройства, входы деши Чратора соединены с разрядными выходами первого счетчика, а второй выход подключен к второму входу первого элемента И и к первым входам элементов ИЛИ с первого по n -3-й, выходы дешифратора с третьего по n -1ый подключены к первым входам элементов И с n -1-ого по 2п-5-й соответственно, остальные входы которых соединены с разрядными выходами счетчиков с второго по n -2-й соответственно и выходами всех предыдуиих счетчиков, кроме первого, а выходь элементов И с П-1-ОГО по 2п-5-й соединены с вто- рыми входами элементов ИЛИ с первого по n -3-й соответственно, остальные входы которых соединены с выходами всех предыдущих элементов И, кроме того, выходы элемезитов И с n -1-ого по 2п-5-й подключены к вторым входам групп элементов И с первой по n -3-тью соответственно и к управляющим входам групп элементов запрета с первой по П -3-тью соответственно, выходы элементов ИЛИ с перЪого по n -3-й подключены к вторым входам элементов И с второго по n -2-ой соответственно. Исто ники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 446О57, кл. (5 06 Р 7/38, 1974. 2,Авторское свидетельство СССР № 748416,кл. Q Об F 15/2О, 198О (прототип),