Устройство для формирования последовательностей чисел Советский патент 1981 года по МПК G06F7/38 

(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

ЧИСЕЛ

Изобретение относится к вычислительной технике и может быть применено в специализированных ЭВМ, предназначенных для решения задач переборного характера. Известно устройство tO. содержащ п последовательно соединенных в коль цо регистров, выходы которых являются выходами устройства. Недостатком известного устройства для перебора является то, что оно не дает возможности генерировать перестановки, перестановки с повторениям Наиболее близким по технической сущности к изобретению является устрой ство З, содержащее циклический регистр, регистр и схему сравнения, к входу которой подключен выход регистра. С помощью известного устройства возможна генерация перестановок, перестановок с повторениями и сочетани Недостатком известного устройства является то, что оно требует значительных затрат оборудования на реали-. зацию блока памяти, для запоминания (п-1) слов разрядности (п-1), а также имеется необходимость подготовки и занесения этой информации в память, что усложняет предварительную подготовку данных. Целью изобретения является упрощения устройства. Поставленная цель достигается тем, что устройство содержит дополнительно п-1 циклических регистров, п дешифраторов, N мультиплексоров (N-2), N+1 счетчиков, N-1 регистров, N-1 схем сравнения, п-1 формирователей импульсов и п+1 элементов И, причем входы первого элемента И подключены к входам схем сравнения, а выход подключен к управляющим входам п элементов И, подключенных другими своими входами к выходам циклических реагентов соответственно, выход i-ro (i 1, 2,..., п) циклического регистра подключен к входу i-ro дешифрато3ра соответственно, j-e выходы дешифраторов (j 1N) подключены к информационным входам j-ro мультиплексора соответственно, выход которого подключен к счетному входу j-ro счетчика соответственно, выход которого подключен к первому входу j-й схемы сравнения соответствелно, второй вход которой подключен к выходу j-ro регистра соответственно, тактовый вход устройства подключен к счетному входу (N+l)-ro счетчика, информационные выходы которого подсоединены к управляющим входам j-x мультиплексоров соответственно, а выход переноса подключен к управляющим входам j-x счетчиков, первого элемента И и первого циклического регистра соответственно, управляющий вход К-го (К 2,3.-.) циклического регистра подключен к выходу (K-l)-ro формирова теля импульсов соответственно, выход которого подключен к первому выходу (K-l)-ro дешифратора соответственно. Структурная схема устройства для формирования последовательностей чисел представлена на чертеже. Устройство содержит п циклических регистров 1 , l. у,, 11 регистров 2, 22, .., 2ы, N схем сравнени ., Зщ, п дешифраторов k, Цу, t) мультиплексоров 5 5ii . 5, П+1 счетчиков 6-f , 62, ..., бщц. , п-1 формирователей импуль сов 7-, 72., . 7vi--f элемент И 8, п элементов И 9. переключатели 10 и 11, причем Н 2. Входы элемента И 8 через переключ тель 10 подсоединены к выходам схем сравнения 3, З 3|д, выход эле мента И 8 подключен к управляющим входам элементов И 9, подключенных другими входами к выходам циклических регистров 1, 12, ..., 1ут Выход i-ro циклического регистра 1 подклю чен к входу i-ro дешифратора , j-e выходы дешифраторов /, 2, ..., vi (j 1, 2,.., И, где М - номер после него кода регистра 1), подключены к информационным входам j-ro мульти плексора 5 , выход которого подключе к входу j-ro счетчика , выход кот рого подключен к первому входу j-о схемы сравнения 3л, второй вход которой подключен к выходу j-ro регистра 2. Тактовый вход устройства t подключен к входу (N+1)-r счетчика информационный выход которого подсоединен к управляющим 5,. 5. входам мультиплексоров р- , р.2. переноса счетчика 6 5jj , ВЫХОД I leiJeMuud счс i 4t-ii « u fj.j ключей К управляющим входам остальных счетчиков 6,6, .... 6), элемента И 8 и циклического регистра 1; соответственно, управляющий вход i-ro циклического регистра через формирователь 7 подключен к первому выходу (i-l)-ro дешифратора 4 , Циклический регистр 1 состоит из п последовательно соединенных Dlog-nt разрядных регистров , ,.., 1,(через обозначено ближайшее целое не меньшее 1огьп), при этом выход первого регистра ), являющийся выходом циклического регистра 1- , через переключатель 11 подсоединен к входам регистров , 1,-, ..,, . Работа устройства заключается в следующем. Для перебора комбинаций кодов (элементов) (А1 , А2, ..., А,д они предварительно заносятся в регистры Ц-. В . , 2nj заносятся регистры 1, 2- числа элементов вида J/, 2. требуемых в вырабатываемых комбинациях. В процессе работы в циклических регистрах 1 , Irj, . , . , 1у осуществляется циклический сдвиг кодов А1, А2, .,., ... , Ajj. При этом на вход дешифратора tyj, и элемента И 9 поступает содер1 Если на вход дерегистрашифратора 4; подается код А1 , то воз1буждается его первый выход, при этом на выходе формирователя 7 вырабатывается импульс, производящий сдвиг в следующем циклическом регистре 1/. Сдвиг в первом циклическом регистре производится при поступлении импульса с выхода переноса счетчика 6ц54.ф имеющего коэффициент пересчета, равный числу регистров 1. Код на вы6ig меняется от 1 ходе счетчика bjg меняется от 1 до на выходе счетчика 6, п, при коде I через мультиплексоры SA к входам счетчиков 6 подключаются выходы дешифратора Ц. Причем, если возбужден j-й выход дешифратора (на его входе находится код А j), подключенный к j-му входу j-ro мультиплексора 5 J, то на 1 увеличивается содержимое счетчика 6 j. При переборе на счетчике 6,j.f всех кодов от 1 от п на счетчиках 6 6 и будет подсчитано число кодов каждого вида А1, А2, ..., AN, содержащихся в сформированной комбинации. Если число кодов каждого вида в сформированной ко бинации совпадает с требуемым числом а , а, ..., а.,, хранимым в соответствующем регистре 2, то импульсом с выхода элемента И 8 комбинация с выходом циклических регистров 1, l, ..., ly, передается на выход устройства через элемен7Ы ИЗ- По сигналу с выхода переноса счетчика ()у прои водится обнуление счетчиков 6, Sji N Пусть в регистры 1, U, U Ь Iz.. li % заносятся коды 123123123, тогда в процессе перебора будут сформированы следующие состояния. Коды, передаваемые на выходы циклических регистров 1 , подчеркнуты. Состояние регист- Состояние счетчи

Рассмотрим примеры генерации различных видов комбинаций.

ПЕРЕСТАНОВКИ в регистры 22 2

заносятся коды

Комбинация с выходов регистров 1 передается на выход устройства, если

6« 1,

образу

1

в регистры 2.

-2заносятся коды п , п Например, для рассматриваемого примера, если в комбинации код 1 должен повторяться 2 раза , код 3 должен повторяться 1 раз, а код 2 не должен содержаться в комбинации в регистры 2 2-2 2 g заносятся коды 2 О 1 Тогда на выход устройства будут переданы коды

311 131 113 Для сокращения времени перебора

2 ч2 23

в регистры

/ft могут быть занесены коды 131313. при этим, с помощью переключателя 11 выход регистра 1« подключается к входу регистра i- регистры 2 , 2 заносятся соответственно коды 2, 1. Выходы схем сравнения 3, 3 Зы с помощью переключателя 10 отключаются от соответствующих входов элемента И 8 (на отключенные входы элемента И 8 либо подается 1, либо эти входы остаются отключенными, что также воспринимается как 1). При этом будут сформированы следующие состояния.

I

1 3

° о

23

3 о 1 1

1

3

1 1 3 3

3 2 2

:1

3 3 3 3 1

1 1 1 3

1i

2

1 2

1 « Для рассмотренного номера при генерацииперестановок на выходы устройствабудут переданы комбинации: 231312 123132 213 321 При генерировании перестановок вырабатываются п комбинаций. Перестановки с повторениями, Перебор перестановок с повторениями, число которых равно где число элементов 1-го вида организуется аналогично перебору перестановок, с той разницей, что

13311321 31 131321 131 3 1 3 3 О а на выход устройства передаются комбинации :

113

131

311

СОЧЕТАНИЯ

Перебор сочетаний сводится к перебору перестановок с повторениями элементов в случае к элементу одного вида и n-k элементов второго вида. Пр генерировании сочетаний всего вырабатывается

VII

гК

к()1

комбинаций.. ,

Данное устройство характеризуется упрощением предварительной подготов- i ки данных, так- как в нем отпадает необходимость в занесении (п-1) слов разрядности (n-l)3log п в блок памяти и экономией оборудования, так как в нем не требуется реализации {n-1)1og пЕ разрядного блока памяти, содержащего (п-1) слов.

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

Из расчетов видно, что при п7б применение данного устройства с точки зрения затрат оборудования становится целесообразным.

.Данное.устройство, кроме применения в ЭВМ, решающих задачи переборного характера, может быть использовано, в качестве блока перенастройки (реконфигурации) в вычислительных ситемах, реализуемых на многофункциональных модулях и предусматривающих

|перераспределение функций, возложенных на многофункциональные модули.

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

Устройство для формирования последовательностей чисел, содержащее .первый циклический регистр, первый

регистр и первую схему сравнения, к первому входу которой подключен выход первого регистра, о т л и чающееся тем, что, с целью упрощения устройства, оно содержит дополни5 тельно п-1 циклических регистров, п дешифраторов, N мультиплексоров (N-2), N+1 счетчиков, -N-1 регистров, N-1 схем сравнения, п-1 формирователей импульсов и п+1 элементов И, причем входы первого элемента И подключены к выходам схем сравнения, а выход - подключен к управляющим входам п элементов И, подключенных другими своими входами к выходам циклических регистров соответственно, выход i-ro (, 2, ..., п) циклического регистра подключен К входу i-ro дешифратора соответственно, j-e выходы дешифраторов (, 2, ..., N) подключены

0 к информационным входам j-ro мультиплексора соответственно, выход которого подключен к счетному входу j-ro счетчика соответственно, выход которого подключен к первому входу j-й схемы сравнения .соответственно, второй вход которой подключен к выходу j-ro регистра соответственно, тактовый вход устройства подключен к счетному входу (N+l)-ro счетчика, информационные выходы которого подсоединены к управляющим входам j-x мультиплексоров соответственно, а выход переноса подключен к управляющим входам j-x счетчиков, первого элемента И и первого циклического регистра соответственно, управляющий вход К-го (, 3, ..., п) циклического регистра подключен к выходу (К-1)-го формирователя импульсов соответственно, вход которого подключен к первому выходу (К-1)-го дешифратора соответственно.

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

№ 656057, кл. G Об F 7/38, 1977 (прототип) .

888107

в ь/ Г ff д