Комбинаторное устройство

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОУСКОМУ СВ ТЕЛЬСТВУ (61) Дополнительное к евт. сеид-ву— (22) Заявлено 31.10.78 (21) 2679192/18-24 (Sf) JA. Kll. с присоединением заявки Нов

6 06 F 7/00

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

СССР по делам изобретений н открытий (23) Приоритет—

Опубликовано 1503 81. бюллетень N9 10 (53) Vga< 681. 327 (088 ° 8) Дата опубликования описания 150481

О.В.Викторов, М.Г.Лукашевич, С.И.Орел и A.Ì.Ðoìàíêåâè÷ (72) Авторы изобретения (71) Заявитель

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

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

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

Недостатком этих устройств явля« ется невозможность генерации сочета- 35 ний с повторениями.

Наиболее близким по технической сущности и достигаемому результату является комбинаторное устройство„ содержащее N счетчиков, группу 2Q элементов И, и -1 групп элементов задержки, причем выход переноса

i-того (i = 2,...,N) счетчика подключен к тактовому входу 1= счетчика и через первый элемент за- 25 держки 1-1 группы — к первому входу

i-1 элемента И первой группы и через второй элемент задержки i-1-ой группы-- ко входу первого элемента задер-, жки i-той группы кроме последней, .30 тактовый вход й-ro счетчика является тактовьм входом устройства, второй вход и выход i-1 элемента И первой группы соединены соответственно с информационным выходом i-1-ro счетчика и информационным входом i.-того счетчика 2) .

Его недостатком является невозможность реализации сочетаний с повторением.

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

Поставленная цель достигается тем, что устройство содержит Н-1 дешифраторов и вторую группу элементов Й, причем первый вход J-того (j =1,..., N-1) дешифратора является установочным входом устройства, второй вход

J-того дешифратора соединен с инфорМационным выходом i-1-го счетчика, а выход подключен к входу сброса

i-1-ro счетчика, первый вход i-1-ro элемента И второй группы соединен с выходом второго элемента задержки

i-1-ой группы, второй вход i-1-ro элемента И второй группы является установочным входом устройства, а выход соединен с тактовым входом

1-го счетчика.

813411

На чертеже показана схема устройства для получения сочетаний из 5 по 3.

Устройство содержит счетчики 1-3, элементы И 4 и 5 первой группы,элементы 6-9 задержки. Элементы И 10 и

11 второй группы, дешифраторы 12 и

13, тактовый вход 14 устройства, установочный вход 15 устройства.

Комбинаторное устройство работает в двух режимах: .сочетаний и сочетаний с повторейиями.

В режиме сочетаний единичный сигнал со входа 15 поступает на первые входы дешифраторов 12 и 13, а также открывает элементы И 10 и 11.

В первом такте работы устройства в режиме сочетаний на тактовый вход счетчика 3 поступает первый тактовый импульс, и счетчики 1-3 устанавливаются, соответственно, в состояния

0-2. На информационные выходы счетчиков 1-3 поступают коды 000, 001 и

010 соответственно. Таким образом, реализуется первое сочетание 012 (табл.1), где номера позиций цифр в сочетании соответствуют номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих счетчиков.

Во втором такте работы устройства в режиме сочетаний на тактовый вход счетчика 3 поступает второй тактовый импульс, и счетчик 3 устанавливается в состояние 3. На информационные выходы счетчиков 1-3 поступают, соответственно, коды 000, 001,011. Таким образом, реализуется второе сочетание 013.

В третьем такте работы устройства в режиме сочетаний реализуется сочетание 014.

В четвертом такте работы устройства в режиме сочетаний на тактовый, вход счетчика 3 поступает четвертый тактовый импульс, и счетчик 3 устанавливается в состояние О. На тактовый вход счетчика 2 с выхода переноса счетчика 3 поступает сигнал переноса, и счетчик 2 устанавливается в состояние 2. Кроме того, единичный сигнал с выхода переноса счетчика 3 через элемент 8 задержки поступает на первый вход элемента 5 и открывает его. Код 010 состояния счетчика 2 с информационного выхода счетчика 2 через элемент И 5 поступает на вход ус ановки счетчика 3 и устанавливает счетчик 3 в состояние 2. Единичный сигнал с выхода элемента 8 задержки через элемент 9. задержки, элемент И 11 поступает на тактовый вход счетчика 3 ° Счетчик 3 устанавливается в состояние 3. На информационные выходы счетчиков 1-3 поступают, соответственно, коды 000,010, 011. Таким образом, в четвертом такте реализуется сочетание 023.

В шестом такте работы устройства в режиме сочетаний реализуется сочетание 034.

В седьмом такте работы устройства в режиме сочетаний на тактовый вход счетчика 3 поступает седьмой тактовый импульс, и счетчик 3 устанавливается в состояние О. На тактовый вход счетчика 2 с выхода переноса счетчика 3 поступает сигнал переноса и счетчик 2 устанавливается в состояние 4. На вход дешифратора 13 с информационного выхода счетчика 2 поступает код 100 состояния счетчика

2. С выхода дешифратора 13 на вход сброса счетчика 2 поступает единич35 ный сигнал. Счетчик 2 устанавливается в состояние О. Сигнал переноса с выхода переноса счетчика 2 поступает на тактовый вход счетчика 1. Счетчик

1 устанавливается в состояние 1.Крорц ме того, единичный сигнал с выхода переноса счетчика 2 через элемент б задержки поступает на первый вход элемента 4. Код 001 состояния счетчика 1 с информационного выхода счетчика 1 поступает на вход установки счетчика 2. Сдетчик 2 устанавливается в состояние 1. Единичный сигнал с выхода элемента 6 задержки через элемент 7 задержки, элемент 10 поступает на тактовый вход счетчика 2,который устанавливается в состояние 2.

Единичный сигнал с выхода элемента 7 задержки и элемента 8 задержки поступает на первый элемент 5. С информационного выхода счетчика 2 через элеЗ5 мент 5 на вход установки счетчика 3 поступает код 010 состояния счетчика

2. Счетчик 3 устанавливается в состояние 2. Единичный сигнал с выхода элемента 8 задержки через элемент 9

4п задержки, элемент И 11 поступает на тактовый вход счетчика 3, который устанавливается в состояние 3. На информационные выходы счетчиков 1-3 поступают, соответственно, коды 001, 010 и 011. Таким образом, реализуется сочетание 123.

В десятом такте работы устройства в режиме сочетаний реализуется последнее сочетание 234.

Работа устройства в режиме сочетаний иллюстрируется табл.1

Таблица 1

012

013

014

023

024

034

813411

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

124

134

10 234

В режиме сочетаний с повторениями 5 нулевой сигнал со входа 15 поступает на первые входы дешийраторов 12 и 13, а также закрывает элементы H 10 и 11 °

B первом такте работы устройства в режиме сочетаний с повторениями на 1О тактовый вход счетчика 3 поступает первый тактовый импульс, а счетчики

1-3 устанавливаются, соответственно, в состояния 0,0 и О. На информацион-. ные выходы счетчиков 1-3 поступают коды 000, 000 и 000 соответственно.

Таким образом, реализуется первое сочетание с повторениями 000 (табл.2), где номера позиций цифр в сочетании с повторениями соответствует номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих счетчиков °

Во втором такте работы устройства в режиме сочетаний с повторениями 2$ на тактовый вход счетчика 3 поступает второй тактовый импульс, и счетчик 3 устанавливается в состояние.1.

На информационные выходы счетчиков

1-3 поступают, соответственно, коды -Зо

000,000 и 001. Таким образом, реализуется второе сочетание с повторениями 001.

В пятом такте работы устройства

Реализуется сочетание с повтоРения- 35 ми 004.

В шестом такте работы устройства в режиме сочетаний с повторениями на тактовый вход счетчика 3 поступает шестой тактовый импульс, и счетчик 3 устанавливается в состояние О. На тактовый вход счетчика 2 с выхода переноса счетчика 3 поступает сигнал переноса, и счетчик 2 устанавливается в состояние 1. Кроме того, единичный сигнал с выхода переноса счетчи- 45 ка 3 через элемент 8 задержки поступает на первый вход элемента И 5 и открывает его. С информационного выхода счетчика 2 на вход установки счетчика 3 поступает код 001 состояния Я} счетчика 2. Счетчик 3 устанавливается в состояние 1. На информационные выходы счетчиков 1-3 поступают соответственно, коды -000, 001 и 001. Таким обРазом, Ре лизу со тание с повто- 5 рениями 011.

В пятнадцатом такте работы устройства в режиме сочетаний с повторениями реализуется сочетание с повторениями 044.

-40

В шестнадцатом такте работы устрой-4 ства в режиме сочетаний с повторениями на тактовый вход счетчика 3 поступает седьмой тактовый импульс, и счетчик 3 устанавливается в состояние О.

На тактовый вход счетчика 2 с выхода б5

Таблица 2 О

19 114

000

001

20 122

21 123

22 124

23" 133

24 134

003

011

144

012

222

013

014

27 223

28 224

29 233

30 234

31 244

022

023

024

033

32 333

33 334

034

044

34 344 переноса счетчика 3 поступает сигнал переноса, и,счетчик 2 устанавливается в состояние О. Сигнал переноса с выхода переноса счетчика 2 поступает на тактовый вход счетчика 1, и счетчик 1 устанавливается в состояние 1.

Кроме того, единичный сигнал с выхода переноса счетчика 2 через элемент б задержки поступает на первый вход элемента И 4 и открывает его. С информационного выхода счетчика 1 через открытый элемент И 4 передачи информации на вход установки счетчика. 2 поступает код 001 состояния счетчика

1. Счетчик 2 устанавливается в состояние 1. Единичный сигнал с выхода элемента б задержки, через элемент 7 задержки и элемент 8 задержки посту.пает на первый вход элемента И 5.С информационного выхода счетчика 2 через элемент И 5 на вход установки счетчика 3 поступает код 001 состояния счетчика 2. Счетчик 3 устанавливается в состояние 1. На информационные выходы счетчиков 1-3 поступают, соответственно, коды 001, 001 и 001 °

Таким .образом, реализуется шестнадцатое сочетание с повторениями 111.

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

Работа устройства в Режиме сочетаний с повторениями. иллюстрируется табл.2

813411

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

112 35 444

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

Составитель Е.Пупырев

Редактор И.Касарда Техред A.Càâêà Корректор М.Шароши, Заказ 772/61 Тираж 745 Подписное

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

113035, Москва, Ж-38, Раушская наб., д.4/5

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная,4

18 113

Известное устройство обеспечивает последовательный перебор сочетаний

С,„ нри всех значениях п, начиная с и единицы. По сравнению с известным, предлагаемое камбинаторное устройство расширяет класс решаемых задач, а именно генерирует не только все С сочетаний, но и все С,„ сочетаний с повторениями кодов состояний и счетчиков с коэффициентами пересчетов, равным m.

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

x1 + х .. x =" и которые известное устройство решать не может °

Комбинаторное устройство, содержащее Н счетчиков, группу элементов

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

И первой группы соединены соответственно с информационным выходом i-1-ro счетчика и информационным входом

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

2 входом устройства, а выход соединен с тактовым входом i-го счетчика.

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

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

9 446057, кл.G 06 F 15/20, 1971.

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

9 374606,. кл.G 06 F 15/20, 1970.