Устройство для перебора сочетаний

(51) 4 С 06 Р 15/20 ИСАНИЕ ИЗОБРЕТЕНИЯ У 54) УСТРОЙСТВО ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ 1 ВТОРСКОМУ СВИДЕТЕЛ(71) Таганрогский радиотехнический институт им, В.Д.Калмыкова (72) В,М.Глушань, М.И.Пупков, М.В,Рыбальченко и Л.И,Щербаков(56) Авторское свидетельство СССР В 643883, кл, С 06 Г 15/20, 1977.Авторское свидетельство СССР В 1008750, кл, С 06 Г 15/31, 1981,( ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ(57) Изобретение относится к вычислительной технике. Целью изобретенияявляется повьппение быстродействия исокращение оборудования. Устройствосодержит генератор тактовых импульсов, накапливающий сумматор, тригруппы элементов И, две группы элементов ИЛИ, элемент ИЛИ, три регистра, три элемента задержки и сдвигатель кодов. 2 ил.1264198 Исходным для данного случая является сочетание А = 00111. Получают45последовательность всех сочетаний,используя приведенный алгоритм,Для АЬ = О, К = 3, ,= (4),(00100), тогда А = А, + А,00111 + 000100 + 01011. Аналогичнымобразом получают все остальные сочетания=00001 А,=10110 /,=00011 А =11001а=00001 А,=11010 ,=00010 А, =11100, 5Таким образом, произведен переборвсех десяти сочетаний, причем он продолжается до тех пор, пока все единиИзобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, "."предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры.Цель изобретения - повьшение быстродействия и сокращение оборудования. 1 СНа Фиг.1 представлена Функциональная схема устройства, на Фиг.2 - схема сдвигателя.Устройство содержит регистр 1, генератор 2 тактовых импульсов, группуэлементов ИЛИ 3, элементы И 4, элементы И 5, регистр 6, регистр 7,сдвигатель 8 кодов, шиФратор , элементы И 9, группу элементов ИЛИ 10,накапливающий сумматор 11, элементы12-14 задержки, элемент ИЛИ 15, элемент ИЛИ 16, элементы И-ИЛИ 17 и 18,элементы И 19-22,В основе принципа работы устройства лежит следующий алгоритм пере- дбора сочетаний. Исходным является сочетание, в котором И единиц записаныв младших разрядах (правых), Очередное сочетание определяется по ФормулеА; = А +А ,где А , - предыдущеесочетание, а а . = 2 2 - 1, Здесь-1Ь - число подряд стоящих нулей, начиная с младшего разряда до первой единицы в ь-м сочетании, 1( - числоподряд стоящих единиц после Ь нулей35до первого очередного нуля,Рассмотрим на примере перебор сочетаний из "5" по "3". Число такихсочетаний определяется ло Формуле: и.4010,И (и - И) 1 312 цы не появляются в старших разрядах подряд.Перед началом работы в накапливающий сумматор 11 записывается исходное сочетание, т.е. единицы записываются в младшие (верхние по Схеме) разряды, а регистры 6 и 7 обнуляются. От генератора 2 единичные импульсы: поступают непосредственно на вход первого элемента И 5, вход первого элемента И 4 Если в младших разрядах регистра 1 записано Ь нулей, то пер вый тактовый импульс последовательно появляется на выходах Ь элементов И 5 и в 1, разрядах регистра 6 записаны единицы, При нахождении после Ь нулей первой же единицы распространение тактового импульса по элементам И 5 прекращается независимо от расположения единиц в следующих разрядах регистра 1. Поэтому в остальные разряды регистра 6 записаны нули. Таким образом, в регистр 6 записано двоичное число 00 111, которое в десятичной системе счисленияравно 2 -1. Причем регистр 6 должениметь иразрядов. Действительно,максимальное число подряд стоящих нулей в младших разрядах, начиная с нулевого, зависит для заданного и отвеличины М и при И = 1 оно .будетнаибольшим. Так предпоследним сочетанием из и по "1" будет сочетание01000. При этом Р = Ь = и - 2,где Р - число разряцов регистра 6.Так как следующее сочетание 1000 О -последнее и хотя цля последнего сочетания Ь = 1. = и, обработкаинформации об этом сочетании уже нетребуется,После прекращения распространениятактового импульса по элементам И 5 происходит переход этого импульса через соответствующий элемент ИЛИ 3 на элемент И 4, соединенный с единичным выходом Ь+1-го разряда регистра 1. На единичном выходе этого разряда регистра 1 - единичный потенциал. Тактовый импульс будет распространяться по элементам И 4 и записываться в соответствующие разряды регистра7 до тех пор, пока после К подрядстоящих единиц в единичных разрядахрегистра 1 не обнаружится первыйнуль, Этот нулевой потенциал на единичном выходе Ь + К + 1-го разряда регистра 6 блокирует распространениетактового импульса по всем следующимэлементам И 4. Таким образом, в регистр 7 записывается следующая комбинация нулей и единицпоо 1о,о.Максимальное число подряд стоящих единиц определяет необходимое число разрядов регистра 7 и составляет ве личину п, что в случае М = исоответствует начальному сочетанию.Для того, чтобы информацию, записанную в регистр 7, можно было преоб 1 разовать в двоичный код десятичногоК числа 2 , ее необходимо сначала сдвинуть на 1. позиций в сторону младших разрядов, а затем заблокировать К разрядов, начиная с младшего, Это20 осуществляется с помощью сдвигателя 8. Иапример, если единичный потенциал появляется на 3 и 4 выходах регистра 7, то он появляется на выходах элементов ИЛИ 16 и И-ИЛИ 17, т,е. проис-. ходит сдвиг единичных потенциалов с 3 и 4 разрядов на 1 и 2 разряды, Единичный потенциал с выхода элемента И-ИЛИ 17, поступая на инверсный вход элемента И 20, блокирует прохождение единичного потенциала с выхода эле 30 мента ИЛИ 16 на выход элемента И 20, но он проходит на выход элемента И 21, так как на его инверсный вход поступает нулевой потенциал и он открыт.35Таким образом, на выходах сдвигак теля формируется число 2 в дво-ичном коде. После того, как на выходах регистра 6 появляется число в 40двоичном коде, оно через элемент ИЛИ10 поступает на вход сумматора 11, в, котором происходит суммирование предыдущего сочетания с числом 2 -1 посигналу на синхронизирующем входе 45сумматора, 11, Этот сигнал поступаетот генератора 2 тактовых импульсов сзадержкой, равной или превышающейвремя формирования числа в регистре6, Затем через элемент 13 задержкисигнал поступает на установочный входрегистра 6 и на входы элементов И 9,Регистр 6 обнуляется, а на вход сумк.,матора 11 поступает число 2черезэлементы И 9 и ИЛИ 10. Через время,необходимое для получечия суммы (А;+К 1+ 2 - 1) + 2 = А единичныйимпульс через элемент 14 задержки обнуляе 1 регистр 7 и переписывает очередное сочетание в регистр 1.Аналогичным образом процесс продолжается до тех пор, пока не будут перебраны все возможные сочетания, Сигналом о переборе всех сочетаний является появление И единиц подряд в старших разрядах сумматора 11, что используется для формирования единичного потенциала - сигнала окончания на выходе последнего элемента И 4. Если единицы разделяет хотя бы один нуль, то сигнала окончания формирования сочетаний не будет, так как этот нуль разрывает цепь прохождения сигнала в соответствующемместе цепочки элементов И 4.Формула изобретенияУстройвтво для перебора сочетаний содержащее генератор тактовых импульсов, накапливающий сумматор, три группы элементов И, элемент ИЛИ, первую группу элементов ИЛИ, о т л и - ч а ю щ е е с я тем, что, с целью повышения быстродействия и сокращения оборудования, оно содержит три регистра, три элемента задержки, сдвига- тель кодов и вторую группу элементов ИЛИ, причем информационный вход каждого первого регистра соединен с выходом соответствующего разряда накапливающего сумматора, первые входы элементов И первой группы соединены соответственно с прямыми выходами разрядов первого регистра, вторые входы элементов И первой группы, кроме первого элемента И, соединены соответственно с выходами элементов ИЛИ первой группы, выход генератора тактовых импульсов подключен к второму входу первого элемента И первой группы и через первый элемент задержки - к входу второго элемента задержки и к первому входу элемента ИЛИ, пер - вый вход -го элемента И второй группы соединен с выходом д-го элемента И второй группы и с первым входом 3-го элемента ИЛИ первой группы (2, Зь фи 1, 1 = 1 ф 2,в п, где и - число разрядов в сочетании), второй вход 3-го элемента ИЛИ первой группы соединен с выходом 1-го элемента И первой группы (1 = 1, 2, п, 3 = 1, 2, , П), выход иго элемента И первой группы является выходом окончания цикла устроиства, 1Ь 4 1 Ч 85первый вход первого элемента И второй группы соединен с вьгходом генератора тактовых импульсов, второй вход каждого элемента И второй группы соединен с инверсным выходом соответствующего разряда первого регистра, ицйормационные входы накапливающего сумматора соединены соответственно с выходами элементов И третьей группы и с выходами элементов ИЛИ второй группы, О первые входы которых соединень соответственно с выходами разрядов второ,го регистра, а вторые входы подключены к выходам соответствующих элементов И третьей группы, первые входы 15 которьгх соединены соответственно с выходами сдвигателя, вторые входы элементов И третьей группы и установочцый вход второго регистра соединены с выходом второго элемента задержки и с входом третьего элемента задержки, выход которого подключен к установочным входам первого и третьего регистров и к второму входу элемента ИЛИ, выход которого соединен с синхронизирующим входом накапливающего сумматора, выходы разрядов третьего регистра соединены соответственно с входами сдвигателя, входы разрядов второго регистра соединены соответственно с выходами с первого по и-й элементов И второй группы, входы разрядов третьего регистра соединены. соответственно с выходами с первого по- 1 - и элементов И первой группы,1264198 Составителу, А.ЖереновТехред М.Ходанич Корректор А.Тяско Редактор И.Касарда Заказ 5564/50 Тираж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5