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

Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, -г предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной и вычи слительной аппаратуры. Цель изобретения - повьш1ение быст родействия и сокращение оборудования На фиг.1 представлена функциональ ная схема устройства, на фиг.2 - схе ма сдвигателя. Устройство содержит регистр 1, .ге нератор 2 тактовых импульсов, группу элементов ИЛИ 3 элементы И 4, элементы И 5, регистр 6, регистр 7, сдвигатель 8 кодов, шифратор , элементы И 9, группу элементов Ш1И 10, накапливающий сумматор 11, элементы 12-14 задержки, элемент ИЛИ IS, элемент ИЛИ 16, элементы И-ИЛИ 17 и 18., элементы И 19-22. В основе принципа работы устройства лежит следующий алгоритм перебора сочетаний. Исходным двляется со четание, в котором N единиц записаны в младших разрядах (правых). Очередное сочетание определяется по формул А А . +л. где А. - предыдущее I -1 1-1 сочетание, аД . . Здесь L - число подряд стоящих нулей, начи ная с младшего разряда до первой-еди ницы в i-t-M сочетании, К - число подряд стоящих едитшц после L нулей :до первого очередного нуля. Рассмотрим на примере перебор сочетаний из 5 по 3. Число таких г сочетаний определяется по формуле: N(п - N) Исходным для данного случая является сочетание А 00111. Получают последовательность всех сочетаний, используя приведенный алгоритм. Для А L О, К 3, Д, (4), (00100), тогда А , А, +Л, 00111 + 000100 + 01011. Аналогичным образом получают все остальные сочетанияЛ,,00010 А,,01101 Д,00001 А 01110 Д,00101 Ад 10011 д 00010 А 10101 Л 00001 А,10110 Л,00011 А 11001 ,00001 А П010 л„ 00010 А 11100 J10 Таким образом, произведен перебор всех десяти сочетаний, причем он продолжается до тех пор, пока все единицы не появляются в старших разрядах подряд. Перед началом работы в накапливающий сумматор 11 записывается исходное сочетание, т„е. единицы записываются в младшие (верхние по схеме) разряды, а регистры 6 и 7 обнуляются. От генератора 2 единичные ш {пульсы . поступают непосредственно на вход первого элемента И 5, вход первого элемента И 4„ Если в младших разрядах регистра 1 записано L нулей, то пёр- вый тактовый импульс последовательно появляется на выходах L элементов И 5 и в L разрядах регистра 6 записаны единицы. При нахождении после L нулей первой же единицы распространение тактового импульса по элементам И 5 прекращается независимо от расположения единиц в следующих разрядах регистра 1 о Поэтому в остальные разряды регистра 6 записаны нули. Таким образом, в регистр 6 записано двоичное число 0,..ОП..,1, кото- . рое в десятичной системе счисления равно 2 -1, Причем регистр 6 должен иметь п-2 разрядов. Действительно, максимальное число подряд стоящих нулей в младших разрядах, начиная с нулевого, зависит для заданного п от величины N и при N 1 оно -будет наибольшим. Так предпоследним сочетанием из п по 1 будет сочетание 0100...0. При этом Р L п - 2, где Р - число разрядов регистра 6. Так как следующее сочетание 1000../)последнее и хотя для Последнего сочетания L Ь„ 0-1, обработка информации об этом сочетании уже не требуется. После прекра1цения распространения тактового импульса по элементам И 5 происходит переход этого импульса через соответствующий элемент ИЛИ 3 на элемент И 4, соединенный с единичным выходом L+1-го разряда регистра На единичном выходе этого разряда регистра 1 - единичный потенциал. Тактовый импульс будет распространяться по элементам И 4 и записываться в соответствующие разряды регистра 7 до тех пор, пока после К подряд стоящих единиц в единичных разрядах регистра 1 не обнаружится первьш нуль. Этот нулевой потенциал на единичном выходе L +К + 1-го разряда регистра 6 блокирует распространение тактового импульса по всем следующем элементам И 4. Таким образом, в регистр 7 записывается следующая комбинация нулей и единиц 0. ..011..1.р.дЖ ПГ Максимальное число подряд стоящих единиц определяет необходимое число разрядов регистра 7 и составляет величину п-1, что в случае N п-1 соответствует начальному сочетанию. Для того, чтобы информацию, записанную в регистр 7, можно было преоб Ьазовать в двоичный код десятичного числа 2 , ее необходимо сначала сдвинуть на L позиций в сторону млад ших разрядов, а затем заблокировать К-1 разрядов, начиная с младшего. Эт осуществляется с помощью сдвигателя 8. Например, если единичный потенциа появляется на 3 и 4 выходах регистра 7, то он появляется на выходах элементов ИЛИ 16 и И-ИЛИ 17, т.е. проис ходит сдвиг единичных потенциалов с 3 и 4 разрядов на 1 и 2 разряды. Еди ничный потенциал с выхода элемента И-ИЛИ 17, поступая на инверсный вход элемента И 20, блокирует прохождение единичного потенциала с выхода элемента ИЛИ 16 на выход элемента И 20, но он проходит на выход элемента И 21, так как на его инверсный вход поступает нулевой потенциал и он открыт . Таким образом, на выходах сдвигателя формируется число 2 в дво.ичном коде. После того, как на выходах регистра 6 появляется число в двоичном коде, оно через элемент ИЛИ 10 поступает на вход сумматора 11, в котором происходит суммирование предьщущего сочетания с числом 2 -1 по сигналу на синхронизирующем входе сумматора 11. Этот сигнал поступает от генератора 2 тактовых импульсов с задержкой, равной или превышаюп1ей время формирования числа в регистре 6. Затем через элемент 13 задержки сигнал поступает на установочный вход регистра 6 и на входы элементов И 9, Регистр 6 обнуляется, а на вход сумматора 11 поступает число 2 через элементы И 9 и ИЛИ 10. Через время, необходимое для получения суммы (А; + 2 -1)-ь2 А.|, единичный импульс через элемент 14 задержки об нyляe r регистр 7 и переписывает очередное сочетание в регистр 1. Аналогичным образом процесс продолжается до тех пор, пока не будут перебраны все возможные сочетания. Сигналом о переборе всех сочетаний является появление N единиц подряд в старших разрядах сумматора 11, что используется для формирования единичного потенциала - сигнала окончания на выходе последнего элемента И 4. Если единицы разделяет хотя бы один нуль, то сигнала окончания формирования сочетаний не будет, так как этот куль разрывает цепь прохождения сигнала в соответствующемместе цепочки элементов И 4. Формула изобретения Устройвтво для перебора сочетаний содержащее генератор тактовых импульсов, накапливающий сумматор, три группы элементов И, элемент ИЛИ, первую группу элементов ИЛИ, отличающееся тем, что, с целью повьпцения быстродействия и сокращения оборудования, оно содержит три регистра, три элемента задержки, сдвигатель кодов и вторую группу элементов ИЛИ, причем информационный вход каждого первого регистра соединен с выходом соответствующего разряда накапливающего сумматора, первые входы элементов И первой группы соединены соответственно с прямыми выходами разрядов первого регистра, вторые входы элементов И первой группы, кроме nepfeqro элемента И, соединены соответственно с выходами элементов ИЛИ первой группы, выход генератора тактовых импульсов подключен к второму входу первого элемента И первой группы и через первый элемент задержки к входу второго элемента задержки и к первому входу элемента ИЛИ, пер- вый вход i-ro элемента И второй группы соединен с выходом i-1-го элемента И второй группы и с первым входом j-ro элемента ИЛИ первой группы (i 2, 3, ..., п-1, 1 1, 2, ..., п-1, где п - число разрядов в сочетании), второй вход j-ro элемента 1-ШИ первой группы соединен с выходом i-ro элемента И первой группы (i 1, 2, ..., п-1, j 1, 2, ..., п-1), выход пго элемента И первой группы является вьгходом окончания цикла устройстпа.

InepBt.iH вход первого элемента И второй группы соединен с выходом генератора тактопьгх импульсов, второй вход каждого элемента И второй группы соединен с инверсным выходом соответствующего разряда первого регистра, информационные входы накапливающего сумматора соединены соответственно с выходами элементов И третьей группы и с выходами элементов ИЛИ второй группы, первые входы которых соединены соответственно с выходами разрядов второ, го регистра, а вторые входы подключены к выходам соответствующих элементов И третьей группы, первые входы которых соединены соответственно с выходами сдвигателя, вторые входы элементов И третьей группы и установочный вход второго регистра соединены с выходом второго элемента задержки и с входом третьего элемента задержки, выход которого подключен к установочным входам первого и третьего регистров и к второму входу элемента И.ПИ, выход которого соединен с синхронизирующим входом накапливающего сумматора, выходы разрядов третьего регистра соединены соответственно с входами сдвигателя, входы разрядов второго регистра соединены соответственно с выходами с первого по n-2-й элементов И второй группы, входы разрядов третьего регистра соединены, соответственно с выходами с первого по ь-1 - и элементов И первой группы.

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