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

На чертеже приведена блок-ехема уетройства.

Устройство для перебора сочетаний содержит блоки 1 памяти, блоки 2 иамяти, регистры 3 сдвига, регистры 4 сдвига, элементы И 5, элемеиты И 6, выход 7 окоичаиия перебора, блок 8 перебора базовых сочетаний, блок 9 перебора базовых сочетаний, элемент И 10, линию задержки И, элемент И 12, линию задержки 13, триггер 14 с единичным входом 15, иулевым входом 16, нулевым выходом 17, единичным выходом 18, элемент И 19, элемент И 20, генератор 21 тактовых импульсов, Зстановочиый вход 22 устройства, установочный вход 23 регистров сдвига, третью линию 24 задержки, установочные входы 25, 26 блоков памяти.

Работа устройства основана на том, что перебор сочетаний из М элементов по N заменяется последовательным перебором двух полных базовых сочетаний и ироисходит следующим образом.

Перед началом работы производится установка устройства в исходное состояние подачей установочного сигнала на вход 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 перебора базовых сочетапий. Если при этом на выходе старшего разряда

блока 8 перебора базовых сочетаний имеется сигиал «1, то через элемент П 10 триггер 14 установнтся в исходное положение, одновременно через линию задержки 11 нроизойдет установка в нулевое положение блоков 8 и 9 перебора базовых сочетаний. Следующий импульс пр.оизводит считывание второй нары базовых сочетаний из блоков памяти 1 и 2 соответственно в блоки 8 и 9 базовых сочетаНИИ. Процесс будет повторяться до исчериания всех пар базовых сочетаний в блоках памяти 1 и 2. При этом сигнал «1 на выходе старших разрядов регистров сдвига 3 и 4 через схему П 6 пройдет на выход окончания

перебора сочетаний. Если сдвиг единицы в регистрах сдвига 4 производится тактовыми импульсами, поступающими через линию задержки 24, сдвиг единицы в регистрах сдвига 3 производится импульсами, проходящими с

выхода регистра сдвига 4 через элементы И 5 или 6,в зависимости от состояния старщего разряда регистра сдвига 3. Таким образом, положительный эффект достигается сокращением числа базовых сочетаний, хранимых в

блоках памяти, а следовательно, и уменьшением количества запоминающих регистров в них.

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

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

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

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

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

вход - к входу четвертого элемента И и к управляюп1,ему входу блоков памяти, выход второго регистра сдвига подключен к первым входам пятого и шестого элементов И, вторые входы которых соединены с прямым и инверсным выходами первого регистра сдвига, выход пятого элемента И подключен к входу записи первого регистра сдвига и к выходу окончания перебора сочетаний, выход шестого элемента И подключен к входам записи первого и второго регистров сдвига, выходы регистров сдвига подключены к соответствующим входам блоков памяти. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 12472, кл. G 06F 15/20, 1973. 2. Авторское свидетельство СССР № 525948, кл. G 06F 7/00, 1973.