Генератор случайных чисел

 

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

СО 03 СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si>s G 06 F 7/58

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4856331/24 (22) 06.08.90 (46) 23.11.92. Бюл. ¹ 43 (72) В.Н.Башлыков и Э.В.Борисов (56) 1. Авторское свидетельство СССР

N 1314339, кл. G 06 F 7/58, 1986.

2. Авторское свидетельство СССР № 1693605, кл. G 06 F 7/58, 1988. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано для формирования случайных чисел. Цель изобретения —. расширение функциональных

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

Известен генератор случайных чисел, содержащий последовательно соединенные ГТИ, датчик чисел с равномерным распределением и сумматор, другой вход которого через регистр соединен с выходом датчика (1).

Недостатком устройства являются относительно узкие функциональные возможности.

Наиболее близким по технической сущности к предлагаемому является генератор случайных чисел, содержащий два элемента задержки, первый счетчик, выход которого соединен с информационным входом регистра, выход которого является выходом генератора, два элемента ИЛИ. одновибратор, датчик равномерно распределенных случайных чисел, блок логарифмирования, блок деления, блок выделения Ы, 1777136 А1 возможностей генератора за счет формирования чисел с отрицательным биномиальным распределением, Генератор содержит генератор тактовых импульсов, счетчики, блок вычисления вероятностей, накапливающие сумматоры, регистр сдвига, блок вычисления чисел с логарифмическим распределением, регистр, элемент ИЛИ, датчик случайных чисел с распределением

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

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

"Больше" схемы сравнения соединен с информационным входом первого ключа. уп1777136 равляющий вход. которого соединен с управляющим входом второго ключа и соединен с выходом первого элемента задержки, вход которого соединен с входом второго элемента задержки и счетным входом счетчика и подключен к выходу второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента задержки, вход которого соединен с выходом второго ключа, информационный вход которого соединен с выходом "Меньше или равно" схемы сравнения, выход первого ключа соединен с входом записи регистра и вторым входом первого элемента ИЛИ, выход второго элемента задержки соединен с входом синхронизации накапливающего сумматора, вход обнуления которого соединен с выходом первого ключа (2), Недостатком устройства являются относительно узкие функциональные возможности, обусловленные тем, что устройство позволяет формировать числа с биномиальным распределением, но не позволяет формировать числа с отрицательным биномиальным распределением, Цель изобретения — расширение функциональных возможностей генератора.

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

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

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

Анализ научно-технической литературы показал, что указанная совокупность существенных признаков до даты подачи заявки известна не была, Поэтому предложение является новым.

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

На чертеже представлена электрическая структурная схема генератора случайных чисел.

Генератор случайных чисел содержит последовательно соединенные ГТИ 1, первый счетчик 2, блок 3 вычисления вероятностей, первый накапливающий сумматор 4, регистр 5 сдвига, блок 6 вычисления чисел с логарифмическим распределением, второй накапливающий сумматор 7 и регистр 8. последовательно соединенные элемент ИЛИ

9, вход которого объединен с входом ГТИ 1. датчик 10 случайных чисел с распределением Пуассона, блок 11 сравнения, одновибратор 12, выход которого соединен с управляющим входом регистра 8, и третий элемент задержки 13, выход которого соединен с другим входом элемента ИЛИ 9. последовательно соединенные дешифратор

14, вход которого соединен с выходом первого счетчика 2, и датчик 15 равномерно распределенных случайных чисел, выход которого соединен с другим входом блока 6.

1777136 последовательно соединенные второй элемент задержки 16, вход которого соединен с выходом дешифратора 14. четвертый элемент задержки 17, выход которого соединен с входами установки в ноль первого счетчика 2, первого накапливающего сумматора 4 и регистра 5 сдвига, и второй счетчик 18, вход установки в ноль которого соединен с входом установки в ноль второго накапливающего сумматора 7 и с выходом третьего элемента задержки 13, а выход — с другим входом блока 11 сравнения, а также первый элемент задержки 19, вход которого соединен с выходом ГТИ 1, а выход- с управляющим входом первого накапливающего сумматора 4.

Блоки 3 и 6 выполнены в виде ПЗУ, работающих в режиме считывания. Информация, достаточная для их программирования, приведена ниже. Датчик 10 в частном случае может быть выполнен в виде последовательно соединенных циклического счетчика и ПЗУ с занесенной в него по соответствующим адресам таблицы чисел с пуассоновским распределением. Программирование может быть проведено и по результатам реального моделирования. Остальные блоки явля ются стандартными блоками вычислительной техники.

Генератор случайных чисел работает следующим образом.

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

Пуассона (Справочник по теории вероятностей и математической статистики.— М„Наука, 1985, с. 111).

Этот способ реализуется следующим образом.

По импульсу запуска, поступающему на вход ГТИ 1, последний запускается, что приводит к потактному заполнению первого счетчика 2. При каждом изменении состояния первого счетчика 2 в блоке 3 вычисляют(1 - P) ся вероятности Р(К) = — — - — - —; (где К - 1, KIAP

2... — текущее состояние счетчика), которые накапливаются s первом накапливающем сумматоре 4. При этом каждое промежуточное значение суммы заносится последовательно в ячейки регистра 5 сдвига.

Таким образом, в ячейках регистра 5 заносятся значения функции логарифмического распределения (там же, с, 115). Дешифратор 14 настроен на некоторое

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

Это позволяет запрограммировать блок

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

Кроме того, каждое срабатывание дешифратора 14 фиксируется вторым счетчиком 18, состояние которого сравнивается в блоке 11 сравнения со случайным числом, имеющим распределение Пуассона, которое сформировано датчиком 10, При превышении числа на выходе второго счетчика 18 числа на выходе датчика 10 срабатывает блок 11, в результате чего одновибратор 12 вырабатывает импульс, по которому результирующий сигнал (очередное случайное число с отрицательным биномиальным распределением) записывается в регистр 8, вновь происходит опрос датчика 10 и повторение описанных выше процессов.

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

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

Генератор случайных чисел, содержащий первый счетчик, первый накапливающий сумматор, три элемента задержки, предельное число значений функции логарифмического распределения. При срабатывании дешифратора 14 происходит очередной опрос датчика 15, который выраба5 тывает число r — возможное значение случайного числа с равномерным распределением.

После малой задержки во втором элементе задержки на время срабатывания датчика

15 сформированный сигнал ф с выхода бло10 ка 6 поступает на вход второго накапливающего сумматора 7. Значение ф формируется в блоке 6, выполненном в виде ПЗУ.

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

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

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

25 накапливающего сумматора, информацион. ный вход которого подключен к выходу пер вого блока постоянной памяти, выход датчика равномерно распределенных случайных чисел подключен к второму адресно30 му входу второго блока постоянной памяти.

1777136

Составитель. В.башлыков

Редактор Т.Иванова Техред М.Моргентал КоРРектоР П.Гереши

Заказ 4122 Тираж . Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035. Москва, Ж-35. Раушская наб.. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород. ул,Гагарина, 101