Устройство для вычисления комбинаторных функций

 

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

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

Известно устройство для решения комбинаторных задач, содержащее триггер, генератор импульсов, генератор m-разрядных двоичных последовательностей с неубывающим числом единиц, элемент И, первый и второй коммутаторы и счетчик, предназначенное для вычисления и суммирования биномиальных коэффициентов С_m^k. Это устройство принято за прототип изобретения.

Однако устройство-прототип не вычисляет широко используемую комбинаторную функцию - число размещений (упорядоченных сочетаний) из m по k (обозначение A_m^k, также [m] _k). Биномиальный коэффициент и число размещений связаны соотношением А_m^k = C_m^k k ! Цель достигается тем, что в устройство, содержащее генератор импульсов, m-разрядный генератор двоичных последовательностей с неубывающим числом единиц, элемент И, счетчик, первый и второй коммутаторы и триггер, вход установки в единицукоторого является входом запуска устройства, а выход подключен к входу запуска генератора импульсов, причем выход генератора импульсов подключен к первому входу элемента И, выход которого соединен с входом счетчика, инверсный выход каждого i-го загрузочного триггера генератора двоичных последовательностей (i = 1,2, . . . , m) подключен соответственно через первый коммутатор к второму входу элемента И и через второй коммутатор к входу обнуления триггера, введены третий и четвертый коммутаторы и делитель частоты на факториальный коэффициент, каждый k-й выход которого (k<m) подключен через третий коммутатор к тактовому входу генератора двоичных последовательностей, при этом выход генератора тактовых импульсов подключен через четвертый коммутатор к тактовому входу генератора двоичных последовательностей и к входу делителя частоты на факториальный коэффициент.

Делитель частоты на факториальный коэффициент содержит n-1 циклических сдвигающих регистров с межрегистровыми связями (n ! - максимальное значение факториального коэффициента, причем каждый k-й регистр (k = 2,3, . . . . , n) состоит из k разрядных триггеров. При поступлении на вход делителя частоты импульсов с частотой f на выходе k-го регистра образуются импульсы с частотой f/k ! .

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

На фиг. 2 схема устройства конкретизирована для значений m = 4, n = 4, причем делитель 9 частоты изображен на уровне функциональной схемы, а в генераторе двоичных последовательностей выделены группа 13 загрузочных триггеров, к инверсным выходам которых подключены коммутаторы 5 и 6, и группа 14 разрядных триггеров. В качестве коммутатора 10 использован n-позиционный переключатель, в качестве коммутатора 11 - двухпозиционный переклю- чатель.

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

В первом режиме коммутаторы 10 и 11 фиксируются в позиции I (см. фиг. 2), при этом делитель 9 частоты отключен, импульсы с генератора 2 поступают непосредственно на тактовый вход 8 генератора 7 двоичных последовательностей, и устройство работает как устройство-прототип, т. е. вычисляет и суммирует биномиальные коэффициенты.

Во втором режиме коммутатор 11 фиксируется в позиции II, коммутатор 10 - в позиции k I, коммутаторы 5 и 6 - в позициях, при которых к элементу И и к входу обнуления триггера 1 подключены соответственно два загрузочных триггера с последовательными номерами k и k+1 (такое подключение соответствует настройке на вычисление С_m^k в устройстве-прототипе). При поступлении сигнала на вход 12 запуска устройства триггер 1 переходит в единичное состояние, с выхода генератора 2 импульсы частоты f поступают на вход делителя 9 частоты, k-го выхода которого через коммутатор 10 импульсы частоты f/k ! поступают на тактовый вход 8 генератора 7 двоичных последовательностей. С момента t₁ изменения состояния k-го загрузочного триггера с его инверсного выхода через коммутатор 5 на второй вход элемента И подается сигнал "1", и тактовые импульсы частоты f с генератора 2 проходят на счетчик 4. Счет заканчивается при изменении состояния (k+1)-го загрузочного триггера, поскольку в этот момент (t₂) с его инверсного выхода сигнал "1" через коммутатор 6 поступает на вход установки триггера 1 в нулевое состояние. Момент t₂ отделен от момента t₁ числом импульсов C_m^k частоты f/k ! (согласно функционированию устройства-прототипа), следовательно, в момент окончания счета в счетчике 4 зафиксировано С_m^kk ! импульсов частоты f, т. е. значение А_m^k.

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

Признаки, отличающие заявляемое техническое решение от прототипа, не выявлены в других технических решениях при изучении данной (вычислительная техника, специализированные вычислительные устройства) и смежных областей техники и, следовательно, обеспечивают заявляемому решению соответствие критерию "существенные отличия". (56) Липский В. Комбинаторика для программистов. М. : Мир, 1988, с. 39-48.

Авторское свидетельство СССР N 1672466, кл. G 06 F 15/20, 1989.

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОМБИНАТОРНЫХ ФУНКЦИЙ, содержащее генератор импульсов, m-разрядный генератор двоичных последовательностей с неубывающим числом единиц, элемент И, счетчик, первый и второй коммутаторы и триггер, вход установки в "1" которого соединен с входом запуска устройства, выход триггера соединен с входом запуска генератора импульсов, выход которого соединен с первым входом элемента И, выход которого соединен с входом счетчика, i-й инверсный выход генератора двоичных последовательностей с неубывающим числом единиц (где i= 1,2, . . . , m) соединен через первый коммутатор с вторым входом элемента И и через второй коммутатор с входом обнуления триггера, отличающееся тем, что в него введены третий и четвертый коммутаторы и делитель частоты на факториальный коэффициент, j-й выход которого (где j= 1,2, . . . , k< m) через третий коммутатор подключен к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц, выход генератора импульсов через четвертый коммутатор подключен к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц и к входам делителя частоты на факториальный коэффициент.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3