Генератор псевдослучайных чисел
Союз Советскнк
Социапиетичвекии
Рвапубяик
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Опубликоваио. 07. 02.82. Ьюллетеиь М 5 Дата опубликоваиия описаиия 09. 02. 82 (ьй)М. Кл . G 06 Е 7/58 9кударетаеиыб каиитат СССР ао делам изааретеиий и атирытий (53) УДК 681. 325 (088.8) (71) Заявитель Иинский радиотехнический институт (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для полуI чения случайных чисел при решении задач методом Ионте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками. Весьма важной областью применения подобных устройств является область генерирования случайных процессов с равномерным спектром, используемых для ю идентификации систем автоматического управления. Кроме того, генератор псевдослучайных чисел, позволяющий получать случайные числа с равномер1j ным распределением, часто используется как составной блок для построения генераторов случайных чисел с произвольным законом распределения. При этом весьма важным оказывается качество первичных равномерно распределенных чисел, которое в первую очередь определяется законом распределения и автокорреляционной функцией. Известен генератор псевдослучайн ых чи сел, соде ржащи и д ва ре ги ст ра сдвига и группу сумматоров по модулю два (1). Недостатком этого генератора явля " ется сложность структурного построения, а также усложненная методика синтеза. Кроме того, необходимым требованием для построения генератора псевдослучайных чисел является необ" ходимость выбора таких структур исход" ных последовательностей, у которых периоды являются взаимно простыми числами, что не всегда оказывается возможным. Наиболее близким по технической сущности к изобретению является генератор псевдослучайных чисел, содержащий М триггеров,ти- 1 двухвходовых сум- маторов по модулю два. Выходы ттттриг" геров соединены со счетными входами триггеров других разрядов и входами тя- g сумматоров по модулю два соответственно, выходы которых соединены со 3 90387 счетными входами первых триггеров ° Для получения суммы по модулю два в описываемом генераторе используются свойства суммирования по модулю два хранений информации, поступающей на счетный вход триггера. В результате выполнения операций суммирования по модулю два на триггерах и сумматорах по,модулю два за один такт формируется YYl-разрядное равномерно распределенное псевдослучайное число (2). ° Недостатком этого устройства является невозможность получения на его выходе значения Р -разрядного псевдослучайного чнсла на = : — % От- д ь о о...а сутствие комбинации 1 к= 000...0 приводит к искажению равномерного закона распределения, которое уменьшается с увеличением величины 9И, Цель изобретения - расширение функциональных возможностей генератора и повышение точности генерирования выходных последовательностей равномерно распределенных И -разрядных псевдослучайных чисел, что достигается приближением вероятности к величине, равной 1/2. Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий Ь1 триггеров, входы которых подключены к выходу генератора синхроимпульсов, дополнительно введены две группы по -2 элементов ИЛИ, группа из и-2 элементов ИЛИНЕ, два элемента НЕ и м сумматоров по модулю два, причем выходы 1 -ных элементов ИЛИ в первой и второй группах подключены к первым входам (1+1)ных элементов ИЛИ, к первым входам первых элементов ИЛИ в обоих rpynnax 40 подключены выход первого триггера и выход m-ого сумматора по модулю два соответственно, ко второму входу 1 " oro элемента ИЛИ первой и второй групп подключены нвыход (i+1)-ого триггера и выход (m- i5oro сумматора по модулю два соответственно, ко входам первого и второго элементов НЕ подключены выходы (m-2)-ных элементов ИЛИ первой и второй групп соответственно, .выход I ого элемента ИЛИ первой группы подключен к первому входу (i+1)-ого элемента ИЛИ-НЕ, а к первому входу первого элемента ИЛИ-НЕ подключен выход первого триггера, выход i-oro элемента,ИЛИ второй группы подключен ко второму входу (m-2- i)-ого элемента ИЛИ-НЕ, ко второму входу (я-2)-ого элемента ИЛИ2 4 НЕ подключен выход m-oro сумматора по модулю два, к пе рвому входу i -ого сумматора по модулю два подключен выход i-oro триггера, ко входу которого подключен выход i-oro сумматора по модулю два, выход i-ого элемента ИЛИ-НЕ подключен ко второму входу (1 +1)-ого сумматора по модулю два, ко второму входу a-oro и oro сумматора по модулю два подключены соответственно выходы второго и первого элементов НЕ, к третьим входам -старших сумматоров по модулю два подключены выходы -младших триггеров, а к третьим входам Wl-) --младших сумматоров по модулю два подключены выходы N-f-старших сумматоров по модулю два, выходы сумматоров по модулю два являются выходами генератора, Ф На фиг. 1 приведена функциональ-, ная схема генератора при юг= 5 и = на фиг. 2 - временная диаграмма работы генератора. функциональная схема генератора псевдослучайных чисел, состоит из 1п= 5 триггеров 1, первой и второй группы по Ю-2 = 3 элементов ИЛИ 2 и 3, первого и второго элементов НЕ ч и 5, группы из М-? = 3 элементов ИЛИ-НЕ б и группы из &=5 сумматоров 7 по модулю два. Выходы 1-ных элементов ИЛИ 2 и 3 в первой и второй группах подключены к первым входам (1+1)-ных элементов ИЛИ, к первым входам первых элементов ИЛИ 2 и 3 обеих групп подключены выход первого триггера группы триггеров 1 и выход уп-oro сумматора 7 по модулю два соответственно, ко второму входу 1"ого элемента ИЛИ 2 и 3 первой и второй группы подключен выход (+1)-ого триггера 1 и выход(Ит )ого сумматора 7 по модулю два соответственно, ко входам первого и второго элементов НЕ 4 и 5 подключены выходы (ы-2)-ных элементов ИЛИ 2 и 3 первой и второй группы соответственно, выход 1-ого элемента ИЛИ 2 первой группы подключен к первому входу(1 +1)-oro элемента ИЛИ-HE 4, а к первому входу первого элемента ИЛИ-НЕ 4 подключен выход первого триггера 1, выход i-ого элемента ИЛИ второй группы подключен ко второму входу (m-i-2)-oro элемента ИЛИ-НЕ ч, ко второму входу (а-2 -, ого элемента ИЛИ-HE 4 подключен выход m-oro сумматора 7 по модулю два, к первому входу i-oro сумматора 7 по модулю два подключен выход q -ого Ф триггера 1, ко входу которого. подклю" формула изобретения Генератор псевдослучайных чисел, содержащий т триггеров, входы которых подключены к выходу генератора синхроимпульсов, о т л и ч а ю щ и йся тем, что, с целью повышения точности генерирования выходных последовательностей, дополнительно введены две группы no m-2 элементов ИЛИ,груп5, 9038 чен выход I îãî сумматора 7 по модулю два, выход i-ого элемента ИЛИ-НЕ 4 подлкючен ко второму входу (i+1)-oro сумматора 7 по модулю два, ко второму входу i-Ого и m-ого сумматора 7 по модулю два подключены соответственно выходы второго и первого элементов НЕ.3 и. 2, к третьим входам )-старших сумматоров 7 по модулю два под-. ключены выходы j-младших триггеров 1, 10 а к третьим входам,m-)-младших сумматоров 7 по модулю два подключены выходы1>й-4-старших сумматоров 7 по модулю два> к синхровходам триггеров 1 подключен выход генератора синх-1s роимпульсов. Функционирование генератора псевдослучайных чисел происходит следующим образом. В исходном состоянии триггеры 1 m генератора находятся в произвольном состоянии, т.е. значение К-ого разряда ХК(,0 ) может принимать значение нуля или единицы с равной вероятностью. 0 отличие от известного, в предлагаемом генераторе в первона.> чальный момент на триггерах может .храниться нулевой код; В зависимости от начального кода на выходах трехвходовых сумматоров 7 по модулю два об- зо разуется псевдослучайное число. По приходу синхроимпульса информация с выходов сумматоров 7 записывается на триггере 1. Элементы ИЛИ .2 и 3, эле-менты ИЛИ-НЕ, элементы НЕ, а также сумматоры по модулю два выполняют операции логического -произведения двух переменных, логического произведения с инверсией двух переменных, инверсии и суммирования по модулю 40 два соответственно, При значениях содержимого К триггеров, обеспечивающих на выходе схем последовательность кодов Ф Р 000...0, устройство генериру7К ет на выходе сдвинутые участки по Ю 4 символов из Ю-последовательности. В то же время в данном генераторе некоторому коду Ц, зависящему от И и 4 и хранящемуся на триггерах 1, соответствует нулевой код на выходе сум- 0 маторов по модулю два, который в очередном такте записывается на триггеры 1. Наличие нулевого кода на триггерах 1 позволяет получить на выходе 1 устройства очередное значение f в то время как появление нулевого кода в разрядах регистра известного ге" нератора срывает генерирование псевдослучайных последовательностей..72 6 Более подробно процесс работы предлагаемого ГПСЧ пояснен конкретным примером. На фиг. 2а показана последовательность состояний последовательного генератора, где.пунктирной стрелкой показана последовательность состояний регистра известного генератора. На фиг. 2б приведена последовательность состояниЙ последователь" ного генератора, содержащего нулевой код после кода 000...1, а также пунктирной стрелкой показана последовательность состояний триггеров I. Как видно на фиг. 2 последовательность кодов на выходе предлагаемого .генератора отличается от последовательности, получаемой на выходе известного генератора, наличием кода 0000. Воэможность получения на выходе генератора комбинации 000...0 приводит к выравниванию вероятности Р(), которая равняется 1/2 Ъ". Таким К образом., получение нулевой комбинации на выходе устройства расширяет его функциональные возможности и обеспечивает повышение качества выходных последовательностей. Отсутствие запрещенных кодов 4 позволяет повысить к надежность генератора, так наличие > нуля на триггерах 1 не срывает генерирования псевдослучайной последовательности. Кроме того, дополнительные аппаратурные затраты на один разряд при построении генератора состав" 4 ляет всего 2 - — элементов ИЛИ, (1 " -) ИЛИ-НЕ, — элементов НЕ, один, 2 2 ш m сумматор по модулю два, Применение предлагаемого генератора псевдослучайных чисел позволяет повысить качество псевдослучайных последовательностей, а тем самым и точность и достоверность решения задач методом Монте-Карло. 7 9038 па из m-2 элементов ИЛИ-НЕ, два элемента НЕ u m сумматоров по модулю два, причем выходы i - ных элементов . ИЛИ в первой и второй группах подключены к первым входам (i+1)-ных элементов ИЛИ, к первым входам первых элементов ИЛИ в обоих группах подключены выход первого триггера и выход m-ого сумматора по модулю два соответственно, ко второму входу i-ого 1о элемента ИЛИ первой и второй групп подключены выход (1+1)-ого триггера и выход (m-i)- îãî сумматора по модулю два соответственно ко входам первого и второго элементов НЕ подключе- Is ны выходы (m-2)-ных элементов ИЛИ первой и второй групп соответственно, выход i-ого элемента ИЛИ первой группы подключен к первому входу (i+1)-oro элемента ИЛИ-НЕ, а к пер- що вому входу первого элемента ИЛИ-НЕ подключен выход первого триггера, выход 4 -oro элемента ИЛИ второй группы подлкючен ко второму входу(Ф-2-i.)-oro элемента ИЛИ-НЕ, ко второму входу -(1Я-2)-oro элемента ИЛИ-НЕ подключен выход Е-ого сумматора по модулю два, 72 8 к первому входу е -ого сумматора по модулю два подключен выход g-oro триггера, ко входу которого подключен выход у --ого сумматора по модулю два, выход -ого элемента ИЛИ-НЕ подключен ко второму входу (1 +l)-ого сумматора по модулю два, ко второму ходу а-ого и Moro сумматора по модулю два.подключены соответственно вы- ходы второго и первого элементов НЕ, к третьим входам J-старших сумматоров по модулю два подключены выходы j,-младших триггеров, а к третьим входам m-j-младших сумматоров по модулю два подключены выходы m-j-старших сумматоров по модулю два, выходы сумматоров Ro модулю два являются выходами генератора. Источники инФормации, принятые во внимание при экспертизе 1. Яковлев В.В. и Федоров Р.Ф. Вероятностные вычислительные машины. Л., "Машиностроение", 1974, с. 344. 2. Авторское свидетельство СССР И 572823, кл. 6 07 С 15/00, 1975 (прототип). 903872 с, г Составитель А. Карасов Редактор Н. Лазаренко Техреду М Гергель Корректор Г. Огар Заказ 121/30 Тираж 731 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 11303, Москва Ж-3 Раушская наб. д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 / / /е а 1 /ЧЪ е СЪ 1 .(( ъ (- съ ( е С р l3 -/ ъ » б / / 1 / 1 (l с о I (с:э с с (съ ср ; / ъ» \. / у М с;» /. 1с, 1 / (< (т» 1 ъ l ! СЪ(/ / / с съ ъ» /с:р съ с:р (съ ° 1 с ( о о -(с:> (/ 1. ! 3/ ь 1ч с> / (с .а (съ с:з I ( с 1с =э / ъ l 1(1 р 1 I с I— %» (а» 1 . 1% ° а.» 
