УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ Советский патент 1969 года по МПК G06F15/31 

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

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

Предложенное устройство отличается тем, что в нем Последовательно соединены счетчики с коэффициентами пересчета, разнящимися ,на единицу, соответствующие выходы дешифраторов которых соединены -со входами схем чИЛИ. Выход переноса i-ro счетчика соединен со входом (/+1)-го счетчика и с единичным ВХОДОМ /-ГО триггера .передачи, единичный выход которого соединен со входом /-го формирователя. Выход формирователя соединен с первым входом (-и схемы передачи, вторые оходьькоторой соединены с выходами (/-|-1)-го счетчика, а выходы - с установочными входами триггеров /-ГО счетчика. Выход формирователя через линию .задержки и схему «ИЛП соединен со счетным вхо.дом i-ro счетчика. Нулевой выход /-ГО триггера передачи соединен с пер.вым ВХОДОМ ()-й схемы «И, выход Которой соединен со входом установки нуля (/-1)-го триггера передачи, а второй вхо.д соЬдияен с соответствующими входами схем «И Первой груплы и с выходом генератора импульсов передачи, блокируюЦий вход которого соединен с единичным вы.ходом триггера. Единичный вход триггера Соединен с выходо.м кипп-реле, вход которого соединен с выходом первого формирователя 1 маульсов передачи, счетный вход /-ГО счетчика через схему «ПЛМ соединен с выходо.м /-и схемы «И, .первый вход которой с единичным выходом /-10 триггера установк), а второй вход соединен с соответствующими входами второй группы схем «И и с выходом блока формирования серий импульсов. Единичный вход /-го триггера установки соединен с выходо.м /-и схемы «П. первый вход которой соединен с единичным выxoдo i (/-1)-го триггера установки, а второй вход объединен с соответствующими входа.ми третьей групны схем «II и через переключатель режи.мов к выходу блока формирования серий импульсов.

Это позволяет осуществить перебор всех воз.можных сочетаний из т .по /г, что реализуется в oднoвpe.мeннo i нал.ччии сигнала на п выходах из п для каждого сочетания.

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

Основньпп: эле.ментами устройства являются счетчики }-4, колигестьо которы.х равно ms-x. Коэффиписнты псресчста счетчиков 1-4 разнятся на и уменьшаются от т . до ;п„,,,.,х + 1-Выход предыдущрго счетчика соединен со входом последующего. Счетчики снабжены дешифраторами состояний (на чертеже не по.казаны). Одинаковые разряды всех дешифраторов объединены схемами «ИЛИ 5, 6, 7, сигналы которых через выходные усилители S, 9, 10 подаются на выходные швны 11, 12, 13 устройства, количество которых равно тц,х.|. Ячейки i4, 15, 16, подключенные к выходным шинам, позволяют визуально фиксировать выходные сигналы.

Триггеры управления 17, 18, 19 и схемы совпадения «И 20, 21, 22 ла их входах и выходах слунсат для засылки в счетчики исходных данных. Засылка п или т о.иределяется положением тумблера 23. Серии импульсов, осуш,еств.чяющие установку п и т (назовем их я-серия и ш-серия), выра1батываются с ломош,ью счетчька z4 обратного счета, ключа 25, формирователя импульсов 26 и схемы совпадения 27, на которую заведены выходы всех триггеров счегчика 24. Ячейка индикации 28, подключенная к выходу схемы «И 27, сигнализирует об окончании п- или т-серии.

Первичные импульсы, используе1мые как для решения задачи, так и для установки исходных данных, вырабатываются генератором 29 тактовых нмпульсов. Тумблер 30 осуш,ест:вляет подачу их в рабочую цепь или в цепь устаноски 1 сходных данных. НажатиелМ киол-ки 31 та чговые импульсы подаются на схему формирсуваиия я- и /7г-серии.

Но ходу работы устройства необходимо последч зательно передавать содержимое вышестоящего счетчика в нижестоящий, что выполняется схемами персаачи 32-34, управляемыми триггерами лередачи 35-37 через формирователи о8-40. Выходные импульсы последних через ЛИ1НИИ задерн ки 41-43 лодаются также на входы тех счетчиков /-4, в которые был передан код из вышестоящего счетчика.

Выход каждого счетчика /-4 соединен с единичным входом соответствующего триггера передачи , а выход лервого счетчика, кроме тото, через схему «ИЛИ 44 - е триггером 45 и через кипп-реле 46 - с триггером 47 управления передачами. Кипи-реле задерживает сигнал на время, необходимое для переносов из счетчика в счетчик. Триггер 47 управляет генератором 48 импульсов передачи, импульсы с которого Через схемы «И 49 и 56 Г1одаютея на нулевые входы триггеров 35-37 и осуществляют последовательный сброс последних В порядке уменьшения их нолгеров. На второй вход схем «И 49-50 подается сигнал с нулевого выхода вышестоящего триггера передачи 35-37.

Упр..1вляемый триггером 45 ключ 51 пропускает или не пропускает тактовые импульсы на вход счетчика L Если при данном выходном сочетании образуется дерево графа, на вход «ответ Д поступает сигнал, и триггер 45 сбрасывается в «О. 52 устройство запускается вручную.

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

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

Вначале все триггеры и счетчики сбрасываются в нулевое иоложение (цепи сброса на чертеже «е показаны). Тумблер 30 переключается в Положение «установка данных. С пульта в счетчик 24 заносится в двоичном коде число п. Тумблер 23 переключается в положение п. Схема 27 выдает на ключ 25 запрещающий потенциал в том случае, если счетчик 24 установится В нуль.

При нажатии кнопки 31 импульсы генератора 29 подаются на клЮЧ 25, который открыт, так как счетчик 24 содержит число п. Формирователь 26 выдает на счетчики /-4 и триггеры управления 17-19 импульсы. Эти же импульсы поступают на счетчик 24, который с приходом п-го импульса установится в «О, а схема 27 запрет ключ 25. Таким образом, на выходе формирователя 26 образуется серия из п импульсов. На счетчик 1 через схему «ИЛИ 56 поступают все импульсы, и он устанавливается в состояние п. Иа я-м выходе его дешифратора появляется сигнал.

На счетчик 2 первый импульс п-серии не проходит, так как на схему «И 57 триггер 19 выдает запрет. Первый импульс, поступающий через схему «И 22, на которую заведен разрешающий потенциал с нулевого выхода триггера 19, устанавливает этот триггер в «1. Все последующие импульсы на счетчик 2 будут поступать через схему «И 57 и схему «ИЛИ 58. Иервый импульс снимает разрешение со схемы «И 22, и триггер 19 останется в положении «1. Откроется схема «И 21, и второй импу.1ьс пе;ребросит триггер 18 в «1. Импульсы, начиная с третьего., будут поступать на счетчик 5. Третий импульс установит в положение «1 следующий триггер и т. д. С окончанием /г-серии состояния счетчиков 1-4 будут отличаться на единицу.

Счетчики от я-f 1 до п„., остаются в нулевом состоянии, и входы их закрыты. На первых п выходах устройства имеются сигналы, образующие первое сочетание. Если tn m,,, то ввод данных на этом заканчивается, если 1;ет, то требуется настроить счетчики по пара eтpy т. Для этого тумблер 23 устанавливается в положение т, в счетчик 24 заносится число т,„.|х-/п и нажимается кнопка 31. Формируется / г-серия, все импульсы которой поступают на входы первых п счетчиков. На выходах устройства происходит сдвиг первого сочетания ВПраво на (и разрядов. Выходы, расположенные левее полученного сочетания, в дальнейшем не используются. После этого тумблер 30 ставится в положение «работа, и устройство готово к решению задачи.

Нажатием кнопки 52 триггер 45 устанавливается в положение «Ь и открывает ключ 51. Импульсы генератора 29 через схему «ИЛИ 55 поступают на счетчик /, на выходе начи«ают просчитываться первые комбинации: 1, 2, 3 ... /г-1, п; 1, 2, 3 ... п-1, 1, 2, 3 ... п-1, и т. д. После того как образуется комбинация 1, 2, З...П-1, т, на выходе счетчика 1 появится импульс переноса, постулаюший на вход счетчика 2. Этот же импульс сбрасывает триггер 45 в нулевое положение и подача импульсов на счетчик 1 прекращается. Триггер передзчи 37 устанавливается в «1. Через отрезок времени, необходимый для переносов ВСех счетчиков (наихудшие случаи), кипп-реле 46 устанавливает в «1 триггер 47, который запускает генератор 48 импульсов передачи. Его импульсы поступают на нулевые ВХОДЫ всех триггеров 35-37, так как Схемы «И 49-50 на их входах после первого переноса открыты. Но в состоянии «1 находится только триггер 37, и с его выхода снимаегся импульс, воздействующий через формирователь 40 на схему передачи 34, которая передает содержимое счетчика 2 в счетчик 1. Через отрезок времени, необходимый для передачи, на схему «1-1ЛИ 56 из лииии задержки 43 поступит импульс и увеличит содержимое счетчнка 1 на единицу. Образуется .выходпая комбинация 1, 2, 3 ... п-2, п, . После этого через линию задержки 59 на триггер 45 поступит импульс и установит его в «1. Открывается ключ 51, и импульсы генератора 29 снова поступают на счетчик /. Если возникает перенос одновременно из нескольких счетчиков, то соответствующие им триггеры передачи 35-37 установятся в «1. Импульсы -генератора 48 будут сбрасывать их поочередно сверху вниз. Произойдет последовательная передача содержимого верхних счетчиков в нижние с добавлением единицы в последние на каждом такте передачи.

Если данное сочетание образует дерево графа, то на триггер 45 со входа «отвод Д поступает импульс, который устанавливает его в «О. Работа устройства приостановится, .и если для регистрации сочетаний, образующих деревья, используется цифропечатающий механизм (ЦПМ), то запуск устройства для дальнейшей работы осуществляется ответным импульсом конца печати, поступающим на вход «ответ ЦМП (если регистрация производится оператором, то кнопкой 52). Счетчик 60 подсчитывает количество деревьев.

После перебора всех сочетаний устройство должно остановиться. Это осуществляется следующим образом. Последнее сочетание соответствует наличию сигнала в старших разрядах всех задействованных счетчиков. Последующий тактовый импульс устанавливает эти счетчики в «О. В результате передач, если

были задействованы все счетчики, или олагодаря перенесу G («+1)-й счетчик, который до этого находился в нулевом состоянии, на первой выходной шине появ.ьяется ег.гна;. которви через дифференцирующую цепочку устаИЕВливает триггер 53 в «1. Сигнал с его нулезсго выхода сбрасывает триггер 45 в «О, и ключ 5/ закрывается. Ячейка индикации «конец, 55 связанная е триггером 3 снгнализирует о конце работы.

Предмет изобретения

Устройство для перебора сочетаний, содержащее счетчики, дешифраторы и логические схемы, отличающееся тем, чю в нем лоследозательно соединены счетчики с коэффициентами пересчета, разнящимися на единицу, соответствующие выходы дешифраторов которых соединены со входами схем «ИЛИ, выход переноса /-го счетчика соединен со входом (/-j-l)-ro счетчика и с единичным входом i-ro триггера передачи, единичный выход которого

соединен со входом i-ro формирователя, выход формирователя соедине.; с первым входом /-и схемы передачи, вторые входы KOTopoii соединены с выходами (J-j-l)-ro счетчика, а выходы-с установочными входами триггеров i-ro

счетчика, выход формирователя через линию задерж.ки и схему «ИЛИ соединен со счетным входом /-ГО счетчика, нулевай выход г-го триггера передачи соединен с первым входом (i-1)-й схемы «И, выход которой соединен

со входом установки нуля (/-1)-го триггера передачи, а второй вход соединен с соответствующими входами схем «И первой группы г, с выходом генератора импульсов передами, блокирующий вход которого соединен с единичным выходом триггера, единичный вход триггера соединен с выходом кипп-реле, вход которого соединен с выходом первого формирователя импульсов передач, счетный вход I-ro счетчика через схему «ИЛИ соединен

с выходом г-й схемы «И, первый в.ход которой соединен с единичным выходом /-го триггера установки, а второй вход соединен е соответствующими входами второй группы схем «И и с выходол блока формирования серий импульсов, единичный вход i-ro триггера установки соединен с выходом /-и схемы «П, первый вход которой соединен с единичным выходом i-ro триггера установки, а второй вход объединен с соответствующими входами

третьей группы схем «И и через переключатель к выходу блока формирования серий импульсов.

/ifleflSu/M pajflgjffi oc/nffffi/fiB/K cvefnwf of