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

(51) М. Кл . 6 07 С 15/00 б 06 Г 1/02 1) 2482846/18-24 и-осудорстоенный комотет СССР оо делам кзобретеиий и открытийпубликовано 15.12.79. Бюлл ата опубликования описания етень 4625.12.79(72) А вторы изобретения В, Н. Ярмолик и С. Н. Демиденко инский радиотехнический институ 7) Заявител(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕ,Л Изобретение относится к области вычислительной техники и может быть использовано при моделировании случайных процессов,Известны генераторы псевдослучайныхчисел на основе регистров сдвига с сумматорами по модулю два в цепи обратнойсвязи (1.Однако генераторы такого типа имеютсущественный недостаток. В случае выборкиочередного псевдослучайного числа в каждый такт работы устройства наблюдается тжесткая корреляция между последуюецимизначениями многоразрядных кодов псевдослучайных чисел. Во избежание наличиякорреляционной зависимости в таких устройствах необходимо, осуществлять выборкувыходных чисел только через с,:.К тактов,где К(и - разрядность псевдослучайногочисла, а п - разрядность регистра сдвига.Но при этом появляется второй существенный недостаток - малое быстродействие,которое в предельном случае в и раз меньше 20тактовой частоты работы устройства.Данные недостатки устраняются в рядеустройств, позволяющих генерировать в каждый такт многоразрядные некоррелированные псевдослучайные числа,Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных чисел, содержащий первый и второй регистры сдвига 12.Такой генератор позволяет генерировать многоразрядные коды в каждый такт работы устройства, однако имеет малый период последовательности псевдослучайных чисел.Целью изобретения является расширение функциональных возможностей генератора за счет увеличения периода формируемой последовательности псевдослучайных чисел.Для достижения поставленной цели генератор содержит первый и второй делители частоты, элемент И-НЕ, элемент И, группу элементов ИЛИ и группу элементов И, выходы которых соединены со входами второго регистра сдвига соответственно, выходы которого являются выхода ми генератора и через элемент И-НЕ соединены с первыми входами группы элементов ИЛИ, выходы которых соединены с первыми входами группы элементов И соответственно, вторые входы которых соединены с выходами первого703852 Формула изобретенияргистра сдвига сбответствеино, входсдвиг- "кбторого подключен к выходу второго делителя частоты, вход которого объединен совторыми входами группы элементов ИЛИи подключен к первому входу элемента Ии к-выходу первого делителя частоты, входкоторого является входом тактовых импуль сов и подключен ко второму входу элемента И,выход которого соединен со входомсдвиг второго регистра сдвига.Блок-схема генератора приведена начертеже. 10Генератор содержит первый и второйрекуррентные регистры 1 и 2 сдвига, первыйи второй делители 3 и 4 частоты, группу 5элементов И, входы которых соединены свыходами регистра 1 и группы 6 элементовИЛИ, а выходы - со входами регистра 2,выходы которого через элемент И-НЕ 7 соединены со входами группы 6 элементовИЛИ, вторые входы которых объединенысо входом элемента И 8, подключены квыходу первого делителя 3 частоты и черезвторой делитель 4 частоты соединены совходом сдвиг регистра 1. Вход тактовыхимпульсов соединен со входом первого делителя 3 частоты и через элемент И 8 -со входом сдвиг регистра 2,2Работает генератор следующим образом.После первоначального занесения произвольных чисел в регистры 1 и 2 по сигналамгенератора тактовых импульсов в регистре 2- - "начинает происходить смена состояний спериодом 2" - 1, На (2 - 1) -ом такте ра- фботы по сигналу делителя 3 частбты значе-ния разрядов регистра 2 суммируются по" модулю два со значением, находящимся вразрядах регистра 1. Получается новое число в регистре 2, которое дает начало новомуэлементарному циклу. На (2 - 1)-ом тактеработы этого цикла происходит следующееизменение состояния регистра 2 и т. д. Элемент И 8 необходим для запрещения изменения состояния регистра 2 в такт суммирования. Так как коэффициентыделения делителей 3 и 4 частоты равны 21. - 1, то"в течение 2" - 1 тактов суммирования из регистра 1 будет "приходить в"качестве"слагаемого одно -" " -"и"то же число. Второе слагаемое, находящееся в разрядах регистра 2, в"каждом такте суммирования-новое; поэтомуйаступит такой момент, коГДа"слагаемые совпадут, и "поскольку поразрядное суммирование ведется по модулю два, то результатом будет ф нулевая последовательность. В этом случае срабатывает элемент И-НЕ 7 и сигнал на его выходе рфазрешйт йроведейие ещеодногб суммирования в следующий такт работы, результатом которого будетновое ййсловрегистре 2, Еще один такт суммирования необходим, так какиначе регистрв течение 2" - 1 тактов генерировал бы только нуле 4вую комбинацию, Число О мы получаем с периодом (2 - 1) (2 - 2) + 1, Через 2" - 1 тактов суммирования меняется состояние регистра 1, йз него теперь будет поступать новое число, и весь предыдущий цикл повторяется. Так будет продолжаться до тех пор, пока регистр 1 не пройдет свой полный период.Таким образом, общий период последовательности, выдаваемый предлагаемым генератором, определяется какТ - (2" - 1) (2 - 2) + 1 (2 - 1) =(2". 1) 3Использование предлагаемого генератора псевдослучайных чисел позволит без значительных аппаратурных затрат получать псевдослучайные числа с достаточно большим периодом повторения, что особенно важно при использовании его в вероятностных преобразователях и в устройствах преобразования входной информации стохастических вычислительных машин. Возможность получения числа О на выходе данного генератора улучшает качество выходной последовательности двоичных чисел. Генератор псевдослучайных чисел, содержащий первый и второй регистры сдвига,отличающийся тем, что, с целью расширения функциональныхвозможностей генератора за счет увеличения периода формируемой последовательности псевдослучайных чисел, он содержит первый и второй делители частоты, элемент И-НЕ, элемент И, группу элементов ИЛИ и группу элементов И, выходы которых соединены со входами второго регистра сдвига "соответственно, выходы которого являются выходами генератора и через элемейт И-НЕ соединены с первыми входами группы элементов ИЛИ, выходы которых соединены с первыми входами группы элементов И соответственно, вторые входы которых соединены с выходами первого регистра сдвига соответственно, вход сдвигф которого подключен к выходу второго делителя частоты, вход которого объединен со вторыми входами группы элементов ИЛИ и подключен к первому входу элемента И и к выходу первого делителя частоты, вход которогоявляетсявходом тактовых импульсов и подключен ко второму входу элемента И, выходкоторого соединен совходом сдвиг второго регистра сдвига. Источники информации,принятые во внимание при экспертизе . 1. Яковлев В. В. и Федоров Р. Ф. Стохастические вычислительные машины. Л.,Машиностроение, 1974, с. 246 - 270. 2. Авторское свидетельство СССР436340, кл. б 06 Г 1/02, 1973 (прототип).ьА.Каговая в Редактор Н. Лобач Заказ 7777(44 ПИ Го делам Москва ф П Па