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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

Союз Советских

Социалмстических

Республик (ii) 888107

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву (22) Заявлено 24Ð 380 (21) 2898854/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 0 7.1281. Бюллетень № 45 дата опубликования описания 0712.81 (51)М. Кл.

G 06 F 7/38

Веударстинный комитет

СССР йв Мелек. изобретений и открытий (53) УДК681. 3 (088. 8) (72) Автор изобретения

В. А. Бо гатыре в

Ленинградский институт точной мехатч (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

ЧИСЕЛ

Изобретение относится к вычислительной технике и может быть применено в специализированных 3ВМ, предназначенных для решения задач переборного характера.

Известно устройство (1 J, содержащее п последовательно соединенных в кольцо регистров, выходы которых являются выходами устройства.

Недостатком известного устройства для перебора является то, что оно не

1О дает возможности генерировать перестановки, перестановки с повторениями.

Наиболее близким по технической

:сущности к изобретению является устройство )2), содержащее циклический реIS гистр, регистр и схему сравнения, к входу которой подключен выход регистра.

С помощью известного устройства

20 возможна генерация перестановок, перестановок с повторениями и сочетаний.

Недостатком известного устройства является то, что оно требует значи2 тельных затрат оборудования на реали-. зацию блока памяти, для запоминания (n-1)! слов разрядности (n-1) 31оп п, а также имеется необходимость подготовки и занесения этой информации. в память, что усложняет предварительную подготовку данных.

Целью изобретения является упрощения устройства.

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

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

= 2,3,...,и) циклического регистра

20 подключен к выходу (К-1)- го формирователя импульсов соответственно, выход которого подключен к первому выходу (К-1) — го дешифратора соответственно.

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

Устройства содержит и циклических регистров 11, 12, ..., 1>, N регистров 21, 22, ..., 2N, М схем сравнения

31 32 °, 3ы, и дешифр аторо в 41, эо

42, ..., 4и, N мультиплексоров 51, 52, ..., 5<, N+1 счетчиков 64, 62, 6 1+1, и-1 формирователей импульсов 71, 72, ..., 7и 1, элемент И 8, и элементов И 9, переключатели 10 э и 11, причем N = 2 .

Входы элемента И 8 через переключатель 10 подсоединены к выходам схем сравнения 3, 3, ..., 3ы, выход элемента И 8 подключен к управляющим 4о входам элементов И 9, подключенных другими входами к выходам циклических регистров 11, 1>, ..., 1 э. Выход

i--ro циклического регистра l„подключен к входу i - го дешифратора 4„, j -e 45 выходы дешифраторов 41, 42, ..., 4и (j = 1, 2,, N, где И вЂ” номер последнего кода регистра 1), подключены к информационным входам 3-го мультиплексора 5, выход которого подключен so к входу j-го тчика 69. Выход которого подключен к первому входу j-ой схемы сравнения 3, второй вход которой подключен к выходу 3-го ре ги стра 21 . Тактовый вход устройства t подключен к входу (N+1)-го счетчика 6„, 4, информационный выход которого подсоединен к управляющим

7 4 входам мультиплексоров 51, 52, 5„, выход переноса счетчика 6 1 подключен к управляющим входам остальных счетчиков 61, б, ..., 61, элемента

И 8 и циклического регистра 11 соответственно, управляющий вход I -го циклического регистра через формирователь 7 подключен к первому выходу (i-1)-ro дешифратора 4 1

Циклический регистр l„состоит из и последовательно соединенных 31og.n tразрядных регистров 1,;, l „, ..., 1д1. (через 11оц пГ обозначено ближайшее

2 целое не меньшее 1oq и), при этом выход первого регистра 11., являющийся выходом циклического регистра 1., У через переключатель 11 подсоединен к входам регистров g„., 1>, ..., l„„.

Работа устройства заключается в следующем.

Для перебора комбинаций кодов (элементов) (Аl, A2, ..., Аы они предварительно занбсятся в регистры 1-. В регистры 21 2, ..., 2ш заносятся числа элементов вида а1, а2, ..., а1, требуемых в вырабатываемых комбинациях.

В процессе работы в циклических регистрах 1,, 1, ..., 1> осуществляется циклический сдвиг кодов Al, А2, Аэ. При этом на вход дешифратора 41, и элемента И 9 поступает содержимое регистра 1 4. Если на вход де,— шифратора 4„. подается код Al, то возбуждается его первый выход, при этом на выходе формирователя 7 вырабатывается импульс, производящий сдвиг в следующем циклическом регистре 11+1.

Сдвиг в первом циклическом регистре

11 производится при поступлении импульса с выхода переноса счетчика

6 1 4 имеющего коэффициент пересчета, равный числу регистров 1. Код на выходе счетчика 61, 1 меняется от 1 до и, при коде i на выходе счетчика 6 через мультиплексоры 5 к входам счетчиков 6 подключаются выходы дешифратора 4i, Причем, если возбужден j é выход дешифратора 4i (на его входе находится код А j), подключенный к j-My входу j-го мультиплексора

5 j, то на "1" увеличивается содержимое счетчика б j. При переборе на счетчике 6 1+j всех кодов от 1 от и на счетчиках 61, 62, ..., бр будет подсчитано число кодов каждого вида

Аl, А2, ..., AN, содержащихся в сформированной комбинации, Если число ко40

flE РЕ СТАНО ВКИ в регистры 2 2 2 .", ..., 2ь заносятся коды 1 1 1 1

Комбинация с выходов регистров 1 передает ся на выход у ст рой ст ва, если в счетчи.ках 64 62 -, 6> Образу.ются коды 1 1, ..., 1, 5 8881 дов каждого вида в сформированной комбинации совпадает с требуемым числом а, аг, ..., а „, хранимым в соответствующем регистре 21, то импульсом с выхода элемента И 8 комбинация с вы- $ ходом циклических регистров 11, 1, l„передается на выход устройства через элементы И 9. По сигналу с выхода переноса счетчика би+.! производится обнуление счетчиков 6„, 6, ..., 61.

Пуст ь B Регис1 Ры l, 12Ф !31, 142, у, 12, 11, 1 1>>. заносят ся коды

1 2 3 1 2 3 1 2 3, тогда B процессе перебора будут сформированы следующие состояния. Коды, передаваемые на выходы циклических регистров l, подчеркнуты.

Состояние регист- Состояние счетчиров 1 ков 6 20

123 123 123 300

312. 123 123 201

231 123 123 111

123 312 123 201

312 312 123 102 2$

231 231 3!2 021

123 231 312 111

312 3! 312 012

231 123 312 1 l1

123 123 312 201 30

312 123 312 102

231 312 312 012

123 312 312 102

312 312 312 003

231 231 231 030 3S

123 231 231 f 20

312 231 231 021

231 123 231 120

123 123 231 210

312 123 731 111

231 312 231 021

123 312 231 111

312 312 231 012

231 231 123 120

123 231 123 210

312 231 123 111

231 123 123 210

123 !23 123 300

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

07 d

Для рассмотренного номера при генерации перестановок на выходы устройства будут переданы комбинации:

231 312

123 132

213 321

При генерировании перестановок вырабатываются и! комбинаций.

Перестановки с пов торениями, Перебор перестановок с повторениями, число которых равно

1!

И„! и где и число элементов i-го вида организуется аналогично перебору перестановок, с той разницей, что в регистры 2gy 2 ( заНОСЯТСЯ Коды и,! Пг ..., и, Например, для рассматриваемого примера, если в комбинации код должен повторяться 2 раза, код 3 должен повторяться 1 раз, а код 2 не должен содержаться в комбинации в ре гистры 2г 2З заносятся коды 2 0 1

Тогда на выход устройства будут переданы коды

311

13!

113

Для сокращения времени перебора в регистры 1„< 1г 1<< 1 1 3 1 мо гут быт ь занесены коды 1 3 1 3 1 3 при этдм. с помощью переключателя 11 выход регистра 1 подключается к входу регистра 1. В регистры 2„, 2 заносятся соответственно коды 2, 1.

Выходы схем сравнения 3, 3 „3g с помощью переключателя 10 отключаются от соответствующих входов элемента И 8 (на отключенные входы элемента И 8 либо подается "!", либо эти входы остаются отключенными, что также воспринимается как "!") . При этом будут сформированы следующие состояния. и Ъ ю ял 1 з гз 6„6, 3 3 1 3 3 0

3 1 3 1 3 .1 0 3

1 3 3 1 3 1 1 2

3 1 3 3 1 1 2

1 3 1 3 3 1 2

1 3 ! 3 2

888107

1 3 3 1 1 3 2 1

3 1 1 3 1 3 2 1

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

1 1 3

1 3 1

3 1 1

СОЧЕТАНИЯ

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

15 р!

У.1 (р — К )!

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

Количест во разрядов, 40

Предлагаемое устройство

Прототип

893 123 45

135093 173

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

Данное. устройство, кроме применения в ЭВМ, решающих задачи переборного характера, может быть использовано в качестве блока перенастройки (реконфигурации) в вычислительных сис. темах, реализуемых на многофункциональных модулях и предусматривающих комбинаций, Данное устройство характеризуется упрощением предварительной подготов-, ки данных, так. как в нем отпадает необходимость в занесении (и-1)! слов разрядности (n-1))log пЕ в блок памяти и экономией оборудования, так как в нем не требуется реализации (и-1) Jlog пР разрядного блока памяти, содержащего (n-1) i слов. зо перераспределение функций, возложенных на многофункциональные модули.

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

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

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

И и первого циклического регистра соответственно, управляющий вход К- го (К 2, 3... n) циклического регистра подключен к выходу (К-1)-го формирователя импульсов соответственно, вход которого подключен к первому выходу (К-1) -го дешифратора соответственноо.

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

Авторское свидетельство СССР

N 446057, кл. G 06 F 7/38 l975 °

2. Авторское свидетельство СССР

N 656057, кл. G 06 F 7/38, 1977 (прототип).

888107

Ю и а/

Составитель B. Кайданов

Редактор Г. Петрова Техред А.Ач Корректор М. Пожо

Заказ l0725/13 Тираж 748 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4