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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскик

Социалистические

Рвслублик ()890391 (61) Дополнительное к авт. свид-ву (51)М. Кл.

G 06 F 7/58 (22)Заявлено 300480 (21) 2919555/18-24 с присоединением заявки 1Е (23) Приоритет

Эв лвретеенай квинтет

СССР ао делан взееретевиН н вткрытнв (53) УДК681 ° 325 (088. 8) Опубликовано 15,1281. Бюллетень М 46

Дата опубликования описания 15.1281 (72) Авторы изобретения

В. Н. Ярмолик, A. Е. Леусенко и А. Н. Морозевич

Минский радиотехнический институт (71) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Изобретение относится к вычислитель|ной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, для построения генераторов случайных процессов с заданными характеристиками, а также для генерирования случайных процессов с равномерным спектром, используемых для идентификации систем автоматического управления. то

Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два Щ.

Недостатком этого генератора явля15 ется сложность структурного построения, методика синтеза подобного генератора псевдослучайных чисел значи тельно затруднена . Кроме того, для построения генератора псевдослучайных чисел необходимо выбирать такие структуры исходных генераторов, у ко" торых периоды являются взаимно простыми числами.

Известен также параллельный генератор псевдослучайных чисел, который отличается максимальной величиной быстродействия и позволяет формировать многоразрядные псевдослучайные числа t2) .

Недостаток этого генератора заключается в сложности схем формирования сдвинутых прследовательностей, определяемой числом входов сумматоров по модулю два. Каждый сумматор в среднем имеет m/2 входов. При этом затраты оборудования, необходимые для схем формирования сдвинутых последоI вательностей, в несколько раз превышают затраты, идущие на построение кольцевого регистра сдвига.

Наиболее близким техническим решением к предлагаемому изобретению является генератор псевдослучайных чисел, содержащий m-разрядный регистр сдвига, два элемента И и элемент ИЛИ, которые реализуют операцию сложения по модулю два содержимого m-ro u j-го

890391 разряда регистра сдвига. Номер j-го разряда в зависимости от разрядности регистра сдвига m выбирается из таблицы P) .

Недостатком этого устройства является отличие вероятности появления нуля или единицы на его выходе от

0 5 °

Цель изобретения - повышение точности генератора. 0

Пост а вленная цел ь дости гает ся т ем, что в генератор псевдослучайных чисел, содержащий m-разрядный регистр сдвига, первый элемент И, к первому входу которого подключен инверсный выход m-ro разряда регистра сдвига

RC второй элемент И, к первому входу которого подключен прямой выход m- го разряжая ре ги стра сдвига, элемент

ИЛИ, выход которого подключен ко вхо-, 20 ду первого разряда регистра сдвига, дополнительно введены третий элемент

И, четвертый элемент И и элемент

ИЛИ-НЕ, причем ко вторым входам первого и второго элементов И подключе- д5 ны инверсный и прямой выходы j-го разряда регистра сдвига соответственно, а выходы первого и второго элементов

И пддключены к первому и второму входам элемента ИЛИ-НЕ, ко входам четвер- З0 того элемента И подключены инверсные выходы m-1 первых разрядов регистра сдвига, а -выход четвертого элемента И подключен к третьему входу элемента

ИЛИ-HE и к пер вому входу трет ье го элеме нт а И, ко второму входу которо ro

35 подключен инверсный выход m -го разря- да. ре ги стра сд ви ra, выход элемент а .ИЛИ-НЕ подключен .к первому входу weмента ИЛИ, ко второму входу которого

40 подключен выход третьего элемента И.

На фиг. 1 приведена функциональная схема генератора; на фиг. 2 - последовательность состояний известного (а) и предлагаемого (б) генераторов приа=3и 1 =1.

Генератор состоит из регистра сдвига 1 первого, второго и третьего элементов И 2, 3, 4, четвертого элемента И 5, элемента ИЛИ-HE 6, и элемента

ИЛИ 7. К первому входу первого элемента И 2 подключен инверсный выход

m-ro разряда регистра сдвига 1, к первому входу второго элемента И 3 подключен прямой выход m-го разряда регистра сдвига 1, а выход элемента

ИЛИ 7 подключен ко входу первого разряда регистра сдвига 1. Ко вторым входам пер во ro и второго зле ме нт а И 2 и 3 подключены инверсный и прямой выходы j-го разряда регистра сдвига 1 соответственно, а выходы первого и второго элементов И 2 и 3 подключены к первому и второму входам элемента

ИЛИ-НЕ 6, ко входам четвертого элемента И 5 подключены инверсные выходы

m-1 первых разрядов регистра сдвига 1, а его выход подключен к третьему входу элемента ИЛИ-НЕ 6 и первому входу третьего элемента И 4, ко второму входу которого подключен инверсный выход

m-го разряда регистра сдвига 1, выход элемента ИЛИ-НЕ 6 подключен к первому входу элемента ИЛИ 7, а ко второму входу элемента ИЛИ 7 подключен выход третьего элемента И 4.

Генератор работает следующим образом.

В исходном состоянии регистр сдвига содержимое k-ro разряда может принимать значение нуля или единицы. В отличие от известных генераторов в данном генераторе в первоначальный момент в разрядах регистра 1 может находит ься нуле вой код. В за виси мости от начального кода на выходе комбинационной части, т.е. на выходе элемента ИЛИ 7, формируется символ, равный нулю или единице. По приходу тактового импульса содержимое регистра сдвига 1 сдвигается на один разряд вправо, а в первый разряд записывается символ, сформированный на выходе элемента ИЛИ 7. При значениях содержимого первых m-1 разрядов регистра сдвига 1, отличных от нуля, элементы

2, 3, 6 и 7 реализуют операцию суммирования по модулю два содержимого

j-го и m-го разрядов регистров сдвига, В этом слу чае ге нерируе т ся И- последовательность, как и в известном. Далее, при появлении в первых m-1 разрядах регистра 1 нулевой ко ;бинации на выходе элемента 5 появляется единичный уро вен ь, который обеспе чивает появление на входе первого разряда регистра сдвига 1 нуля.

При поступлении очередного тактового импульса в регистре сдвига 1 находятся нулевые значения во всех разрядах. Появление нуля в m-ом разряде обеспечивает появление единицы на выходе элемента 4, которая через элемент 7 поступает на вход первого разряда ре,истра сдвига 1. Очередной тактовый импульс обеспечивает появление в ре ги ст ре .сд ви га 1 комби нации 100... 0, т.е. нулей ho всех разрядах, кроме

3О

Формула изобретения

ff f

t0f

01g

001

110

1f1

0ff

101

01д

001 опо

1DQ

Фи2.2

ВНИИПИ Заказ11007/78 Тираж 748 Подписное филиал ППП"Патент", r. Ужгород,ул. Проектная,4

5 89039 первого. Далее, так же как и известном, генерируется М-последовательность. B этом случае содержимое первых m-1 разрядов регистра сдвига 1 отлично от нуля и элементы 2, 3, 6 и 7 реализуют 3 операцию суммирования по модулю два.

Как видно из фиг. 2 последовательI ность на выходе предлагаемого генератора отличается от М-последовательности, полученной на выходе известного толь- 1О ко кодом 000, следующим после кода

001.

Введение нулевой комбинации в Мпоследовательность позволяет приблизить вероятность нуля и единицы к

0,5. В силу того, что количество нулей и единиц в выходной последова тельности генератора равняется 2, а количество символов 2, вероятность нуля и единицы на выходе системы равняется 0,5. Кроме того, дополнительные затраты оборудования составляют всего три логических элемента.

Применение подобного генератора псевдослучайных чисел позволит, повысить качество псевдослучайных последовательностей, а тем самым точность и достоверность решения задач методом

Монте-Карло.

Генератор псевдослучайных чисел, содержащий m-разрядный регистр сдвига, 3$ первый элемент И, к первому входу ко1 б торого подключен инверсный выход m-f о разряда регистра сдвига, второй элемент И, к первому входу которого подключен прямой выход m ãî разряда регистра сдвига, элемент ИЛИ, выход которого подключен ко входу первого разряда регистра сдвига, о т л и ч а юшийся тем, что, с целью повышения точности генератора, он содержит третий элемент И, четвертый элемент

И, элемент ИЛИ-НЕ, причем ко вторым входам первого и второго элементов И подключены инверсный и прямой выходы

j-го разряда регистра сдвига соответственно, а выходы первого и второго элементов И подключены к первому и второму входам элемента ИЛИ-НЕ, ко входам четвертого элемента И подключены инверсные выходы m-1 первых разрядов регистра сдвига, а выход четвертого элемента И подключен к третьему входу элемента ИЛИ-НЕ и к первому входу третьего элемента И, ко второму входу которого подключен инверсный выход m го разряда регистра сдвига, а выход элемента ИЛИ-НЕ подключен к первому входу элемента ИЛИ, ко второму входу которого подключен выход третьего элемента И.

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

Яковлев В.В., Федоров P.Ô. Вероятностные вычислительные машины. Л., "Машиностроение", 1974, с. 263.

2. Там же, с. 254.

3. Там же с. 247 (прототип)