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

ю

О)

to ел

ND Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной аппарату ры. Цель изобретения - повьппение быстродействия устройства. На чертеже представлена схема устройства. Устройство содержит триггеры 1 - 6, элементы ИЛИ 7 - П, триггеры 12 17, элементы И 18 - 29, элементы ИЛИ-НЕ 30,- 38, элементы И 39-- 43, элементы 44 - 48 задержки, регистр 49 сдвига, элемент 50 задержки, пере ключатель 51, элемент 52 задержки, элемент ИЛИ 53, элементы И 54 - 59 и имеет тактовый вход 60, элемент 61коммутации, информационные выходы 62- 67, выход 68, Устройство работает по следующему принципу. Каждое очередное сочетание прлуча ется из предыдущего путем перевода m левых следующих подряд единичных разрядов в О, а первого правого нулевого разряда в I и последующег восстановления в крайних левых разрядов единиц. Если в k левых разрядах стоят нули, то осуществляется обход этих разрядов и в О переводятся m подряд следующих единичных разрядов, начиная с (l(-i-1)ro разряда а (К+1тн-1)-й разряд переводится в При этом независимо от того, с каких разрядов начинается их перевод в нулевое состояние, в единичное состояние восстанавливаются tn-l левых раз рядов. Пример формирования всех сочетаний для случая in 6 и пп 3. 1.111000 6.101010 11.110001 16.001J0 2.1101007.01101012.101001 17.10001 3.1011008.100110 13.011001 18.01001 4.011100 9.010110 14.100101 19.00101 5.110010 10.001110 15.010101 20.0001 Из приведенного примера видно, что перевод в единицу нулевого разряда, которому предшествует группа из подряд следующих единичных разрядов, происходит точно также, как в обычно двоичном счетчике. Поэтому триггеры 1 - 6 в устройстве представляют собой обычный двоичный счетчик с той лишь разницей, что на счетных входах триггеров 5-6 стоят дополнительные элементы ИЛИ. Для получения очередного сочетания перевода (гп+1)-го нулевого разряда в единицу недостаточно. Необходимо еще в ) левых разрядах восстановить единицы. Это обеспечивается триггерами 12 - 17 с элементами И 18 - 28 на выходах, элементами 30 48 и регистром 49 сдвига. Кроме того. триггеры 12 - 17 с элементами 18 28 обеспечивают обход нулевых разрядов. Элементы 54 - 59 И обеспечивают выдачу сочетаний после прекращения переходных процессов. Элементы 50 53 обеспечивают подготовку к работе триггеров 12 - 17 и регистра сдвига. Перед началом работы триггеры 1 6 по нулевым входам устанавливаются в нулевое состояние, а затем по единичньпи входам в триггеры 1 - 3 записываются единицы. После этого замыкается контакт элемента 61, в результате чего в триггеры 12 - 14 переписываются единицы из триггеров 1 - 3, а в триггеры 15 - 17 переписываются нули. Кроме того, регистр 49 устанавливается в исходное состояние, т.е. в его первый разряд записывается единица, а во все остальные - нули. Первый тактовый импульс через переключатель 51 поступает на элементы 18 и 24 и, так как триггер 12 находится в единичном состоянии, через открытьй элемент 18 поступает на счетный вход триггера 1. Б результате этого триггеры 1 - 3 последовательно перебрасываются в нулевое состояние, а триггер 4 - в единичное. При этом на элемент И 39 поступают единичные сигналы соответственно с единичного выхода триггера 12 с нулевого выхода триггера 1. Положительный перепад напряжения с выхода элемента 39, проходя через элемент 35 ИЛИ-НЕ инвертируется, и уже отрицательный проходит на вход элемента 30 ШШ-НЕ, на входе которого вновь получаем положительный перепад. На вход элемента ИЛИ-НЕ 30 через элемент 44 задержки также поступает положительный потенциал, но с определенной задержкой. До тех пор, пока на обоих входах элемента ИЛИ-НЕ 30 находятся нулевые потенциалы, на его выходе будет положительный импульс. Как

только с выхода элемента 44 задержки поступит на вход элемента 30 ШШ-НЕ единичный потенциал, на его выходе появится отрицательный перепад и положительный импульс закончится. Этот импульс передвинет единицу с первого разряда, во второй в регистре 49. Формирование импульса цепочкой элементов 3,35,39,44 и аналогичными последующими цепочками необходимо, для того, чтобы сигналы с последующих триггеров не поглотились сигналами с предыдущих триггеров, а во-вторых, чтобы с триггеров 1-6, находящихся в нулевом состоянии, на вход регистpa 49 не подавались постоянно единичные потенциалы. Так как первый и второй разряды регистра 49 не подключены, то при поступлении на него перво-ро импульса ника.ких изменений не про изойдет. Первый импульс является как бы подготовительным. При переход триггера 2 из единичного состояния в нулевое, аналогично описанному, элементы ИЛИ-НЕ 31, ИЛИ-НЕ 36, И 40 и 45 задержки.сформируют единичный импульс, который, пройдяэлементы 35 и 30, передвинет в регистре 49 единицу с второго разряда в третий. При этом, поскольку единичньш выход третьего разряда регистра 49 соединен со входом триггера 1, то он восстановится в единичное состояние. Таким же образом при переходе в нулевое состояние триггера 3 на выходе элемента ИЛИ-НЕ 32 сформируется единичный импульс, который, пройдя через элементы 36,31,35 и 30, передвинет единицу с третьего разряда в четвертый в регистре 49, и в триггере 2 восстановится единица. Таким образом, на единичных выходах триггеров 1 6 будем иметь второе сочетание 110.100. После этого первьй тактовый импульс, задержанный элементом 52, перепишет информацию из триггеров 1 6 в триггеры 12 - 17, а регистр 49 установит в исходное состояние.

Второй тактовый импульс аналогично описанному установит триггер 3 в единичное состояние, а триггеры 1 и 2 в нулевое состояние. В моменты перехода триггеров 1 и 2 из единичного в нулевое состояние будут сформированы последовательно два единичных кмпульса. Первый из этих импульсов подготовит регистр 49, т.е. продвинет единицу с первого разряда во второй.

а по второму импульсу произойдет восстановление едини11;ы в триггере 1 в результате чего получим третье сочетание 101100. Затем второй задержанный элементом 52 тактовый импульс перепищет информацию из триггеров 1 6 н триггеры 12 - 17. Третий тактовый импульс анапогичным образом сформирует на выходах триггеров 1 - 6 четвертое сочетание 011100. Теперь к моменту поступления четвертого тактового импульса триггер 12 будет находиться в нулевом состоянии, и элемент 18 И будет закрыт, а элемент И 24 открыт. Поэтому четвертый тактовый импульс не пройдет на вход триггера 1, а обойдет его и через открытый единичным потенциалом с триггера 13 элемент И 19 поступит на счетный вход триггера 2. При этом триггеры 2-4 последовательно перейдут из единичного состояния в нулевое, а триггер 5 - в единичное. На выходах элементов 31 - 33 будут последовательно сформированы единичные импульсы, которые через регистр 49 запишут единицы в триггеры 1 и 2. При этом будет сформировано пятое сочетание 110010.

Так будет продолжаться до тех пор пока все три единицы не окажутся в трех последних триггерах соответственно 4 - 6 и 15 - 17. Тогда очередной тактовый импульс поступит на счетный вход триггера 4, последовательно переведет из единичного в нулевое состояние триггеры 4 - 6 и появится на выходе элемента И 29, Появление сигнала на выходе эл. . 29 является признаком окончания перебора всех сочетаний.

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

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

Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств,предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной аппаратуры. Целью изобретения является повышение быстродействия устройства. Устройство содержит две группы триггеров, четыре группы элементов И,две группы элементов ИЛИ,группу элементов задержки,две группы элементов Ш1И-НЕ, регистр сдвига, два элемента задержки, элемент коммутации, переключатель и . с элемент ИЛИ. 1 ил.