Генератор случайных чисел
Иллюстрации
Реферат
щ 590790
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВЙДЕТЕЛЬСТВУ
Союз Сенатских
Социалистических
Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 11.09,75 (21) 2172038/18-24 с присоединением заявки № (23) Приоритет (51) М. Кл. G )7(Il5/00
G 06F 1/02
Государственный комитет
Совета Министров СССР по делам изобретений (43) Опубликовано 30.01.78. Бюллетень ¹ 4 (53) УДК 681.325(088.8) и открытий (45) Дата опубликования описания 13.02.78 (72) Автор изобретения
А. A. Коорт (71) Заявитель (54) ГЕНЕРАТОР СЛУ 1АЙИЫХ ЧИСЕЛ
Изобретение относится к области вычислительной техники и Mo?KcT найти применение при моделировании марковской последовательности слу гайных чисел с гамма-распределением.
Известны генераторы случайных чисел.
Один из известных генераторов случайных чисел содер?кит регистр сдвига, генератор случайных символов, генератор тактовых импульсов, вероятностный (1, m)-полюсник, элемент ИЛИ и элементы И. Однако этот генератор не позволяет получить марковские последовательности случайных чисел с одномерным распределением вероятности, отличным от распределения Бернулли (1).
Другой нз известных генераторов случайных чисел содср?кит источник случайных импульсов, блок формирования импульсов, фильтр низких частот, электронный ключ, амплитудный селектор, многофазный ждущий мультивибратор, блоки памяти, блок управления и матричный переключатель. Однако этот генератор не позволяет получить случайные числа с точно заданным одномерным распределением вероятности, а может лишь аппроксимировать заданное точное распределение вероятности с помощью фильтра низких частот и матричного переключателя (2).
Наиболее близким техническим реш нием к данному изобретению является генератор случайных чисел, содержан,пй первый умножитель, выход которого является выходом генератора, первый вход соединен с выходом первого датчика чисел, а второй вход — с выходом блока последовательного суммирования, псрвь1й вход которого соединен с выходом блока сравнения, входы которого подключены соответственно к выходам первого блока памяти и счетчика, вход которого сое10 дпнен с выходом генератора импульсов и со входом датчика нормальных случайных чисел (3).
Хотя этот генератор последовательности случайных чисел основан на точных зависи15 мостях мсжду распределениями исходных и вь.раб",òывае:1ых случайных чисел, его недостаток заключастся в том, что он вырабатывает только некоррелированные между собой случайные числа. Это обстоятель20 ство ограничивает область применения генератора, поскольку усложнение задач, решаемых методом цифрового моделирования и методом статистических испытаний, требует не только генерирования последовательностей случайных чисел с распределениями, более сложнымн по сравнению с равномерным или нормальным распределением, но и с определенными и причем регулируемыми корреляционными связями между числами последовательности.
590790
Целью изобретения является расширение функциональных возможностей генератора за счет получения марковской последовательности случайны.; чисел с гамма-распределением.
Для достижения поставленной цели датчик дополнительно содержит второй умножитель, первый сумматор, первый квадратор, элемент задер>кки, второй 610I< памяти, третий умножитель, блок извлечения квадратного корня, второй сумматор, второй датчик чисел, инвертор, второй квадратор и третий датчик чисел, выход которого соединен с первым входом второго умножителя и через второй квадратор и инвертор — с первым входом второго сумматора, второй вход которого подключен к выходу второго датчика чисел, а выход через блок извлечения квадратного корня — к первому входу третьего умножителя, выход которого соединен с первым входом первого сумматора, а второй вход через второй блок памяти и элемент задер>кки — с выходом первого сумматора и входом первого квадратора, выход которого соединен со вторым входом блока последовательного суммирования, а второй вход первого сумматора — с выходом второго умножителя, причем второй вход второго умножнтеля соединен с выходом датчика нормальных случайных чисел.
Блок-схема генератора приведена на чертеже.
Генератор:содержит генератор 1 импульсов, датчик 2 нормальных случайных чисел, счетчик 3, первый квадратор 4, блок 5 последовательного суммирования, первый умножитель б, второй умножитель 7, первый сумматор 8, второй блок 9 памяти, элемент 10 задержки, третий умножитель 11, третий датчик 12 чисел, второй квадратор 13, инвертор 14, второй сумматор 15, блок 1á извлечения квадратного корня, второй датчик 17 чисел, первый блок
18 памяти, блок 19 сравнения, первый датчик
20 чисел и выходную клемму 21.
Выход генератора 1 импульсов соединен со входами датчика 2 нормальных случайных чисел и счетчика 3. Выход датчика 2 нормальных случайных чисел соединен со вторым входом второго умножителя 7, выход которого соединен со вторым входом первого сумматора 8. Выход первого сумматора 8 подключен ко входу первого квадратора 4, выход которого — ко второму входу блока 5 последовательного суммирования. Выход блока 5 последовательного суммирования соединен со вторым входом первого умножителя б, выход которого соединен с выходной клеммой
21. Выход первого квадратора 8 соединен также через последовательно соединенные второй блок 9 памяти и элемент 10 задержки со вторым входом третьего умножителя 11, выход которого соединен с первым входом первого сумматора 8. Выход третьего датчика 12 чисел присоединен к первому входу второго умножителя 7 и через последовательно соединенные второй квадра.ор 13 и инвертор
15 0
З0
14 — к первому входу второго сумматора 15.
Ко второму входу второго сумматора 15 присоединен выход второго датчика 17 чисел.
Выход второго сумматора 15 через блок 1б извлечения квадратного корня соединен с первым входом третьего умножителя 11. Выход счетчика 3 соединен с одним из входов блока 19 сравнения, к другому входу которого подключен выход первого блока 18 памяти, а к выходу — первый вход блока 5 последовательного суммирования. Выход первого датчика 20 чисел соединен с первым входом первого умножителя б.
Устройство работает следующим образом.
Генератор 1 импульсов, управляющий датчиком 2 нормальных случайных чисел и счетчиком 3, а также последовательно соединенные первый квадратор 4, блок 5 последовательного суммирования и первый умножитель б необходимы для генерирования последовательности случайных чисел с одномерным гамма-распределением полуцелого параметра. Датчик 2 формирует нормально распределенные независимые случайные числа с нулевым средним значением и единичной дисперсией. Получение необходимого одномерного распределения вероятности основано на том обстоятельстве, что сумма квадратов независимых нормальных случайных чисел, распределенных одинаково с нулевым средним значением, имеет гамма-распределение полуцелого параметра. Последовательность случайных чисел приобретает свойство марковости благодаря тому, что возводимое в кваррат первым квадратором 4 нормальное случайное число образуется сложением в первом сумматоре 8 генерируемого в датчике 2 на каждом его такте нового независимого нормального числа, умноженного во втором умножителе 7 на положительное число, меньшее единицы, и сформированного на предыдущем такте нормального числа с выхода первого сумматора 8, хранимого во втором блоке
9 памяти, задерживаемого элементом 10 задержки на один такт и умно>каемого в третьем умножителе 11 на положительное число, меньшее единицы. Положительные числа, меньшие единицы, поступают на первые входы умножителей 7 и 11: на вход второго умножителя 7 непосредственно с выхода третьего датчика 12, а на вход третьего умножителя 11 — после преобразования.
Марковская последовательность случайных чисел с гамма-распределением характеризуется тремя параметрами: степенью корреляционной связи, параметром формы и масштабом чисел. Для удобства пользования генератором случайных чисел желательно, чтобы изменение этих параметров происходило независимо друг от друга. Для того чтобы изменение степени корреляционной связи не зависело от изменения масштаба генерируемых чисел, должно соблюдаться следующее соотношение
С,=)i С вЂ” Ci, 45
G5 между числами на первых входах умножителей 7 и 11 где CI — уровень первого входа второго умножителя 7; Сг †урове первого входа третьего умножителя 11 и С вЂ” положительная константа.
Для обеспечения этого условия положительное число от третьего датчика 12 чисел подается на первый вход третьего умножителя 11 через последовательно соединенные второй квадратор 13, инвертор 14, второй сумматор 15 и блок 16 извлечения квадратного корня, причем на второй вход второго сумматора
15 подается постоянное число от второго датчика 17 чисел.
Форма кривой одномерной плотности вероятности случайных чисел с гамма-распределением определяется количеством слагаемых в сумме предварительно возведенных в квадрат нормальных случайных чисел, образуемой в блоке 5 последовательного суммирования. Суммирование прекращается импульсом на первом входе блока 5 последовательного суммирования после определенного количества тактовых импульсов с генератора импульсов 3. Для изменения формы одномерного распределения случайных чисел применен первый блок 18 памяти для хранения различных целых положительных чисел, задаваемых исходя из требований к последовательности случайных чисел. При совпадении числа тактовых импульсов с содержанием первого блока 18 памяти в блоке 19 сравнения образуется импульс, прекращающий суммирование и передающий содержимое блока
5 последовательного суммирования на второй вход первого умножителя 6. Марковская последовательность случайных чисел с гаммараспределением снимается с выхода умножителя 6.
Таким образом, настоящее изобретение позволяет получить марковскую последовательность случайных чисел с гамма-распределением, т. е. оно обеспечивает достижение поставленной псред ним цели.
B генераторе случайных чисел можно осуществить изменение масштаба генерируемых чисел, например, с помощью первого датчика
20 чисел.
К достоинствам генератора следует отнести независимое друг от друга регулирование трех параметров, характеризующих марковскую последовательность случайных чисел с гамма-распределением.
Некоррелированную последовательность случайных чисел с гамма-распределением можно получить установлением максимального числа на выходе третьего датчика 12 чисел. В этом случае на первом входе третьего умножителя 11 будет число О, а следовательно, и второе слагаемое на входе первого сумматора 8 окажется равным нулю.
З0
6
При помощи этого генератора можно получить и марковскую приблизительно нормальную последовательность сл чайных чисел.
Для этого в первом блоке 18 памяти должно храниться достаточно большое число, предположительно не меньше нескольких десятков.
В технике цифрового моделирования и при решении различных задач методом статистических испытаний псевдослучайные числа имеют определенные преимущества перед случайными. К достоинствам генератора следует причислить то, что можно генерировать как случайные, так и псевдослучайные последовательности в зависимости от того, является ли датчик 2 датчиком случайных нормальных чисел или датчиком псевдослучайных нормальных чисел.
Важные в практике «хи»-квадрат-распределение, распределение Эрланга и экспоненциальное распределение являются частными случаями гамма-распределения при определенных значениях его двух параметров. Поэтому путем введения определенных чисел в первый блок 18 памяти и установления определенного числа на выходе первого датчика 20 чисел можно при помощи предложенного генератора генерировать марковские последовательности случайных чисел с «хи»квадрат-распределением, распределением Эрланга и экспонснциальным распределением, с регулировкой степени корреляции между последовательными случайными числами посредством третьего датчика 12 чисел.
Таким образом, предложенный генератор случайных чисел обладает новыми и более широкими возможностями по сравненшо с существующими генераторами и позволяет решать более сложные задачи из области цифрового моделирования и статистических испытаний.
Формула пзооретения
Генератор случайных чисел, содержащий первый умножитель, выход которого является выходом генератора, первый вход соединен с выходом первого датчика чисел, а второй вход — с выходом блока последовательного суммирования, первый вход которого соединен с выходом блока сравнения, входы которого подключены соответственно к выходам первого блока памяти и счетчика, вход которого соединен с выходом генератора импульсов и с входом датчика нормальных случайных чисел, отличающийся тем, что, с целью расширения функциональных возможностей генератора, он содержит второй умножитель, первый сумматор, первый квадратор, элемент задержки, второй блок памяти, третий умножитель, блок извлечения квадратного корня, второй сумматор, второй датчик чисел, инвертор, второй квадратор и третий датчик чисел, выход которого соединен с первым входом второго умножителя и через второй квадратор и инвертор — с первым входом второго сумматора, второй вход которого под590790
Составитель В. Караева
Тсхрсд Л. Гладкова
Корректор 3. Тарасова
Редактор Р. Киселева
Подписное
Заказ 3269/5 Изд, № 168 Тираж 738
НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий
113035, Москва, К-35, Раушская наб., д. 4/5
Типография, пр. Сапунова, 2 включен к выходу второго датчика чисел, а выход через блок извлечения квадратного корня — к первому входу третьего умножителя, выход которого соединен с первым входом первого сумматора, а второй вход через второй блок памяти и элемент задержки — с выходом первого сумматора и входом первого квадратора, выход которого соединен с вторым входом блока последовательного суммирования, а второй вход первого сумматора— с выходом второго умножителя, причем вто8 рой вход второго умнож ителя соединен с выходом датчика нормальных случайных чисел.
Источники информации, принятые во внимание при экспертизе
1. Авторское свидетельство СССР М 437061, кл. G 06F 1/02, 1973.
2. Авторское свидетельство СССР № 466500, кл. G 06F 1/02, 1973.
3. Патент США ¹ 3.811.038, кл. G 06F 7/38, 1972.