Устройство для вычисления числа сочетаний
Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, решающих вероятностные комбинаторные задачи, связанные определением вероятностей биномиального распределения. Устройство содержит регистры 1,2, 10, 16, 19, блоки 5, 7 вычитания, блок 3 вычитания единицы, умножители 5, 8, 9,20, делитель 13, счетчик 14, схему сравнения 17, блок формирования пачки импульсов, триггер 15, элемент И 18, ключ 11. Расширение функциональных возможностей обусловлено вводом в состав устройства дополнительных блоков: пятого регистра, второго блока вычитания, блока вычитания единицы, второго, третьего и четвертого умножителей, блока формирования пачки импульсов, триггера, элемента И и ключа. 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (si)s G 06 F 15/20
ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ
ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР ) ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (;iNiл 1 Ы9 1Т. ) 1.A моя з
27 22
1 (21) 4758079/24 (22) 10.11,89 (46) 23.12.92. Бюл. М 47 (72) B.À.Ëóêîÿíîâ (56) Авторское свидетельство СССР
N 1259283, кл. G 06 F 15/20, 1985.
Авторское свидетел ьство С СС Р, I
М 1396148, кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ
ЧИСЛА СОЧЕТАНИЙ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, решающих вероятностные комбинаторные задачи, „„ Ц „„1783540 А1 связанные определением вероятностей биномиального распределения. Устройство содержит регистры 1, 2, 10, 16, 19, блоки 5, 7 вычитания, блок 3 вычитания единицы, умножители 5, 8, 9, 20, делитель 13, счетчик
14, схему сравнения 17, блок формирования пачки импульсов, триггер 15, элемент И 18, ключ 11, Расширение функциональных возможностей обусловлено вводом в состав устройства дополнительных блоков: пятого регистра, второго блока вычитания, блока вь1читания единицы, второго, третьего и четвертого умножителей, блока формирования пачки импульсов, триггера, элемента И и ключа, 1 ил.
1783540
Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, решающих вероятные комбинаторные задачи, связанные с определением вероятностей биноминаль- 5 ного распределения, Цель изобретения — расширение функциональных возможностей устройства за счет определения вероятностей биноминального распределения, 10 . Функциональная схема устройства представлена на чертеже.
Устройство содержит регистры 1, 2, блок 3 вычитания единицы, умножитель 4, блок 5 вычитания, блок 6 формирования 15 пачки импульсов, блок 7 вычитания, умножители 8, 9, регистр 10, ключ 11, тактовый генератор 12, делитель 13, счетчик 14; триггер 15, регистр 16, схему сравнения 17, элемент И 18, регистр 19, умножитель 20, вход 20
21 комбинированного параметра и, вход 22 вероятностного параметра р, вход 23 пуска устройства, вход 24 комбинированного параметра К выход 25 числа сочетаний Ср выход 26 вероятности биноминального распределения.р . Блок 3 производит операцию вычитания из единицы вероятного параметра, т.е. (1-р).
Умножитель 4 с накоплением результата производит вычисления числа (1-р)" "= 30
n — k.
- П (1 — р), используя метод итераций, число
i =1 которых определяется длиной пачки импульсов, поступающих от блока 6. 35
Блок 6 формирования пачки импульсов обеспечивается формирование последовательности из (и-Ic) импульсов.
Умножитель 9 с накоплением результата предназначен для вычисления произве- 40
n-k дения р = П р.
I =.1
Устройство работает следующим образом.
Перед началом работы устройства производится запись в регистр 1 значения комбинационного параметра и, в регистр
2 — значения вероятного параметра р, в регистр 19 — значения комбинационного параметра К
Блоки с внутренними элементами памяти приводятся в исходное состояние: умножители 4, 9 с накоплением результата, а также регистр 16 — в состояние 1 (начальный сомножитель), счетчик 14 состояния О, блок
6 — на начало формирования пачки импульсов.
Работа устройства начинается по команде "Пуск", подаваемой на вход 23. По этой команде триггер 15 устанавливается в единичное состояние, и сигнал с его выхода включает тактовый генератор 12. Тактовые импульсы поступают на вход синхронизации блока 6 формирования пачки импульсов и через открытый ключ 11 на счетный вход счетчика 14.
Блок 7 вычитания определяет разность (n — l<), код которой подается на вхОд задания числа импульсов блока 6 формирования пачки импульсов.
Пачка импульсов поступает на вход синхронизации, умножителя 4, По окончании . пачки в блоке 6 вырабатывается сигнал, подаваемый на один из входов элемента И 18, Значение вероятного параметра .р поступает на вход блока 3 вычитания единицы.
Блок вычитания единицы определяет разность (1-р), которая подается на информационный вход умножителя 4. Умножитель 4, управляемый пачкой импульсов, произво.и-k дит вычисление произведения II (1-р) nyi=1 тем (и-k) — кратного умножения на число (1-р) (йа первой операции число(1-р) умножителя на 1).
Умножитель.9 осуществляет k-кратное умножение вероятностного параметра р на себя (на первой итерации параметр р умножается на 1), накапливая тем самым произведение р ..
Счетчик 14 осуществляет счет тактовых импульсов.
Схема сравнения 17 обеспечивает сравнение кода состояния счетчика и кода комбинационного параметра К поступающего из регистра 19, В случае равенства кодов формируется сигнал, который, поступая на запрещающий вход ключа 11, прекращает прохождение импульсов от тактового генератора 12.
Пусть сравниваемые числа не равны.
Тогда код параметра из регистра 1 поступает на вход блока 5 вычитания, на другой вход которого подается код состояния счетчика предыдущей итерации, хранящийся в регистре 10. На выходе блока 5 вычитания формируется разность n-(I-1) (на первой итерации — (n-O)).
Код разности и-(1-1) с выхода блока 5 вычитания поступает на вход умножителя
8, на другой вход которого с выхода регистра 16 подается двоичный код произведе1-1 ния С = П ((и-0-1))/!) (на первой
3 =! итерации.— 1). Умнохситель 8 вычисляет произведение Сл (ii-(1-1)), Код произведения на вход делителя 13, на другой вход которо1783540 го поступает код числа 1 с выхода счетчика
14. Делитель вычисляет частное Сп код
i которого записывается в регистр 16, и может быть снят с выхода 25.
На К-й итерации на выходе счетчика 14 образуется код состояния, соответствующий параметру К в результате чего схема сравнения 17 сформирует сигнал, который, поступая на запрещающий вход ключа 11, прекратит прохождение импульсов от тактового генератора 12 на вход счетчика 14.
Таким образом, в регистре 16 будет накоплено произведение C> .
Сигналы, поступающие с выходов схемы сравнения 17 и блока 6 формирования пачки импульсов на соответствующие входы элемента И, разрешают прохождение импульса от тактового генератора нэ вход синхронизации умножителя 20 и нулевой вход триггера 15. Триггер, устанавливаясь в нулевое состояние, выключает генератор
12, прекращая тем самым формирование импульсов.
Умножитель 20 производит перемножение трех сомножителей С, Р, (1-р)", 25 поступающих на егo информационный входы. На первом этапе определяется произведение С . Р двоичный код которого на втором этапе умножителя на двоичный код числа (1 — р)", Результат работы умножите- 30 ля — двоичный код вероятности биноминального распределения Р = С . р (1-р)" может быть снят с выхода 26 устройства.
Формула изобретения
Устройство для вычисления числа сочетаний, содержащее четыре регистра, первый блок вычитания, первый умножитель, делитель, счетчик, схему сравнения и такто- 40 вый генератор, причем информационные входы первого и второго регистров являются входами комбинационных параметров устройства, выход первого регистра соединен с первым входом первого блока вычита- 45 ния, выход первого блока вычитания соединен с первым входом первогоумножи-. теля, выход первого умнажителя соединен с первым входом делителя, выход делителя соединен с информационным входом треть- 50 его регистра, выход третьего регистра является выходом числа сочетаний устройства и соединен с вторым входом первого умножителя, выход второго регистра соединен с первым входом схемы сравнения. выход счетчика соединен с вторыми входами схемы сравнения и делителя, а также с информационным входом четвертого регистра, выход четвертого регистра соединен с вторым входом первого блока вычитания, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения вероятностей биноминального распределения, оно содержит пятый регистр, триггер, второй блок вычитания, блок вычитания единицы, второй, третий и четвертый умножители, блок формирования пачки импульсов, элемент И, ключ, причем информационный вход пятого регистра является входом вероятностного параметра устройства, выход пятого- регистра соединен с информационным входом второго умножителя и входом блока вычитания единицы, выход блока вычитания единицы соединен с информационным входом третьего умножителя, единичный вход триггера является пусковым входом устройства, выход триггера соединен с управляющим входом тактового генератора, выход тактового генератора соединен с первым входом элемента И, с входами синхронизации блока формирования пачки импульсов и второго умножителя, а также через ключ — с входом счетчика, выходы первого и второго регистров соединены с входами второго блока вычитания, выход второго блока вычитания соединен с входом задания числа импульсов блока формирования пачки импульсов, информационный выход блока формирования. пэчки импульсов соединен с входом синхронизации третьего умножителя, выход окончания пачки блока формирования пачки импульсов соединен с вторым входом элемента И, выход элемента И соединен с нулевым входом триггера и синхронизирующим входом четвертого умножителя, выход схемы сравнения соединен с управляющим входом ключа и третьим входом элемента И, выход третьего регистра соединен с вторым входом первого умножителя и первым информационным входом четвертого умножителя, выходы второго и третьего умножителей соединены соответственно с вторым и третьим информационными входами четвертого умножителя, выход четвертого умножителя является выходом вероятности биноминального распределения устройства.
