Генератор псевдослучайных чисел
ОП ИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
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
