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

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

1

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

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

Его недостатком являются неудовлетворительные статистические свойства.

Наиболее близким по технической сущности к предлагаемому является генератор псевдослучайных чисел, содержащий генератор М-последовательности, счетчики, генератор тактовых импульсов, регистр памяти 123Однако этот генератор не позволяет получать псевдослучайные числа с основанием К,

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

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

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

20 выходы которого соединены с соответствующими разрядными входами регистра памяти, выходы которого являются выходами генератора, вход которого через первый элемент, задержки соединен с управляющим входом первого счетчика и непосредственно - с входом генератора М-последовательности, разрядные выходы которого соединены с соответствующими разрядными входами первого счетчика, выход которого соединен непосредственно с управляющим входом регистра памяти, через второй элемент задержки - с входом Сброс второго счетчика и непосредственно с нулевым входом триггера, единичный вход которого через третий элемент задержки подключен к выходу первого элемента задержки, а выход триггера соединенс первым входок элемента И, второй вход которого со единен С выходом генератора тактовых импульсов. На фиг. 1 приведена блок-схема генератора; на фиг. 2 - гистограмма генератора. Генератор содержит М-последовательности, состоящий из регистра 1 с сумматором 2 по модулю два в цепи обратной связи. Разрядные входы счетчика 3.подключены к соответствующим разрядным выходам регистра 1 . Вход yпpaвлeн - Я записью счетчика 3 подключен к входу запуска генератора через первый элемент задержки, а выход Все нули подключен к входу сброса триггера S, входу управления записью регистра 6 памяти и через второй элемент 7 задержки - к входу сброса счетчика С. .Выход первого элемента k задержки через третий элемент 9 задержки подключен также к входу установки триггера 5, выход которого подключен к первому входу элемента И 10. Второй вход элемента И 10 соединен с выходом генератора 11 тактовых импульсов, а выход с входом вычитания счетчика 3 и с входом сложения счетчика 8, Разрядные выходы счетчика 8 соединены с соответствующими разрядными входами регистра 6 памяти, а разрядные выходы последнего являются разрядными выходами генератора. Счетчик 8 считает по модулю К, На фиг, 2 пока заны распределения вероятностей появления двоичных псевдослучайных чисел на выходах регистра (кривая/ и на выходе генератора (кривая 8), пунктиром (кривая 9) показано идеально равномерное распределение К-ичных чисел. По оси абсдисс 4 отложены числа М 0,1, (где N - число разрядных входов сдвигового регистра 1, подключенных к разрядным входам счетчика. 3) , и выделено S участков оси, кратных числу К-основа ;ив заданной системы счисления. По оси ординат отложены вероятность формирования числа на выходах сдвигового регистра 1, равная YW средняя вероятность появления К-ичных чисел на выходе генератора, равная , Генератос работает следуюш.им образом. Перед началом формирования очередного псевдослучайного числа на информационный зход регистра 1 по-ступает сигнал с выхода сумматора по модулю 2, значение которого определяется знамениями тех разрядов сдвигового регистра 1, выходы которых подключен - к входам сумматора 2, При поступлении управляющего сигнала на вход запуска генератора (и тем самым- на вход запуска сдвигового регистра 1) содержимое регистра перемещается Нгэ один разряд, а в первый разряд записывается зн.зчениеJ соответствующее сигналу нг информационном вход€ регистра 1 . На разрядных выходах регистра 1, подключенных к разрядным входам счетчика 3 появляется очередное двоичное псевдослучайное число. Через время, достаточное для завершения переходных процессов Б регистре 1f на вход управления записью счетчика 3 с выхода элем&нта задержки поступает задержанный сигнал запуска генератора и очередное двоиМное псевдослучайное число записывается в счетчик 3. Через время, достат-очное для установки разрядных триггеров счетчика 3 з сооветствующее этому числу состояния, с выхода эле.мента 9 задер кки на вход установки триггера 5 поступает дополнительно задержанный сигнал запуска генератора, и триггер 5 устанавливается в циничное состояние. На первый вход элемента И 10 при этом поступает сигнал, разрешающий прохождение импульсов, непрерывно формируемыми генератором 11 импульсов и поступающих на второй вход элемента И 10о Импульсы с выхода элемента И 10 поступают одновременно на вход вычитания счетчика 3 и на зход еложения счетчика 8. С приходом каждого очередного импульса содержимое счетчика 3 уменьшается, а счетчика 8 увеличивается. После того, как соде жимое счетчика 8 достигает К-1, очередной импульс установит этот счетчик в нулевое состояние, таким обра зом содержимое этого счетчика в люб омент времени не превышает числаК После прихода на вход вычитания счетчика 3 количества импульсов, травного ранее записанному в него двоичному числу, его содержимое станет равным нулю и на его выходе Все нули возникает соответствующий сигнал. Этот сигнал, поступив на вход сброса триггера 5 сбросит его в такое состояние, при котором прекратится прохождение импульсов через элемент И 10. Одновременно сигнал Все нули поступит на вход записи регистра 6 и двоичный код числа, накопленный к этому моменту в счетчике 8 (этот код, очевидно, соответствует остатку сформированного двоичного псевдослучайного чис ла по модулю К), будет записан в регистр 6, сменив внем код предыдущего числа, и поступит на выход генератора. Через промежуток времени, достаточный для окончания переписи кода из счетчика 8 в регистр 6, на вход сброса счетчика 8 через элемент 7 задержки поступит сигнал Все нули, счетчик 8 установится при этом в нулевое состояние, подготавливаясь тем самым к формированию следующего К-ичного псевдослучайного числа. Следует отметить, что для увеличения длины формируемой последовательности К-ичных псевдослучайных чисел (т.е. периода повторения чисел в этой последовательности) число разрядов регистра 1 может быть выбрано большим, чем число разрядов счетчика 3 (т.е. больше М). Отклонение распределения вероятностей появления К-ичных чисел на выходе устройства (фиг. 2, кривая 8) от идеального зависит от соотношени между числами К и N (т.е. основание выходной системы счисления и числом разрядов двоичного псевдослучай ного числа) следующим образом. Фор мирование генератором двоичного псевдослучайного числа в любом из кратных числу К интервалов iK (i+1)-KJ, отмеченных на фиг. 2 пунктирными линиями, происходящее с вероятностью, плотность распределения которой соответствует кривой 7, приведет к появлению на выходе устройства К-ичного псевдослучайного числа, численно равного расстоянию двоичного псевдослучайного числа от нижней границы соответствующего интервала. Неравномерность в распределении вероятностей 8 формирования К-ичных псевдослучайных чисел обусловлено тем, что из S -f- 1 интервалов первый и последний имеют области, вероятность попадания двоичного псевдослучайного числа в которых равна нулю. Максимальная вероятность формирования К-ичных псевдослучайных чисел соответствует области , 2 - S-Kf l внутри первого интервала, так как вероятность попадания двоичного псевдослучайного числа в соответствующую область любого из S + 1 интервалов отлична от nvnqx О и равна Р „са В областях (0,1) и ( K-l, К-1) вероятность формирования К-ичных псевдослучайных чисел равна К сп ТТГ вероятность псевдослучайного числа в соответствующей области не равна О только в S интервалах. Отклонение распределения вероятностей формирования К-ичных псевдослучайных чисел на выходе устройства от идеальной, для которой вероятность формирования любого К-ичного псевдослучайного числа равна иА 17 описывается разностями р - р UA кпса Практически при S 10 указанное отклонение не превышает 2%, что вполне достаточно для практических целей. Таким образом, предлагаемое устройство в отличие от известных обеспе чивает формирование равномерно распределенных чисел в заданной системе счисления, что расширяет его функциональные возможности. формула изобретения Генератор псевдослучайных чисел, содержащий генератор Н последо8ател ности, два счетчика, регистр памяти генератор тактовых импульсов, отличающийся тем, что, с целью .расширения области его применения за счет использования системы счисления с основанием К, он содержит три элемента задержки, три|- гер и элемент И, выход которого соединен с вычитающим входом первого счетчика и суммирующим входом второго счетчика, разрядные выходы которого соединены с соответствующими разрядными входами регистра памяти выходы которого являются выходами генератора, вход которого через первый элемент задержки соединен с управляющим входом первого счетчика и непосредственно - с входом генератора М-последовательности, разрядные

,ж.

//

1

ю

-п.„,

:

П-дд и.ту-li

S 9

g ® 15

J

/

V

К- 18 выходы которого соединены с соотвеТ ствуощими разрядными входами перво™ го счетчика, выход которого соединен непосредственно с управляющим входом регистра памяти, через второй элемент задержки с входом Сброс второго счетчика и непосредственно с нулевым входом триггера, единичный вход которого через третий элейент задержки подключен к первого элемента задержки, а выход триггера соединен с первым входом элемента И, втооой вход которого соединен с выхоД-.м --енератора тактовых импульсов. Источники информации, принятые во внимание при экспертизе 1,Вобнев М.П. Генерирование случайных сигналов. М,, Энергия, 1971 , с. 200. 2.Авторское свидетельство СССР № 656086, кл. G 06 F 1/02, 1977 (прототип).

01 г-s-K-i к-1

фиг. г

)-H-1

2К-1 К-1