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

ОПИСАНИ ЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДИЕЯЬСТВУ 238238 Союз Ссветскиз Социалистическими РеспубликЗависимое от авт. свидетельстваЗаявлено 19.1 Х.1967 ( 1184860/18-24 Кл, 42 птз, 15/32 ИП 1 х 6 061хД 1, 681.325 67(088.8) иоритет -Комитет по делам изобрвтениЯ и открытиЯ при Совете Министров СССРОпубликован 20.11.1969. Бюллетень9 ата опубликования описания 18.И 1.1969 Д ъ Т. 1 л,и три шин Авторыизобретен В абаи и Р. Вэая;витель СТР ОЙ СТВО ДЛЯ 11 ЕР ЕБОРА СОЧЕТАНИЙ присоединением заявкиПредложенное устройство относится к обласз и вычислительной техники и является составной частью машины, решающей топологицеские задачи.Известные устройства для перебора сочетаний, содержащие счетчики, дешифраторы и логические схемы, не позволяют производитьперсоор все. возможных сочетаний,Предложенное устройство отличается тем,по в нем последовательно соединены счетчики с коэффициентами пересчета, разнящимисяна единицу, соответствующие выходы дешифраторов которых соединены со входами схемИЛИ. Выход переноса 1-го счетчика соединен со,входом (1+1)-го счетчика н с сдиничным входом 1-го триггер а, передачи, единичны иВыход которого соединен со входом 1-го формирователя, Выход формирователя соединенс первым водом 1-й схемы, передачи, вторыеВходы, которой соединены с выходами (1+1)-го 20счетчика, а выходы - с установочными входами триггеров 1-го счетчика. Выход формироВателя через линию задержки и схему ИЛИсоединен со счетным входом 1-го счетчика. Нулевой выход 1-го триггера передачи соединен г 5с первым входом 1 - 1).й схемы И, выходкоторой соед 51 нсн со входом установки нуля(1 - 1)-го триггера передачи, а второй вход со.единен с соответствующими входами схем Ипервой группы и с выходом генератора импуль ссв передачи, блокнрук, ций вход которого соединен с единичным Выходом триггера. Един 111 ны 1 вход триггера сэсдпнсн с выходом кппп-реле, Вход кэтэ 1 эГО соединен с выходом Гсрвого фор 11 пэоватГля пз 111 ьсов,передаи счетный вход-го с 1 стниса через схему 1 Л 11 соединен с зыходом 1-й схе:1 ы 1, псрВый Вход которой соединен с единичным выходом 1-1 о триггера устанэвкн, а второй вход сосдинсн с соответствующими Вхсдамн Второй группы схем П н с Выходо Олэка формирования серий импульсов. Единичный вход 1-го триггера установки соединен с выходом:-н схемы П, псрвый вход которой соединен с единичным выходом ( - 1) -Го триггера устанОВки, а второй вход объсд;шсн с соответствующими входам;третьей группы схем П и через переключатель режизОв и Выходх бка формирования серий импульсов.Это позволяет Осущсств;1 ть перебор всех ВОЗЗОЖНЫХ СОЧЕТЯНИН ПЗ 111 ПО П, ЧТО РСЯЛН зуется в одноврсменном наличии сигнала на а Выходах из пт для каждсГО составня.На чертеже приведена функциональная схема предлагаемого устройства.Основнымп элсментамн устройства являютс 51 с 1 стчпки 1 - 4, 1 эличсстпо которых ряВно пщ. 1 хоэффпннснт 1 ПсРссчста счетчнкОВ 1 - 4 разнятся на единицу и умсньшякзтся от 1 тг ,ДО 1 лщ - .11 щ,к- - 1.ВыхОД кажДОГО пРсдыДУЩР.го счетчика соединен со входом последующего.Счетчики снабжены дешпфраторами состояний(на чертеже не показаны), Одинаковые разряды всех дешифраторов обьсдинены схемами11 г 1 И 5, 6, 7, сигналы которых через выходные усилители 8, 9, 10 подаются на выходныешины 11, 12, 18 устройства, колество которых равно и. 51 чсйки 14, 15, 16, подключенные к выходным шинампозволяют визуи;ьно фиксировать выходные сигналы.Триггеры управления 17, 18, 19 и схемы совпадения И 20, 21, 22 па их входах и выходахслужат для засылки в счетчики исходных данных, Засылка и илн т определяется положением тумолера 28. Серии импульсов, осуществляющие установку и и т (назовем их и-серия;: ги-серия), вырабатываотся с,помощью счетчика 24 ооратного счета, ключа 25, формирователя импульсов 26 и схемы совпадения 27,на которую заведены выходы всех триггеровсчегчпка 24. Ячейка индикации 28, подключенная к выходу схемы И 27, сигнализирует обокончании и- или т-серии,Первичные импульсы, используемые как длярешения задачи, так и для установки исходныхданных, вырабатываются генератором 29 тактовых импульсов. Тумблер 80 осуществляетподачу их в рабочую цепь или в цепь устано"к исходных данных. 1-1 ажатием кнопки 81таг, Овые Рмпульсы подотся на схему форхировапгя и- и иг-серии.11 о ходу работы усгройсгва необходимо последательно передавать сощжихОе Вышестощего с егпка в нижсстояций, -то выполняется схемами переда ги 8- - 84, управляемымп трггерачи,псредачи 85 - 87 через формирователи о 8 - 40. Выходные импульсы последних через;ини; задерхкки 41 - 48 .подаютсятакже на входы тех счетиков 1 4,;в которыеоыл передан код из вышестоящего счетчика,Выход каждого счетчика 1 4 соединенс единичным входом соответствующего триггера передачи 85 - 8/, а выход, первого счетчика,кроме того, через схему ИЛИ 44 - с триггером 45 и через кипп-реле 46 - с триггером 47управления переда ами. Кипп-реле задерживает сигнал на время, необходимое для переносов из счетчика в счетчик. Триггер 47 управляет генератором 48 импульсов передчп, пмгг;льсы с когорого через схемы И 49 и 50г)подаются на нулевые входы триггерсв 85 - У/и осущесгвляют последовательный сброс последних в порядке уменьшения их номеров, 1 гаьторой вход схем Й 49 - 50 подаегся сигналс нулевого выхода вышестоящего триггера передачи 85 - 87.Управляемый триггером 45 ключ 51 пропускает или не пропускает тактовые импульсына вход счетчика 1, Если при данном выходном сочетании образуется дерево графа, навход ответ Д поступает сигнал, и триггер45 сбрасывается в 0. Кноппкой 52 устройствозапускается вручную.Триггер 58 и дифференцпрующая цепочка 54, подключенная к первой выходноп шине,5 10 15 20 25 30 35 40 45 50 55 60 65 4осуществляют останов устройства после перебора всех сочетаний, о чем сигнализирует ячейка 55 индикации конец.Устройство работает следующим образом, Вначале все триггеры и счетчики сбрасьгваотся в нулевое положение (цепи сброса на чертеже не показаны), Тумблер Ю переключается в положение установка данных.С пульта в счетчик 24 заносится в двоичном коде число )г, Тумблер 28 переключается в,положение и, Схема 27 выдает на ключ 25 запрещающ й потенциал в том случае, если счетчпк 24 установится в нуль.Г 1 ри нажатии кнопки 81 импульсы генератора 29 подаются на ключ 25, который открыт, так как счетчик 24 содержит число )г, Формирователь 26 выдает на счетчики 1 - 4 и триггеры управления 17 - 19 импульсы. Эти же им,гульсы поступают на счетчик 24, который с приходом и-го импульса установится в 0, а схема 27 запрет ключ 25. 1 аким образом, на выходе формирователя 26 образуется серия из и юпгульсов. На счетчик 1 через схему ИЛИ 56 поступают все импульсы, и он устанавливается в состояние гг. На и-м выходе его дешифратора появляется сигнал.На счетчик 2 первый импульс и-серии не проходит, так как на схему И 57 триггер 19 выдает запрет. Первый импульс, поступающий через схему И 22, на которую заведен разрешающий потенциал с нулевого выхода триггера 19, устанавливает этот триггер в 1. Все последующие импульсы на счетчик 2 будут поступать через схему И 57 и схему ИЛИ 58. Первый импульс снимает разрешение со схемы И 22, и риггер 19 останется в ноложении . Откроется схема И 21, и второй имлу Ьс перебросит триггер 18 в 1. Импульсы, начная с третього, будут поступать на счетчик 8. Третий импульс установит в положецие 1 следующий триггер и т. д. С окончанием г-серии состояния счетчиков 1 - 4 будут отличаться на единицу.Счетчики от и1 до ц,остаются в нулеьом состоянии, и входы их закрыты, На перзых г выходах устройства имеются сигналы, образующие первое сочетание. Если т = пг , то ввод данных на этом заканчивается, если :ет, то требуется настроить счетчики по параглру и, Для этого тумблер 28 устанавливается в положение т, в счетчик 24 заносится число и - т и нажимается кнопка 81. Формируется т-серия, все импульсы которой поступают на входы первых и счетчиков, На выходах устройства происходит сдвиг первого сочетания вправо на (т , - т) разрядов. Выходы, расположенные левее полученного сочегания, в дальнейшем не используются. После этого тумблер 80 ставится в положение работа, и устройство готово к решению задачи.Нажатием кнопки 52 триггер 45 устанавливается в положение 1 и открывает ключ 51, Импульсы генератора 29 через схему ИЛИ 56 поступают на счетчик 1, на выходе начи 238238,нают просчитываться первые комбинации: 1, 2, З.п - 1, п; 1,2,3.п - 1, и+1; 1, 2,3 п - 1, и+2 и т. д, После того как образуется комбинация 1, 2, 3 и - 1, т, на выходе счетчика 1 появится импульс первноса, постулаюший на вход счетчика 2, Этот же импульс сбрасывает триггер 45 в нулевое положение и подача импульсов на счетчик 1 прекращается, Триггер передачи 37 устаНавливается в 1. С 1 ерез отрезок времени, необходимый для переносов всех счетчиков (наихудшие случаи), кипп-реле 4 б устанавливает в 1 триггер 47, который запускает генератор 48 импульсов лередачи. Его импульсы поступают на,нулевые входы всех триггеров 55 - Ы, так как схемы И 49 - 50 на их входах послс первого перенося открыты. Но в состоянии 1 находится только триггер 57, и с его выхода снимаегся импульс, воздействующий через формирователь 40 на схему передачи 34, которая передает содержимое счетчика 2 в счетчик 1. Через отрезок времени, необходимый для передачи, на схему ИЛИ 5 б из лиНии задержки 45 поступит импульс и увеличит содержимое счетчика 1 на единицу. Образуется, выходная комбинация 1, 2, 3 , и - 2, и, и+1. После этого через линию задержки 59 на триггер 45 поступит импульс и установит его в 1. Открывается ключ 51, и импульсы генератора 29 снова поступают на счетчик 1. Если возникает перенос одНоврехенино из нескольких счетчиков, то соответствующие им триггеры передаги 55 - 57 установятся в 1. Импульсы генератора 48 будут сбрасывать их .поочередно сверху вниз. Произойдет последовательная передача содержимого верхних счетчиков в нижние с добавлснием единицы в последние на каждом такте .передачи.Если даНное сочетание образует дерево графа, то на триггер 45 со входа отвод Д:поступает импульс, который устанавливает его в О. Работа устройства приостановится, и если для регистрации сочетаний, образующих деревья, используется цифр опечатаю щий механизм (ЦПМ), то запуск устройства,для дальнейшей работы осуществляется ответным импульсом ,конца печатипоступающим на вход ответ ЦМП (если регистрация производится оператором, то кнопкой 52). Счетчик бО,подсчитывает количество деревьев.После перебора всех сочетаний устройство должно остаповиться. Это осуществляется следующим образом. Последнее сочетание соответствует наличию сигнала в старших разрядах,всех задействованных счетчиков. Последующий тактовый импульс устанавливает эти счетчики в О, В результате передач, если5 10 Устройство для перебора сочстянцй, содержащее счетчики, дешцфраторь 1 ц ло ц ссИс схемы, отличающееся тем, что в нем последовяГельно соединены счет 1 ики с коэн)фиццснтами пересчета, разнящимися на единицу, соотгстствующие выходы дсшифраторов которы.; соединены со входами схем 11 Л 11, выход переноса -Го счетчика соединен со входом (+1)-го счетчика и с единичным входом -го триггера передачи, едцнц Ный выход которого соединен со входом 1-го формирователя, выход формирователя соединсц с первым входом 1-й хсмы передачи, вторые входы которой соединены с выходами (1+1)-го счетчика, Я выходы - с установочными входами триггеров 1-го счетчика, выход формирователя через линИо здсртк,кц ц схему 11111 соединен со счетным входом 1-ГО с 1 етчцка, нулевой выход 1-го триггера .передачи соединен с первым входом ( - 1)-й схемы 11, выход которой соединен со входом установки нуля ( - 1)-го триггера передачи, а второй вход соедцнсн с соответствующими входамц схем 11 первой группы и с выходом генсратора импульсов передаи, блокирующий вход которого соедцнсн с сдцниНым выходом триггера, единичный вход триггера соединен с выходом кцпп-реле, вход которого соединен с выходом первого формцрователя импульсов передачи, счетный вход -го счетчика через схему ИЛИ соединен с выходом -й схемы 11, .первый вход которой соединен с единичным выходом -ГО трцггера установки, а второй вход соединен с соответствующими входами второй группы схем И и с выходом блока формирования серий импульсов, единичный вход -Го триггера установки соединен с выходом 1-1 схемы И, первый вход которой согдцнен с сдцнц Ных выходом 1-го триггера установки, а второй вход Обьедцнен с соответствующцмц входямц третьей группы схем И ц через переключатель режимов к выходу блока формирования серий импульсов,15 20 25 30 35 40 45 50 55 были задействованы все счетчики, цлц благоДЯ 1)я нерсносу "; (и+1) -й счетчик, который дО ЭТОГО НЯХОДИЛСЯ В НУЛСВР СОСТОЯ 1 ЦИ, На ПЕР- вой выходной шине появляется сигнал. Ноторвй через дифференццруОщую ИспоНу устанавливает триггер 5 д в 1. Сигнал с его нулсвсго выхода сбрасывает триггер 45 в О, и ключ а 1 закрывается. Ячейка индикации конец, 55 связанная с триггером . Л сцгцалцзцрует О конце работы. Предмет ц зоб р етенцяСос га вп тель М. Ар шанскийРедактор Б. С, Нинкина Тсхрсд Л. Я. Левина Корректор 3, И. ЧванкиийЗаказ 144611 Тираж 480 ПодписноеНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССРй 1 оскпя, Цспгр, пр. Серова, д 4Типография, пр. Сапунова, 2