Генератор псевдослучайных чисел Советский патент 1982 года по МПК G06F7/58 

(5) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вы1 1слительной Технике и может быть использовано в качестве устройства для полу чения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками. Весьма важной областью применения подобных устройств является область генерирования случайных процессов с рав номерным спектром, используемых для идентификации систем aвтo «lтичecкoгo управления. Кроме того, генератор псевдослучайных чисел, позволяю«ций получать случайные числа с равномерным распределением,часто используется как составной блок для построения генераторов случайных чисел с произвольным законом распределения. При ЭТОМ весьма важным оказывается качест во первичных равномерно распределенных чисел, которое в первую очередь определяется законом распределения и автокорреляционной функцией. Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два fl). Недостатком этого генератора является СЛОЖНОСТЬ структурного построения , а также усложненная методика синтеза. Кроме того, необходимым требованием для построения генератора псевдослучайных чисел является необ ХОДИМОСТЬ выбора таких структур исходных последовательностей, у которых периоды ЯВЛЯЮТСЯ взаимно простыми числами, ЧТО не всегда оказывается возможным. Наиболее близким по технической сущности к изобретению является генератор псевдослучайных чисел, содержащий hi триггеров, лвухвходовых сумматоров по модулю два. Выходы Wтриггеров соединены со счетными входами триггеров других разрядов и входами f f сумматоров по модулю два соответственно, выходы которых соединены со счетными входами первых j триггеров. Для получения суммы по модулю два в описываемом генераторе используются свойства суммирования по модулю два хранений информации, поступающей на счетный вход триггера. В результате выполнения операций суммирования по модулю два на триггерах и сумматорах по. модулю два за один такт формируется ки-разрядное равномерно распределенное псевдослучайное число з. Недостатком этого устройства явля ется невозможность получения на его выходе значения к разрядного псевдо ооо.. - о случайного числа | сутствие комбинации }к 000...О . приводит к искажению равномерного за кона распределения, которое уменьшается с увеличением величины Wi . Цель изобр,етения - расширение функциональных возможностей генератора и повышение точности генерирования выходных последовательностей равномерно распределенных Иг разрядных псевдослучайных чисел, что достигается приближением вероятности к величине, равной 1/2. Поставленная цель достигается тем что в генератор псевдослучайных чисел, содержащий УУ триггеров, входы которых подключены к выходу генерато ра синхроимпульсов, дополнительно введены две группы по элементов ИЛИ, группа элементов ИЛИ НЕ, два элемента НЕ и kvi сумматоров по модулю два, причем выходы 1-ных элементов ИЛИ в первой и второй груп пах подключены к первым входам (+1) ных элементов ИЛИ, к первым входам первых элементов ИЛИ в обоих группах подключены выход первого триггера и выход т-ого сумматора по модулю два соответственно, ко второму входу-iого элемента ИЛИ первой и второй групп подключены квыход ((+1)-ого триггера и выход ( сумматора по модулю два соответственно, ко входам первого и второго элементов НЕ подключены выходы (т-2)-ных элементов ИЛИ первой и второй групп соответственно, .выход 1-ого элекюмта ИЛИ первой группы подключен к пер вому входу {и-1)-ога элемента ИЛИ-НЕ а к первому входу первого элемента ИЛИ-НЕ подключен выход первого триггера, выход i-oro элемента .ИЛИ второй группы подключен ко второму входу (т-2-i)-oroэлемента ИЛИ-НЕ, ко второму входу (т-2)-ого элемента ИЛИ 90 4 НЕ подключен выход т-ого сумматора по модулю два, к первому входу i-oro сумматора по модулю два подключен выход i-oro триггера, ко входу которого подключен выход J-oro сумматора по модулю два, выход -i-oro элемента ИЛИ-НЕ подключен ко второму входу ((+1)-ого сумматора по модулю два, ко второму входу 1-ого и сумматора по модулю два подключены соответственно выходы второго и первого элементов НЕ, к третьим входам -старших сумматоров по «эдулю два подключень выходы -младших триггеров, а к третьим входам И1- -младших сумматоров по модулю два подключены выходы in-J-старших сумматоров по модулю два, выходы сумматоров по модулю два являются выходами генератора. На фиг. 1 приведена функциональ-; ная схема генератора при И7 5 иУ 3; на фиг. 2 - временная диаграмма работы генератора. Функциональная схема генератора псевдослучайных чисел, состоит из Vn 5 триггеров 1, первой и второй группы по КМ-2 3 элементов ИЛИ 2 и 3, первого и второго элементов НЕ и 5, группы из hT-. 3 элементов ИЛИ-НЕ 6 и группы из сумматоров 7 по модулю два. Выходы- -ных элементов ИЛИ 2 и 3. в первой и второй группах подключены к первым входам ( элементов ИЛИ, к первым входам первых элементов ИЛИ 2 и 3 обеих групп подключены выход первого триггера группы триггеров 1 и выход КГ)-ого сумматора 7 по модулю два соответственно, ко второму входу -ого элемента ИШ 2 и 3 первой и второй группы подключен выход ()-oгo триггера 1 и выxoд{ v -f ого сумматора 7 по модулю два соответственно, ко входам первого и второго элементов НЕ 1 и 5 подключены выходы (т-2)-ных элементов ИЛИ 2 и 3 первой и второй группы соответственно, выход i-oro элемента ИЛИ 2 первой группы подключен к первому входу(i +1)-ого элемента ИЛИ-НЕ , а к первому входу первого элемента ИЛИ-НЕ Ц подключен выход первого триггера 1, выход i-oro элемента ИЛИ второй группы подключен ко второму входу (m-i-2)-oro элемента ИЛИ-НЕ Ц, ко второму входу (т-2)- , ого элемента ИЛИ-НЕ k подключен выход т-ого сумматора 7 по модулю два, к первому входу i-oro сумматора 7 по модулю два подключен выход- -ого триггера 1 , ко входу которого, подключем выход i-oro сумматора 7 по модулю два, выход i-oro элемента ИЛИ-НЕ подлкючен ко второму входу (i+1)-oro сумматора 7 по модулю два, ко второму входу i-oro и т-ого сумматора 7 по модулю два подключены соответстве но выходы второго и первого элементов НЕ-3 и 2, к третьим входам j-ста ших сумматоров 7 по модулю два подключены выходы j-младших триггеров 1 а к третьим входам,m-j-младших сумматоров 7 по модулю два подключены вь1ходыуп- -старших сумматоров 7 по модулю два, к синхровходам триггеров. 1 подключен выход генератора син роимпульсов. Функционирование генератора псевдослучайных чисел происходит следующим образом. В исходном состоянии триггеры 1 генератора находятся в произвольном состоянии, т.е. значение К-ого разряда ) (жет принимать значение нуля или единицы с равной вероятностью. В отличие от известного, в предлагаемом генераторе в первоначальныи момент на триггерах может -хм ниться нулевой код-. В зависимости от начального кода на выходах трехвходовых сумматоров 7 по модулю два образуется псевдослучайное число. По приходу синхроимпульса информация с выходов сумматоров 7 записывается на триггере 1. Элементы ИЛИ .2 и 3 злементы ИЛИ-НЕ, элементы НЕ, а также сумматоры по модулю два выполняют операции логического произведения двух переменных, логического произведения с инверсией двух переменных, инверсии и суммирования по модулю два соответственно. При значениях со держимого hi триггеров, обеспечиващи на выходе схем последовательность ко дов t.f 000. ..О, устройство генериру ет на выходе сдвинутые участие по vn символов изVn-последовательности. В то же время в данном генераторе некоторому коду 1 , зависящему от (п и л и хранящемуся на триггерах 1,соответствует нулевой код на выходе сумматоров по модулю два, который в оче редном такте записывается на триггеры 1. Наличие нулевого кода На три герах 1 позволяет получить на выходе устройства очередное значение j , в то время как появление нулевого ко да в разрядах регистра известного ге нератора срывает генерирование псевдослучайных последовательностей., 26 Более подробно процесс работы предлагаемого ГПСЧ пояснен конкретным примером. На фиг. 2а,показана последова- тельность состояний последовательного генератор, где.пунктирной стрелкой показана последовательность состояний регистра известного генератора. На (. 26 приведена последовательность состояний последовательного генератора, содержащего нулевой код после кода 000...1, а также пунктирной стрелкой показана последовательность состояний триггеров 1. Как видно на фиг. 2 последовательность кодов на выходе предлагаемого .генератора отличается от последовательности, получаемой на выходе известного генератора, наличием кода 0000. Возможность получения на выходе генератора комбинации 000...О приводит к выравниванию вероятности Р((). которая равняется Таким образом, получение нулевой комбинации на выходе устройства расширяет его функциональные возможности и обеспечивает повьциение качества выходных последовательностей. Отсутствие за- прещенных кодов , позволяет повысить надежность генератора, так наличие нуля на триггерах 1 не срывает генерирования псевдослучайной последова тельности. Кроме того, дополнительные аппаратурные затраты на один разряд при построении генератора составвсего 2 - - m элементов ИЛИ, (1 .- |) ИЛИ-НЕ, I элементов НЕ, один. сумматор по модулю два. Применение предлагаемого генератора псевдослучайных чисел позволяет овысить качество псевдослучайных последовательностей, а тем самым и точость и достоверность решения задач етодом Монте-Карло. Формула изобретения Генератор псевдослучайных чисел, одержащий m триггеров, входы котоых подключены к выходу генератора инхроимпульсов, отли чающи йся тем, что, с целью повышения точости генерирования выходных последоательностей, дополнительно введены ве группы по т-2 элементов ИЛИ.группа из m-2 элементов ИЛИ-НЕ, два элемента НЕ и m сумматоров по модулю два, причем выходы i-ных элементов ИЛИ в первой и второй группах подключены к первым входам (+1)-ных элементов ИЛИ, к первым входам первых элементов ИЛИ в обоих группах подключены выход первого триггера и выход т-ого сумматора по модулю два соответственно, ко второму входу i-oro элемента ИЛИ первой и второй групп подключены выход (+1)-ого триггера и выход (m-i)-oro сумматора по модулю два соответственно ко входам первого и второго элементов НЕ подключены выходы {т-2)-ных элементов ИЛИ первой и второй групп соответственно, выход 1-ого элемента ИЛИ первой группы подключён к первому входу (i-fl)-oro элемента ИЛИ-НЕ, а к первому входу первого элемента ИЛИ-НЕ подключен выход первого триггера, выход 4-ого элемента ИЛИ второй группы гюдлкючен ко второму входу (.-ого элемента ИЛИ-НЕ, ко второму входу ()-ого элемента ИЛИ-НЕ подключен выход уп-ого сумматора по модулю два.

к первому входу i-ого сумматора по модулю два подключен выход 1-ого триггера, ко входу которого подключен выход i-ого сумматора по модулю два, выход 4-ого элемента ИЛИ-НЕ подключен ко второму входу (1 +О-ого .сумматора по модулю два, ко второму рходу -ого и Итого сумматора по модЬю два подключены соответственно выходы второго и первого элементов НЕ, к третьим входам j-старших сумматоров по модулю два подключены выходы j-младших триггеров, а к третьим входам т-J-младших сумматоров по модулю два подключены выходы т-j-старших сумматоров по модулю два, выходы сумматоров по модулю два являются выходами генератора.

Источники информации, принятые во внимание при экспертизе

1.Яковлев В.В, и Федоров Р.Ф. Вероятностные вычислительные машины, Л., Машиностроение, 197, с. .

2.Авторское свидетельство СССР N 572823, кл. G 07 С 15/00, 1975 (прототип).

4 I

, / чх- / /

/ , / /

/ /

V

53 «:5- «5 «:э ,

Kjf 1 /I.1 /

«а С5 - « ,сэ .0 /сэ|Сэ «- Сэ ,c

- ,0 сг Сэ - -.-сэ г

С5,.С-, Са СЭ I й J СЭ , «5 , Х СЭ | L vтз1 -/ э ..-Сас:5-г а о , J

/ / ОСЭСЭ , 1 V3 V3 13( сэсэсэ сэ - ч. f «ъ It (| сэ - сэСэоо - сэ «а с:з йэ«5 «: сэ«- СэО ciC5 /o о - сз .-. - ,/ / N/ - - еэ /«э t:i- еэ- -f сэ сэ J 1/ 1 сэ(э СЭ - С5 - сэ1т-1сэ сэсэ1- -lov-.сэсэ- - - O.U/-.о ,V