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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалмстическихРеспублик ц 888107 К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(51)М. Кл. а Об Г 7/З 8 3 Ъеударстинагй комитет СССР ае делам. изобретений и открытий(72) Автор изобретения Богатыре 7) Заявите Лен адский институт точной мехам) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСЧИСЕЛ к вычислибыть примеЭВМ, предадач перестра. С помощью изве возможна генераци рестановок с повт Недостатком из является то, чтоного устрои пере ст аново ениями и со стного устр о требует з твапеетаний. йства ачиИзобретение относитсятельной технике и можетнено в специ али зированныхназначенных для решения зборного характера,Известно устройство 1 1, содержаще п последовательно соединенных в кольцо регистров, выходы которых являются выходами устройства.Недостатком известного устройства для перебора является то, что оно не дает возможности генерировать перестановки, перестановки с повторениямиНаиболее близким по технической ;сущности к изобретению является устройство 2, содержащее циклический регистр, регистр и схему сравнения, к входу которой подключен выход регительных затрат оборудования на реализацию блока памяти, для запоминания(и) слов разрядности (и)31 оп п,а также имеется необходимость подготовки и занесения этой информации. в 5память, что усложняет предварительную подготовку данных.Целью изобретения является упрощения устройства.Поставленная цель достигается тем, 0мчто устроиство содержит дополнительно ициклических регистров, и дешифраторов, М мультиплексоров (Й),И+1 счетчиков, Мрегистров, й схем сравнения, иформирователейимпульсов и и+1 элементов И, причемвходы первого элемента И подключенык входам схем сравнения, а выход подключен к управляющим входам и элементов И, подключенных другими своими входами к выходам циклических реагентов соответственно, выход 1-го(1=1, 2 и) циклического регисра подключен к входу 1-го дешифрат88810 25 ра соответственно, -е выходы дешифраторов Ц =1 М) подключены к информационным входам 1 - го мул ьти плексора соответственно, выход которогоподключен к счетному входу 1-го счетчика соответственно, выход которогоподключен к первому входу -й схемысравнения соответственно, второйвход которой подключен к выходу -горегистра соответственно, тактовый 1 Овход устройства подключен к счетномувходу (М+1)-го счетчика, информационные выходы которого подсоединены куправляющим входам 1-х мультиплексоров соответственно, а выход переноса 15подключен к управляющим входам 1-хсцетчиков, первого элемента И и первого ци кличе ского ре ги стра соот ветственно, управляющий вход К-го (К == 2,3и) циклического регистра20подключен к выходу (К)-го формирователя импульсов соответственно, выходкот оро го под ключе н к пер во му выходу(К)-го дешифратора соответственно,Структурная схема устройства дляформирования последовательностейчисел представлена на чертеже.Устройства содержит и циклическихрегистров 11, 12, , 1, М регистров 2, 22, , 2 М, М схем сравнения31, 3, , 3 М, и дешифраторов 4,1,ЭО4, , 41 М мультиплексоров 5,1,52, , 5 М+1 сцетциков 6, 62,бМ+,1, иформирователей импульсоа 7, 7 г7 и, элемент И 8,и элементов И 9, переключатели 10 Э 5и 11, причем М = 2 д,Входы элемента И 8 через переключатель 10 подсоединены к выходам схемсраия 3, 3, , 3 М, ыхд элемента И 8 подключен к управляющим 4 Овходам элементов И 9, подключенныхдругими входами к выходам циклических регистров 1 А, 1, , 11. Выход1-го циклического регистра 1 подключен к входу 1-го дешифратора 4, 1-е 45выходы дешифраторов 41, 4, , 4 и(1 = 1, 2, , Н, где М - номер последнего кода регистра 1), подключенык информационным входам 1-го мультиплексора 5 , выход которого подключен 5 Ок входу 3- го с етчика 69 . Выход которого подключен к первому входу Э-ойсхемы сравнения 3, второй входкоторой подключен к выходу 1-горе ги стра 2 . Тактовый вход устройства с подключен к входу (М+1)-госчетчика 6 1, информационный выходкоторого подсоединен к управляющим 7входам мультиплексоров 5, 52,5, выход переноса счетчика 6 подключен к упоааляющим входам остальныхсчетчиков 61, б, , 61, элементаИ 8 и циклического регистра 11 соответственно, управляющий вход 1-гоциклического регистра через формирователь 7 подключен к первому выходу(1-1)-го дешифратора 4Циклический регистр 1 состоит изи последовательно соединенных 3 од.и.разрядных регистров 11, 121,, 1 м(через 3 1 оу иГ обозначено ближайшее2целое не меньшее 1 ог и), при этомвыход первого регистра 1, являющийся выходом циклического регистра 1Учерез переключатель 11 подсоединен квходам регистров , 11 пРабота устройства заключается вследующем.Для перебора комбинаций кодов (элементов) (А 1, А 2, , АМ они предварительно занбсятся в регистры 1 . Врегистры 2 1, 2, , 2 М заносятсячисла элементов вида а 1, а 2, , аМ,требуемых в вырабатываемых комбинациях,В процессе работы в циклических ре- гистрах 1 1, , 1 осущест вляет - ся циклический сдвиг кодов А 1, А 2,АМ. При этом на вход дешифратора 4 и элемента И 9 поступает содержимое регистра 11. Если на вход де, - шифратора 4 подается код А 1, то возбуждается его первый выход, при этом на выходе формирователя 7 вырабатывается импульс, производящий сдвиг в следующем циклическом регистре 1+,1.Сдвиг в первом циклическом регистре 11 производится при поступлении импульса с выхода переноса сцетчика 6 М имеющего коэффициент пересчета, равный числу регистров 1. Код на выходе счетчика бм ,1 меняется от 1 до и, при коде 1 на выходе счетчика 6 М через мультиплексоры 5к входам счетчиков 6подключаются выходы дешифратора 41, Причем, если возбужден 1-й выход дешифратора 41 (на его входе находится код А ), подключенный к 1-му входу 1-го мультиплексора 5 , то на "1" увеличивается содержимое счетчика б 1. При переборе на счетчике 611 .1 всех кодов от 1 от п на счетчиках 6,1, 62, , бм будет подсчитано число кодов каждого вида А 1, А 2, , АМ, содержащихся в сформированной комбинации, Если число ко5 8881 дов каждого вида в сформированной комбинации совпадает с требуемым числом а, аг, , а, хранимым в соответствующем регистре 2, то импульсом с выхода элемента И 8 комбинация с вы- й ходом циклических регистров 11, 1 г,1 передается на выход устройства через элементы И 9. По сигналу с выхода переноса счетчика би,. производится обнуление счетчиков 6, бг, 1 в6,.1.Пусть в регистры 1, 1 1 1, Ц 1, 12 11, 1 1. заносятся коды 1 2 3 1 2 3 1 2 3, тогда в процессе перебора будут сформированы следующие состояния. Коды, передаваемыена выходы циклических регистров 1, подчеркнуты.Состояние регист- Состояние сцетциров 1 ков б эе 123 123 123 300312, 123 123 го 1231 123 123 111123 312 123 го312 312 123 102 ь 231 231 312 021123 231 312 111312 3312 012231 123 312 111123 123 312 201 30 312 123 312 102231 312 312 012123 312 312 102312 312 312003231 231 231 030 зз 123 231 231 120312 231 231 021231 123 231 120123 123 231 210312 12 3 7 31 111231 312 231 021123 312 231 111312 312 231 012231 231 123 120123 231 123 210312 231 123 111231 123 123 210123 123 123 300Рассмотрим примеры генерации различных видов комбинаций. ПЕРЕСТАНОВКИв регистры 2 2 2 ."., , ги заносятся коды 1 1 1 1 Комбинация с выходов регистров 1 передает ся н а выход у ст рой ст ва, еслив счетчи,ках б, бг, , би образу,ются коды 1 1 , , 1,07 4Для рассмотренного номера при генерации перестановок на выходы устройства будут переданы комбинации:23 312123 132213 32При генерировании перестановок вырабатываются икомбинаций,Перестановки с повторениями,Перебор перестановок с повторениями,число которых равноЬ1где ичисло элементов 1-го вида организуется аналогично перебору перестановок, с той разницей, цто в регистрыф заносятся коды п 1 пд.п 1 Например, для рассматриваемого при мера, если в комбинации код 1 должен повторяться 2 раза, код 3 должен повторяться 1 раз, а код 2 не должен содержаться в комбинациив ре гистры 2,22 2 Я заносятся коды 2 0 1 Тогда на выход устройства будут переданы коды311131113Для сокращения времени перебора в регистры 1 1 г 1 11 1 г мо гут быт ьзанесены коды 1 3 1 3 1 3 при этом. с помощью переключателя 11 выход регистра 1 подключается к входу регистра1. В регистры 2, 2 заносятся соответственно коды 2, 1.Выходы схем сравнения 3, 33 й с помощью переключателя 10 отключаются от соответствующих входов элемента И 8 на отключенные входы элемента И 8 либо подается , либо эти входы остаются отключенными, что также воспринимается как ), При этом будут сформированы следующие состояния.1 И Ъ Ю аъ 1 з гав 6 63 1 3 1 3 . 3 0 3 1 3 1 31 0 3 1 3 3 1 3 1 1 2 31 3 3 1 1 2 1 3 1 3 3 1 2 1, 3 1 3 1 1 3 1 21 3 3 1 1 3 2 1 31 3 1 3 2 1 1 3 1 3 1 3 3 0 а на выход устройства передаются комбинации:1 1 33 13 1 1СОЧЕТАНИЯПеребор сочетаний сводится к перебору перестановок с повторениями элементов в случае к элементу одного вида и иэлементов второго вида. При генерировании сочетаний всего выраба- тывается 1 О 5 р К 1 (и- К )20 Результаты расчета затрат оборудования в микросхемах для реализации прототипа и данного устройства сведены в таблицу,35.Затраты .оборудования .вмикросхемах Количест воразрядов,40 Предлагаемоеустройство Прототип 893 123 45 135093 173чееюИз расчетов видно, что при и 76 применение данного устройства с точки зрения затрат оборудования становится целесообразным.Данное. устройство, кроме применения в ЭВМ, решающих задачи перебор- ного характера, может быть использовано в качестве блока перенастройки (реконфигурации) в вычислительных сис. темах, реализуемых на многофункциональных модулях и предусматривающих комбинаций,Данное устройство характеризуетсяупрощением предварительной подготов- ,ки данных, так как в нем отпадает необходимость в занесении (и) словразрядности (и)1 ос п в блок памяти и экономией оборудования, таккак в нем не требуется реализации(и)1 оц и. разрядного блока памяти,содержащего (и) слов.30 перераспределение функций, возложенных на многофункциональные модули.Формула изобретенияУстройство для формирования последовательностей чисел, содержащее,первый циклический регистр, первыйрегистр и первую схему сравнения, кпервому входу которой подключен выходпервого регистра, о т л и ч а ющ е е с я тем, что, с целью упрощения устройства, оно содержит дополнительно ициклических регистров,и дешифраторов, М мультиплексоров(М"), М+1 счетчиков, Мрегистров,Мсхем сравнения, иформирователей импульсов и и+1 элементов И, причем входы первого элемента И подключены к выходам схем сравнения, а выход - подключен к управляющим входамп элементов И, подключенных другимисвоими входами к выходам циклическихрегистров соответственно, выход 1-го( =1, 2, , п) циклического регистра подключен- к входу-го дешифратора соответственно, 1-е выходы дешифраторов (1=1, 2 М) подключенык информационным входам- го мультиплексора соответственновыход которого подключен к счетному входу 1-госчетчика соответственно, выход которого подключен к первому входу 1-йсхемы сравнения соответственно, второй вход которой подключен к выходу-го регистра соответственно, тактовый вход устройства подключен к счетному входу (М+1)-го счетчика, информационные выходы которого подсоединены к управляющим входам 1-х мультиплексоров соответственно, а выходпереноса подключен к управляющим входам "х счетчиков, первого элементаИ и первого циклического регистрасоответственно, управляющий вход К- го(К 2 3.и) циклического регистра подключен к выходу (К)-го формирователя импульсов соответственно,вход которого подключен к первому выходу (К)-го дешифратора соответственно.Источники информации,принятые во внимание при экспертизеАвторское свидетельство СССРН 6057, кл. 6 06 Г 7/38, 1975.2. Авторское свидетельство СССРМф 656057, кл. С 06 Р 7/38, 1977 (прототип)."Патент", г. Ужгород, ул. Проектная, 4 ли 888107Ю юг уу/ 5/13 Тираж 748 ВНИИПИ Государственного по делам изобретений 13035, Москва, 3-35, Раушс