Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОМБИНАТОРНЫХ ФУНКЦИЙ
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОМБИНАТОРНЫХ ФУНКЦИЙ

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОМБИНАТОРНЫХ ФУНКЦИЙ

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2006934
Класс(ы) патента: G06F15/20
Номер заявки: 5007487/24
Дата подачи заявки: 01.07.1991
Дата публикации: 30.01.1994
Заявитель(и): Владимирский политехнический институт
Автор(ы): Романов В.Ф.; Туляков В.С.
Патентообладатель(и): Романов Владимир Федорович; Туляков Валерий Станиславович
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации.
Известно устройство для решения комбинаторных задач, содержащее триггер, генератор импульсов, генератор m-разрядных двоичных последовательностей с неубывающим числом единиц, элемент И, первый и второй коммутаторы и счетчик, предназначенное для вычисления и суммирования биномиальных коэффициентов Сmk. Это устройство принято за прототип изобретения.
Однако устройство-прототип не вычисляет широко используемую комбинаторную функцию - число размещений (упорядоченных сочетаний) из m по k (обозначение Amk, также [m] k). Биномиальный коэффициент и число размещений связаны соотношением
Аmk = Cmk ˙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 (такое подключение соответствует настройке на вычисление Сmk в устройстве-прототипе). При поступлении сигнала на вход 12 запуска устройства триггер 1 переходит в единичное состояние, с выхода генератора 2 импульсы частоты f поступают на вход делителя 9 частоты, k-го выхода которого через коммутатор 10 импульсы частоты f/k ! поступают на тактовый вход 8 генератора 7 двоичных последовательностей. С момента t1 изменения состояния k-го загрузочного триггера с его инверсного выхода через коммутатор 5 на второй вход элемента И подается сигнал "1", и тактовые импульсы частоты f с генератора 2 проходят на счетчик 4. Счет заканчивается при изменении состояния (k+1)-го загрузочного триггера, поскольку в этот момент (t2) с его инверсного выхода сигнал "1" через коммутатор 6 поступает на вход установки триггера 1 в нулевое состояние. Момент t2 отделен от момента t1 числом импульсов Cmk частоты f/k ! (согласно функционированию устройства-прототипа), следовательно, в момент окончания счета в счетчике 4 зафиксировано Сmk˙k ! импульсов частоты f, т. е. значение Аmk.
Заявляемое техническое решение отличается от прототипа тем, что содержит делитель частоты на факториальный коэффици- ент, третий и четвертый коммутаторы, подключенные по описанной выше схеме, что обеспечивает соответствие критерию "новизна". При этом в дополнение к функциям прототипа оно приобретает новые функциональные возможности.
Признаки, отличающие заявляемое техническое решение от прототипа, не выявлены в других технических решениях при изучении данной (вычислительная техника, специализированные вычислительные устройства) и смежных областей техники и, следовательно, обеспечивают заявляемому решению соответствие критерию "существенные отличия". (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) через третий коммутатор подключен к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц, выход генератора импульсов через четвертый коммутатор подключен к тактовому входу генератора двоичных последовательностей с неубывающим числом единиц и к входам делителя частоты на факториальный коэффициент.