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

 

О П И С А Н И Е ц 576574

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнптслыгое к аьт. свпд-I3) (22) Заявлено 29.12.75 (21) 2306036!24 (51) М. Кл.- G 06Г 15 20 с присоединением заявки ¹

Совета Министров СССР по аелам изобретений и открытий

Опубликовано 15.10.77. Бюллетень № 38

Дата опубликования описания 26.10.77 (53) УДК 681.14(088.8) (72) Авторы изобретения

В. В. Епихин и А. А. Обухович (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

ГосУдаРственный комитет (23) приоритет

Изобретение относится к области вычислительной техники и может быть использовано при реализации технических средств вычислительной техники.

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

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

Наиболее близким техническим решением к данному изобретению является устройство для перебора сочетаний, содержащее блоки 15 перебора базовых сочетаний, элементы И, элементы задержки, триггер и блоки памяти, выходы которых соединены с соответствующими входами блоков перебора базовых сочетаний, выходы которых соединены с входами 20 первого элемента И, вход которого подключен к единичному входу триггера, вторые входы блоков перебора базовых сочетаний чсрез первый элемент задержки подключены к вкоду сброса блоков перебора базовык сочета- 25 ний, управляющий вход первого из которых подключен к выходу второго элемента И, первый вход которого соединен с выходом второго блока перебора базовых сочетаний, а второй вход — с его управляющим входом и с 30 выходом третьего элемента И, первый вход которого и первый вкод четвертого элемента

И подключсны к вы: оду гснсратора тактовых импульсов, а вторыс входы третьего и четвертого элементов И соединены с соотвстствующимп выкодамп триггера, нулевой выход которого подключен через второй элемент задержки к выход четвсртсго элемента И (2).

Недостатком такого устройства являстся то, что в его блоках памяти необходимо xpBHHTb все пскодныс базовые сочетания, что значительно усложняет устройство.

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

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

576574

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

Устройство для псрсоора сочетаний содерtI HT б, IOI(I 1 IIBKI5ITII, 0 0 ; t 2 IIBM511 kl, PcI IlcTры 3 сдвига, регистры 4 сдвига, элементы И

5, элементы И 6, выход 7 окон апия псреоора, блок 8 перебора базовых сочетаний, блок

9 перебора базовых сочетаний, элемент Ii 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 перебора базовых сочетаний.

Если при этом на выходе старшего разряда

ЗО

c)o

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

3 производится импульсами, проходящими с выхода регистра сдвига 4 через элементы И

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

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

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

Составитель В. Евстигнеев

Редактор Н. Каменская Техред А. Камышникова Корректор Л. Брахнина

Подписное

Заказ 2308/9 Изд. М 822 Тираж 818

НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2 выход пятого элемента И подключен к входу записи первого регистра сдвига и к выходу окончания перебора сочетаний, выход гпестого элемента И подключен к входам записи первого и второго регистров сдвига, выходы регистров сдвига подключены к соответствую1»м входам блоков памяти.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР Хо 12472, 5 кл. G 06F 15/20, 1973.

2. Авторское свидетельство СССРХв525948, кл. G 06F 7/00, 1973.