Комбинаторное устройство Советский патент 1981 года по МПК G06F7/00 

(54) КОМБИНАТОРНОЕ -УСТРОЙСТВО

Изобретение относится к aBTOwaTHv ке и вычислительной технике и может быть использовано для решения комбинаторных задач, а также для генерации кодовь1Х последовательностей в устройствах контроля. Известно комбинаторное устройство осуществляющее перебор сочетаний, содержащее последовательно соединенные счетчики с коэффициентами пересчета, разнящимися на единицу, схемы И, схемы ИЛИ, линии задержки,, триггеры, дешифраторы, формирователи, генераторы импульсов ll. Недостаток устройства в том, что он не осуществляет генерацию переста новок. В&иболее близким техническим реше нием к изобретению является комбинаторное устройство, содержащее в i-то (,...,М) разряде регистр, три эле мента И, элемент ИЛИ, причем выход ре.:истра каждого разряда соединен с первым входом первого элемента И то же разряда, выход которого соединён с первым входом элемента ИЛИ, выход которого соединен с первым входом второго элемента И следующего разря да, и первым входом регистра следую щего разряда, а второй вход соединей с выходом второго элемента И того же разряда, второй вход которого «, соединен с первым входом третьего элемента И того же разряда и вторым входом первого элемента И того же разряда, выход третьего элемента И каждого разряда соединен со вторым входом регистра того же разряда. Устройство содержит кроме того дешифратор 21, Недостатком его является низкое быстродействие. Цель изобретения - повышение быстродействия. Цель достигается тем, что устрЬйство содержит W-4 распределителя, N-3 кольцевых сдвиговых регистров, группу элементов И, первую группу из N-2 элементов .ШШ,. вторую группу элементов ИЛИ, причем первый и последний выходы первого распределителя соединены с первьал входом третьего элемента И соответственно первого и последнего разрядов устройства и с первыми входами соответственно первого и N-2 элеменфов группы ИЛИ. Каждый остальной выход первого распределителя сое динен с первым входом соответствующего элемента ИЛИ первой группы и со вторыми входами следующего элемента

ИЛИ первой группы, выходы элементов ИЛИ группы соединены с первыми входами третьих элементов И .соответствующих разрядов, вторые входы которых соединены между собой и являются тактовым входом устройства, входы первого распределителя, кроме последнего, соединены с выходами следующег распределителя и выходами i-того кольцевого регистра сдвига, входы последнег о распределителя соединены с выходами двух последних кольцевых регистров сдвига, управляющий вход каждого кольцевого регистра сдвига соединен с выходом соответствующего элемента И группы, нервый вход которого соединен с выходом следующего элемента И группы, а второй вход соединен с выходом соответствующего элемента ИЛИ второй группы, первый и второй входы которого соединены с , первыгт и последним выходами соответствующего кольцевого регистра.

На чертеже схематически показано устройство.

Оно содержит регистры 1-6, элементы И 7-12, элементы И 13-18, элементы И 19-24 элементы ИЛИ 25-30, кольцевые регистры сдвига 31-33, распредeJiИтeли 34-35, триггеры управления сдвигом 36-38, тактовый вход 39 устройства, выход 40 распределителя, ajJCMOHT ИЛИ 41, выход 42 распределителя, эле.мент ИЛИ 43, выход 44 распределителя, выход 46 распределителя элемент, ИЛИ 45, элемент ИЛИ 47, выход 48 распределителя, входы 49-57 распределителя, выходы 58-66 распределителя, входы 67-84 распределителя элементы И 85-90, элемент ИЛИ 91, элементы И 92 и 93, элементы -ИЛИ 9499, элементы И 100-111, элементы ИЛИ 112-118, элементы И 119-126.

Комбинаторное устройство работает . следующим образом.

В первом такте работы устройства регистры 1-6 устанавливаются соотII -1 и II о II

ветственно в состоянии О i , , 4, 5. На информационные выходы регистров 1-6 поступают соответственно сигналы 000, 001, 01(3, 011, 100, 101. Таким образом, в первом такте работы устройства реализуется первая перестановка 012345 (см. та лицу), где номера позиций цифр в перестановке соответствуют номерам регистров, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих регистров.

Регистр 31 устанавливается в состояние 00010, регистр 32 - в состояние 0.00010, регистр 33 - в состояние 0000010 {см. таблицу).

На входы распределителя 34 с выходов кольцевого регистра 31 поступают соответственно сигналы 0,0, 0,1,0. Нл входы элемента ИЛИ 112 с входов 63 и 71 распределителя 34 поступают

нулевые сигналы, а единичный сигнал с входа 70 распределителя 34 поступает через элемент ИЛИ 113 на вход каждой из схем И 107, 109-111.

На входы 79-84 распределителя 35 с выходов сдвигающего регистра -32 поступают соответственно сигналы 0,0,0,0,1,0.

Нулевой сигнал с входа 79 через выход 59 этого распределителя и вход 50 поступает на вход каждого из эле- , ментов,И 102, 104, 106, 108, 110, 111 Нулевой сигнал с входа 84 распределителя 35 через выход 65 этой схемы и вход 56 распределителя 34 поступает на вход каждого из элементов И 100, . 101, 103, 105, 107, 109. Нулевые сигналы с выходов первого и последнего разряда, сдвигающего регистра 33 поступают, .соответственно на входы 72 и 78 распределителя сигна лов 35. С выхода 72. этой схемы.нулевой сигнал поступает на вход каждого из элементов И 120, 124, 125, а также через выход 58 распределителя 35 и вход 49 распределителя 34 поступает на вход каждого из элементов И 101, 104,

105,108, 109, 111. С входа 78 распределители 35 нулевой сигнал поступает на вход каждого из элементов

И 119, 121, 123, 125, а также через выход 66 распределителя35 и вход 57 распределителя 34 поступает на вход Каждого из элементов И 100, 102, 103,

106,107, 110.

Таким образом, все элементы И 100111, 119-126 закрыты нулевыми сигналами на входах, и сигналы из регистров 31 и 32 через распределители 34 и 35 соответственно не поступают.

Нулевой сигнал с выхода второго разряда регистра 33 через вход 73, элемент ИЛИ 114, выход 60, вход 51, элемент ИЛИ Э5, выход 40 закрывает элементы И 7 и 19 и открывает элемент И 13. Нулевой сигнал с выхода третьего разряда сдвигающего регистра 5з через вход 74 распределителя сигналов 35, элемент ИЛИ 115, выход 61, вход 52 распределителя сигналов 34, элемент ИЛИ 96, выход 42, элемент ИЛИ 41 закрывает элементы И 8 и 20 и открывает элемент И 14. Нулевой сигнал с выхода четвертого разряда регистра 35 через вход 75 распределителя 35, элемент ИЛИ 116, выход 62, вход 53 распределителя сиг налов 34, элемент ИЛИ 97, выход 44, элемент ИЛИ 43 закрывает элементы И 9 и 21 и Ь крывает элемент И 15. Нулевой сигнал с выхрда пятого разряда регистра 33 через вход 76 распределителя 35, элемент ИЛИ 117, выход 63, вход 54 распределителя 34, элемент ИЛИ 98, выход 46, элемент ИЛИ 45 закрывает элементы И 10 и 22 и открывает элемент И 16, Единичный сигнал с выхода шестого разряда регистра 33 через вход 77 распределителя 35, элемент ИЛИ 118, выход 64, вход 55 распределителя 34, элемент ИЛИ 99, выход 48, элемент ИЛИ 47 открывает элементы И 11 и 23 и закрывает элемент И 17. Кроме того, единичный сигнал, поступающий с выхода 48 распределителя 34, открывает элементы И 12 и 24 и закрывает элемент И 18, Триггеры управления сдвигом 36-38 устанавливаются в нулевое состояние (см, таблицу), и на первые входы эле ментов И 85, 88 и 92 поступают нулевые сигналы, а на первые входы элементов И 86, 89 и 93 поступают единичные сигналы с соответствующих выходов триггеров, благодаря чему в ре гистрах разрешается левый сдвиг. Нулевые сигналы с выходов первого .и последнего разрядов регистра, 33 че рез элемент ИЛИ 94 поступают на вход элемента И 90 и закрывают его. Нулевые сигналы с выходов первого и последнего разрядов сдвигающего регист ра 32 через элемент ИЛИ 91 поступают на вход элемента И 87 л закрывают его, Во -втором такте работы устройства тактовый сигнал поступает на вход каждого из элементов И 19-24, и единичные сигналы с выходов открытых элементов И 23 и 24 поступают на так товые входы регистров 5 и 6. Код 100 с информационного выхода регистра 5 через открытые элементы И 11, 13-16 и элементы ИЛИ 25-29 поступает на вход установки регистра 6, Код 101 с информационного выхода регистра 6 через открытый элемент И 12 и элемент ИЛИ 30 поступает на вход установки регистра 5, Регистры 5 и 6 устанавливаются соответственно в состояния 5 и 4, Информация в других регистрах фиксируется нулевыми сигналами из тактовых входов, . Таким образом, во втором такте ра боты устройства реализуется перестановка 012354,; Кроме того, во втором такте тактовый сигнал поступает на вторые вхо ды элементов И 92 и 93, единичный си нал с выхода элемента И 93 поступает, в цепь левого сдвига регистра 33, и единица в этом регистре сдвигается на один разряд влево, В Третьем такте работы устройства такжовый сигнал 39 поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода пятого разряда регистра 33 через элементы ИЛИ 11 и 98 распределителей 35 и 34 соответственно, элементы ИЛИ 45 и 47 и Ofkрытые cxeivttJ И 22 и 23 поступает на тактовые входы регистров 4 и 5, обеспечивая обмен информацией между этими регистрами, . Таким образом, в третьем такте ра боты устройства реализуется перестановка 012534, Кроме того, единица в регистре 33 сдвигается на один ра: ряд влево. В следующих трех тактах работы устройства реализуются последовательно перестановки 015234, 051234 и 501234. Единица в регистре 33 сдвигается влево и в шестом такте сдвигается в первый разряд регистра 33, Единичный сигнал с выхода первого разряда сдвигсцощего регистра 33 поступает на единичный вход триггера 38 управления сдвигом, триггер 38 управления сдвигом устанавливается в единичное состояние, и в регистре 33 разрешается .первый сдвиг. Кроме того, единичный сигнал с выхода первого разрядарегистра 33 через элемент ИЛИ 94 открывает элемент И 90, а также поступает на вход 72 распределителя 35 -и открывает элементы И 120, 122, Г24, 126, В седьмом такте работы устройства тактовый сиг;нал с шины 39 тактовых сигналов поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода пятого разряда регистра32 через открытый элемент ИЛИ 118 распределителя 35 сигналов, элемент ИЛИ 99 распределителя 34 сигналов поступает на выход 48, обеспечивая обмен информацией между регистрами 5 и 6, Реализуется перестановка 501243, Кроме того, тактовый сигнал с входа тактовых сигналов 39 поступает в цепь правого сдйига регистра 33, а через открытые схемы И 90 и 89- в цепь левого сдвига сдвигающего регистра 32. Единица в сдвигающем регистре 33 сдвигается на один разряд вправо, а единица в сдвигающем регистре 32 - на один разряд влево, В тридцатом такте работы устройства реализуется перестановка 540123, единица в регистре 32 находится в первом разряде этого регистра, а единица в регистре 33 сдвигается Б- первый разряд этого регистра. Единичный сигнал.с выхода первого разряда регистра 33 поступает на единичный вход триггера 38 управления сдвигом, этот триггер устанавливается в единичное состояние, и в регистре 33 разрешается правый сдвиг. Элементы И 87 и 90 открыты единичными сигналами, поступающими через элементы ИЛИ 91 и 94 соответственно с выходов первых разрядов,регистров 32 и 33. Единичные сигналы с выходов первых разрядов регистров 32 и 33 через распределители 35 поступают соответственно на входы 50 и 49 схемы распределителя 34 сигналов и открывают в ней элементы И 104, 108, 111. В тридцать первом такте работы устройства тактовый сигнал с шины 39 тактовых сигналов поступает на вход каждого из элементов И 19-24.

ЕДИНИЧНЫЙ сигнал с выхода четвертого разряда сдвиганицего регистра. 31 через элемент ,ИЛИ 113, открытый элемент ИЛИ 111, элемент ИЛИ 99 схемы распределения сигналов 34 поступает |на выход 48 этой схемы, o6ecjie4HBaH обмен информацией между регистрами 5 и 6. Реализуется перестановка 540132.

Кроме того, тактовый сигнал с шины тактовых сигналов 39 через открытые элементы И 90 и 88 поступает в цепь правого сдвига сдвигакяцего регистра 32, через открытые элементы И.90, 87 и 86 - в цепь левого сдвига сдв.игающего регистра 31, а через открытый элемент И 92 - в цепь правого сдвига сдвигающего регистра 33. Единица в сдвигающем регистре 31 сдвигается на один разряд влево, а единицы в сдвигающих разрядах 32 и 33 - на . один разряд вправо.

В семьсот девятнадцатом такте ра-, боты устройства реализуется перйстановка 102354, единицы в сдвигающих регистрах 31 и 32 находятся в последних разрядах этих регистров, а единица в сдвигающем регистре 33 сдвигается в предпоследний разряд этого регистра.

В семьсот двадцатом такте работы устройства тактовый сигнал с шины тактовых сигналов поступает на вход ка1ЖдогЬ из элементов И 19-24. Единичный сигнал с выхода предпоследнего разряда сдвигающего регистра 33 через элементы ИЛИ 118 и 99, соответственно схем распределения сигналов 35 и 34 поступает на выход 48 схемы распределения сигналов 34, обеспечивая обмен информацией между регистрами 5 и 6. Реализуется последняя перестановка 102345, а единица в сдвигающем регистре -33 сдвигается в по-следний.разряд этого регистра.

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

Известное устройство обеспечивает перечисление перестановок, но обладает существеннЕлм недостатком - низким быстродействием. Для перечисления всех Р п. перестановок требуется п тактов работы.

По сравнению с известным предлагаемое комбинаторное устройство является более быстродействующим, так как обеспечивает генерацию всех- Р п I перестановок за п . тактов работы. Так, для реализации Р 720 перестановок шести элементов предлагаемому комбинаторному устройству требуется 720 тактов работы, в то время как известному устройству требуется 46 656 тактов.

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

Комбинаторное устройство, содержащее в i-том (i 1,...,N) разряде ре- . гистр, три элемента И, элемент ИЛИ, причем выход регистра каждого разряда соединен с первым входом первого элемента И того же разряда, выход которого соединен с первым входом элемента ИЛИ, выход которого соединен с первым входом второго элемента И следующего разряда, и первым входом регистра следующего разряда, а второй вход соединен с выходом второго элемента И того же разряда, второй вход которого соединен с первым входом третьего элемента И того же разряда и вторым входом первого элемента И того же разряда, выход третьег, .элемента И каждого разряда соединён со вторым входом регистра того же разряда, отличающееся тем, что, с целью повышения быстродействия, устройство содержит () распределителя, N-3 кольцевых сдви80530210

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

говых регистров, группу элементов И, первую группу элементов ИЛИ, вторую группу элементов ИЛИ, причем первый

0 и последний выходы первого распределителя соединены с первым входом третьего элемента И соответственно первого и последнего разрядов устройства и с первыми входами соответственно первого и последнего элемен5тов ИЛИ первой группы, остальные выходы первого распределителя соединены с первыми входами соответствующих элементов ИЛИ первой группы и со вторыми входами следукицегр элемента ИЛИ

0 первой группы, выходы элементов ИЛИ первой группы соединены с первыми входами третьих элементов И соответствующих разрядов, вторые входы которых соединены между собой и являются так5товым входом устройства, входы j-того

(j lN-3) распределителя, кроме

последнего, соединены с выходами следующего распределителя и выходами i-того кольцевого регистра сдвига, входы последнего распределителя сое°

0 Динены с выходами двух последних кольцевых, регистров сдвига, управляющий вход каждого кольцевого регистра сдвига соединен с выходом соответствующего элемента И группы, первый вход ко5торого соединен с выходом следукидего элемента И группы, а второй вход соединен с выходом соответствующего элемента ИЛИ второй группы, первый и второй входы которого соединены с

0 Первым и последним выходами соответствующего кольцевого регистра.

Источники информации, принять11е во внимание при экспертизе 1. Авторское свидетельство СССР № 374606, кл. G 06 F 15/32, 1970,

2, Авторское свидетельство СССР № 446057, кл. G 06 F 7/38, 1972.