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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 11926656 Союз СоветскихСоциалистическихРеспублик(22) Заявлено 30,0580 (21) 2933417/18-24с присоединением заявки Нов(23) Приоритет -Опубликовано 070582. Бюллетень йо 17 51 М, Кд,з С 06 Р 7/58 Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 070582(54) ГЕНЕРАТОР СЛУЧАЙНОГО ПОТОКА СЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть исполь.зовано в системах вероятностного моделирования для формирования случайных процессов с различными статисти-. ческими характеристиками.Известен генератор случайных равномерно распределенных чисел, содержащий источник шума, пересчетную схему, генератор импульсов, многофазный мультивибратор, логйческие элементы. Этот генератор не позво-. ляет формировать случайные числа с задаваемым законом распределения 1.Однако он не позволяет получать случайный поток чисел.Наиболее близким по технической сущности к предлагаемому является генератор чисел с произвольным законом распределения случайного потока, содержащий генератор равномерно распределенных случайных чисел, регистр.и группу элементов И, группу элементов ИЛИ, дешифраторы. 2) .Оцнако известный генератор достаточно сложен и также не позволяет получить случайные потоки чисел.Задача получения случайных потоков чисел с различными законами распределения возникает, например,при необходимости моделиров аниялюдских потоков в городском транспорте, в зданиях и т.п которые,как правило, являются неординарными1,ель. изобретения.- упрощениеустройства.Для достижения поставленной цели 10 в генератор случайного потока случайных чисел, содержащий генераторравномерно распределенных случайныхчисел, выходы которого, кроме первого, соединены с первыми входамиразрядных элементов И соответственно, разрядные элементы ИЛИ, регистри два элемента И, введены три элемента задержки, счетчик, блок задания параметров элементов задержки,два переключателя, выходы регистрасоединены с первыми входами разрядных элементов ИЛИ соответственно,вторые входы которых соединены свыходами разрядных элементов И предыдущего разряда соответственно, авыходЫ разрядных элементов ИЛИ соединены со вторыми входами элементовИ последующего разряда соответст,венно, первый выход генератора рав,номерно распределенных случайныхчисел соединен со вторым входомэлемента ИЛИ первого разряда, выход элемента И последнего разрядасоединен с первыми входами первогои второго элементов И, выходы которых подключены соответственно кпервому входу первого переключателяи к счетному входу счетчика, выходы которого являются выходами генератора, выход первого элементазадержкИ, соединен со вторым входомпервого переключателя и со входомвторого элемента задержки, выходкоторого соединен со вторым входомпервого элемента И и со входомтретьего элемента задержки, выходкоторого соединен со вторым входомвторого элемента И и со входом первого элемента задержки, управляющие входы элементов задержки подключены к выходам блока задания параметров элементов задержки, выходпервого переключателя подключен ковходу фСброс 1 счетчика и ко входувторого переключателя, выход которого подключен ко входу фСбросвторого элемента задержки.На фиг, 1 приведена функциональная схема генератора; на фиг.2-5временные диаграммы, иллюстрирующиеработу генератора.Генераторсодержит регистр 1 (кода), выходы которого соединены спервыми входами элементов ИЛИ 2, выходы которых соединены с первымивходами элементов И 3, вторые входыкоторых соединены с выходами генератора равномерно распределенных случайных чисел 4, а выходы - со вторыми входами элементов ИЛИ 2 и,2 9,,2, Второй вход элемента ИЛИ 2соединен с первым выходом генератораравномерно распределенных случайныхчисел 4. Выход элемента З соединенс первыми входами элементов И 5 и б,выходы которых соединены соответственно с первым входом переключателя7,и счетным входом счетчика 8, выходы которого являются выходами генератора. Элементы 9-11 задержкисоединены в последовательную замкнутую цепочку, управляющие их входыподключены к выходам блока заданияпараметров элементов 12 задержки,Выход элемента 9 задержки соединенсо вторым входом первого переключателя 7, выход которого подключенко входу Сбросф счетчика 8 и ковходу второго переключателя 13, выход которого подключен ко входуСброс 1 элемента 10 задержки,выход которого соединен со вторымвходом элемента И 5, Выход элемента11 задержки соединен со вторым входом элемента И б,Генератор работает следующимобразом,Блоки 1-4 формируют случайный поток ординарных событий, а остальные блоки формируют случайные числа иприв язываютих к определеннымточкам на оси времени,Первоначально рассмотрим работублоков 1-4,5 Генератор 4 равномерно распределенных случайных чисел формируетравномерно распределенные случайныечисла в диапазоне 0-2 , где и - числло разрядов генератора 4. При этом10 в каждом такте опроса генератора 4в каждом его разряде формируется1 с вероятностью, равной 0,5.Сигналы с выходов генератора 4 пос-тупают на первые входы элементов И 3;15 на вторые входы которых поступаютсигналы с выходов элементов ИЛИ 2; ,на входы которых, в свою очередь,подаются сигналы с предыдущих элементов И, либо выходов регистра 120 кода. На выходе последнего оператором может быть задан любой код.Пусть имеется сигнал только наи-ом выходе регистра 1 кода. Тогдачерез элемент ИЛИ 2 П подготавлива 25 ется к срабатыванию элемент И Зв,который срабатывает каждый раз, когда возникает сигнал на и-ом выходегенератора 4, Поскольку этот сигналвозникает с вероятностью, равной0,5, то на выходе элемента И 3 будет иметь место бернулиевская последовательность импульсов с вероятностью, равной 0,5. Для такого потока распределение числа импульсов,возникших на постоянном интервалеС , включающем несколько тактов Копроса генератора 4 описывается биномиальным законом распределенияР(Е) = СЕ,РЕ. (1 Р)- (1)где Р К(1) - вероятность появления40 событий (импульсов) заК тактов опроса генератора 4;Р - параметр распределения.Случайное число опросов К генера 45 тора 4 до появления следующего импульса, т,е. по существу, длительность интервала между импульсами,выраженная через число тактов К, длятакого потока описывается геометри 50 ческим распределениемРк(6) = Р(1 - Р), (2)где Р Я ) - вероятность того, что докочередного появленияимпульса пройдет 1 так 55тов;Для рассмотренного выше случая ввыражениях (1) и (2) параметр Римеет значение, равное 0,5.Если сигнал 1 будет не на60и-ом выходе регистра 1 кода, а на(и) -ом его выходе, то импульсына выходе элемента И Зо, будет появляться с вероятностью Р = 0,50,5Если сигнал1в регистре 1 кода перемещать из одного разряда в другой в направлении к его началу,параметр Р в выражениях (1) и (2) будет уменьшаться в геометрическойпрогрессии, т.е. Р = (0,5 РВ пределе, когда 1 из регистра кода вообще будет вытолкнутараспределение (1) будет стремитьсяк пуассоновскомР (Р) = - .еЛк Р(3)где Р (Ю), - вероятность того, что заК опросов генератора4 появится ровно 1 импульсов потока;параметр (интенсивность)потока.Распределение, интервалов временимежду импульсами при этом будетстремиться к распределениюЛ, е Л (4)где- значение интервала временимежду импульсами потока;Х - параметр (интенсивность) потока.Таким образом, меняя местоположение 1 в регистре кода, можно навыходе элемента И 3получать случайные стационарные ординарные потсУки в заданном классе распределений,изменяющихся в диапазонах от (1) до (2) до соответственно (3) и (4),Сформированный на выходе элементаИ 3 случайный поток имеет самостоятельное практическое приложение и может быть применен для моделированияразличного рода случайных, однородных, стационарных, ординарных пото-ков. Интенсивность потока задаетсячастотой опросов генератора 4.Способы Формирования случайныхчисел.Первоначально рассмотрим случай, когда переключатель 7 замыкает контакты с(, Ь , а переключатель 13разомкнут (фиг. 2).Случайный поток импульсов с выхода элемента И 3 и (Фиг. 2 а) поступает на первые входы элементов И 5 и б. На вторые входы этих элементов поступают потенциалы высокого уровня с выходов элементов задержки соответственно 10 и 11.Элементы 9-11 задержки образуют трехфазный мультивибратор, на выходах которого последовательно во времени формируются три интервала времени (фиг. 26,Ь,), длительность каждого из которых может регулироваться блоком задания параметров элементов 12 задержки.Для облегчения дальнейшего изложения будет выделен фрагмент реализации случайного потока с выхода элемента И Зп и перенумерованы все импульсы в выделенном отрезке времени (фиг. 2 с 1) . Интервалы с выходов элементов9-11 задержки формируются во временинезависимо от случайного потока(фиг. 2 Ь, Ь, ъ). Следовательно, совпадение импульсов потока с этими 5 интервалами является случайным.В момент формирования интервалавремени с выхода элемента 9 никакихдействий не производится. Этот интервал необходим для обеспечения 10 отсутствия последействия в выходномпотоке чисел (фиг. 25).По окончании интервала времени свыхода элемента 9 задержки запускается элемент 10 задержки, который 15 формирует.на своем выходе интервалвремени, предназначенный для считывания и привязки к очередномуимпульсу потока сформированного впредыдущем цикле случайного числа всчетчике 8 (фиг. 26), Производитсяэта привязка благодаря тому,что высоким уровнем потенциала с выхода элемента 10 задержки открытэлемент И 5 и первый же после срабатывания элемента 10 задержки импульспотока проходит через элемент И 5 ипереключатель 7 на считывающий входсчетчика 8. Накопленное к этому моменту времени число в счетчике считывается и выдается на выход генератора.Остаток времени интервала с выхода элемента 10 задержки также способствует отсутствию последействияв выходном потокечисел, Таким образом участки подсчета импульсов изслучайного первичного потока разделены с двух сторон пассивными участками, что обеспечивает отсутствиепоследействия, но снижает быстро действие, Однако эти участки можноуменьшить при помощи блока 12 дожелаемой величины. После окончания интервала време 45 ни с выхода элемента 10 задержки.запускается элемент 11 задержки,который: Формирует интервал времени,предназначенный для формированияочередного случайного числа путем50 подсчета числа импульсов первичногопотока на заданном детерминированноминтервале (Фиг. 2 г), В течение этого интервала открыт элемент И б,через который импульсы с выходаэлемента И 3 поступают на счетныйвход счетчика 8. На фиг. 2 этоимпульсы 1; б, 7, 8, 14, 15, 16 1718. В частности импульсы б, 7, 8,накопленные в счетчике 8 считываются затем при возбужденном элементе 10 задержки импульсом 10 потока (Фиг, 2 В,д).Структура выходного потока длярассмотренного случая, приведенаЮа фиг. 2 ., Рассмотрим свойства 65 утого потокаВероятности Ри Р 1 подсчитываются соответственно по формулам611(8)Ь .+Ь 1+ Ьгде ь, ь 1, ь 1 З - интервалы времени, формируемые соответственно элементами 11, 10,9 задержки,С учетом (6), (7), (8) выражение: " ((10)Р , ( 1Как видно из выраженйя (10), интервал времени Ь 1, формируемый элементом 9 задержки, не влияет на паЭтот поток является потоком безпоследействия, стационарным, неординарным, Он может быть задан системой из двух законов распределений,первый из которых описывает интервал времени с; между неординарнымисобытиями, а второй - случайноечисло ш в одном событии.Из описания первичного потока(фиг, 2 а). Видно, что он являетсястационарным потоком Пальма, который Оподвергается р -преобразованию(фиг, 2 Ь), причем видно, .что р1.При таких условиях прореженный поток (фиг. 2 В) приближается к прос"тейшему, даже если первичный поток 15и не был пуассоновским, т.е, описывался выражением (2). Следовательно,интервалы времени с; имеют показательное распределение (4). Случайное же число ш может задаваться , 20либо выражением (1), либо выражением(3) в зависимости от кода регистра1 кода.Работа генератора при замкнутомпереключателе 13 поясняется диаграммой, приведенной на фиг. 3, В этомслучае элемент 10 задержки 1 сбрасывается" (прекращает формироватьинтервал времени) первым же импульсом первичного потока, прошедшимчерез элемент И 5 (фиг. 36). Приэтом структура потока практическине изменяется, но повышается быстродействие генератора за счет уменьшения интервалов.Работа генератора в случае, когда переключатель завыкает контакты6-8, а переключатель 13 разомкнут,поясняется диаграммой, приведеннойна фиг, 4. В этом случае считываниесостояний счетчика осуществляется 40по переднему фронту импульса с выхода элемента 9 задержки, т.е. случайные числа ш с выхода счетчика 8следуют через детерминированныеинтервалы С, формируемые элементами задержки, В этом режиме работыгенератора величины. импульса с выхода элемента 9 задержки может бытьуменьшена до величины, необходимойдля считывания кода счетчика 8,. а 50с выхода элемента 10 сведена к нулю,Для этого можно также замкнуть переключатель 13,Выше рассмотрена работа генератора для случая, когда длительностиинтервалов времени элементов задержек больше средней длительности интервалов времени между импульсамипервичного потока, Рассмотрим работугенератора для случая, когда интервалы времени элементов задержекменьше интервалов времени между импульсами первичного потока. При этомпереключатель 7 замыкает контактыо-Ь, а переключатель 13 разомкнут(фиг. 5) .65 В этом режиме работы генератора интервалы времени с; при любом первичном потоке стремятся к .показательному распределению, Распределение случайного числа ш импульсов на случайном интервале Т; в этом случае определится как случайная функция от случайного аргумента.Для наиболее распространенного случая, когда первичный поток является пуассоновским, закон распределения случайной величины ш описывается распределением Паскаля с параметром ф" т.е.(в=О, 1, 2,)где Рш(с,) - вероятность того, чтоза случайный интервалвремени ; на счетныйвход счетчика 8 поступит ровно в импульсов;ш - случайное число импульсов в одном неординарном событии выходногопотока,"Х - интенсивность первичного пуассоновского потока;Р - вероятность попадания1импульса первичного потока в счетчике 8,"р. - параметр выходного потока - потока неординарных событий с интервалами времени Т;Параметры А и,сс,связаны между собой соотношениемР = Р 1, (6) где Р 1 - вероятность попадания импульса первичного потокана счетный вход счетчика 8,т.е. вероятность считывания кода счетчика в течение интервала времени бэлемента 10 задержки.Формула изобретения Генератор случайного потока случайных чисел, содержащий генератор равномерно распределенных случайных чисел, выходы которого, кроме первого, соединены с первыми входами соответствующих. разрядных элементов ,И, разрядные элементы ИЛИ, регистр и два элемента И, о т л и ч а ю" щ и й с я тем, что, с целью упроще- ния, в него введены три элемента задержки, счетчик, два переключателя и блок задания параметров элементов задержки, выходы регистра соединены с первыми входами разрядных элементов ИЛИ соответственно, вторые входы которых соединены с выходами разрядных элементов И преды 35 раметры выходного потока, Поэтому для ,повышения быстродействия в данном режиме работы генератора он может быть сведен к нулю, МенЯя соотношение между интервалами времени ь 1 и ь 11 можно менять параметры выходного цотока,Математическое ожидание случайного числа в определится по формулеМ(в) = - = = - = . (11) 1 ОЛР 1 ЛР 1 РЬ 11ЛР 1Дисперсия определится по формулеП(в) = МЮ(М(в + 1) (12)Таким образом, предлагаемый генератор позволяет формировать случайные числа с различным распреде лением на случайном интервале также с различным распределением. Кроме того, генератор позволяет получить стационарные неординарные потоки случайных чисел с различными распре- о делениями интервалов и чисел. дущего разряда соответственно, авыходы разрядных элементов ИЛИ соединены со вторыми входами элементов И последующего разряда соответственно, первый выход генератораравномерно распределенных случайныхчисел соединен со вторым входом элемента ИЛИ первого разряда, выходэлемента И последнего разряда соеди. -нен с первыми входами первого и второго элементов И, выходы которыхподключены соответственно к первомувходу первого переключателя н ксчетному входу счетчика, выходы которого являются выходами генератора,выход первого элемента задержкисоединен со вторым входом первогопереключателя и с входом второгоэлемента задержки, выход которогосоединен со вторым входом первогоэлемента И и с входом третьего элемента задержки, выход которого соединен со вторым входом второго элемента И и с входом первого элементазадержки, управляющие входы элементов задержки подключены к выходамблока задания параметров элементовзадержки, выход первого переключателя подключен к входу фСбросффсчетчика и к входу второго переключателя, выход которого подключенк входу 1 Сброс второго элементазадержки.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельствО СССРВ 175314, кл, С 06 Г 7/В 8, 1964.2. Авторское свидетельство СССР9 127863, кл, 6 06 Р 7/58, 19599 26656 Ф Ю 8 7 1,тавител Те 1 Тираж 732ВНИИПИ Государственного комитетапо делам изобретений и открыти 11,3035, Москва, Ж, Раушская наб. Заказ 2982/4 ПодцисСР 4 Мкгород, ул. Проектная, 4 те иап П Сос ь В. Жовинский ктор П. Макаревич хредЕ. Кастелевич Корректор А, дэятко