Устройство для вычисления числа сочетаний Советский патент 1992 года по МПК G06F15/20 

(Л

С

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, решающих веро- ятностные комбинаторные задачи, связанные определением вероятностей биномиального распределения. Устройство содержит регистры 1,2, 10, 16, 19, блоки 5, 7 вычитания, блок 3 вычитания единицы, умножители 5, 8, 9,20, делитель 13, счетчик 14, схему сравнения 17, блок формирования пачки импульсов, триггер 15, элемент И 18, ключ 11. Расширение функциональных возможностей обусловлено вводом в состав устройства дополнительных блоков: пятого регистра, второго блока вычитания, блока вычитания единицы, второго, третьего и четвертого умножителей, блока формирования пачки импульсов, триггера, элемента И и ключа. 1 ил.

00

со

СП

ь о

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

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

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

Устройство содержит регистры 1, 2, блок 3 вычитания единицы, умножитель 4, блок 5 вычитания, блок б формирования пачки импульсов, блок 7 вычитания, умножители 8, 9, регистр 10, ключ 11, тактовый генератор 12, делитель 13, счетчик 14, триггер 15, регистр 16, схему сравнения 17, элемент И 18, регистр 19, умножитель 20, вход 21 комбинированного параметра п, вход 22 вероятностного параметра р, вход 23 пуска устройства, вход 24 комбинированного параметра k, выход 25 числа сочетаний С , выход 26 вероятности биноминального распределения pk. Блок 3 производит операцию вычитания из единицы вероятного параметра, т е. (1-р).

Умножитель 4 с накоплением результата производит вычисления числа (1-p)

n-k

П (1-р), используя метод итераций, число

1 1

которых определяется длиной пачки импульсов, поступающих от блока 6.

Блок 6 формирования пачки импульсов обеспечивается формирование последовательности из (n-k) импульсов.

Умножитель 9 с накоплением результата предназначен для вычисления произвеk nfrk дения р - П р.

i 1

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

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

2- значения вероятного параметра р, в регистр 19-значения комбинационного параметра k.

Блоки с внутренними элементами памяти приводятся в исходное состояние: умножители 4, 9 с накоплением результата, а также регистр 1 б - в состояние 1 (начальный сомножитель), счетчик 14 состояния 0, блок 6 - на начало формирования пачки импуль- соа

Работа устройства начинается по команде Пуск, подаваемой на вход 23. По

этой команде триггер 15 устанавливается в единичное состояние, и сигнал с его выхода включает тактовый генератор 12. Тактовые импульсы поступают на вход синхронизации блока б формирования пачки импульсов и через открытый ключ 11 на счетный вход счетчика 14.

Блок 7 вычитания определяет разность (n-l), код которой подается на вход задания

числа импульсов блока 6 формирования пачки импульсов.

Пачка импульсов поступает на вход синхронизации умножителя 4. По окончании пачки в блоке 6 вырабатывается сигнал, подаваемый на один из входов элемента И 18, Значение вероятного параметра р поступает на вход блока 3 вычитания единицы. Блок вычитания единицы определяет разность (1-р), которая подается на информационный вход умножителя 4. Умножитель 4, управляемый пачкой импульсов, произвоn-k

дит вычисление произведения П (1--р)пуi 1

тем (n-k) - кратного умножения на число (1-р) (на первой операции число (1-р) умножителя на 1).

Умножитель 9 осуществляет k-кратное умножение вероятностного параметра р на

себя (на первой итерации параметр р умножается на 1), накапливая тем самым произведение pk.

Счетчик 14 осуществляет счет тактовых импульсов.

Схема сравнения 17 обеспечивает сравнение кода состояния счетчика и кода комбинационного параметра k, поступающего из регистра 19, В случае равенства кодов формируется сигнал, который, поступая на

запрещающий вход ключа 11, прекращает прохождение импульсов от тактового генератора 12.

Пусть сравниваемые числа не равны. Тогда код параметра из регистра 1 постулает на вход блока 5 вычитания, на другой вход которого подается код состояния счетчика предыдущей итерации, хранящийся в регистре 10. На выходе блока 5 вычитания формируется разность п-(1-1) (на первой

итерации - (п-0)).

Код разности п-(Ы) с выхода блока 5 вычитания поступает на вход умножителя 8, на другой вход которого с выхода регистра 16 подается двоичный код произведения Сп 1 П ((n-())/j) (на первой

J-i

итерации - 1). Умножитель 8 вычисляет произведение (п-(1-1)), Код произведения на вход делителя 13, на другой вход которо

го поступает код числа I с выхода счетчика

На К-й итерации на выходе счетчика 14 образуется код состояния, соответствую- щий параметру к, в результате чего схема сравнения 17 сформирует сигнал, который, поступая на запрещающий вход ключа 11, прекратит прохождение импульсов от тактового генератора 12 на вход счетчика 14. Таким образом, в регистре 16 будет накоплено произведение Сп .

Сигналы, поступающие с выходов схемы сравнения 17 и блока 6 формирования пачки импульсов на соответствующие входы элемента И, разрешают прохождение импульса от тактового генератора на вход синхронизации умножителя 20 и нулевой вход триггера 15. Триггер, устанавливаясь в нулевое состояние, выключает генератор 12, прекращая тем самым формирование импульсов,

Умножитель 20 производит перемножение трех сомножителей Сп , Pk, (1-p), поступающих на его информационный входы. На первом этапе определяется произведение Сп . Pk двоичный код которого на втором этапе умножителя на двоичный код числа (1-p). Результат работы умножите- ля - двоичный код вероятности биноминального распределения Pk Сп . pk(1-p) может быть снят с выхода 26 устройства.

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

Устройство для вычисления числа сочетаний, содержащее четыре регистра, первый блок вычитания, первый умножитель, делитель, счетчик, схему сравнения и такто- вый генератор, причем информационные входы первого и второго регистров являются входами комбинационных параметров устройства, выход первого регистра соединен с первым входом первого блока вычита- ния, выход первого блока вычитания соединен с первым входом первого умножителя, выход первого умножителя соединен с первым входом делителя, выход делителя соединен с информационным входом треть- его регистра, выход третьего регистра является выходом числа сочетаний устройства и соединен с вторым входом первого умножителя, выход второго регистра соединен с

0

g

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