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

11 ц 590790 ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВЙДЕТЕЛЬСТВУ(61) Дополнительное к авт. свид-ву йюз Ооюетскик Социалистических Республик(22) Заявлено с присое Государстеенныи комите 3) Приорит овета Министров СССпо делам изобретений и открытий 3) УДК 681.325(088.8(43) Опубликовано 30,01.78. Бюллетень(45) Дата опубликования описания 13.02.78(72) Автори зоб р ете 1 оорт аявитель 54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ решением генератор Изобретение относится к области вычислительной техники и может найти применение при моделировании марковской последовательности слугайных чисел с гамма-распределением,Известны генераторы случайных чисел.Один из известных генераторов случайных чисел содержит регистр сдвига, генератор случайных символов, генератор тактовых импульсов, вероятностный (1, гп)-полюсник, элемент ИЛИ и элементы И. Однако этот генератор не позволяет получить марковские последовательности случайных чисел с одномерным распределением вероятности, отличным от распределения Бернулли (1.Другой нз известных генераторов случайных чисел содержит источник случайных импульсов, блок формирования импульсов, фильтр низких частот, электронный ключ, амплитудный селектор, многофазный ждущий мультивибратор, блоки памяти, блок управления и матричный переключатель. Однако этот генератор не позволяет получить случайные числа с точно заданным одномерным распределением вероятности, а может лишь аппроксимировать заданное точное распределение вероятности с помощью фильтра низких частот и матричного переключателя (2Наиболее близким техническимк данному изобретению является случайных чисел, содержан,пй первый умно- житель, выход которого является выходом генератора, первый вход соединен с выходом первого датчика чисел, а второй вход - с вы ходом блока последовательного суммирования, псрвь 1 й вход которого соединен с выходом блока сравнения, входы которого подключены соответственно к выходам первого блока памяти и счетчика, вход которого сое дпнен с выходом генератора импульсов и совходом датчика нормальных случайных чисел 3.Хотя этот генератор последовательностислучайных чисел основан на точных зависи мостях между распределениями исходных ивь.рабгтывае:алых случайных чисел, его недостаток заключастся в том, что он вырабатывает только некоррелированные между сооой случайные числа. Это обстоятель ство ограничивает область применения генератора, посколыо усложнение задач, решаемых методом цифрового моделирования и методом статистических испытаний, требует не только генерирования последовательи стсй случайных чисел с распредсленпями, более сложнымн по сравнению с равномерным нли нормальным распределением, но и с определенными и причем регулируемыми корреляционными связями между числамипоследовательности, 58079055 60 65 Целью изобретения является расширение функциональных возможностей генератора за счет получения марковской последовательности случайных чисел с гамма-распределением.Для достижения поставленной цели датчик дополнительно содержит второй умножитель, первый сумматор, первый квадратор, элемент заде 1)л(КР, второй блок памяти, трети умно- житель, блок извлечения квадратного корня, второй сумматор, второй датчик чисел, инвертор, второй квадратор и третий датчик чисел, выход которого соединен с первым входом второго умножителя и через второй квадратор и инвертор - с первым входом второго сумматора, второй вход которого подключен к выходу второго датчика чисел, а выход через блок извлечения квадратного корня - к первому входу третьего умножителя, выход которого соединен с первым входом первого сумматора, а второй вход через второй блок памяти и элемент задержки - с выходом первого сумматора и входом первого квадратора, выход которого соединен со вторым входом блока последовательного суммирования, а второй вход первого сумматора - с выходом второго умножителя, причем второй вход второго умножнтеля соединен с выходом датчика нормальных случайных чисел,Блок-схема генератора приведена на чертеже.Генератор содержит генератор 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 20 25 Зо З 5 40 45 50 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 - после преобразования. Марковская последовательность случайных чисел с гамма-распределением характеризуется тремя параметрами: степенью корреляционной связи, параметром формы и масштабом чисел. Для удобства пользования генератором случайных чисел желательно, чтобы изменение этих параметров происходило независимо друг от друга. Для того чтобы изменение степени корреляционной связи не зависело от изменения масштаба генерируемых чисел, должно соблюдаться следующее соотношение45 50 55 60 65 между числами на первых входах умножителей 7 и 11 где С 1 - уровень первого входа второго умно- жителя 7; Сг в урове первого входа третьего умножителя 11 и С - положительная константа.Для обеспечения этого условия положительное число от третьего датчика 12 чисел подается на первый вход третьего умножителя 11 через последовательно соединенные второй квадратор 13, инвертор 14, второй сумматор 15 и блок 16 извлечения квадратного корня, причем на второй вход второго сумматора 15 подается постоянное число от второго датчика 17 чисел.Форма кривой одномерной плотности вероятности случайных чисел с гамма-распределением определяется количеством сла. гаемых в сумме предварительно возведенных в квадрат нормальных случайных чисел, образуемой в блоке 5 последовательного суммирования. Суммирование прекращается импульсом на первом входе блока 5 последовательного суммирования после определенного количества тактовых импульсов с генератора импульсов 3. Для изменения формы одномерного распределения случайных чисел применен первый блок 18 памяти для хранения различных целых положительных чисел, задаваемых исходя из требований к последовательности случайных чисел. При совпадении числа тактовых импульсов с содержанием первого блока 18 памяти в блоке 19 сравнения образуется импульс, прекращающий суммирование и передающий содержимое блока 5 последовательного суммирования на второй вход первого умножителя 6. Марковская последовательность случайных чисел с гамма- распределением снимается с выхода умножителя 6.Таким образом, настоящее изобретение позволяет получить марковскую последовательность случайных чисел с гамма-распределением, т. е. оно обеспечивает достижение поставленной псред ним цели.В генераторе случайных чисел можно осуществить изменение масштаба генерируемых чисел, например, с помощью первого датчика 20 чисел.К достоинствам генератора следует отнести независимое друг от друга регулирование трех параметров, характеризующих марковскую последовательность случайных чисел с гамма-распределением.Некоррелированную последовательность случайных чисел с гамма-распределением можно получить установлением максимального числа на выходе третьего датчика 12 чисел. В этом случае на первом входе третьего умножителя 11 будет число О, а следовательно, и второе слагаемое на входе первого сумматора 8 окажется равным нулю. 5 10 15 20 25 Зо 35 40 6При помощи этого генератора можно получить и марковскую приблизительно нормальную последовательность случайных чисел, Для этого в первом блоке 18 памяти должно храниться достаточно большое число, предположительно не меньше нескольких десятков.В технике цифрового моделирования и при решении различных задач методом статистических испытаний псевдослучайные числа имеют определенные преимушества перед случайными. К достоинствам генератора следует причислить то, что можно генерировать как случайные, так и псевдослучайные последовательности в зависимости от того, является ли датчик 2 датчиком случайных нормальных чисел или датчиком псевдослучайных нормальных чисел,Важные в практике хи-квадрат-распределение, распределение Эрланга и экспоненциальное распределение являются частными случаями гамма-распределения при определенных значениях его двух параметров. Поэтому путем введения определенных чисел в первый блок 18 памяти и установления определенного числа на выходе первого датчика 20 чисел можно при помощи предложенного генератора генерировать марковские последовательности случайных чисел с хи- квадрат-распределением, распределением Эрланга и экспонснциальным распределением, с регулировкой степени корреляции между последовательными случайными числами посредством третьего датчика 12 чисел.Таким образом, предложенный генератор случайных чисел обладает новыми и более широкими возможностями по сравненшо с существующими генераторами и позволяет решать более сложные задачи из области цифрового моделирования и статистических испытаний. Формула изобретенияГенератор случайных чисел, содержащий первый умножитель, выход которого является выходом генератора, первый вход соединен с выходом первого датчика чисел, а второй вход - с выходом блока последовательного суммирования, первый вход которого соединен с выходом блока сравнения, входы которого подключены соответственно к выходам первого блока памяти и счетчика, вход которого соединен с выходом генератора импульсов и с входом датчика нормальных случай. ных чисел, отличающийся тем, что, с целью расширения функциональных возможностей генератора, он содержит второй умно- житель, первый сумматор, первый квадратор, элемент задержки, второй блок памяти, третий умножитель, блок извлечения квадратного корня, второй сумматор, второй датчик чисел, инвертор, второй квадратор и третий датчик чисел, выход которого соединен с первым входом второго умножителя и через второй квадратор и инвертор - с первым входом второго сумматора, второй вход которого под590790 со оставитель Корректор 3. Тарасова хрсд Л, Гладко Реда кто селев Изд, Жо 168 Тираж 738 1 ПО Государственного комитета Совета Министров СС по делам изобретений и открытий 113035, Москва, К, Раушская наб., д. 4/5каз 3269/5 одписное ипография, пр. Сапунова, 2 включен к выходу второго датчика чисел, а выход через блок извлечения квадратного корня - к первому входу третьего умножителя, выход которого соединен с первым входом первого сумматора, а второй вход через второй блок памяти и элемент задержки - с выходом первого сумматора и входом первого квадратора, выход которого соединен с вторым входом блока последовательного суммирования, а второй вход первого сумматора - с выходом второго умножителя, причем вто 8рой вход второго умножителя соединен свыходом датчика нормальных случайных чисел.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР437061,кл. Ст 06 Р 1/02, 193.2. Авторское свидетельство СССР466500,кл. 6 06 Р 1/02, 1973,10 3. Патент США3.811.038, кл. 6 061. 7/38,1972.