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

(53)5 6 06 Р 7/5 ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ИСАНИЕ ИЗОБРЕТЕНИ 2 ЕЛ слительано для ель изо- нальных АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) 1. Авторское свидетельство СССМ 1314339, кл. 6 06 Е 7/58, 1986.2, Авторское свидетельство СССМ 1693605, кл. 6 06 Е 7/58, 1988.(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИС(57) Изобретение относится к вычиной технике и может быть использовформирования случайных чисел. Цбретения в . расширение функцио Изобретение относится к вычислительной технике и может быть использовано дляформирования случайных чисел с отрица тельным биномиальным распределением,Известен генератор случайных чисел,содержащий последовательно соединенные ПИ, датчик чисел с равномерным распределением и сумматор, другой входкоторого через регистр соединен с выходомдатчика 1),Недостатком устройсительно узкие функцисти.Наиболее близким по технической сущности к предлагаемому является генераторслучайных чисел, содержащий два элементазадержки, первый счетчик, выход которогосоединен с информационным входом регистра, выход которого является выходом генератора, деа элемента ИЛИ.одновибратор, датчик равномерно распределенных случайных чисел, блок логарифмирования, блок деления, блок выделения возможностей генератора за счет формирования чисел с отрицательным биномиальным распределением, Генератор содержит генератор тактовых импульсов, счетчики, блок вычисления вероятностей, накапливающие сумматоры, регистр сдвига, блок вычисления чисел с логарифмическим распределением, регистр, элемент ИЛИ, датчик случайных чисел с распределением Пуассона, блок сравнения, одновибратор, элементы задержки, дешифратор и датчик равномерно распределенных случайных чисел, 1 ил. целой части, сумматор, накапливающий сумматор, схему сравнения, два ключа и третий элемент задержки, причем выход первого элемента ИЛИ соединен с входом одновибратора, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с входом запуска датчика равномерно распределенных случайных чисел, выход которого через первый блок логарифмирования соединен с входом делимого блока деления, вход делителя которого является входом задания константы. выход блока деления через блок выделения целой части соединен с первым входом сумматора, второй вход которого является входом единицы генератора, выход сумматора соединен с информационным входом накапливающего сумматора. выход которого соединен с первым входом схемы сравнения, второй вход которой является входом задания числа констант генератора, выход "Больше" схемы сравнения соединен с информационным входом первого ключа. уп 1777136равляющий вход. которого соединен с управляющим входом второго ключа и соединен с выходом первого элемента задержки, вход которого соединен с входом второго элемента задержки и счетным входом счетчика и подключен к выходу второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента задержки, вход которого соединен с выходом второго ключа, информационный вход которого соединен с выходом "Меньше или равно" схемы сравнения, выход первого ключа соединен с входом записи регистра и вторым входом первого элемента ИЛИ, выход второго элемента задержки соединен с входом синхронизации накапливающего сумматора, вход обнуления которого соединен с выходом первого ключа 2,Недостатком устройства являются относительно узкие функциональные возможности, обусловленные тем, что устройство позволяет формировать числа с биномиальным распределением, но не позволяет формировать числа с отрицательным биномиальным распределением,Цель изобретения - расширение функциональных возможностей генератора. Поставленная цель достигается тем, что, в генератор, содержащий элемент ИЛИ, первый счетчик, первый накапливающий сумматор. одновибратор, блок сравнения, регистр, выход которого является выходом генератора, датчик равномерно распределенных случайных чисел и первый, второй и третий элементы задержки, при этом выход третьего элемента задержки соединен с первым. входом элемента ИЛИ, второй вход которого является входом запуска генератора, введены ГТИ, вход которого соединен с вторым входом элемента ИЛИ, а выход соединен с информационным входом первого счетчика и с входом первого элемента задержки, выход которого соединен с управляющим входом первого накапливающего сумматора, дешифратор, выход которого соединен с входом второго элемента задержки и с входом опроса датчика равномерно распределенных случайных чисел, блок вычисления вероятностей, вход которого соединен с входом дешифратора и с выходом первого счетчика, а выход соединен с информационным входом первого накапливающего сумматора, последовательно соединенные регистр сдвига, информационный вход которого соединен с выходом первого накапливающего сумматора, блок вычисления чисел с логарифмическим распределением, второй вход которого соединен с выходом датчика равномерно 5 10 15 20 25 30 35 40 50 55 распределенных случайных чисел, и второй накапливающий сумматор, выход которого соединен с информационным входом регистра, управляющий вход которого соединен с, входом третьего элемента задержки и с выходом одновибратора, датчик случайных чисел с распределением Пуассона, вход которого соединен с выходом элемента ИЛИ, а выход - с первым входом блока сравнения, выход которого соединен с входом одновибратора, последовательно соединенные четвертый элемент задержки, вход которого соединен с выходом второго элемента задержки. а выход соединен с входами установки в ноль первого счетчика, первого накапливающего сумматора и регистра сдвига, и второй счетчик, вход установки в ноль которого соединен с выходом третьего элемента задержки, а выход - с вторым входом блока сравнения, при этом управляющий вход и вход установки в ноль второго накапливающего сумматора соединены соответственно с выходом второго элемента задержки и третьего элемента задержки.Анализ научно-технической литературы показал, что указанная совокупность существенных признаков до даты подачи заявки известна не была, Поэтому предложение является новым.Кроме того, цель изобретения достигается именно всей совокупностью вновь введенных признаков, которая в предложенном виде в известных публикациях не использовалась. Это подтверждает наличие существенных отличий. На чертеже представлена электрическая структурная схема генератора случайных чисел.Генератор случайных чисел содержит последовательно соединенные ГТИ 1, первый счетчик 2, блок 3 вычисления вероятностей, первый накапливающий сумматор 4, регистр 5 сдвига, блок 6 вычисления чисел с логарифмическим распределением, второй накапливающий сумматор 7 и регистр 8. последовательно соединенные элемент ИЛИ 9, вход которого объединен с входом ГТИ 1. датчик 10 случайных чисел с распределением Пуассона, блок 11 сравнения, одновибратор 12, выход которого соединен с управляющим входом регистра 8, и третий элемент задержки 13, выход которого соединен с другим входом элемента ИЛИ 9. последовательно соединенные дешифратор 14, вход которого соединен с выходом первого счетчика 2, и датчик 15 равномерно распределенных случайных чисел, выход которого соединен с другим входом блока б, 1777136последовательно соединенные второй элемент задержки 16, вход которого соединен с выходом дешифратора 14. четвертый элемент задержки 17, выход которого соединен с входами установки в ноль первого счетчика 2, первого накапливающего сумматора 4 и регистра 5 сдвига, и второй счетчик 18, вход установки в ноль которого соединен с входом установки в ноль второго накапливающего сумматора 7 и с выходом третьего элемента задержки 13, з выход - с другим входом блока 11 сравнения, а также первый элемент задержки 19, вход которого соединен с выходом ГТИ 1, а выход- с управляющим входом первого накапливающего сумматора 4,Блоки 3 и 6 выполнены в виде ПЗУ, работающих в режиме считывания. Информация, достаточная для их программирования, приведена ниже. Датчик 10 в частном случае может быть выполнен в виде последовательно соединенных циклического счетчика и ПЗУ с занесенной в него по соответствующим адресам таблицы чисел с пуассоновским распределением, Программирование может быть проведено и по результатам реального моделирования, Остальные блоки являются стандартными блоками вычислительной техники.Генератор случайных чисел работает следующим образом.В основу работы генератора положен известный способ формирования случайных чисел с отрицательным биномиальным распределением, по которому формируют сумму чисел с логарифмическим распределевием, количество которых является случайным и подчиняется распределению Пуассона (Справочник по теории вероятностей и математической статистики. - МНаука, 1985, с. 111),Этот способ реализуется следующим образом.По импульсу запуска, поступающему на вход ГТИ 1, последний запускается, что приводит к потзктному заполнению первого счетчикз 2. При каждом изменении состояния первого счетчика 2 в бкоке 3 вычисляют(1 - Р)ся вероятности Р(К) = -- - - - - ; (где К - 1,Ки Р2 - текущее состояние счетчика), которые накапливаются в первом накапливающем сумматоре 4. При этом каждое промежуточное значение суммы заносится последовательно в ячейки регистра 5 сдвига,Таким образом, в ячейках регистра 5 заносятся значения функции логарифмического распределения (там же, с, 115). Дешифратор 14 настроен на некоторое1520304050 55 срабатывания дешифратора 14, и сигнал свыхода датчика 15 образуют адресный код для блока б. Все возможные сочетания этих сигналов имеют соответствующее решение, соответствующее значению аргумента функции распределения, при котором она наиболее близка к величине гЭто позволяет запрограммировать блок 6 заранее и испольэовать его в виде датчика чисел с логарифмическим распределением, сумма которых накапливается во второмсумматоре-накопителе 7. После поступления во второй накапливающий сумматор 7 очередного случайного числа первый счетчик 2, первый накапливающий сумматор 4 ирегистр 5 обнуляются, а описанные вышепроцессы по формированию случайных чисел с логарифмическим распределением повторяются.Кроме того, каждое срабатывание дешифратора 14 фиксируется вторым счетчиком 18, состояние которого сравнивается в блоке 11 сравнения со случайным числом, имеющим распределение Пуассона, которое сформировано датчиком 10, При превышении числа на выходе второго счетчика 18числа на выходе датчика 10 срабатываетблок 11, в результате чего одновибратор 12 вырабатывает импульс, по которому результирующий сигнал (очередное случайное число с отрицательным биномиальнымраспределением) записывается в регистр 8, вновь происходит опрос датчика 10 и повторение описанных выше процессов.Таким образом, благодаря введениюдополнительных блоков и связей существенно расширяются функциональные возможности устройства, поскольку оно позволяет формировать случайные числа с отрицательным биномиальным распределением.Ф о рмул а и зоб рете н и я Генератор случайных чисел, содержащий первый счетчик, первый нзкапливающий сумматор, три элемента задержки,предельное число значений функции логарифмического распределения. При срабатывании дешифратора 14 происходит очередной опрос датчика 15, который выраба тывает число г - возможное значение случайного числа с равномерным распределением,После малой задержки во втором элементе задержки на время срабатывания датчика 15 сформированный сигнал ф с выхода бло ка 6 поступает на вход второго накапливающего сумматора 7. Значение ф формируется в блоке б, выполненном в виде ПЗУ.Полный набор значений функции распределения, сформированный к моментуодновибратор, блок сравнения, регистр, датчик равномерно распределенных случайных чисел и элемент ИЛИ, первый вход которого является входом запуска генератора, выходом которого является выход регистра, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет формирования чисел с отрицательным биномиальным распределением, в него введены узел.вычисления вероятности, выполненный в виде первого блока постоянной памяти, второй накапливающий сумматор, узел формирования чисел с логарифмическим распределением. выполненный в виде второго блока постоянной памяти, регистр сдвига, четвертый элемент задержки, датчик случайных чисел с распределением Пуассона, второй счетчик, дешифратор и генератор тактовых импульсов, вход запуска которого соединен с входом запуска генератора, а выход подключен к информационному входу первого счетчика и через первый элемент задержки - к тактовому входу первого накапливающего сумматора, выход которого подключен к информационному входу регистра сдвига, выход которого соединен с первым адресным входом второго блока постоянной памяти, выход которого подключен к информационному входу второго накапливающего сумматора, выход которого соединен с информационным входом регистра, выход элементе ИЛИ подключен к входу запуска датчика случайных чисел с распреде лением Пуассона, выход которого соединенс первым входом блока сравнения, выход "Больше" которого через одновибратор подключен к входу синхронизации регистра и через второй элемент задержки - к второ му входу элемента ИЛИ и к обнуляющимвходам второго накапливающего сумматора и второго счетчика, выход которого подключен к второму входу блока сравнения, выход первого счетчика соединен с адресным вхо дом второго блока постоянной памяти и свходом дешифратора, выход которого подключен к входу запуска датчика равномерно распределенных случайных чисел и через третий элемент задержки - к входу синхро низации второго накапливающего сумматора и к входу четвертого элемента задержки, выход которого соединен со счетным входом второго счетчика и с входами обнуления регистра сдвига, первогосчетчика и первого 25 накапливающего сумматора, информацион, ный вход которого подключен к выходу первого блока постоянной памяти, выход датчика равномерно распределенных случайных чисел подключен к второму адресно му входу второго блока постоянной памяти,1777136 Редактор Т.Иванова Корректор П,Гереш ат "Патент", г. Ужгород. ул,Гагарина, 1 дательский роизводсте аэ 4122ВНИИПИ Госуда Составитель. В.башлыковТехред М.Моргентал Тираж Подписноенного комитета по изобретениям и открытиям при ГКНТ С 3035, Москва, Ж, Раушская наб., 4/5