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

 

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

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

< >842787

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к ввт. сеид-ву (22) ЗаЯвлено 16,1277 (21) 2556228/18-24 с присоединением заявки ¹ 2556 26 2/18-24 (23) Приоритет

Опубликовано 300681 Бюллетень Мо 24

Дата опубликования описания ЗОЯ6,81 (51)М. Кл.з

С 06 Р 7/00

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

СССР по делам изобретений н открытий (53) УДК б 81 ° 327 (088.8) (72) Авторы изобретения

О.В,Викторов, М.Г.Лукашевич, С.И.Орел и A М.Романкевич

Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА КОМБИНАТОРНЫХ

ВЫБОРОК

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

Известны комбинаторные устройства, осуществляющие перечисление перестановок. Одно из известных устройств содержит кольцевые регистры, линии задержки, пороговые элементы, генератор импульсов и блок логики, в состав которого входят сумматор, импликатор и ждущий мультивибратор. Такое комбинаторное устройство обеспечивает15 перечисление всех P перестановок,но не осуществляет генерирование перестановок с повторениями и размещений (1) .

Наиболее близким к предлагаемому 2О изобретению является комбинаторное устройство, содержащее и последовательно соединенных К-разрядных счетчиков и группу элементов И, выходы которых являются выходами устройства, à вхо- 25 дом устройства является вход и-ro счетчика. Такое комбинаторное устройство обеспечивает. последовательный пребор сочетаний С„„ при всех и значениях и, начиная с единицы (2) . 3p

Недо ст ат ком устройства является невозможность генерирования перестановок с повторениями и размещений.

Цель изобретения — расширение функциональных возможностей за счет реализации перестановок с повторениями.

Поставленная цель достигается тем, что в устройство введен блок разрешения выдачи, причем выходы i-ro (i = 1, n) счетчика подключены ко входам i-й группы блока разрешений выдачи, при этом каждый выход счетчика подсоединен к первому входу соответствующего элемента И группы, второй вход которого соединен с выходом блока разрешения выдачи.

Блок разрешения выдачи содержит (к-1) группы элементов И, (е-1) ивходовых сумматора и элемент И, причем входы каждого i-го элемента И

j-й (j=l, к-1) группы соединены со входами i-A группы блока разрешения выдачи, а вйходы элементов И J-й группы подключены ко входам j-ro сумматора, при этом выходы всех сумматоров подсоединены ко входам элемента И, выход которого, является выходом блока разрешения выдачи. Блок разрешения выдачи содержит

Сп схем сравнения и элемент ИЛИ-НЕ, 84?787 причем входы Е-й (В = 1, C„ ) cxe сравнения первой и второй групп являются входами соответственно S-й (S = 1, n) и <-й (t = 1, n) групп блока разрешения выдачи, при этом

S Ф t и для любых двух схем сравнения цары S, t не равны между собой, а выходы всех схем сравнения подключены ко входам элемента ИЛИ-НЕ, выход которого является выходом блока разрешения выдачи, !О

На фи г. 1 изображена структурная схема устройства для перебора комбинаторных выборок; на фиг. 2 — функциональная схема устройства для генерирования перестановок с повторениями из пяти элементов (n = 2, п = 1, n = 2, п = n+ и+ n@=: 5); на фиг. 3 представлена фуйкциональная схема устройства для генерирования размещений из пяти элементов по Щ три (m = 5, n = 3); на фиг. 4 вариант 5-ти входового сумматора.

Устройство для перебора комбинаторных выборок (фиг. 1) содержит последовательно соединенных счетчиков 1, группу 2 элементов И, блок 3 разрешения выдачи. Выходы элементов

И группы 2 являются выходами устройства, а входом устройства является вход и-го счетчика 1. Выходы i-го (i = 1, п) счетчика 1 подключены ко входам i-й группы блока 3 разрешения выдачи, при этом каждый выход счетчика 1 подсоединен к первому входу соответствующего элемента И группы 2, второй вход которого соединен с выходом блока 3 разрешения выдачи.

Устройство для генерирования перестановок с повторениями Р(2,1,2) (фиг. 2) содержит пять счетчиков

4-8, группу 9 элементов И, блок 10 4() разрешения выдачи, в состав которого входят группа 11 элементов И 12-16, группа 17 элементов И 18-22,два 5входовых сумматора 23 и 24, элемент

И 25. Коэффициенты пересчета всех счетчиков равны 3. Выход каждого последующего счетчика подключен ко входу прещ дущего, а вход последнего счетчика соединен с шиной 26 такто0 ка подсоединен к первому входу соответствующего элемента И группы 9, второй вход которого соединен с выходом блока 10 разрешения выдачи.

Вы о) ы счетчика 4 подключены ко входам элементов И 12 группы 11, И 18 груцпы 17. Выходцы счетчика 5 подсоединеныы ко входам элементов И 1 3 группы 11, И 19 группы 17. Выходы счетчика 6 подключены ко входам элементов И 14 группы 11, и 20 группы g()

17. Выходы счетчика 7 подсоединены ко входам элементов И 15 группы

11, И 21 группы 17. Выходы счетчика .8 подключены ко входам элементов

И 16 группы 11, И 22 группы 17.

Один из возможных вариантов пост- роения 5-входового сумматора показан на фиг. 4. Сумматор содержит два одноразрядных сумматора 27 и

28 на два входа, два одноразрядных сумматора 29 и 30 на три входа °

Выходы элементов И 12-16 группы

11 подключены ко входам 5-входового сумматора 23. Выходы элементов И 1822 группы 17 подсоединены ко входам

5-входового сумматора 24. Выходы сумматоров 23 и 24 подключены ко входам элемента И 25, выход которого

l является выходом блока 10 разрешения выдачи .

Устройство для генерирования размещений А (фиг. 3) содержит три счетчика 31 — 33, группу 34 элементов

И, блок 35 разрешения выдачи, в состав которого входят три схемы сравнения 36 38, элемент ИЛИ HE 39. Один из возможных вариантов построения схемы сравнения представлен на фиг. 3.

Коэффициенты пересчета равенств кодов всех счетчиков равны 5. Выход каждого последующего счетчика подключен ко входу предыдущего, а вход последнего счетчика соединен с ши— ной тактовых импульсов 40, Каждый выход счетчика подсоединен к первому входу соответствующего элемента

И группы 34, второй вход которого соединен с выходом блока 35 разрешения выдачи, Выходы счетчика 31 подключены к первой группе входов

36 и 37 схем сравнения. Выходы счетчика 32 подключены ко второй группе входов 36 схемы сравнения и подсоединены к первой группе входов 38 схемы сравнения. Выходы счетчика 33 подключены ко второй группе входов

37 и 38 схем сравнения. Выходы 36-38 схем сравнения подсоединены ко входам элемента ИЛИ-НЕ 39, выход которого является выходом блока 35 разрешения выдачи, В режиме генерирования перестановок с повторениями устройство работает следующим образом (фиг. 2) .

На выход 5-входового сумматора поступает двоичный код числа входов, на которые поступили единичные си гн алы, На вход 8 счетчика с шины 26 поступает первый тактовый импульс и устанавливает счетчики 4, 5, 6, 7, и 8 соответственно в состояния 0,0,1,2 и.

2„На выходы старших и младших разрядов счетчиков 4,5,6, / и 8 поступают соответственно сигналы 00, 00, 0 1, 10 и 10.

Нулевые сигналы с выходов счетчиков 4 и 5 поступают на .инверсные входы соответственно элементов И 12, И 13, единичные сигналы с выходов которых поступают на первый и второй входы сумматора 23. Единичный сигнал с выхода младшего разряда счетчика

6 закрывает элемент И 14. Единичные

842787 сигналы с выходов ст арших разрядов счетчиков 7 и 8 закрывают соответственно элементы И 15, И 16. Нулевые сигналы с выходов элементов И 14, И 15, И 16 поступают соответственно на третий, четвертый и пятый входы сумматора 23. С выходов сумматора 5

23 сигналы 0,1 и О поступают на входы элемента И 25.

Нулевые сигналы с. выходов младших разрядов счетчиков 4, 5, 7 и 8 закрывают соответственно элементы И 18, JQ

И 19, И 21, И 22, нулевые сигналы с выходов которых поступают на первый; второй, четвертый и пятый входы сумматора 24. Нулевой сигнал с выхода старшего разряда счетчика б открывает элемент И 20, через который единичный сигнал с выхода младшего разряда счетчика б проходит на третий вход сумматора 24. С выходов сумматора 24 сигналы 1, О и О поступают на входы элемента И 25.

Единичный сигнал с выхода элемента И 25 открывает элементы И группы 9 и разрешает выдачу кодов состояний счетчиков 4-8. Таким образом, на первом такте работы реализуется первая перестановка с повторениями 00122, где номера позиций цифр в перестановке соответствуют номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют де- 30 сятичной записи двоичных кодов состояний счетчиков.

На.вход счетчика 8 с шины 26 поступает второй тактовый импульс и устанавливает счетчики 4-8 соот- 35 ветственно в состояния 0,0, 2, О и О.

На выходы счетчиков 4-8 поступают соответственно сигналы 00, 00, 10, 00 и 00.

Нулевые сигналы с выходов младших разрядов счетчиков 4-8 закрывают соответственно элементы И 18-22, нулевые сигналы с выходов которых поступают на все входы сумматора 24..

Нулевые сигналы с выходов сумматора

24 закрывают элемент И 25, нулевой 45 сигнал с выхода которого запрещает выдачу кодов состояний счетчиков

4-8.

На вход 8 счетчика с шины 26 поступает третий тактовый импульс и ус- 50 танавливает счетчики 4-8 соответственно в состояния 0,0,2,0 и

На выходы счетчиков 4-8 поступают соответственно сигналы 00,00, 10 00 и Ol, 55

Нулевые си гн алы с выходов 4, 5 и 7 счетчиков поступают на инверсные входы соответственно элементов И 12, И 13, И 15, единичные сигналы с выходов которых поступают на первый, второй и четвертый входы у. атора 60

23. Сигналы 1,1 и О с выходов сумматора 23 закрывают элемент И 25, нулевой сигнал с выхода которого запрещает выдачу кодов состояний счетчиков 4-8, 65

На вход счетчика 8 с шины 26 поступает седьмой тактовый импульс.

На выходы счетчикон 4-8 поступают соответственно сигналы 00,00,10,01 и 10. Нулевые сигналы с выходов счетчиков 4 и 5 поступают на инверсные входы соответственно элементов И 12, И 13, единичные сигналы с выходов которых поступают на первый и второй входы cyмматора 23.

С выходов сумматора 23 сигналы

0,1 и О поступают на входы элемента

И 25.

Нулевой сигнал с выхода старшего разряда счетчика 7 открывает элемент

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

24 ° С выходов сумматора 24 сигналы

1,0 и О поступают на входы элемента

И 25.

Единичный сигнал с выхода элемента И 25 открывает элементы И группы

9 и разрешает выдачу кодов состояний счетчиков 4-8, Таким образом, на седьмом такте работы реализуется вторая перестановка с повторениями 00212.

Работа устройства иллюстрируется табл. 1, в которой представлены состояния счетчиков 4-8, Те такты, н ко= торых устройство генерирует перестановки с посторениями P (2, 1, 2), пронумерованы.

На последнем такте работы устройства реализуется тридцатая ерестанонка с повторениями 22100.

В режиме генерирования размещений устройство работает следующим образом {фиг. 3) .

На выход схемы равенства поступает единичный сигнал в случае равенства кодов, поступающих на входы схемы равенства первой и второй групп, На вход счетчика 33 с Шины 40 поступает первый тактовый импульс и устанавливает счетчики 31-33 соответственно в состояния 0,1 и 2. На выходы старших, средних и младших разрядов счетчиков 31-33 поступают соответственно сигналы 000, 001 и 010.

С выходов счетчиков 31 и 32 сигналы 000 и 001 поступают соответственно на первую и вторую группы входов схемы 36 сравнения. С выходов счетчиков 31 и 33 сигналы 000 и 010 поступают соответственно на перную и вторую группы входов схемы 37 срав,нения. С выходов счетчиков 32 и 33" сигналы 001 и 010 поступают соответственно на первую и вторую группы входон схемы сравнения 38. Нулевые сигналы с выходон схем 36-38 сравнения поступают на входы элемента ИЛИ-НЕ

39, единичный сигнал с выхода которого открывает элементы И группы 34 и разрешает выдачу кодов состояний счетчиков 31-33.

Таким образом, на первом такте работы реализуется первое размещение

012, где номера позиций цифр в раз842787

Т а б л и ц а 1

Перестановки с повторениями

2 ) ) ) ) ((3 4 5 6 7 8

1 00122

00200

02122 11122

20122

20201

20202

20211

20212

20220

02200

11201 23

11202

11210 24

11211

11212

11220

00201 11 02201

02202

12 02210

02211

02212

02220

00202

00211

2 00212

00220 мещении соответствуют номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичный кодов состояний счетчиков.

На вход 33 счетчика с шины 40 поступает второй тактовый импульс и устанавливает счетчики 31-33 соответст5 венно в состояние О, 1 и 2 ° На выходы старших, средних и мпадших разрядов счетчиков 31-33 поступают соответственно сигналы 000, 001 и 011, С выходов счетчиков 31 и 32 сигналы 000 и 001 поступают соответст- венно на первую и вторую группы входов схемы равенства кодов 26. С выходов счетчиков 31 и 33 сигналы 000 и 011 поступают соответственно на пер- 5

1 вую и вторую группы входов схемы 13 сравнени я; С выходов счетчиков 32 и 33 сигналы 00 1 и О 11 поступают соответственно на первую и вторую группы входов схемы 38 сравнения. 2Q

Нулевые сигналы с выходов схем 36-38 сравнения поступают на входы элемента ИЛИ-НЕ 39, единичный сигнал с выхода которого открывает элементы И группы 34 и разрешает выдачу кодов состояний счетчиков 31 — 33.

Таким образом, на втором такте работы реализуется второе размещение

013.

На вход счетчика 33 с шины 40 поступает четвертый тактовый импульс и у ст ан авли в ает счетчики 31 — 33 соответственно в состояния О, 2 и О. На выходы старших, средних и мпадших разрядов счетчиков 31-33 поступают соответственно сигналы 000, 010 и

000.

С выходов счетчиков 31 и 32 сигн алы О 00 и О 10 поступают соот вет ственно на первую и вторую группы входов схемы 36 сравнения. С выходов 40 счетчиков 31 и 33 сигналы 000 и 000 поступают соответственно на первую н вторую группы входов схемы 37 сравнения. С выходов счетчиков 32 и 33 сигналы 010 и 000 поступают

45 соответственно на первую и вторую группы входов схемы 38 сравнения, С выходов схем 36-38 сравнения сигналы 0,1 и О поступают на входы элемента ИЛИ-НЕ 39, нулевой сигнал с выхода которого закрывает элементы И группы 34 и запрещает выдачу кодов состояний счетчиков 31-33.

Работа устройства иллюстрируется табл ° 2, в которой представлены состояния счетчиков 31-33. Те такты, в которых устройство генерирует размещения A) пронумерованы.

На последнем такте работы устройства реализуется шестидесятое размещение 432.

Известное устройство обеспечивает последовательный перебор сочета-, ний С, при всех значениях n„ наи чиная с единицы ° По сравнению с ним предлагаемое устройство расширяет функциональные возможности за счет реализации всех Р (и.(, и . ..n) перестановок с повторениями кодов состояний и„ + n >...+ n счетчиков с коэффициентами пересчета, равными к, .всех А„ размещений кодов состояний и счетчиков с коэффициентами перес,чета, равными m, В случае равенства коэффициента пересчета к (или m) числу счетчиков

Ф

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

Предлагаемое изобретение может быть использовано при решении комбинаторных задач (перечисление полиномиальных коэффициентов, вычисление перманентов), а также задач вычислительной математики (раскрытие определителей матриц), Укаэанные задачи известное устройство решить не может, Предлагается внедрение изобретения в производство на ПО ЭЛЕКТРОНХАШ, а также в систему обработки данных, разрабатываемую кафедрой вычислительной техники совместно с СКБ МИС ИК

AH УССР, 842787

Хо

Продолжение табл. 1

5 6 7 8

02221

02222

10001

3 00221

00222

0 1000

01001

01002

0 1010

01011

01012

01021

4 01022

01100.

01101

01102

01111

01112

01121

01122

01201

10002

10011

10012

10020

10021

10022

10 100

10101

10102

10111

10112

10) 21

10122

10200

10201

10202

10211

10212

10221

5 01202

01210

01211

01212

6 0 1220

01221

01222

02001

10222

11000

20001 28

11001

11002

110 10

11011

02002

02010

20002

20010 29

20011

20012

20020

02011

7 020 12

0 2020

8 02021

02022

02101

11012

11020

11021

20021

20022

20 100 30

20101

11022

11101

12221

11222

12001

12002 25

120 10

12011

12012

12020 26

12021

12022

12101

12102

12111

12112

12121

12122

12200 27

12201

12202

12211

12212

12221

12222

20221

20222

21001

21002

210 1 0

21011

21012

21021

21022

2110)

21102

21111

21112

21121

21122

21201

21202

21211

21212

21221

21222

22001

22002

22011

220 12

22021

22022

22 100

842787

Продолжение табл. 1

4 5 6 T 8

11102 21 20102

20111

20112

11120 22 20120

02121

11121

20121

Т а блиц а 2

Р аз меще ни я ((3 (4 j ) (1 2

012 16 120

223

331

224

332

013

121

31

014

122

230

333

334

020 17 123

021 18 124

022 19 130

231

232

340

233

341

131

234

342

023

343

024 20 132

240

241

344

030

133

031 21 134

032 22 140

400

242

36 243

401

033

141

244

402

034

142

300

403

040

143

404

041

144

52

410

042

200

303

411

043

201

304

412

044

202

413

310

100

203

311

414

204

101

55

312

420

102

313

421

210

14

103

211

314

422

9 02102

02111

02112

10 02120 2

11111

11112

5 6 7 8

37 301

38 302

842787

Продолжение табл. 2

104

212

320

423

110 29 213

111 30 214

321

424

322

430

112

220

323

431

324

113

221

60

432

114

330

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

1. Устройство для перебора комбинаторных выборок, содержащее и последовательно соединенных к-разрядных счетчиков и группу элементов И, выходы которых являются выходами устройства, а входом устройства является вход и-го счетчика, о т л и ч а ю щ е е— с я тем, что, с целью расширения функциональных возможностей за счет 25 реализации всех перестановок с повторениями и всех размещений, устройство содержит блок раэреаения выдачи, при- чем выходы i-ro (i= l,... n) счетчика подключены к входам 1-й группы блока () разрешения выдачи, при этом каждый выход счетчика подсоединен к первому входу соответствующего элемента И груп 1ы, второй вход которого соединен с выходом блока разрешения выдачи, 2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок разрешения выдачи содержит (к-1) группы элементов И, (к-1) и-входовых сумматора и элемент И, причем входы каждого i-го элемента И j-й (j=l к-1) группы соединены с входами i-й груп-. пы блока разрешения выдачи, а выходы элементов И j-й группы подключены к входам j-ro сумматора, при этом выходы всех сумматоров подсоединены ко входам элемента И, выход которого является выходом блока разрешения выдачи .

3. Устройство по и. 1, о т л и ч аю щ е е с я тем, что блок разрешения выдачи содержит С схем сравнения и элемент ИЛИ-НЕ, причем входы Я-й (R--l, C ) схемы сравнения и первой и второй групп являются входами соответственно S-йjS - 1, п и t-й (t = 1, n ) групп блока разрешения выдачи, при этом S P t и для любых двух схем сравнения пары S не равны между собой, а выходы всех схем сравнения подключены к входам элемента ИЛИ-НЕ, выход которого является выходом блока разрешения выдачи.

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

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

Р 446057, кл. G 06 F 15/20, 1974.

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

9 374606, кл. G 06 F 15/20, 1973 (прототип) .