Генератор псевдослучайных чисел Советский патент 1979 года по МПК G07C15/00 G06F1/02 

(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

1

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

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

Однако генераторы такого типа имеют существенный недостаток. В случае выборки очередного псевдослучайного числа в каждый такт работы устройства наблюдается жесткая корреляция между последующими значениями многоразрядных кодов псевдослучайных чисел. Во избежание наличия корреляционной зависимости в таких устройствах необходимо .осуществлять выборку выходных чисел только через 1: тактов, где - разрядность псевдослучайного числа, an - разрядность регистра сдвига. Но при этом появляется второй существенный недостаток - малое быстродействие, которое в предельном случае в п раз меньше тактовой частоты работы устройства.

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

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

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

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

Для достижения поставленной цели генератор содержит первый и второй делители частоты, элемент И-НЕ, элемент И, группу элементов ИЛИ и группу элементов И, выходы которых соединены со входами второго регистра сдвига соответственно, выходы которого являются выходами генератора и через элемент И-НЬ соединены с первыми входами группы элементов ИЛИ, выходы которых соединены с первыми входами группы элементов И соответственно, вторые входы которых соединены с выходами первого pefйСтpa с дви г а сбответстве ййго, вход« сд в иг которого подключен Квыходу второго делителя частоты, вход которого объединен со вторыми входами группы элементов ИЛИ и подключен к первому входу элемента И и К выходу первого делителя частоты, вход Которого является входом тактовых импуль гов и подключен ко второму входу элемента И, выход которого соединен со входом «сдвиг второго регистра сдвига. Блок-схема генератора приведена на чертеже. Генератор содержит первый и второй рекуррентные регистры 1 и 2 сдвига, первый и второй делители 3 и 4 частоты, группу 5 элементов И, входы которых соединены с выходами регистра, 1 и группы 6 элементов ИЛИ, а выходы - со входами регистра 2, выходы которого через элемент И-НЕ 7 соединены со входами группы 6 элементов ИЛИ, вторые входы которых объединены со входом элемента И 8, подключены к выходу первого делителя 3 частоты и через второй делитель 4 частоты соединё ны со входом «сдвиг регистра 1. Вход тактовых импульсов соединен со входом первого делителя 3 частоты и через элемент И. 8 - со входом «сдвиг регистра 2. Работает генератор следующим образом. После первоначального занесения произвольных чисел в регистры 1 и 2 по сигналам генератора тактовых импульсов в регистре 2 начинает происходить смена состояний с периодом L На ( 1)-ом такте работы по сигналу делителя 3 ча :тотьГзначёния разрядов регистра 2 суммируются по модулю два со значением, находящимся в разрядах регистра 1. Получается новое число в регистре 2, которое дает начало новому элементарному циклу. На ()-ом такте работбг этого цикла происход йТ следующее изменение состояния регистра 2 и т. д. Элемент И 8 необходим для запрещения изменения состояния регистра 2 в такт суммиро.вания. Так как коэффициентыделения делителей 3 и 4 частоты равны 1, Т О в течение тактов суммирования из регистра 1 б ёт11фМеДитГ%ТйЧествесЛ аг&ейого одно же число. Второе слагаемое, находящееся в разрядах регистра 2, в каждом тактё ёумиирования новое, поэтому наступит такой й01йент, коГДа слагае мые совпадут, ипоскольку поразрядное суммирование ведется по модулю два, то результатом будет нулевая последовательность. В этом случае срабатывает элемент И-НЕ 7 и сигнал на .,.,-- . .------ f. --.--.. -- - -. -- -t,-.™1-..-:;.wi-4.,Jtjt..--- - ; Г - - .- его выходе разрещит проведение еще одного суммирования в следующий такт работы, результатом которого буДе нО&6ё й6лО1в регистре 2. Еще один такт суммирования необходим, так как иначе регистр в течение . тактов генерировал бы только нулевую комбинацию. Число «О мы получаем с периодом ()() + L Через 1.тактЪв суммирования меняется состояние регистра 1, из него теперь будет поступать новое число, и весь предыдущий цикл повторяется. Так будет продолжаться до тех пЬр, пока регистр 1 не пройдет свой полный период. Таким образом, общий период последовательности, выдаваемый предлагаемым генератором, определяется как Т : ()() + 1(2 - 1) () . ИспОлШОвание предлагаемого генератора псевдослучайных чисел позволит без значительнь1Х аппаратурных затрат получать псевдослучайные числа с достаточно больщим периодом повторения, что особенно важно при использовании его в вероятностных преобразователях и в устройства преобразования входной информации стохастических вычислительных мащин. ВозможнОстЬ получения числа «О на выходе данного генератора улучшает качество выходной последовательности двоичных чисел. Формула изобретения Генератор псевдослучайных чисел, содержащий первый и второй регистры сДвига, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет увеличения периода формируемой пъследовательности псевдослучайных чисел, он содержит первый и второй делители частоты, элемент И-НЕ, элементИ, группу элементов ИЛИ и группу элементов И, выходы которых соединены со входами второго регистра сдвТ1 ГасОотве±ственно, выходы которого являются выходами генератора и через элемент И-НЕ СОеЖнены с первыми входами группы элементов ИЛИ, выходы которых соединены с первыми входами группы элементов И соответственно, вторые входы которых соединены с выходами первого регистра сдвига соответственно, вход «сдвиг Которого подключен к выходу второго дели-; теля частоты, вход которого объединен со -вторыми входами группы элементов ИЛИ И подключен К первому входу элемента И и к выходу первого Делителя частоты, вход котОрогО является ВХОДОМ тактовых импульсов и подключен ко второму входу элемента И, выходК0т0р 0г0 соединен со входом «сдвиг второго регистра сдвига. Источники информации, приняТйе йо внимание при экспертизе . 1.Яковлев В. В. и Федоров Р. Ф. Стохастические вычислительные мащины. Л., «Машиностроение, 1974, с. 246 - 270. 2.Авторское свидетельство СССР № 436340, кл. G 06 F 1/02, 1973 (прототип).

о

,

ОГрГ

; |ПГ Т -f

::х