Устройство для перебора перестановок Советский патент 1980 года по МПК G06F15/20 

.v:.,:. л...,..-.,.., ,.,:. Изобретение относится к области автоматики и вычислительнр;й техники предназначено для получения всех п перестановок из п величин и может использоваться для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Известно устройство для перебора перестановок, содержащее счетчики, схемы ИЛИ и И l. Недостатком его является большая сложность. Наиболее близким по своей технической сущности к данному изобретению является устройство для перебор сочетаний, содержащее в каждом из п разрядов регистр, элементы И, ИЛИ, элемент -задержки, причем вход первого элемента И соединен с тактовым входом устройства, а выход его подключен к тактовому входу регистра . того же разряда, информационный вхо которого соединен с первым входом второго элемента И того же разряда и с выходом элемента ИЛИ следующего разряда, выход регистра каждого раз да соединен с первым входом третьег элемента И того же разряда, выход которого соединен с первым входом . элемента ИЛИ того же разряда, второй вход котброгЪподключей к выходу второго элемента И того же разряда, устройство содержит, кроме того, дополнительный регистр, тактовый вход которого является тактовым входом устройства, информационный вход которого подключен к выходу элемента ИЛИ первого разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда 2 . Устройство содержит, кроме того, ключи, мультивибратор, блок регистрации. Недостатком его является низкое быстродействие. Целью изобретения является повышение быстродействия. Цель достигается тем, что каждый -тый (| 1,... п ) разряд устройства содержит счетчик по модулю i + 2 и четвертый элемент И, первый и второй инверсные входы которого соеди(1ены с выходами счетчика соответстренно последующего и предыдущего разрядов,третий выход четвертогоэлеиента И каждого разряда через соответствующий элемент задержки подклюаен к тактовому входу устройства,вы|:од счетчика каждого разряда соединен CO вторым иывеь спым входом первого третьего элементов И и со вторым входом второго элемента И того же разряда, причем выходы счетчиков пе вого и последнего разрядов и разряд ные выходы регистров являютсявыходами устройства. На чертеже представлено устройст во для перебора перестановок (дляпУстройство содержит регистр 1, элемент И 2, элемент ИЛИ 3, элемент И 4, счетчик 5, элемент И 6, тактовый вход 7, элемент 8 задержки, элемент И 9, разрядные выходы 1 регистров, выходы 11 счетчика последнего разряда, выход 12 счетчика первого разряда, вспомогательный ре гистр 13. Устройство работает следующим образом. Перед началом работы во все пять регистров 1 заносятся коды перестав емь:х величин, счетчики 5 сбрасывают ся в состояние О, вследствие чего открываются элементы И 2 и И б, зап раются элементы И 4 и выходы регист ров 1 подключаются ко входам соседних слева регистров 1, причем выходы цервого регистра 1 подключаются ко входам пятого регистра 1, запираются элементы И 9 и на входы счет чиков по модулю 5, 4, 3 тактойые им пульсы не поступают. Работа устройства начинается с подачей на вход 7 серии тактовых сигналов. Величины задержек элементов задержки, .подключенных соответственно к счетчикам 5 по модулю б, 5, 4, выбираются такимобразом, чтобы они удовлетворяли соотноьаению: тг , вследствие чего на счетчик по модулю б тактовые импульсы начинают поступать с запаздыванием на Tg-rn-cr (где: m 4 С - длительность так тового импульса) При поступлении тактовых сигналов на регистры 1 коды, записанные в них через элементы И 2 и ИЛИ 3, сдвигаются в соседние слева регистры 1, причем из первого регистра 1 сдвиг происходит в пятый регистр. После поступления на счетчик 5 по модулю 5 пяти тактовых импульсов на его выходе появляется единич ный сигнал, который запрещает считы вание кодов из регистра 1, откры--; вает элемент И 9 и на его счетчик 5 пи модулю 5 проходит 1 тактовый импульс, запирает соответствующие элементы И 2 и И б, отпирает соответствующие элементы И л, вследствиЬ чего цепь из пяти рег ист1ров | ам кается в обход пятогЪ регистра 1, С приходом mecTorjD тактового им п уль а на™ счетчик 5 по модулю 6, если нет запрета с выхода счётчика по модулю ), счетчик сбрасывается в состояние О, закрывая при этом

748416 элемент И 9, подключенный ко входу счетчика 5 по модулю 5. Когда на вход счетчика 5 по модулю 5 Поступит 4 тактовых импульса, на выходе этого счетчика .появится единичный сигнал. Этот сигнал запрещает подачу следующего тактового сигнала на счетчик 5 по модулю 6, запирая схему И 9, подключенную к его входу; разрещает подачу следующего тактового сигнала на счетчик 5 по модулю-4, элемент И 9, подключенный к его входу, открывает, запирает соответствующие элементы И 2 и,И 6, отпирает соответствующие элементы И 4, вследствие чего цепь из пяти регистров 1 замыкается в обход пятого и четвертого регистров 1, выходной сигнал со счетчика 5 по модулю б запрещает считывание кодов регистров 1. С приходом следующего тактового импульса на счетчик 5 по модулю 5, если нет запрета с выхода счетчика 5 по модулю 4, счетчик сбрасывается в состояние О, открывая при этом элемент И 9, подключенный ко входу счетчика 5 по модулю б, и , счетчик 5 по модулю б сбрасывается |В состояние 0. .После поступления на счетчик 5 по модулю 4 трех тактовых импуль-сов на его выходе появляется единичный сигнал. Этот сигнал запрещает подачу следующего тактового импульса на счетчик 5 по модулю 5, запирая элемент И 9, подключенный к его входу, разрешает подачу следующего тактового сигнала на счетчик 5 по модулю 3,открывая элемент И 9, подключенный к его входу; запирает соответствующие элемента И 2 и И 6, отпирает соответствующие элементы И 4, вследствие чего цепь из пяти ре- . ристров 1 замыкается в обход пятого, четвертого и третьего регистров 1, выходной сигнал со счетчика 5 по модулю б запрещает считывание кодов из регистров 1. С приходом следующего тактовогоимпульса на счетчик 5 по модулю 4, если нет запрета с выхода счетчика по модулю 3, он сбрасывается в состояние О, открывая элемент И 9, подключенный ко входу счётчика 5 по модулю 5. После этого сбрасывается в состояние О счетчик 5 по модулю 5 и счетчик 5 по модулю б. После поступления двух тактовый импульсов на вход счетчика 5 по модулю 3,на его выходе появляется единичный сигнал.Этот сигнал запрещает подачу следующего тактового сигнала на счетчик 5 rio модулю 4,зёпирая элемент И 9, подключенный к его входу; запирает соответствующие элементы И 2,. отпирает соответствующий элемент И 4,, вследствие чего колы с выходов перво748416

Прототип предлагаемого изобретения обеспечивает перебор всех п перестановок из п кодов за rt тактов (в случае для 5 чисел - 3125 тактов). По сравнению с прототипом, предлагаемое устройство обеспечивает перебор : всех п перестановок из п кодов за ,tf J Tактов (в случае для 5 чисел - 153 такта) .

Формула изобретения

Устройство для перебора перестановок, содержащее вспомогательный регистр, и также в каждом из п разрядов регистр, элементы И, ИЛИ, элемент

8

задержки, причем первый вход первого элемента И каждого разряда соединен с тактовым входом устройства, а выхо подключен к тактовому входу регистра того же разряда, информационный вход которого соединен с первым входом второго элемента И того же разряда и с выходом элемента ИЛИ следующего разряда, выход регистра каждого разряда соединен с первым входом третьего элемента. И того же разряда, выход которого соединен с первым входом элемента ИЛИ того же разряда, второй вход которого подключен к выходу второго элемента И того же разряда, тактовый вход вспомогательного регистра является тактовым входом устройства, информационный вход которого подключен к выходу элемента ИЛИ первого разряда, а выход дополнительного регистра соединен с первьм входом второго элемента И последнего разряда, отличающийся тем, что, с целью повышения быстродействия, каждый -тый ( l,...f) разряд устройства содержит счетчик п модулю + 2, четвертый элемент И, первый и второй, инверсные входы которого соединены с выходами счетчика соответственно последующего и предьздущего разрядов, третий выход четвертого элемента И каждого разряда через соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого раз(ряда соединен со вторым инверсным входом первого и третьего элементов И и со вторым второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов и разрядные выходы регистров являются выходами устройства.

Источники информации, принятые во внимание при экспертизе

. 1. Авторское свидетельство CCQP 1 374606, кл. G 06 F 7/00, 1970.

2. Авторское свидетельство СССР № 446057, кл. G Об F 7/38, от 22,11,72.