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

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

Иллюстрации

Показать все

Реферат

 

(п)665303

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 14.04.77 (21) 2475552/18-24 с присоединением заявки № (23) Приоритет (51) М. Кл."G 06F 7/38

Государственный комитет (43) Опубликовано 30.05.79. Бюллетень № 20 (53) УДК 681.325.5 (088.8) по делам изобретений н открытий (45) Дата опубликования описания 30.05.79 (72) Авторы изобретения

В. К. Сидоренко и П. Г, Шистко (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

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

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

Недостаток этого устройства заключается в его сложности.

Наиболее близким к изобретению техническим решением является устройство для перебора сочетаний, содержащее дешифраторы, логические элементы, счетчики с коэффициентами пересчета, разнящимися на единицу, соединенные последовательно. Соответствующие выходы дешифраторов соединены с входами элементов ИЛИ, выход переноса i-го счетчика — с входом (i+1)-го счетчика и с единичным входом i-го триггера передачи, единичный выход которого связан с входом -го формирователя. Выход формирователя подключен к первому входу

i-го элемента передачи, вторые входы которого подсоединены с выходам (i+1) -го счетчика, а выходы — к установочным входам триггеров i-ro счетчика. Выход формирователя через линию задержки и элемент

ИЛИ соединен со счетным входом .i-го счетчика, нулевой выход т -ro триггера передачи — с первым входом (i — 1)-го элемента И, выход которого связан с входом установки нуля (т — 1)-го триггера передачи, а второй вход — с соответствующими входами эле5 ментов И первой группы и с выходом генератора импульсов передачи, блокирующий вход которого соединен с единичным выходом триггера. Единичный вход триггера подключен к выходу кипп-реле, вход кото1р рого связан с выходом первого формирователя импульсов передачи, счетный вход i-го счетчика через элемент ИЛИ вЂ” с выходом

i-ro элемента И, первый вход которого соединен с единичным выходом i-го триггера

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

Недостатки устройства — большое количество аппаратуры и невысокое быстродействие.

Цель изобретения — упрощение устройства и повышение быстродействия.

Поставленная цель достигается тем, что -й (i=1, ..., т) выход j-го (j=1, ..., п) кольцевого счетчика соединен с (т+1) -м входом (j — 1)-го кольцевого счетчика, первые входы всех кольцевых счетчиков явля665303

+nv

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

Техред Н. Строганова Корректор И. Позняковская

Редактор И. Грузова

Заказ 1133/12 Изд. № 334 Тираж 779 Подписное

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

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

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

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

Оно содержит и кольцевых счетчиков 1ь

1ïУстройство работает следующим образом.

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

На вход сброса подается одиночный импульс, который устанавливает счетчик с коэффициентом пересчета п в начальное состояние. На его первом выходе появляется сигал «1», который поступает на предыдущиТ; кольцевой счетчик с коэффициентом пересчета n — 1 и устанавливает его в состояние «1» на втором выходе и т. д. В результате на выходах кольцевых счетчиков с коэффициентами пересчета от п до т образуется первая выходная комбинация.

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

Таким образом, осуществляется перебор сочетаний из m по и.

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

10 Устройство для перебора сочетаний из m элементов по и, содержащее и последовательно соединенных кольцевых счетчиков, коэффициент пересчета каждого следующего счетчика на единицу меньше, чем у пре15 дыдущего, отличающееся тем, что, с целью упрощения устройства и повышения быстродействия, i-й (i = 1, ..., m) выход /-го (j=1, ..., n) кольцевого счетчика соединен с (i+1) -м входом (/ — 1) -го кольцевого счетчика, первые входы всех кольцевых счетчиков являются входами сброса кольцевых счетчиков, счетные входы кольцевых счетчиков являются входами запуска кольцевых счетчиков, выходы кольцевых счетчиков являются выходом устройства.

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

1. Авторское свидетельство СССР

¹ 525100, кл. G 06Г 15/32, 1976.

30 2. Авторское свидетельство СССР № 238238, кл. G 06F 15/32, 1970.