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

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

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик

3Ъаударствеииый комитет

СССР (23) Приоритет ио делам изобретений и открытий (53) У@К 81 ..g2g (088.8) ОпУбликовано 07.07.82. бюллетень .щ 25

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

A.Н. Белевич (71) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

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

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

ra с сумматором по модулю два в цепи обратной связи t,1), Его недостатком являются неудовлетворительные статистические свойства.

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

Однако этот генератор не позволяет получать псевдослучайные числа с основанием K.

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

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

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

3 9420 держки соединен с управляющим входом первого счетчика и непосредственно - с входом генератора И-последовательности, разрядные выходы которогб соединены с соответствующими разрядными входами первого счетчика, выход которого соединен непосредственно с управляющим входом регистра памяти, через второй элемент задержки - с входом "Сброс" ;в второго счетчика и непосредственнос нулевым входом триггера, единичный вход которого через третий эле" мент задержки подключен к выходу первого элемента задержки, а Выход тРИГГЕРа СОЕДИНЕН С ПЕРВЫяи ВХОДОМ элемента И, второй вход которого соединен с выходом генератора тактовых импульсов.

На фиг. 1 приведена блок-схема генератора; на фиг. 2 - гистограмма генератора.

Генератор содержит M-последовательности, состоящий из регистра 1 с сумматором 2 по модулю два В

25 цепи обратной связи.

Разрядные входы счетчика ),подключены к соответствующим разрядным выходам регистра 1. Вход управления записью счетчика 3 подключен к входу запуска генератора через первый элемент 4 задержки, а выход

"Все нули" подключен к входу сброса триггера 5, входу управления записью регистра 6 памяти и через

Зс второй элемент 7 задержки - к Входу сброса счетчика 8я .Выход первого элемен;а ч задержки через третий элемент 9 задержки подключен также к входу . становки триггера 5„ Bblxop которого подключен к первому входу элемента И 10. Второй вход элемента

И 10 соединен с выходом генератора

11 тактовых импульсов, а выход с входом вычитания счетчика и с

45 входом сложения счетчика 8. Разрядные выходы счетчика 8 соединены с соответствующими разрядными входами регистра 6 памяти, а разрядные Выходы последнего являются разрядными выходами генератора. Счетчик 8 считает по модулю К. На фиг. 2 показаны распределения вероятностей появления двоичных псевдослучайных чисел на выходах регистра (кривая 7) и на выходе генератора (кривая 8)„ пунктиром (кривая 9) показано идеально равномерное распределение

К-ичных чисел. По оси абсцисс

Отложены числа М = 0,1, 2 1 "(где

И - число разрядных входов сдвигоВого регистра 1, подключенных к разрядным Входам счетчика. 3), и выделено S участков оси, кратных числу

К-основа.;ию заданной системы счисления, По оси Ординат Отложены вероятность формирования числа на выходах сдвлгового регистра 1, равная

1 — н средняя ееррятнрсте ооявления К-ичных чисел на Выходе генератора, равная

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

Перед началом формирования Очереднор-О псевдослучайного числа на информационный Вход регистра 1 по-. ступает сигнал с вь;хода сумматора

"o модулю 2, значение которого Определяется значениями тех разрядов сдвигового регистра 1, aü.õoäû;

ТЕМ СВМЫМ На ВХОД Запv ÑÊoo СДВИГО

Вого реглсеоа 1) содержимое регистра пер чещается на один разряд, а В первый разряд загисывается значеНИЕе СООтВЕтСтВУЮЩЕЕ CV.ÃHàЛУ НВ ИНфоРмаЦионном "oõoÄå РегистРа 1, На разрядных Выходах регистра 1, подключенных K разрядным Входам счетЧИКа У, ПОЯВЛЯЕТСЯ ОЧЕРЕДНОЕ ДВОИЧное псевдослу айно-" число, Через время, достаточное для завершения переходных процессов в регистре 1, на вход управления записью

c«eò«HKà ) с выхода элемента 4 задержки поступает задержанный сигнал запуска генератора и Очередное двоичное псевдо лучайное число записывается в счетчик 3, Через время, достаточнОВ для p танОВки разрядных триггеров счетчика з соо "ВетствуЮЩЕЕ ЭТОМУ ЧИСЛУ СОСтОЯНИЯе С ВЫХОДа элемента 9 задержки на вход установки триггера 5 поступает дополнительно задержанный сигнал запуска генератора, и триггер 5 устанавливается в циничное состояние. На первый

Вход элемента l 10 при этом поступает сигнал, разрешающий прохождение импульсОВ, непрерывно формируемыми генератором 11 импульсов и поступающих на второй вход элемента

И 10. Импульсы с выхода элемента

И 10 поступают одновременнс на Вход

Вычитания счетчика 3 и на Вход сло942014 пунктирными линиями, происходящее с вероятностью, плотность распределения которой соответствует кривой

7, приведет к появлению на выходе устройства К-ичного псевдослучайного числа, численно равного расстоянию двоичного псевдослучайного числа от и нижней границы соответствующего ин1, тервала. Неравномерность в распреде10 лении вероятностей 8 формирования

К-ичных псевдослучайных чисел обусловлено тем, что из S 4- 1 интервалов первый и последний имеют области, вероятность попадания двоичного

15 псевдослучайного числа в которых равна нулю, Максимальная вероятность формирования К-ичных псевдослучайных чисел соответствует области t l, 20 2 - S К - 1) внутри первого интервала, так как вероятность попадания двоичного псевдослучайного числа в соответствующую область любого из S + 1 интервалов отлична от

25 5l0X + 1

0 и равна Р к псх

В областях (0,1) и (2 "- S ° К-1, К-1) вероятность формирования К-ичных псевдослучайных чисел равна

Зо, РК „ =, так как вероятность псевдослучайного числа в соответствующей области не равна 0 только в S интервалах.

З5 Отклонение распределения вероятностей формирования К-ичных псевдослучайных чисел на выходе устройства от идеальной, для которой вероятность формирования любого К-ично40 ro псевдослучайногп числа равна

P, = —, описывается разностями

1 S

"и* к пс = К

5 жения счетчика 8, С приходом каждого очередного импульса содержимое счетчика 3 уменьшается, а счетчика 8 увеличивается. После того, как содер жимое счетчика 8 достигает К-1, очередной импульс установит этот счетчик в нулевое состояние, таким образом содержимое этого счетчика в любо момент времени не превышает числа КПосле прихода на вход вычитания счетчика 3 количества импульсов, равного ранее записанному в него двоичному числу, его содержимое станет равным нулю и на его выходе нВсе нули" возникает соответствующий сигнал. Этот сигнал, поступив на вход сброса триггера 5 сбросит его в такое состояние, при котором прекратится прохождение импульсов через элемент И 10. Одновременно сигнал "Все нули" поступит на вход записи регистра 6 и двоичный код числа, накопленный к этому моменту в счетчике 8 (этот код, очевидно, соответствует остатку сформированного двоичного псевдослучайного числа по модулю I(), будет записан в регистр 6, сменив в нем код предыдущего исла, и поступит на выход генератора. Через промежуток времени, достаточный для окончания переписи кода из счетчика 8 в регистр

6, на вход сброса счетчика 8 через элемент 7 задержки поступит сигнал

"Все нули", счетчик 8 установится при этом в нулевое состояние, подготавливаясь тем самым к формированию следующего К-ичного псевдослучайного числа, Следует отметить, что для увеличения длины формируемой последовательности К-ичных псевдослучайных чисел (т.е, периода повторения чисел в этой последовательности) число разрядов регистра 1 может быть выбрано большим, чем число разрядов счетчика 3 (т.е. больше N).

Отклонение распределения вероятностей появления К-ичных чисел на выходе устройства (фиг. 2, кривая 8) от идеального зависит от соотношения между числами К и М (т.е. основанием выходной системы счисления и числом разрядов двоичного псевдослучайного числа) следующим образом. формирование генератором двоичного псевдослучайного числа в любом из кратных числу К интервалов (i К (i+1)- К), отмеченных на фиг. 2

max 5+1 1 к пс> ИА 222-1 1К и

Практически при Ь ) 1О указанное отклонение не превышает 2i, что вполне достаточно для практических целей.

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

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

9420

Генератор псевдоспучайных чисел, содержащий генератор И"последовательности; два счетчика, регистр памяти, генератор тактовых импульсов, отличающийся тем, что, с целью расширения области его применения за счет использования си темы счисления с основанием К, сн со- 10 держит три элемвнта задержки, триггер и элемент И, выход которого roераеее с вычитающим входом первого счетчика и суммирующим входом второго счетчика, разрядные выходы которого соединены с соответствующими разрядными входами регистра памяти выходы которого являются выходам. генератора, вход которого через пер" вый элемент задержки соединен с 26 управляющим входом noopBorc, счетчика и непосредственно - с входом генератора И-последовательности, разрядные

1й 8 выходы которого соединены с соответ ствующими разрядными входами первого счетчика, выход которого соединен

:йепосредственно с управляющим входом регистра памяти, через второй элемент задержки с входом "Сброс" второго счетчика и непосредственно " с нулевым входом триггера, единичный вход которого через третий элеМент задержки подключен к выходу первого элемента задержки, а выход триггера с ед нен с первым входом элемента И, втооой вход которого соединен с выход;и .енератора тактовых импульсов.

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

1. Бобнев И.П. Генерирование слу" чайных сигналов. М., Энергия", 1971, ". ?00.

2. Лвторское свидетельство СССР ;" 656086, кл. G 06 F 1/02, 1977 (прототип).

94201 4

К фиг. 2

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

Редактор П. Макаревич Техред Ж. Кастелевич Корректор V.Пономаренко

Заказ 4841/39 Ти раж 731 Подписное

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

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

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