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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик и 942014(23) Приорнтет во делам изобретений н открытий(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ 1Изобретение относится к вычисли.тельной технике, а именно к уст"ройствам формирования псевдослучайных помледовательностей равномерно распределенных чисел и можетбыть использовано для формированияравномерно эаспределенных псевдослучайных чисел в системе счисления с заданным основанием при ре"шении выцислительных задач методомМонте-Карло, для формированиявходных воздействий при испытаниях К-ицных цифровых устройств.Известен генератор псевдослуцай"ных чисел, содержащий регистр сдви"га с сумматором по модулю два вцепи обратной связиЕго недостатком являются неудовлетворительные статистические свойства,Наиболее близким по техническойсущности к предлагаемому являетсягенератор псевдослучайных чисел,содержащий генератор М-последовательности, счетчики, генератор тактовых импульсов, регистр памяти 12.Однако этот генератор не позволяет получать псевдослучайные числас основанием К,5Цель изобретения - расширениефункциональных возможностей генера"тора за сцет использования системысчисления с основанием К,Для достижения поставленной целив известный генератор псевдослучайных чисел, содержащий генераторМ-последовательности, два счетчика,регистр памяти, генератор тактовыхимпульсов, введены три элемента задержки, триггер и элемент И, выходкоторого соединен с вычитающим входом первого счетчика и суммирующимвходом второго счетчика, разрядные20 выходы которого соединены с соответствующими разрядными входами ре.гистра памяти, выходы которого являются выходами генератора, входкоторого через первый элемент, за20 3 9 20 держки соединен с управляющим входом первого счетчика и непосредственно - с входом генератора И-последовательности, разрядные выходы которогб соединены с соответствующими разрядными входами первого счетчика, вцход которого соединен непосредственно с управляющим входом регистра памяти, через второй элемент задержки - с входом "Сброс" ,в второго счетчика и непосредственнос нулевым входом триггера, единичный вход которого через третий зле" мент задержки подключен к выходу первого элемента задержки, а выход триггера соединен с первырч входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов.На фиг, 1 приведена блок-схема генератора; на Фиг. 2 - гистограмма генератора.Генератор содержит И-йоследовательности, состоящий из регистра с сумматором 2 по модулю два в25 цепи обратной связи.Разрядные входы счетчика 3,подключены к соответствующим разрядным выходам регистра 1. Вход управления записью счетчика 3 подключен к входу запуска генератора через первый элемент 1 задержки, а выход "Все нули" подключен к входу сброса триггера 5, входу управления записью регистра б памяти и через35 второй элемент 7 задержки - к входу сброса счетчика 8, .Выход первого элемента ч задержки через третий элемент 9 задержки подключен также к входу . становки триггера 5 выход которого подключен к первому входу элемента И 10. Второй вход элемента И 10 соединен с выходом генераторатактовых импульсов, а выход с входом вычитания счетчика 3 и с45 входом сложения счетчика 8. Разрядные выходы счетчика 8 соединены с соответствующими разрядными входами регистра 6 памяти, а разрядные выходы последнего являются разрядными выходами генератора, Счетчик 8 считает по модулю К. На Фиг. 2 показаны распределения вероятностей появления двоичных псевдослучайных чисел на выходах регистра (кривая ) и на выходе генератора (кривая 8) пунктиром (кривая 9) показано идеально равномерное распределение К-ичных чисел, По оси абсцисс отложены числа М = 0,1, 21 "гдеИ - число разрядных входов сдвигового регистра 1, подключенных кразрядным входам счетчика. 3), и выделено 5 участков оси, кратных числуК-основанию заданной системы счисления, По оси ординат отложены вероятность Формирования числа на выходах сдвлгового регистра 1, равнаяв : йд , н средняя еериетнссте ндявления К-ичных чисел на выходе генератора, равнаяГенератор работает следующим образомПеред началом Формирования очередно"о псевдослучайного числа наинФормационный вход регр стра 1 поступает сигнал с вь;хода сумматорапо модулю 2, значение которого определяется значениями тех разрядовсдвигового регистра 1, вь;ходы оторых подключены к входам сумматора 2,Ори поступлении управляющего сигнала на вход запуска генератора итем самым - на вход запуска сдвигового регистра 1) содержимое регистраперемещается на один разряд, а впервый разряд загисывается значениер соответствующее сигналу ня инФормационном входе регистра 1, Наразрядных выходах регистра 1, подключенных. к разрядным входам счетчика 3, появляется очередное двоичное псевдослучайное число,Через время, достаточное для завершения переходных процессов в регистре 1, на вход управления записью счетчика 3 с выхода элементазадержки поступает задержанный сигнал запуска генератора и очередное двоичное псевдо лучайное число записывается в счетчик 3, Через время, достаточное для установки разрядных триггеров счетчика 3 з соо "ветствующее этому числу состояния, с выхода элемента 9 задержки на вход установки триггера 9 поступает дополнительно задержанный сигнал запуска генератора, и триггер 5 устанавливается в циничное состояние. На первый вход элемента И 1 О при этом поступает сигнал, разрешающий прохождение импульсов, непрерывно Формируемыми генератором 11 импульсов и поступающих на второй вход элемента И 10, Импульсы с выхода элемента И 10 поступают одновременнс на вход вычитания счетчика 3 и на вход сло94201 ч пунктирными линиями, происходящеес вероятностью, плотность распределения которой соответствует кривойприведет к появлению на выходеустройства К-ичного псевдослучайногочисла, численно равного расстояниюдвоичного псевдослучайного числа от й нижней границы соответствующего ин, тервала. Неравномерность в распреде О лении вероятностей 8 ФормированияК-ичных псевдослучайных чисел обусловлено тем, что из 5 4. 1 интервалов первый и последний имеют области, вероятность попадания двоичного15 псевдослучайного числа в которыхравна нулю.Максимальная вероятность Формирования К-ичных псевдослучайныхчисел соответствует области 20 2 - 5 К . 1 внутри первого интервала, так как вероятность попадания двоичного псевдослучайногочисла в соответствующую область любого из 5 + 1 интервалов отлична от 25 1 п ц х4 10 и равна РКПсХ и +В областях (0,1) и (2 "-5 К,К) вероятность формирования К-ичных псевдослучайных чисел равна ЗО, 5РХ= -1- , так как вероятностьпсевдослучайного числа в соответствующей области не равна 0 тольков 5 интервалах.З 5 Отклонение распределения вероятностей формирования К-ицных псевдослучайных чисел на выходе устройства от идеальной, для которой вероятность формирования любого 1(-ично 40 го псевдослучайного числа равнаР , = - , описывается разностями 45 50 55 5жения счетчика 8, С приходом каждого очередного импульса содержимоесчетчика 3 уменьшается, а счетчика 8увеличивается. После того, как содержимое счетчика 8 достигает К, очередной импульс установит этот счетчик в нулевое состояние, таким образом содержимое этого счетчика в любомомент времени не превышает числа КПосле прихода на вход вычитаниясчетчика 3 количества импульсов,равного ранее записанному в негодвоичному числу, его содержимоестанет равным нулю и на его выходенВсе нули" возникает соответствующий сигнал. Этот сигнал, поступивна вход сброса триггера 5 сброситего в такое состояние, при которомпрекратится прохождение импульсовчерез элемент И 10. Одновременносигнал "Все нули" поступит на входзаписи регистра 6 и двоичный кодцисла, накопленный к этому моментув счетчике 8 (этот код, очевидно,соответствует остатку сформированного двоичного псевдослучайного числа по модулю К), будет записан врегистр 6, сменив в нем код предыдущего числа, и поступит на выходгенератора. Через промежуток времени, достаточный для окончания переписи кода из счетчика 8 в регистр6, на вход сброса счетчика 8 черезэлемент 7 задержки поступит сигнал"Все нули", счетчик 8 установитсяпри этом в нулевое состояние, подготавливаясь тем самым к Формированию следующего К-ичного псевдослучайного числа,Следует отметить, цто для увеличения длины Формируемой последовательности К-ицных псевдослуцайныхчисел (т.е, периода повторения чисел в этой последовательности) цисло разрядов регистра 1 может бытьвыбрано большим, цем число разрядовсчетчика 3 (т.е, больше й),Отклонение распределения вероятностей появления К-ицных чисел навыходе устройства (Фиг. 2, кривая 8)от идеального зависит от соотношениямежду числами К и М (т.е, основаниемвыходной системы счисления и числом разрядов двоичного псевдослучайного числа) следующим образом, Формирование генератором двоичногопсевдослучайного числа в любомиз кратных числу К интервалов1К(1+1) К 1, отмеченных на фиг, 2 щах 5+1 1 к псъ ид 2 мК и 1 5и К псъ К 23 -1 Практически при 5 ) 1 О указанное отклонение не превышает 23, цто вполне достаточно для практических целей,Таким образом, предлагаемое устройство в отличие от известных обеспечивает Формирование равномерно распределенных чисел в заданной системе счисления, что расширяет его функциональные возможности.7Формула изобретения 920 Генератор псевдоспучайных чисел,содержащий генератор И"последовательности; два счетчика, регистр памяти,генератор тактовых импульсов,о т л и ч а ю щ и й с я тем, что,с целью расширения области его применения за счет использования си те"мы счисления с основанием М, сн со Одержит три элемвнта задержки, триггер и элемент И, выход которого соединен с вычитающим входом первогосчетчика и суммирующим входом второго счетчика, разрядные выходы ко Бторого соединены с соответствующимиразрядными входами регистра памятивыходы которого являются выходамигенератора, вход которого через пер"вый элемент задержки соединен с 26управляющим входом первого счетчикаи непосредственно - с входом генера"тора И-последовательности, разрядные 1 й 8выходы которого соединены с соответ" ствующими разрядными входами первого счетчика, выход которого соединенйепосредственно с управляющим входомрегистра памяти, через второй элемент задержки с входом "Сброс" второго счетчика и непосредственно "с нулевым входом триггера, единичный вход которого через третий элеМентзадержки подключен к выходу первого элемента задержки, а выход триггерас еднен с первым входом элемента И, втооой вход которого соединен с выход,.менератора тактовых импульсов. Источники инФормации,принятые во внимание при экспертизе1. Бобнев И.П. Генерирование слу"чайных сигналов. М., Энергия",1971, с. 200,2. Лвторское свидетельство СССР1 656086, кл. С 06 Е 1/02, 1977прототип).1/39 Тираж 131 ПодписноНИИПИ Государственного комитета СССРпо делам изобретений и открытий13035, Москва, 3-35, Раушская наб., д. 4/5 Заказ 4 илиал ППП "Патент", г. Ужгород, ул. Проектная, 4