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

.А.Чихладзе, В.А.Богатыре Й Л рузинский орд политехниче 1) Заявите а Ленина ий инсти(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ЕНИЙ т быть тройе за х одо циональящего гаемомуетсяинений,где т 1первыйруппусчетчиго, соетчика,чен кт 1 запоми- торую е 30 Устройство относится к ци вычислительной технике и мож применено в вычислительных у ствах, решающих комбинаторнь дачи.Известен метод перебора т соединений, как перестановка на ЭВИ 1 11,Однако это связано с нера ным использованием дорогосто машинного времени.Наиболее близкое к предла по техническому решению явля устройство для перебора соед содержащее (п) счетчиков, число переставляемых кодов, и второй элемент И, первую г элементов ИЛИ, элемент задер при этом выход переноса т -го ка (12 и), кроме последне единен со входом (1+1)-го сч вход первого счетчика подклю выходу первого элемента И, нающих элементов, первую и.в рдена Трудового КрасногоЯним, В.И.Ленина группы элементов И, причем входызапоминающих элементов подключены квыходам элементов И первой группы, первый вход первого элемента И которой подключен квыходам элементов И второй группы,первые входы остальных элементов Ипервой группы подключены к выходам(1-1) -го запоминающего элемента, вы- Оходы запоминаицих элементов начиУная со второго, подключены к первым входам элементов .И второй группы 1 21.Недостатком этого устройства яв" 3ляется невозможность реализации перестановки кодов.Цель изобретения - расширениекласса решаемых задач за счет возможности перебора всевозможных п ре"становок кодов.Укаэанная цель достигается тем,что в устройство для перебора соединений, содержащее (и) счетчиков, где т 1- число переставляемых кодов,3 91535 4 первый и второй элементы И, первую ные входы которых с группу элементов ИЛИ, элемент за- входом первого элем держки, при этом выход переноса -го синхронизации счет счетчика (1=2 п), кроме последвыходом второго эле него, соединен со входом (1+1) -говход которого подк счетчика, вход первого счетчика под- ройства, выходами у ключен к выходу первого элемента И, ся выходы элементов 11 запоминающих элементов и первую и На чертеже предс вторую группы элементов И, причем предлагаемого устро" входы запоминающих элементов подклю О Блок-схема содер чены к выходам элементов И первой выходы устройства 2, группы, первый вход первого элемента . 4 элементы И, перв И которой подключен к выходам эле- ИЛИ 5, вход устройс ментов И второй группы, первые входы задержки, запоминаю остальных элементов И первой группы 15 вую группу элементо подключены к выходам (1-1)-го запоми- пу элементов И 1 О тIнающего элемента, выходы запоминаю- ментов Я 11, четвер щих элементов, начиная со второго, тов И 12, пятую гру подключены к первым входам элементов гРУппУ элементов 1 П И второй группы, содержит третью, 20 ИЛИ-НЕ 15, переключ четвертую и пятую группы элементов группу элементов И, группу элементов ИЛИ-НЕ, переклю- низации счетчиков 18 чатель, элемент ИЛИ-НЕ, вторую груп импульсов, объед пу элементов ИЛИ, первые входы-ых ющие элементы 8, пер элементов которой 1=2 п- и второй 25 тов И 9, вторую груп вход (и-) -го связаны со вторыми вхо- И 10, пятую группу э дами 1-ых: (Е=1 п) элементов И вто- вторую группу элемен рой группы и через 1-ые элементы И Устройство работ третьей группы - с выходами 1-ых эле- Разомментов ИЛИ первой группы,подключен- ЗО 11 еред началом раб ными к прямым выходам разрядов соот- ющие элементы 8 рас ветствующих счетчиков, а вторые вхо- пульсов 19 записыв цы 1 -ых элементов ИЛИ второй группы ветствующие перестав подключены к выходам (1+1)-ых элеС помошью переключат ментов ИЛИ второй группы и ко вторым З 5 личест о перестся количество перест входам 1-ых элементов И первой группы, выход первого элемента ИЛИ вто 16 должно быть на е рой группы подключен ко вторым входам первого и второго элементов И перла объектов, В счетч чески записывается. ч вой группы, инверсные выходы первых 40ствующее на .единицу разрядов и прямые выходы остальныхего номеру, при этом разрядов счетчиков подключены к вхопересчета вычитающих дам элементов ИЛИ-НЕ, выходы которых подключены к первым входам элементовИ четвертой группы, выходы которыхподключены через элемент задержки кинверсным входам элементов И пятоигруппы, прямые входы которых связаныс выходами соответствующих запоминающих элементов, а выходы переноса 50счетчиков, кроме первого, соединенычерез элемент ИЛИ-НЕ с первым входомпервого элемента И, а через переключатель - с первым входом, второго элемента И, выходы переноса счетчиков,кроме последнего, соединены со вторыми входами соответствующих элементовИ третьей и четвертой групп, остальвязаны со вторымента И, со входомчиков и инверсныммента И, второйлючен ко входу устстройства являютИ пятой группы.тавлена блок-схемаиства,жит счетчик 1,первый 3 и второйую группу элементовтва 6 элемент 7щие элементы 8, перв И 9, вторую групретью группу элетую группу элеменппу элементов И 131 И-НЕ 4, элементатель 16, вторуюИЛИ 17, вход синхрораспределительиняющий запоминавую группу элеменпу элементовлементов И 13,тов ИЛИ 17.ает следующим оботы в запоминапределителя имаются коды, соотляемым объектам,еля 16 задаетавляемых объекство счетчиковз переключательдиницу меньше чисиках 1 автомати=исло, соответувеличенномукоэффициентысчетчиков таковы, что каждыи раз после их обнуления в нить пять записывается эточисло. 11 ерестановка кодов реализуется в распределителе 19 импульсов путем циклического сдвига с изменяющимся числом элементов 8 памяти, участвующих в нем. Сдвиги управляются счетчиками 1, соединенными так, чтобы организовать циклическое (цикл в цикле) изменение числа элементов 8 памяти, участвующих в циклическом сдвиге.Счетчики 1 работают в два подтакта, при наличии импульса на входе5 9115356 происходит подготовка записи по- . чследующего по порядку числа за- слись во вспомогательный регистр счет- Рчика) в соответствующем счетчике 1,са при отсутствии импульса - запись 5этого числа (перепись из вспомога.ттельного регистра в основной), Цик- млы организуются следующим образом. кПри подаче тактовых импульсовна пвход 6 выдается сигнал "Сдвиг" с 1 О ввыхода элемента И группы 11, связан- Уного через элементы ИЛИ группы 5 сс выходом счетчика 1, следующегоза счетчиком 1, на выходе переноса дкоторого образуется высокий потек гциал. иК началу следующего такта содер- джимое счетчика 1, следующего за об- Внуленным, уменьшается на единицу, ва счетчик 1, находящийся в нулевом 20 псостоянии, принимает значение на единицу больше его номера. Если сре- нди счетчиков 1 нет обнуленных, то эвыдача сигнала "Сдвиг" производится пс элемента И группы 11 на выходе перввого счетчика, в этом случае единица с выхода элемента И 4 проходит сна вычитающий вход первого счетчикачерез элемент И 3, управляемый элементом ИЛИ-НЕ 15, на выходе которого имеется единица при отсутствиисреди последующих счетчиков 1 обнуленных. К началу следующего такта его содержимое первого счетчика уменьшается на единицу. 35При поступлении сигнала "Сдвиг"в распределителе 19 импульсов происходит циклический сдвиг кодов в элементах 8 памяти, определяемых элементом И группы 11, с которого выдаетсясигнал сдвига, при этом выход последнего из них через соответствующийэлемент И группы 10 подключается квходу первого элемента 8 памяти. Еслисодержимое счетчика 1 отлично от единицы, то сигнал с выхода элементаИ группы 12 через элемент 7 задержкине блокирует группу элементов И 13и содержимое распределителя импульсовпоступает на выход устройства (выдается очередная перестановка), в противном случае содержимое распределите"ля 19 импульсов на выход устройства2 не поступает (вспомогательное состояние),55 При выборке всех й, перестановок1при 11 переставляемых объектах (коов), задаваемых с помощью переклю 6ателя 16, сигнал переноса с (и"1)четчика 1 производит останов устойства (отключения входа устройтва 6).Рассмотрим несколько тактов рабоы устройства. Пусть в элементах паяти записаны коды 1-4, а в счетчиах 1 - 2 - 4, тогда в первом тактероизводится обмен содержимого перого и второго элементов 8 памяти именьшение на 1 содержимого первогочетчика 1, который теперь содержит единицу и, следовательно, при слеующем такте будет получено вспомоательное состояние устройства, неоступающее на его выход и произойет обнуление первого счетчика .следующем такте при потенциале наыходе переноса первого счетчикароизойдет выдача сигнала сдвига элемента 11 второго счетчика 1 и уменьшеие его содержимого на единицу, притом в распределителе 19 импульсовроизойдет циклический сдвиг, захваты"ающнй первые три регистра 8, Таким образом, в распределителе 19 импульов будет записано: 2,3,1,4, а в счетчиках 1 - 2,2,4 и т.д,Предлагаемый принцип работы устройства достаточен для получения всех перестановок кодов (объектов). Ниже для пояснения принципа работы устройства приведены все И, =24 перестановки для 4-х объектов, обозначенных через 1,2,3,4, состояния устройства, не поступающие на его выход (вспомогательные), заключены в скобки. Для каждого состояния представлено содержимое счетчиковк концу соответствующего такта:1,2,3,4 2,3,4(1,2,3,4) 2,3,0При появлении нуля в третьем счетчике 1 перебор перестановок прекращается.Предлагаемое устройство позволяет осуществить перебор всевозможных перестановок кодов и может быть использовано в качестве составной части (блока) ЭВИ для решения комбинаторных задач.Формула изобретенияУстройство для перебора соединений, содержащее (и) счетчиков, где И - число переставляемых кодов, первый и второй элементы И, первую группу элементов ИЛИ, элемент задержки, при этом выход переноса 1 -го счетчика (1=2.и), кроме последнего, соединен со входом (1+1)-го счетчика, вход первого счетчика подключен к выходу первого элемента И, И запоминающих элементов, первую и вторую группы элементов И, входы запоминающих элементов подключены к выходам элементов И первой группы, первый вход первого элемента И которой подключен к выходам элементов И второй группы, первые входы остальных элементов И первой группы подключены к выходам (1-1) "го запоминающего элемента, выходы запоминающих элементов, начиная со второгоподключены к первым входам элементов И второй группы, о тл и ч а ю щ е. е с я тем, что, с целью расширения класса решаемых задачза счет возможности перебора всевозможных перестановок кодов, оно содержит третью, четвертую и пятую груп 5 пы элементов И группу элементовИЛИ-НЕ, переключатель, элемент ИЛИ-НЕвторую группу элементов ИЛИ, первыевходы-ых элементов которой 1=2,пи второй вход (и)-го связаны10 со вторыми входам 1 с-ых (1=п)элементов И второй группы и через1-ые элементы И третьей группы - с.%выходами 1-ых элементов СПИ первойгруппы, подключенными к прямым выхо 15 дам разрядов соответствующих счетчиков, а вторые входы 1-ых элементовИЛИ второй группы подключены к выхо- .дам (1+1) -ых элементов ИЛИ второйгруппы и ко вторым входами 1-ых эле 20 ментов И первой группы, выход первого элемента ИЛИ второй группы подключен ко вторым входам первого и второго элементов И первой группы, инверсные выходы первых разрядов и пря 25 мые выходы остальных разрядов счетчиков подключены к входам элементовИЛ 11-НЕ, выходы которых подключены кпервым входам элементов И четвертойгруппы, выходы которых подключены30 через элемент задержки к инверснымвходам элементов И пятой группы, прямые входы которых связаны с выходами соответствующих запоминающих элементов, а выходы переноса счетчиков,кроме первого, соединены через элемент ИЛИ-НК с первым входом первого элемента И, а через переключательс первым входом второго элементаИ, выходы переноса счетчиков, кромеЮ последнего, соединены со вторыми входами соответствующих элементов И третьей и четвертой групп, остальныевходы которых связаны со вторым входом первого элемента И, со входомн 5 синхронизации счетчиков и инверснымвыходом второго элемента И, второйвход которого подключен ко входу устройства, выходами устройства являютсявыходы элементов И пятой группы.50 Источники информации,принятые во внимание при экспертизе1, 1 ор 1 ееепФа 1 оп о 1 регщцйай 1 опГцпсй 1 опз 1 п 1111 ас, 1 Ч - Туре Сот"рцйеге, 1 ЕЕЕ, Тгапз. Сощрцегз. 976,25, Нф Ъ, р. 929-93 Ь,2. Авторское свидетельство СССРВ 374606, кл. С 06 Г 15/34, 1970иал ППП аказ 1130/4 тел 911535 ираж 732 Подпис город, ул. Проектная, 4