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

Союз СоаетскнкСоциапистичвскиаРвспубяик ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(ы)м. кл. С 06 Е 7/58 Ьеударетаснкый каиктат СССР ао делан изааретевва и аткрыткв(71) Заявитель Иинский радиотехнический институт(4) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Ионте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками. Весьма важной областью применения подобных устройств является область генерирования случайных процессов с равномерным спектром, используемых дляю идентификации систем автоматического управления. Кроме того, генератор псевдослучайных чисел, позволяющий получать случайные числа с равномер 1 ным распределением, часто используется как составной блок для построения генераторов случайных чисел с произвольным законом распределения. При этом весьма важным оказывается качест. во первичных равномерно распределенных чисел, которое в первую очередь определяется законом распределения и автокорреляционной функцией. Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два 1.Недостатком этого генератора явля" ется сложность структурного построения, а также усложненная методика синтеза, Кроме того, необходимым требованием для построения генератора псевдослучайных чисел является необ" ходимость выбора таких структур исход" ных последовательностей, у которых периоды являются взаимно простыми числами, что не всегда оказывается возможным,Наиболее близким по технической сущности к изобретению является гене" ратор псевдослучайных чисел, содержащий М триггеров,и-двухвходовых сум- маторов по модулю два. Выходы ттттриг" геров соединены со счетными входами триггеров других разрядов и входами тя-сумматоров по модулю два соответственно, выходы которых соединены со3 90387 счетными входами первыхтриггеров. Для получения суммы по модулю два в описываемом генераторе используются свойства суммирования по модулю даа хранений информации, поступающей на счетный вход триггера, В результате выполнения операций суммирования по модулю два на триггерах и сумматорах по,модулю даа за один такт формируется и -разрядное равномерно распределенное псевдослучайное число 2.Недостатком этого устройства является невозможность получения на его выходе значения Р-разрядного псевдослучайного числа си =- . в. От- ао оа сутствие комбинации к= 0000 приводит к искажению равномерного закона распределения, которое уменьшается с увеличением величины 9 и,Цел ь и зобретения - расши рени е Функциональных возможностей генератора и повышение точности генерирования выходных последовательностей равномерно распределенных и-разрядных псевдослучайных чисел, что достигается приближением вероятности к величине, равной 1/2.Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий Ч триггеров, входы которых подключены к выходу генератора синхроимпульсоа, дополнительно введены две группы по Уиэлементов ИЛИ, группа из 1 у 1-2 элементов ИЛИНЕ, два элемента НЕ и м сумматоров по модулю два, причем выходы 1 -ных элементов ИЛИ в первой и второй группах подключены к первым входам (1 +1)- ных элементов ИЛИ, к первым входам первых элементов ИЛИ в обоих группах40 подключены выход первого триггера и выход а-ого сумматора по модулю два соответственно, ко второму входу 1 " ого элемента ИЛИ первой и второй групп подключены нвыход (1+1)-ого триггера и выход (а ого сумматора по модулю два соответственно, ко входам первого и второго элементов НЕ подключены выходы (в)-ных элементов ИЛИ первой и второй групп соответственно, .выход 1-ого элемента ИЛИ первой группы подключен к первому входу (1+1)-ого элемента ИЛИ"НЕ, а к первому входу первого элемента ИЛИ-НЕ подключен выход первого триггера, выход 1-ого элемента,ИЛИ второй группы подключен ко второму входу (щ- 1) -ого элемента ИЛИ-НЕ, ко второму входу (в)-ого элемента ИЛИ 2 4НЕ подключен выход щ-ого сумматора помодулю даа, к первому входу 1-огосумматора по модулю даа подключенвыход 1-ого триггера, ко входу которого подключен выход 1-ого сумматорапо модуле два, выход 1-ого элементаИЛИ-НЕ подключен ко второму входу(1 +1)-ого сумматора по модулю два,ко второму входу 1"ого и и-ого сумматора по модулю даа подключены соответственно выходи второго и первогоэлементов НЕ, к третьим входам-старших сумматоров по модулю два подключены выходы-младших триггеров, а ктретьим входам Ю- -младших сумматоров по модулю два подключены выходыФстарших сумматоров по модулюдаа, выходы сумматоров по модулю дваявляются выходами генератора,На Фиг. 1 приведена Функциональ-,ная схема генератора при м = 5 и== 3; на Фиг. 2 - временная диаграмма работы генератора,Функциональная схема генераторапсевдослучайных чисел, состоит из1 п= 5 триггеров 1, первой и второйгруппы по Ю= 3 элементов ИЛИ 2 и 3,первого и второго элементов НЕ ч и 5,группы из Ьч= 3 элементов ИЛИ-НЕ би группы из и=5 сумматоров 7 по модулю два, Выходы 1-ных элементовИЛИ 2 и 3 в первой и второй группахподключены к первым входам (1+1)-ныхэлементов ИЛИ, к первым входам первыхэлементов ИЛИ 2 и 3 обеих групп подключены выход первого триггера группы триггеров 1 и выход 1 и-ого сумматора 7 по модулю два соответственно, ковторому входу 1"ого элемента ИЛИ 2 и 3первой и второй группы подключен выход (+1)-ого триггера 1 и выход(Итдого сумматора 7 по модулю два соответственно, ко входам первого и второгоэлементов НЕ М и 5 подключены выходы(ы.2-ных элементов ИЛИ 2 и 3 первойи второй группы соответственно, выход1-ого элемента ИЛИ 2 первой группыподключен к первому входу(1 +1)-огоэлемента ИЛИ-НЕ 1, а к первому входупервого элемента ИЛИ-НЕ 4 подключенвыход первого триггера 1, выход 1-огоэлемента ИЛИ второй группы подключенко второму входу (е-2)-ого элемента ИЛИ-НЕ ча ко второму входу (а",ого элемента ИЛИ-НЕ 4 подключен выходв-ого сумматора 7 по модулю два, кпервому входу 1-ого сумматора 7 помодулю два подключен выход 1 -огоФтриггера 1, ко входу которого, подклюФормула изобретения Генератор псевдослучайных чисел, содержащий щ триггеров, входы которых подключены к выходу генератора синхроимпульсов, о т л и ц а ю щ и йся тем, что, с целью повышения точности генерирования выходных последовательностей, дополнительно введены две группы по иэлементов ИЛИ, груп 5, 9038чен выход -ого сумматора 7 по модулю два, выход 1-ого элемента ИЛИ-НЕ 1подлкючен ко второму входу (1+1)-огосумматора 7 по модулю два, ко второму входу 1 ого и я ого сумматорапо модулю два подключены соответственно выходы второго и первого элементов НЕ.3 и. 2, к третьим входам 1-старших сумматоров 7 по модулю два под-.ключены выходы 1-младших триггеров 1, 1 оа к третьим входам,в-младших сумматоров 7 по модулю два подключенывыходы 1 естарших сумматоров 7 помодулю два к синхровходам триггеров 1 подключен выход генератора синх роимпульсов.Функционирование генератора псевдослучайных чисел происходит следующим образом,8 исходном состоянии триггеры 1 2 огенератора находятся в произвольномсостоянии, т.е. значение К-ого разряда ХКО, может принимать значениенуля или единицы с равной вероятностью. О отличие от известного, в 25предлагаемом генераторе в первоначальный момент на триггерах может .храниться нулевой код; В зависимости отначального кода на выходах трехвходовых сумматоров 7 по модулю два об- зоразуется псевдослучайное число. Поприходу синхроимпульса инФормация свыходов сумматоров 7 записывается натриггере 1. Элементы ИЛИ,2 и 3, эле-.менты ИЛИ-НЕ, элементы НЕ, а такжесумматоры по модулю два выполняютоперации логического .произведениядвух переменных, логического произведения с инверсией двух переменных,инверсии и суммирования по модулю 4 Одва соответственно, При значениях содержимого Й триггеров, обеспечивающихна выходе схем последовательность кодов Ф0000, устройство генериру 7 Кет на выходе сдвинутые участки по ф 4символов из Ю-последовательности. Вто же время в данном генераторе некоторому коду Ц , зависящему от Ми ии хранящемуся на триггерах 1, соответствует нулевой код на выходе сумматоров по модулю два, который в очередном такте записывается на триггеры 1, Наличие нулевого кода на триггерах 1 позволяет получить на выходеустройства очередное значение 1 к55в то время как появление нулевого кода в разрядах регистра известного ге"нератора срывает генерирование псевдослучайных последовательностей. 72 6Более подробно процесс работыпредлагаемого ГПСЧ пояснен конкретным примером.На Фиг. 2 а показана последовательность состояний последовательного генераторЬ, где.пунктирной стрелкой показана последовательность состояний регистра известного генератора. На фиг. 2 б приведена последовательность состояниЙ последователь"ного генератора, содержащего нулевойкод после кода 0001, а также пунктирной стрелкой показана последовательность состояний триггеров 1, Каквидно на Фиг, 2 последовательностькодов на выходе предлагаемого .генератора отличается от последовательности, получаемой на выходе известного генератора, наличием кодаОООО,Воэможность получения на выходегенератора комбинации 0000 приводит к выравниванию вероятностиР(Ю ), которая равняется 1/2 Ъ". ТакимтКобразом получение нулевой комбинациина выходе устройства расширяет егоФункциональные возможности и обеспечивает повышение качества выходныхпоследовательностей. Отсутствие запрещенных кодов 4 позволяет повыситькнадежность генератора, так наличиенуля на триггерах 1 не срывает генерирования псевдослучайной последовательности. Кроме того, дополнительные аппаратурные затраты на один разряд при построении генератора состав"Цляет всего 2 - - элементов ИЛИ,(1 " -) ИЛИ-НЕ, - элементов НЕ, один,2 2П Осумматор по модулю два,Применение предлагаемого генера-.тора псевдослучайных чисел позволяетповысить качество псевдослучайных последовательностей, а тем самым и точность и достоверность решения задачметодом Монте-Карло.7 9038 па из щэлементов ИЛИ-НЕ, два элемента НЕ и щ сумматоров по модулю два, причем выходы 1-ных элементов . ИЛИ в первой и второй группах подключены к первым входам (1+1)-ных элементов ИЛИ, к первым входам первых элементов ИЛИ в обоих группах подключены выход первого триггера и выход я-ого сумматора по модулю два соответственно, ко второму входу 1-ого 1 о элемента ИЛИ первой и второй групп подключены выход (1+1)-ого триггера и выход (щ)-ого сумматора ло модулю два соответственно ко входам первого и второго элементов НЕ подключе з ны выходы (щ)-ных элементов ИЛИ первой и второй групп соответственно, выход 1-ого элемента ИЛИ первой группы подключен к первому входу(1+1)-ого элемента ИЛИ-НЕ, а к пер- що вому входу первого элемента ИЛИ-НЕ подключен выход первого триггера, выход 4 -ого элемента ИЛИ второй группы подлкючен ко второму входуФ-1,)-ого элемента ИЛИ-НЕ, ко второму входу(.1 Я)-ого элемента ИЛИ-НЕ подключен выход 1 и-ого сумматора по модулю два,72 8к первому входу 1-ого сумматора помодулю два подключен выход 1-оготриггера, ко входу которого подключен выход-ого сумматора по модулюдва, выход -ого элемента ИЛИ-НЕ подключен ко второму входу (1 +1)-огосумматора по модулю два, ко второмуходу -ого и й-ого сумматора по модуЬю два.подключены соответственно вы-ходы второго и первого элементов НЕ,к третьим входам )-старших сумматоров по модулю два подключены выходы ,-младших триггеров, а к третьимвходам щмладших сумматоров по модулю два подключены выходы пт.-старших сумматоров по модулю два, выходысумматоров по модулю два являютсявыходами генератора,Источники инФормации,принятые во внимание при экспертизе1. Яковлев В.В. и Федоров Р.Ф.Вероятностные вычислительные машины.Л "Машиностроение", 1974, с. 344.2. Авторское свидетельство СССРИф 572823, кл, 6 07 С 15/00, 1975/ Составитель А. Карасов Редактор Н. Лазаренко Техреду И.Гергель Корректор Г. Огар Заказ 121/30 Тираж 731 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 11303, Москва ЖРаушская наб. д, 4 Д филиал ППП "Патент", г. Ужгород, ул. Проектная,