Устройство для решения комбинаторных задач Советский патент 1991 года по МПК G06F7/38 

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

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

На фиг.1 представлена функциональная схема устройства; на фиг 2 - конкретный вариант ее выполнения для с функциональной схемой генератора двоичных последовательностей с неубывающим числом единиц.

Ключом к достижению цели служит тот факт, что смена числа единиц с k-1 на k в выходном коде генератора

двоичных последовательностей, т.е. переход от сочетаний из m no k-1 к сочетаниям из m no k происходит одновременно с установкой значения О на выходе k-ro загрузочного триггера (загрузочного триггера k-ro регистра). Устройство содержит триггер 1, генератор 2 импульсов, генератор 3 m-разрядных двоичных последовательностей с неубывающим числом единиц, включающий тактовый вход 4, m загрузочных триггеров 5 и разрядные триггеры 6, элемент И /, первый 8 и второй 9 коммутаторы, счетчик 10, вход 11 запуска устройства, генератор 13 двоичных последовательностей содержащий, (фиг,2) загрузочные триггеры

ON, XI N3

N

О

о

316

5, разрядные триггеры 6, элементы ИЛ 12, элементы И 13.

Устройство работает следующим образом,,

В исходном состоянии устройства триггер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов заблокирован„ Коммутатор 8 соединяет инверслый выход k-ro загрузочного три тера генератора 3 с вторым входо элемента И, коммутатор 9 соединяет инверсный выход j-ro загрузочного три: гера генерчтора 3 с входом установки . в нулевое состояние

(1- 1,2,...,m-1, ,3,..0,m; k j)

При поступлении сигнала на вход 11 запуска устройства триггер 1 переходит в единичное состояние, генератор 3 дяончньк последовательностей устчнавливае л л в начальное состояние, UPS KoropjM на Bsixoflax загрузоч триггеров присутствуют значения

1, а на выгодах разрядных триггеров

i/trbrrp ,) - значения О (цепи начально, установки не показаны; о С выхода генератора 2 поступают та.1 оиг 1 :; {JtjjTbcn нд тактовый 4 гене,агора 3, который вырабатывает на гг кодах v -.ные кодовые комбинации с неуо% 1 аклциь единиц,, При этом

3; /ЛГлСЦ гЖДОГи ЗЗГОузочного триггера где ,2, „ „ ,m Hj- Lib. ieTCF i на О на прямом и соответственно О на 1 на инверс- ном : , оде) в тот момент, когда начи- нао ся перебор кодовых комбинаций, ч го v,, ответствует началу счета сочетания Г С момента л чменения состоя К

ния k-ro загрузочного триггера с его инверсного вычода через коммутатор 8 на второй вход элемента И поступает сигнал 1, и тактовые импульсы проходят на счетчик 10. Счет заканчивается прк .зменении состояния загрузочного триггера (j k), поскольку в этот момент с его инверсного выхода сигнал 1 через коьтчутатор 9 поступит на вход установки -рпггера 1 в нулевое состояние, В результате в счетчике 10 будет зафиксирован код,

& i равный С с Отметим, что в тече-

i к ние всего периода счета коммутаторы

8 и 9 находятся в фиксированных позициях о

При подключении к элементу И и к входу обнуления триггера 1 соответственно двух загрузочных триггеров с

последовательными номерами k и k+1 в счетчике 10 будет зафиксировано

число

т

тье. биномиальный коэффициент Стс Максимальная вычисляемая сумма биномиальных коэффициентов рав-

inна

I)

Г1

Lm

так как в вычисление не включаются тривиальные коэф0 Уу)

фициенты Ст Ст 1 (известно, что

С 2 ). В качестве коммутато- ров 8 и 9 использованы т-позиционные

т

переключатели 0

В таблице приведены в виде двоичных массивов все 16 состояний генератора 3 для (фиг.2), которые последовательно сменяют друг друга по тактам (левый столбец массива - выходы загрузочных триггеров; остальные элементы,образук ие треугольную матрицу - выходы разрядных триггеров) о Выходы генератора 3 формируются как дизъюнкции значений элементов в разрядных столбцах. Из таблицы РИДНО, что состояние : аждого загрузочного триггера изменяется за время полного цикла только один раз, отмечал переход к началу счета С с чоным k.

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

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

ключей соответственно через первый И и через второй коммутатор - к вхо- коммутатор к второму входу элемента ду обнуления триггера.

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

Состояния

Сочетания I Число сочетаний

ФигЛ