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

Изобретение относится к автоматике и вычислительной технике и может использоваться для решения комбинаторных задач, а также в системах конт роля для генерации кодовых последовательностей. Известно устройство для выбора перестановок, содержащее кольцевые регистры, линии задержки, пороговые элементы, генератор импульсов и блок логики, в состав которого входят сумматор, импликатор и ждущий мультивибратор 1 . Недостатком известного устройства является низкое быстродействие (перебор всех п перестановок из п кодов обеспечивается за п тактов), Наиболее близким по технической сущности к предлагаемому является устройство для перебора перестановок, содержащее вспомогательный регистр, а также в каждом i-м (i 1,2,.,., п) разряде регистр, элементы И, ИЛИ, сче тчик по модулю (i + 2), элемент задержки, причем первый вход первого элемента И каждого разряда соединен с тактовым входом устройства, а выход подключен к тактовому входу регистра того же разряда, информационный-вход которого соединен с первым входом второго элемента И того же разряда и с ВЕЛХодом элемента ИЛИ следующего разряда, выход регистра каждого разряда соединен с первьвл входом третьего- элемента И того же разряда, выход которого соединен с первьм входом элемента ИЛИ того же разряда, второй вход которого подключен к выходу второго элемента И того же разряда, тактовый вход вспомогательного регистра является тактовьм входом устройства, информационныЯ вход которого подключен к выходу элемента ИЛИ первого .разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда, первый и второй, инверсный входы четвертого элемента И соединены с выходами счетчика соответстве-нно последующего и предьщущего разрядов, третий выход четвертого элемента И каждого разряд через соответствующий элемент задержки подключен к тактовому входу устройства , выход счетчика каждого разряда соединен с вторым инверсным входом первого и третьего элементов И и с вторьи входом второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов и разрядные выходы регистров являются выходами устройства 2 . Недостатком известного устройства является низкое быстродействие (пере бор всех п, перестановок из п кодов осуществляется за 2- i тактов). Цель изобретения - повышение быст родействия устройства. Поставленная цель достигается тем то устройство для перебора перестан . вок содержащве (п - 1) счетчиков с коэффициентами пересчета 2,3.. .,п соответственно, регистр (п - 2) групп элементов И и ИЛИ,п|жчем выход первого подключен к первому входу первого эл мента И первой группы, выход р-го счетчика (р 2,3,..., п-2) подключен к первому входу первого элемента И р-й группы, выход которого подключен к счетному входу {р+1)-го счетчика, выход первого элемента И первой группы подключен к счетному входу второго счетчика, введены (п-1) групп элементов И-ИЛИ и дешифраторы. причем каждая h-я группа элементов И-ИЛИ (h 1,2,.., п-1) содержит h элементов 2 И-ИЛИ и один элемент (h+1) И-ИЛИ, первый вход устройства соединен с первыми входами первых элементов И первой группы элемента 2 И-ИЛИ, i-й вход устройства (i 2,3,..,, п) соединен с первым входом i-ro элемента И элемента i И-ИЛИ (1-1)-й группы и с первыми входами вторых элементов И элементов 2 И-ИЛИ (1+1)-и группы, выходы элементов 2ИИЛИ первой группы соединены с первыми входами первых элементов И второй группы элементов 2И-ИЛИ соответствен но и с первыми входами элементов И элемента 3И-ИЛИ второй группы соот ветственно,выходы j-и группы элемен тов 2И-Ш1И и элемента (j +1) И-ИЛИ ( j 1,2,..., п-2) соединены с первы ми входами первых элементов И (+1)-й группы элементов 2И-ИЛИ соответ твен но и с первыми входами элементов И элемента ( j +2) И-ИЛИ ( +1)-й группы соответственно, выходы (п-1)-и группы элементов 2И-ИЛИ и элемента пИ-ИЛИ соединены с выходами устройства соответственно, первый выход первого дешифратора соединен с вторым входом второго элемента И второго элемента 2И-ИЛИ первой группы, второй выход первого дешифратора соединен с вторым входом первого элемента И второго эле мента 2И-ИЛИ первой группы и с вторыми входами элементов И первого элемен та 2И-ИЛИ первой группы, первый вы-, ход 1-го дешифратора (2 2,3,...г ij г1) соединен с вторым входом (j+l)го элемента И элемента (Й+1) И-ИЛИ К-й грутгпы, к-й выход 2-го дешифратора (к - 2,3,..., fe+1) соединен с вто рьм входом (В - к + 2)-го элемента И элемента (+1) И-ИЛИ -й группы и с вторыми входами элементов И (fi-K+2)-ro элемента 2И-ИЛИ t-й группы, входы де- шифраторов соединены с выходами счетчиков соответственно, вход тактовых импульсов устройства соединен со счетным входом первого счетчика, выход которого подключен к первому входу второго элемента И первой группы, вы ход которого подключен к первому входу элемента ИЛИ, вторые входы элементов И первой группы подключены к первому выходу п-го дешифратора, выход fe-ro счетчика (Е п-1) подключен к первому входу второго элемента И р-й Группы, выход которого подключен к р-му входу элемента ИЛИ, вторые входы элементов И р-й группы подключены к р-му выходу п-го дешифратора, выход (п-1)-го счетчика подключен к (п-1)-му входу элемента ИЛИ, выход которого подключен « шине конца работы устройства, выходы регистра подключены к входам п-го дешифратора соответственно. На Чертеже представлена блок-схема предлагаемого устройства. Устройство содержит счетчики с коэффициентами пересчета 2, 3, 4, ..., п, дешифраторы ., 3, регистр 4, элементы 2И-ИЛИ 5lJ-5 y ЗИИЛИ 6, 4И-ИЛИ 7,..., пИ-ИЛИ 8, элементы И 9 -9п-2, 10-,-10п-2/ элемент ИЖ 11, входы , 13, выходы 14-)14f,, выходн ую шину 15 конца работы. Первый вход 12-1 соединен с первыми входами первых элементов И первой группы элементов 2И-ИЛИ , i-й вход 12- (i 2,3,..., п) соединен с первым входом i-ro элемента И элемента iИ-ИЛИ и с первыми входами вторых элементов И (1-1)-й группы элементов ;2И-ИЛИ , п-й вход 12п соединен с первым входом п-гр элемента И i элемента пИ-ИЛИ 8 и с первьаии входами вторых элементов И (п-й)-и группы элементов 2И-ИЛИ 5 выходы первой группы элементов 2И-ИЛИ 5 - 62 соединены с первыми входами элементов И второй группы соответствующих элементов 2И-ИЛИ 5 - 5| и с первьми входами соответствующих элементов И элемента. ЗИ-ИЛИ б, выходы J-fi группы элементов 2И-ИЛИ 5 - 5| и элемента ( j +1) И-ИЛИ ( J - 1, 2,...,п-2) соединены с первьми входами первых элементов И соответствующих элементов 2И-ИЛИ Si 5j4i первыми входами соответствующих элементов И элемента ( j+2)И-ИЛИ, выходы (п-1)-и группы элементов 2И-ИЛИ элемента пИ-ИЛИ 8 соединены с соответствующими выходами 14,, - 14,, , первый выход первого дешифратора 2 соединен с вторым входом второго элемента И элемента 2И-ИЛИ 5g , второй выход первого дешифратора соединен г; вторьм входом первого элемента И элрмента 2И-ИЛИ 5i и с BTOjMiJM входом второго элемента И и вторым инверсньа 4 входоМ первого элемента И элемента 2И-ИЛИ 5 первый выход Е-го дешифратора (, 3,..., п-1) соединён с вторыл входом В+1) элемента И sjieMeHTa (+1)И-ИЛИ к-й выход Е-го девшфратора (к г 2, 3/ ... +1) соединен с вторым входом (Ь - к+2) элемента И элемента (2+1)ИИЛИ/ прямым входом второго элемента И и инверсным входом первого элемента И элемента 2И-ИЛИ Sg.j входы дешифраторов 2 соединены с выход аши соответствующих счетчиков in--г вход 13 тактовых импульсов соединен с входом счетчика 1-,, выход которого соединен с входами элементов И 9, И 10, элемента И 9 сое линен с входом счетчика выходы элементов И 10 - И lO-n-2 соединены входами элемента ИЛИ 11, выход р-го счетчика соединен с входами элементов И 9: и И 10., выход элемента И 9j соединён с входом {р+1) счетчика, вы ход п-1) счетчика l.. соединен с вх дом элемента ИЛИ 11, вых,од регистра 4 соединен с входами дешифратора 3, выходы дешифраторы 3 соединены соответственно с инверсньми входами элементов И 9 и с входами элементов И 1 выход элемента ИЛИ 11 соединён с выходной шиной 15 конца работы. Устройство работает следующим обраэом. В регистр 4 записывается число т, значение которогоравно числу пере, станавливаемых чисел (т 2,3,..., п-1). Если m п, то в регистр 4 чис ло не записывается. Для примера рассмотрим работу уст ройства для перестановки четырех чисел. В регистр 4 записывается число 4. На третьем выходе дешифратора 3 высокий потенциал и элемент И 9 зак рыт, элемент И lOj открыт, а остальные элементы И 9 открыты, элементы И 10 закрыты, выход счетчика 1з чере

995093 ткрытый элемент И lOj и элемент ИЛИ 11 соединен с выходной шиной 15 конца работы. Счетчики IT - 1 ,.,, находятся в нулевом состоянии, на первнк выходах дешифраторов 2/, - 2„. - высокие потенциалы, которые поступают на i-e элементы И элементов 1И-ИЛИ, в элементах 2И-ИЛИ открыты первые элементы И, так как на инверсные входы не подано высоких потенциалов. Следовательно, первый вход соединен с первым вы ходом, второй - с вторьал, третий - с третьим и т.,д. . . В зависимости от состояний счетчиков 1 - 1„ входы 12;, - 12п будут подключаться через элементы И-ИЛИ к различным выходам 14-1 .- Так, в зависимости от состояния счетчика Ц второй вход 122 может быть подкгаочен к второму выходу 142 (состояние счетчика 1 - 0) и к первому выходу 14,, а первый вход 12 - к второму выходу 142 (состояние счетчика 1 - 1). В зависимости от состояния второго счетчика 12 третий вход 12. подключен к третьей выходной шине 14 (состояние . 0), третий вход 123 подключен к второй, а второй вход 12з - к третьему выходу (состояние 1), третий вход подключен к первому, а первый вход - к третьему выходу (состояние 2).. В зависимости от состояния р-го счетчика 1р (р+Г) вход подключен к (р-И)-му вькоду (сЬстояние 0) , р-И) в«од подключен к р-му выходу, а р-й вход - к (р+1) выходу(состояние 1) н т.д., (р+1) вход подключен к первому выходу, а первый вход - к (р+Г) выходу (состояние р) . Если на входы подать числа, то на выходах в зависимости от состояний счетчиков получат все возможные перестановки этих чисел. Возможные перестановки для четырех чисел предетавлеЯы в таблице.

О 1 О 1 О 1 О

1234

О О О О О О 1 21 3 4 1324 2314 3214 3 12 4 1243

При поступлении 24 тактового импульса счетчики 1 - Ij устанавливают ся в нулевое состояние, а импульс с выхода счетчика i поступает через элемент И Юз/ элемент ИЛИ 11 на выходную шину 15 конца работы.

За 24 такта работы обеспечивается перебор всех перестановок из четырех чисел. Если требуется обеспечить перебор перестановок 5 чисел, то в регистр 4 записывается число 5, элемент R 1Q« открыт, а элемент И 9 закрыт и выход четвертого счетчика 1 соединен с выходной шиной 15 через элементы И Ю и ИЛИ 11, После поступления 24 тактового и -чпульса счетчики l-j-l устанавливаются-в нулевое состояние, а счетчик 1 - в единичное и работа устройства продолжается до тех пор, пока не поступит 120 тактовый импульс который установит счетчики 1 1 - в нулевое состояние и импульс с выхода четвертого счетчика поступит через

Продолжение таблицы

элементы И 104 и -ИЛИ 11 на выходную шину 15 конца работы.

Аналогично устройство работает при переборе перестановок любого m п числа чисел.

Лредлагаемое устройство для перебора перестановок по сравнению с устройством-прототипом имеет большее быстродействие за счет исключения повторяющихся перестановок. Предлагаемое устройство для п чисел обеспечивает . все перестановки за п тактов работы,

п а устройство-прототип за / i I , что

п .

на il тактов больше, чем в иэобреi i

тенич,. В предлагаемом устройстве исключены линии задержки, используемые в устройстве-прототипе. Это обеспечивает возможность дальнейшего увеличения быстродействия устройства за счет повышения частоты тактовых импульсов. Кроме того, устройство-прототип обеспечивает перебор перестановок только п чисел. Изобретение же позволяет осуществлять перебор любого количества m чисел (го 2,3,..., п) за га; тактов работы, что также расширяет область его применения. Формула изобретения Устройство для перебора перестановок, содержащее (п-Г) счетчиков.с коэффициентами пересчета 2,3,..., п соответственно, регистр, (п-2) групп элементов И и ИЛИ, причем выход первого счетчика подключен к первому входу первого элемента И первой груп пы, выход р-го счетчика (р г 2,3,... п-2) подключен к первому входу перво го элемента И р-й группы, выход кото рого подключен к счетному входу (р+1 го счетчика, выход первого элемента Ьервой группы подключен .к счетному входу второго счетчика, о т л и ч а ю щ е ег с я тем, что, с целью повышения его быстродействия, в устройст во введены (п-1) групп элементов И-И и дешифраторы, причем каждая h-я rpy па элементов И-ИЛИ (h 1,2,.., ,) содержит, h элементов 2И-ИЛИ и один элемент (h+l) И-ИЛИ, первый вход уст ройства соединен спервыми входами первых элементов И первой группы эле меита 2И-ИЛИ, i-й вход устройства (1 2,3,..., п)соединен с первым входом i-ro элемента И элемента 1ИИЛИ (1-1)-и группы и с первыми вхола ми вторых элементов И элементов 2ИИЛИ (1+1)-и группы, выходы элементов 2И-ИЛИ первой группы соединены с пер вьми входами первых элементов И второй группы элементов 2И-ИЛИ соответственно и с первыми входами элементов И элемента ЗИ-ИЛИ второй группы соответственно, выходы j-й группы эле;ментов 2И-ИЛИ и элемента ( +1). И-ИЛИ ( j -1,2,..., п-2) соединены с первыми входами первых элементов И ( 3+1)-й группы элементов 2И-ИЛИ соответственно и с первыми входами элементов И элемента ( j+2) И-ИЛИ (j -И)-й группы соответственно, выходы (п-1)-и группы элементов 2И-ИЛИ и элемента пИ-ИЛИ соединены с выходами устройства соответственно, первый выход первого депгафратора соединен с вторым входом второго элемента И второго элемента 2И-ИЛИ первой л руппы, второй выход первого денжфратора соединен с вторым входом первого элемента И второго элемента 2Ч-ИЛИ первой группы и с вторыми входами элементов И первого элемента 2И-ИЛИ первой группы, первый выход -го дестфратора ( - 2,3,..., п-1) соединен с вторьМ входом (Е+1)-го элемента И элемента (t+1) И-ИЛИ 1-1 группы, к-й выход 1-го дешифратора (к s 2,3,..., Е+1) соединен с вторым входом (В - к+2)-го элемента И элемента (i+1) И-ИЛИ t-K группы и с вторъми входами элементов И (-K+2)-ro элемейта 2И-ИЛИ t-й группы, входы дешифраторов соединены с выходами счетчиков соответственно, вход тактовых импульсов устройства соединен со счетным входом первого счетчика, выход которого подключен к первому входу второго элемента И первой группы, выход которого подклюгчен к первому входу элемента ИЛИ, Вторые входы элетиентозв И первой группы подключены к первому выходу п-го дешифратора, выход Е-го счетчика ( ; п-1). подключен .к первому входу второго элемента И р-й группы, выход которого подключен к р-му входу элемента ИЛИ, вторые входы элементов И р-й группы подключены к р-му выходу п-го дешифратора, выход (п-1)-го счетчика подключен к (п-1)-му входу элемента ИЛИ, выход которого подключен: к шине конца работы :устройства, выходы регистра подключены к входам п-го дешифратора соответственно. Источники информации, Принятые во внимание при экспертизе 1.Авторское свидетельство СССР 446057, кл. G Об F 7/38, 1.972. 2,Авторское свидетельство СССР 748416,, кл. G 06 F 15/20, 1978 (прототип) . -.