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

Республик АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 61) Дополнптслы ое к т. свпд-ву 22) Заявлено 29.12.75 (21) 23060362 с присоединением заявки Ье51) М Кл 06 Г 1512 Государственный комнте Совета Министров СССР по аелам изобретений риоритет юллетень М 3 публиковано 15,10.7(53) УДК 681.14(088,8) ткрытни ата опубликования описания 26.10.77 Авторыизобретени В, В. Епихин и А. А. Обухови 71) Заявител 54) УСТРОЙСТВО ПЕРЕБОРА СОЧ Й Изооретение относится к области вычислительной техники и может быть использовано при реализации технических средств вычислительной техники.Известно устройство для перебора сочетаний (1), которое содержит блок памяти, блоки перебора базовых сочетаний, кольцевые регистры, распределитель, счетчик, элементы И, линии задержки и логические схемы, 1.1 едостатком этого устройства являстся то, что в его памяти необходимо хранить большое число базовых сочетаний.Наиболее близким техническим рсшением к данному изобретению является устройство для перебора сочетаний, содержащее блоки перебора базовых сочетаний, элементы И, элементы задержки, триггер и блоки памяти, выходы которых соединены с соответствующими входами блоков перебора базовых сочетаний, выходы которых соединены с входами первого элемента И, вход которого подключен к единичному входу триггера, вторые вкоды блоков перебора базовых сочетаний чсрез первый элемент задержки подключены к вкоду сброса блоков перебора базовык сочетаний, управляющий вход первого из которых подключен к выходу второго элемента И, первый вход которого соединен с выходом второго блока перебора базовых сочетаний, а второй вход - с его управляющим входом и с выходом третьего элемента И, первый вход которого и первый вкод четвертого элемента И подключсны к выходу гснсратора тактовых импульсов, а вторыс входы третьего и чет всртого элементов И соединены с соотвстствующимп выкодамп триггера, нулевой выход которого подключен через второй элемент задержки к выход четвсртсго элемента И (2).Недостатком такого устройства являстся то, 10 что в его блоках памяти необходимо крапитьвсе пскодныс базовые сочетания, что значительно усложняет устройство.С целью уменьшения объема оборудованияв предлагаемое устройство дополнительно 15 введены регистры сдвига, элементы И и линия задержки, выкод которой подключен к управляющему входу второго регистра сдвига, а вкод - к входу четвертого элемента 11 и к управляющему вкоду блоков памяти, вы код второго регистра сдвига подключен кпервым входам пятого и шестого элементов И, вторые вкоды которы.; соединены с прямым и инверсным выкодамп первого рсгпстра сдвига, вход пятого элемента И подключен к 25 входу записи первого регистра сдвига и к выкоду окончания перебора сочетаний, выход шестого элемента И подключен и входам записи первого и второго регистров сдвига, выходы регистров сдвига подключены к соответ ствующпм входам олока памяти,10 15 20 25 На чсртсжс приведена блок-схема устройства.Устройство для псрсоора сочетаний содержит олокп 1 памяти, олокп 2 памяти, регистры 3 сдвига, регистры 4 сдвига, элементы И 5, элементы И 6, выход 7 окончания псреоора, блок 8 перебора базовых сочста)ий, блок 9 перебора базовых сочетаний, элемент И 10, линию задержки 11, элемент И 12, линию задержки 13, триггер 14 с единичным входом 15, нулевым входом 16, нулевым выходом 17, единичным выходом 18, элемент И 19, элемент И 20, гс)ератор 21 тактовых импульсов, уста)овочпый вход 22 устройства, установочный вход 23 регистров сдвига, третью линию 24 задержки, установочные входы 25, 26 олоков памяти.Работа устройства основана па том, что перебор сочетаний из М элементов по Ж заменяется последовательным перебором двух полных базовых сочетаний и происходит следующим образом.Перед началом работы производится установка устройства в исходное состояние подачей установочного сигнала на вход 22, При этом блоки перебора базовых сочетаний 8 и 9 устанавливаются в нулевое положение, триггер 14 - в единичное. Через вход 23 в первые разряды регистров сдвига 3 и 4 заносятся единицы, через входы 25 и 26 в блоки памяти 1 и 2 соответственно заносятся исходные базовые сочетания, После этого генератор 21 выдает на элементы И 19 и 20 тактовые импульсы. Псрвый тактовый импульс через элемент И 20 производит считывание первой пары базовых сочетаний из блоков памяти 1 и 2 в блоки перебора базовых сочетаний 8 и 9 соответственно. Сигнал 1 на выходе первых разрядов регистров сдвига 1 и 2 является разрешающим для считывания базовых сочетаний из блоков памяти 1 и 2 в регистры. Пройдя линию задержки 24, первый тактовый импульс поступает на управляющий вход регистра сдвига 4 и продвигает единицу во второп разряд. Одновременно через линию задержки 13 триггер 14 устанавливается в нулевое состояние, открывая по одному из входов элемент И 19,Следующий тактовый импульс через элемент И 19 поступает на вход блока псребора 9 базисных сочетаний и осуществляет циклический сдвиг его содержимого на один разряд. В результате на выходах блоков перебора 8 и 9 базисных сочетаний имеется очередное сочетанис, Последующие тактовые импульсы продвигают единицу по всем разрядам блока перебора 9 базисных сочетаний вплоть до старшего. При этом каждый раз будет получаться новос сочетание. Появление 1 на выходе старшего разряда регистра 9 подготовит элемент И 12 к открытшо, и следующий тактовый импульс поступит па вход блока 9 и через элементы И 19 и 12 - па вход блока 8 перебора базовых сочетаний. Если при этом на выходе старшего разряда ЗО 35 40 45 50 55 бо 65 блока 8 псребора базовых сочетаний имеется сигнал 1, то через элемент И 10 триггер 14 установится в исходное положение, одновременно через линию задержки 11 произойдет установка в пулевое положение блоков 8 и 9 псрсбора базовых сочетаний. Следующий импульс производит считывание второй пары базовых сочетаний из блоков памяти 1 и 2 соответственно в блоки 8 и 9 базовых сочетаний, Процесс будет повторяться до исчерпания всех пар базовых сочетаний в блоках памяти 1 и 2. При этом сигнал 1 на выходе старших разрядов регистров сдвига 3 и 4 черсз схему И 6 пройдет на выход окончания перебора сочетаний. Если сдвиг единицы в рсгистрах сдвига 4 производится тактовыми импульсами, поступающими через линию задсржки 24, сдвиг единицы в регистрах сдвига 3 производится импульсами, проходящими с выхода регистра сдвига 4 через элементы И 5 или 6,в зависимости от состояния старшего разряда регистра сдвига 3. Таким образом, положительный эффект достигается сокращением числа базовых сочетаний, хранимых в блоках памяти, а следовательно, и уменьшением количества запоминающих регистров в пих. Формула изобретенияУстройство для перебора сочетаний, содержащее блоки перебора базовых сочетаний, элементы И, элемснты задержки, триггер и блоки памяти, выходы которых соединены с соответствующими входами блоков перебора базовых сочетаний, выходы которых соединены с входами первого элемента И, выход которого подключен к единичному входу триггера, вторые входы блоков перебора базовых сочетаний через первый элемент задержки подключены к входу сброса блоков перебора базовых сочетаний, управляющий вход первого из которых подключен к выходу второго элемента И, первый вход которого соединен с выходом второго блока перебора базовых сочетаний, а второй вход - с его управляющим входом и с выходом третьего элемента И, первый вход которого и первый вход четвертого элемента И подключены к выходу генератора тактовых импульсов, а вторые входы третьего и четвертого элементов И соединены с соответствующими выходами триггера, нулевой выход которого подключен через второй элемент задержки к выходу четвертого элемента И, о т л и ч а ю щ ееся тем, что, с целью уменьшения объема оборудования, в него дополнительно введены рсгистры сдвига, элементы И и линия задсржки, выход которой подключен к управляющему входу второго регистра сдвига, а вход - к входу четвертого элемента И и к управляющему входу блоков памяти, выход второго регистра сдвига подключен к первым входам пятого и шестого элементов И, вторые входы которых соединсны с прямым и инвсрсным выходами первого регистра сдвига,Подписное Заказ 2308/9 Изд, Мо 822 Тираж 818 НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Типография, пр, Сапунова, 2 выход пятого элемента И подключен к входу записи первого регистра сдвига и к выходу окончания перебора сочетаний, выход шестого элемента И подключен к входам записи первого и второго регистров сдвига, выходы регистров сдвига подключены к соответствующим входам блоков памяти,Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР Мв 12472,5 кл. 6 06 Р 15/20, 1973. 2. Авторское свидетельство СССРМв 525948, кл. 6 06 Г 7/00, 1973.