Комбинаторное устройство Советский патент 1981 года по МПК G06F7/00 

1

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

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

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

Наиболее близким по технической сущности и достигаемому результату является комбинаторное устройство содержащее N счетчиков, группу элементов И, М -1 групп элементов задержки, причем выход переноси t-Toro (i 2,.,.,N) счетчика подключен к тактовому входу t 1 счетчика и через первый элемент задержки 1-1 группы - к первому входу 1-1 элемента И первой группы и через второй элемент задержки i-1-бй груйпы - ко входу первого элемента задер жки г-той группы кроме последней,

тактовый в.ход Н-го счетчика является ТАКТОВОМ входом устройства, второй вход и выход i-1 элемента И первой группы соединены соответственно с информационным выходом {-1--ГО счетчика и информационным входом 1-того счетчика f2.

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

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

Поставленная цель достигается тем, что устройство содержит N-1 дешифра5торов и вторую группу элементов И, причем первый вход j-того (j 1,..., N-1) дешифратора является установочным входом устройства, второй вход J-Toro д&1Шфратора соединен с инфор0мационным выходом 1-1-го счетчика, а выход подключен к входу сброса i-1-го счетчика, первый вход 1-1-г6 элемента И второй группы соединен с

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

0 ,-го счетчика.

На чертеже показана схема устройства для получения сочетаний из 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 устанавливается в состояние 0. На тактовый вход счетчика 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 устанавливается в состояние 0. На тактовый вход счетчика 2 с выхода переноса счетчика 3 поступает сигнал переноса и счетчик 2 устанавливается в состояние 4. На вход дешифратора 13 с информационного выхода счетчика 2 поступает код 100 состояния счетчика 2. С выхода дешифратора 13 на вход сброса счетчика 2 поступает единичный сигнал. Счетчик 2 устанавливается в состояние О. Сигнал переноса с выхода переноса счетчика 2 поступает на тактовый вход счетчика 1. Счетчик 1 устанавливается в состояние 1.Кроме того, единичный сигнал с выхода переноса счетчика 2 через элемент б задержки поступает на первый вход элемента 4. Код 001 состояния счетчика 1 с информационного выхода счетчика 1 поступает на вход установки счетчика 2. Сдетчик 2 устанавливается в состояние 1. Единичный СИГНсШ

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

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

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

Таблица

012

013

014

023

024

034

123 Продолжение табл. 1 8124 9134 10 234 В режиме сочетаний с повторениями нулевой сигйал со входа 15 поступает на первые входы дешифраторов 12 и 13 а также закрывает элементы И 10 и 11 В первом такте работы устройства в режиме сочетаний с повторениями на тактовый вход счетчика 3 поступает первый тактовый импульс, а счетчики 1-3 устанавливаются, соответственно, в состояния 0,0 и 0. На информационные выходы счетчиков 1-3 поступают коды 000, обо и 000 соответственно. Таким образом, реализуется первое сочетание с повторениями 000 (табл.2 где номера позиций цифр в сочетании с повторениями соответствует номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих счетчиков. Во втором такте работы устройства в режиме сочетаний с повторениями на тактовый вход счетчика 3 поступает второй тактовый импульс, и счетчик 3 устанавливается в состояние 1. На информационные выходы счетчиков 1-3 поступают, соответственно, кода 000,000 и 001. Таким образом, реализуется второе сочетание с повторениями 001. В пятом такте работы устройства реализуется сочетание с повторениями 004. В шестом такте работы устройства в режиме сочетаний с повторениями на тактовый вход счетчика 3 поступает шестой тактовый импульс, и счетчик 3 устанавливается в состояние О. На тактовый вход счетчика 2 с выхода переноса счетчика 3 поступает сигнал переноса, и счетчик 2 устанавливается в состояние 1. Кроме того, единичный сигнал с выхода переноса счетчика 3 через элемент 8 задержки поступа ет на первый вход элемента И 5 и открывает его. С информационного выхода счетчика 2 на вход установки счетчика 3 поступает код 001 состояния счетчика 2. Счетчик 3 устанавливается в состояние 1. На информационные выхо ды счетчиков 1-3 поступают соответственно, коды -000, 001 и 001. Таким образом, реализуется сочетание с повторениями 011. В пятнадцатом такте работы устройства в режиме сочетаний с повторениями реализуется сочетание с повторениями 044. В.шестнадцатом такте работы устрой ства в режиме сочетаний с повторениями на тактовый вход счетчика 3 поступает седьмой тактовый импульс, и счет чик 3 устанавливается в состояние 0. На тактовый вход счетчика 2 с выхода переноса счетчика 3 поступает сигнгш переноса, и.счетчик 2 устанавливается в состояние О. Сигнгш переноса с выхода переноса счетчика 2 поступает на тактовый вход счетчика 1, и счетчик 1 устанавливается в состояние 1. Кроме того, единичный сигнал с выхода переноса счетчика 2 через элемент 6 задержки поступает на первый вход элемента И 4 и открывает его. С информационного выхода счетчика 1 через открытый элемент И 4 передачи информации на вход установки счетчика 2 поступает код 001 состояния счетчика 1. Счетчик 2 устанавли вается в состояние 1. Единичный сигнал с выхода элемента 6 задержки, через элемент 7 задержки и элемент8 задержки поступает на первый вход элелданта И 5.С информационного выхода счетчика 2 через элемент И 5 на вход установки счетчика 3 поступает код 001 состояния счетчика 2. Счетчик 3 устанавливается в состояние 1. На информационные выхода счетчиков 1-3 поступают, соответственно, коды 001, 001 и 001. Таким -образом, реализуется шестнадцатое сочетание с повторениями 111, В тридцать пятом такте работы устройства в режиме сочетаний с повторениями реализуется сочетание с повторениями 444. Работа устройства в режиме сочетаний с повторениями, иллюстрируется табл.2 . Та. блица 2 о

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

17112 35 444

18113

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

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

х- ч- x,j . . . х„ - п

которые известное устройство решать не может.

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

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

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

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

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

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

1.Авторское свидетельство СССР № 446057, кл.б Об F 15/20, 1971.

2.Авторское свидетельство СССР 374606, кл.С 06 F 15/20, 1970.