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

ки в нулевое состояние 14, прямым выхо дом 15 и инверсным выходом 16, элемен И 17, элемент задержки 18, распределитель 19, шину 2О тактовых импульсов, шину 21 установки и шину 22 окончания работы. Устройство работает следующим образом. Перебор сочетания из М элементов по N заменяется перебором двух сочетаний, каждое из которых в качестве исходных имеет полное базовое сочетание. Полным базовым сочетанием называется такое со четание, из которого можно получить М (включая исходное) различных сочетаний благодаря циклическому сдвигу исходного сочетания. Например, из сочетания /Л 111...11000....00 можно получить еше М-1 сочетаний благо даря его циклическому сдвигу. Базовые сочетания подбираются по опр деленным правилам. Для некоторых значе ний М и значений N (от О до N ) все б зовые сочетания будут равны: Для М 3Для М 6 000 ооооооо о 001 1ОО0001 - 1 011 20000111 111 3OOOlOll 2 001001 Для М 4 0000 оОООШЛ 0001 1ОО1011 0011Y OlOOllj OlOlJ oioioy 001111Л 0111 3 OlOlllU 4 1111 4 Oil Oil) Для М 5 011111 5 00000 О mill 6 00001 1 00011 OOlOl 001114 OlOllj 01111 4 11111 5 Для любык значений N и М двоичные базовые сочетания получают путем всех комбинаций с о ответствую ишх базовых соче таний, например, для М 6иМ 12 со ответствуют следующие базовые сочетания ( R 5, Т 7): 11ООО 1111000 11111 1ОООООО 11ООО 111010О 11110 1100ООО 11000 1110010 11110 1010000 11110 10О100О110ОО 11011ОО 111ОО 1110000110ОО 1101О10 11100 1101ООО10100 1111000 11100 110О1ОО1О100 111О10О 11100 11О001О1010О 111О01О 11100 10101ОО1О10О 1101100 1101О 11100001О100 1101010 11010 110100010000 1111100 11010 1100100 10000 иною 11010 1100010 10000 mono 11010 1010100 00000 111111О Таким образом, каждое сочетание из двенадцати по шести можно представить в виде комбинации двух базовых сочетаний (двойных базовых сочетаний). При этом исходные базовые сочетания имеют разрядность НиТ (R +Т М). Максимальное количество сочетаний, ко торое можно получить из двойного базового, равно RT (включая само двойное базовое сочетание). Порядок получения всех сочетаний из двойных базовых следующий. Сначала сдвигается циклически одно из составляющих сочетаний; если оно содер жит Т разрядов, то сдвигается (Т-1) раз, и после этого осуществляется одновременный циклический сдвиг первого и второго составляющих сочетаний. Такая процедура повторяется Н раз. Рассмотрим работу устройства на примере перебора сочетаний при М 12,N 6, Н 5иТ 7. Перед началом работы устройство устанавливают в исходное состояние по глине 20. При этом триггер 12 устанавливается в единичное состояние, распределитель 19 в первое положение, а блоки перебора 2 и 5 - в нулевое состояние. Блок перебора 2 имеет пять разрядов и первые пять выходов блока памяти 1 подключены к его входам. Блок перебора 5 имеет семь разрядов, и к его входам подключены семь последних выходов блока памяти 1. Далее по щине 20 начинают поступать тактовые импульсы. Так как перед поступлением первого тактового импульса триггер 12 находится в единичном состоянии, открыт элемент И 17, и первый тактовый импульс через элемент И 17 поступает на продвижение распределителя 19. Распределитель 19 переводится во второе положение, при этом на его первом выходе появляется импульс, который производит считывание первой строки из блока памяти 1. Содержимое первой строки из блока памяти 1 записывается в блоках перебора 2 и 5. В результате этого в блоке перебора 2 имеется базовое сочетание 11111, а в блоке перебора 5 - базовое сочетание 1000000. Блоки перебора 2 и 5 осуществл5пот циклический сдвиг их содержимого. Сигнал на управляющих входах 4 или 7 блоков перебора 2 или 5 появляется в случае, если на все разряды блока перебора поданы из блока памяти 1 все единицы или все нули, а также в том случае, если содержимое блока циклически сдвигается на величину равную разрядности блока, уменьшенную на единицу, т.е. для блока перебора 2 после четьфех сдвигов, а для блока перебора 5 - после шести сдвигов. На выходах 3 и 6 блоков перебора 2 и 5 появляются сочетания двенадцати элементов по шесть. После первого тактового импульса на выходах 3 и 6 блоков перебора 2 и 5 будет первое сочетание 1111110000ОО, Так как импульс с выхода элемента И 17 поступил на кход элемента задержки 18, перед приходом второго тактового им пульса триггер 12 находится в щлевом состоянии и открыт элемент И 11. Последующие шесть тактовых импульсо поступивших по шине 20, пройдут через элемент И 11 на продвижение блока перебо и на вход элемента И 10. Элемент И 10 открыт, если на управляюш.ем входе 7 блока перебора 5 имеется сигнал. Таким образом, по шести последующим тактовым импульсам получим следующие сочетания: Щ110100000 111110010000 111110О01000 11111000010О 111110000010 1111100ОО001 Таким образом, произошло шесть циклических сдвигов содержимого блока перебора 5. После этого на управляющем входе 7 блока перебора 5 появляется сигнач. Так как и на управляющем входе 4 блока 2 имеется сигнал, собирается элемент И 8, и по переднему фронту сигнала с его выхода перебрасывается триггер 12 в еди ничное положение и сбрасываются блоки перебора 2 и 5 в нулевое положение чере первый элемент задержки 9. Следующий т товый импульс через элемент И 17 пер ведет распределитель 19 в третье положение, и происходит считывание второй строки блока памяти 1. В результате на выходах 3 и 6 блоков перебора 2 и 5 им

ется сочетание 1111011ООООО.

60 НИИ перебора сочетаний. Триггер 12 импульсом с элемента задержки 18 перебрасывается в нулевое состояние и открывается элемент W 11. Следующие шесть тактовых импульсов поступят на продвижение блока перебора 5, в результате чего получим следующие сочетания:111100110000 1111О0011000 111100001100 111100000110 111100000011 111101000001 Так как содержимое блока перебора 5 сдвигалось шесть раз, на управляющем входе 7 появляется сигнал, который откры-вает элемент И 10. Следующий тактовый импульс осуществит циклический сдвиг содержимого блока перебора 2 и содержимого блока перебора 5. При этом на управляющем кходе 7 блока перебора 5 пропадает сигнал и сдвиг этим тактовым импульсом не входит в подсчет импульсов сдвига для выдачи сигнала на управляющем входе 7. В результате получаем очередное сочетание 011111100ООО. Последующие шесть тактовых имщ льсов поступят на продвижение только блока перебора 5 и в результате получим еще шесть из двенадцати по шесть: 011110110000 011110011000 011110001100 011110000110 011110000011 011110000001 Далее опять происходит одновременный циклический сдвиг содержимого блоков перебора 2 и 5 при поступлении очередного тактового импульса. Последующие шесть тактовых импульсов циклически сдвигают только содержимое блока перебора 5 и т.д. до тех пор, пока на управляющих входах 4 и 7 одновременно появятся сигналы. После этого происходит сброс содержимого блоков перебора 2 и 5 и очередной так- товый импульс, поступивший по шине 20, продвинет распределитель 19 в следующее положение и произойдет считывание очередной строки блока памяти 1 в блоки перебора 2 и 5. Далее опять продолжается ия лический сдвиг содержимого блоков перебора 2 и 5. Этот процесс повторяется до тех пор, пока не будут считаны все строки блока памяти 1 и на шине 22 (последний выход распределителя 19) не появится импульс, сигнализирующий об окончаФормула и зобретения

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

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

21 о