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

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

Иллюстрации

Показать все

Реферат

 

ОП И1САНЙЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

< )703852

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 05.05.77 (21) 2482846/18-24 (51) М. Кл .

G07 С 15/00

G 06 F 1/02 с присоединением заявки №вЂ”

Госудорстоенный комотет

СССР оо делам кзобретеиий и открытий (23) Приоритет—

Опубликовано 15.12.79. Бюллетень № 46

Дата опубликования описания 25.12.79 (53) УДК 681.325 (088.8) (72) А вторы изобретения

В. H. Ярмолик и С. Н. Демиденко

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

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

Известны генераторы псевдослучайных чисел на основе регистров сдвига с сумматорами по модулю два в цепи обратной связи (1) .

Однако генераторы такого типа имеют существенный недостаток. В случае выборки очередного псевдослучайного числа в каждый такт работы устройства наблюдается ® жесткая корреляция между последуюецими значениями многоразрядных кодов псевдослучайных чисел. Во избежание наличия корреляционной зависимости в таких устройствах необходимо. осуществлять выборку выходных чисел только через 1.:.К тактов, где К < и — разрядность псевдослучайного числа, а и — разрядность регистра сдвига.

Но при этом появляется второй существенный недостаток — малое быстродействие, которое в предельном случае в и раз меньше тактовой частоты работы устройства.

Данные недостатки устраняются в ряде устройств, позволяющих генерировать в каж2 дый такт многоразрядные некоррелированные псевдослучайные числа.

Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных чисел, содержащий первый и второй регистры сдвига (2).

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

Целью изобретения является расширение функциональных возможностей генератора за счет увеличения периода формируемой последовательности псевдослучайных чисел.

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

703852 4

I вую комбинацию. Число «О» мы получаем с периодом (2 — 1) (2 — 2) + 1, Через

2" — 1 тактов суммирования меняется состояние регистра 1, из него теперь будет поступать новое число, и весь предыдущий цикл повторяется. Так будет продолжаться до тех пор, пока регистр 1 не пройдет свой полный период.

Таким образом, общий период последовательности, выдаваемый предлагаемым генератором, определяется как o T = ((2" — 1) (2" — 2) + 1) (2 — 1) = (2 1) з

Использование предлагаемого генератора псевдослучайных чисел позволит без значительных аппаратурных затрат получать псевдослучайные числа с достаточно боль45 шим периодом повторения, что особенно важно при использовании его в вероятностных преобразователях и в устройствах преобразования входной информации стохастических вычислительных машин. Возмож2о ность получения числа «О» на выходе данного генератора улучшает качество выходной последовательности двоичных чисел.

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

" рй истра сдвига соответствейно, вход «сдвиг»

"кбторого подключен к выходу второго делителя частоты, вход которого объединен со вторыми входами группы элементов ИЛИ и подключен к первому входу элемента И и к выходу первого делителя частоты, вход которого является входом тактовых импуль сов и подключен ко второму входу элемента И, выход которого соединен со входом

«сдвиг» второго регистра сдвига.

Блок-схема генератора приведена на чертеже.

Генератор содержит первый и второй рекуррентные регистры 1 и 2 сдвига, первый и второй делители 3 и 4 частоты, группу 5 элементов И, входы которых соединены с выходами регистра 1 и группы 6 элементов

ИЛИ, а выходы — со входами регистра 2 выходы которого через элемент И-НЕ 7 соединены со входами группы 6 элементов

ИЛИ, вторые входы которых объединены со входом элемента И 8, подключены к выходу первого делителя 3 частоты и через второй делитель 4 частоты соединены со входом «сдвиг» регистра 1. Вход тактовых импульсов соединен со входом первого делителя 3 частоты и через элемент И 8— со входом «сдвиг» регистра 2.

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

После первоначального занесения произвольных чисел в регистры 1 и 2 по сигналам генератора тактовых импульсов в регистре 2

"начинает происходить смена состояний с периодом 2" — 1, На (2 — 1) -oM такте работы по сигналу делителя 3 частбты значения разрядов регистра 2 суммируются по модулю два со значением, находящимся в разрядах регистра 1. Получается новое число в регистре 2, которое дает начало новому элементарному циклу. На (2 — 1)-ом такте работы этого цикла происхбдит следующее изменение состояния регистра 2 и т. д. Элемент И 8 необходим для запрещения изменения состояния регистра 2 в такт суммирования.

Так как коэффициенты деления делителей 3 и 4 частоты равны 2 - — 1, то в течение

2" — 1 тактов суммирования из регистра 1 будет приХодить в качестве "слагаемого одно д

-" " - " и "то же число. Второе слагаемое, находящееся в разрядах регистра 2, в "каждом такте суммирования новое; поэтому йаступит такой момент, коГДа слагаемые совпадут, и "поскольку поразрядное суммирование ведется по модулю два, то результатом будет нулевая последовательность. В этом случае срабатывает элемент И-НЕ 7 и сигнал на его выходе разрешй«т проведейие еще одногб суммирования в следующий такт работы, результатом которого будет новде йисло в регистре 2. Еще один такт суммирования необходим, так как иначе регистр в течение

2" — 1 тактов генерировал бы только нулеГенератор псевдослучайных чисел, содержащий первый и второй регистры сдвига, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет увеличения периода формируемой последовательности псевдослучайных чисел, он содержит первый и второй делители частоты, элемент И-НЕ, элемент И, группу элементов ИЛИ и группу элементов И, выходы которых соединены со входами второго регистра сдвига соответственно, выходы которого являются выходами генератора и через элемейт И-НЕ соединены с первыми входами группы элементов ИЛИ, выходы которых соединены с первыми входами группы элементов И соответственно, вторые входы которых соединены с выходами первого регистра сдвига соответственно, вход «сдвиг» » которого подключен к выходу второго делителя частоты, вход которого объединен со

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

И, выход которого соединен со входом «сдвиг» второго регистра сдвига.

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

1. Яковлев В. В. и Федоров P. Ф. Стохастические вычислительные машины. Л., «Машиностроение», 1974, с. 246 — 270.

2. Авторское свидетельство СССР № 436340, кл. G 06 F 1/02, 1973 (прототип).

8хо

Составитель А. Карасов

Редактор Н. Лобач Техред О. Луговая Корректор Г. Решетняк

Заказ 7777/44 Тираж 669 Подписное

ЦНИИ ПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ПП П «Патент», г. Ужгород, ул. Проектная, 4