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

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

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

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

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

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

Задача получения случайных потоков чисел с различными законами

распределения возникает, например, при необходимости моделирования людских потоков в городском транспорте, а зданиях и т.п., которое, как правило, являются неординарными.

Цель изобретения - упрощение устройства.

Для достижения поставленной цели в генератор случайного потока слу10чайных чисел, содержащий генератор равномерно распределенных случайных чисел, выходы которого, кроме первого, соеди нены с первь ми входами разрядных элементов И соответствен15но, разрядные элементы ИЛИ, регистр и два элемента и, введены три элемента задержки, счетчик, блок задания параметров элементов задержки, два переключателя, выходы регистра

20 соединены с первыми входами разрядных элементов ИЛИ соответственно, вторые входы которых соединены с выходами разрядных элементов И предыдущего разряда соответственно, а

25 выходы -разрядных элементов ИЛИ соединены со вторыми входами элементов И последующего разряда соответственно, первый выход генератора раа.номерно распределенных случайных

30 чисел соединен со вторым входом

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

рого подключен ко входу

второго элемента задержки.

На фиг. 1 приведена функцио.нальная схема генератора; на фиг.2-5 временные диаграммы, иллюстрирующие работу генератора.

Генераторсодержит регистр 1 (кода) , выходы которого соединены с входами элементов ИЛИ 2, выходы которых соединены с первыми входами элементов И 3, вторые входы которых сЬединены с выходами генератора равномерно распределенных случайных чисел 4, а выходы - со вторыми входами элементов ИЛИ 2(,29,.. ...,2п. Второй вход элемента ИЛИ 2 соединен с первым выходом генератор равномерно распределенных случайных чисел 4. Выход элемента Зу, соединен с первыми входами з лементов И 5 и б выходы которих соединены соответственно с первым входом переключателя 7 и счетным входом счетчика 8, выходы которого являются выходами генератора. Элементы 9-11 задержки соединены в последовательную замкнутую цепочку, управляющие их входы подключены к выходам блока задания параметров элементов 12 задержки. Выход элемента 9 задержки соединен со вторым входом первого переключателя 7, выход которого подключен ко входу Сброс счетчика 8 и ко входу вторюго переключателя 13, выход которого подключен ко входу Сброс элемента 10 задержки, выход которого соединен со вторым входом элемента И 5. Выход элемента 11 задержки соединен со вторим входом элемента И б.

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

Блоки 1-4 формируют случайный поток ординарных событий, а остальные

блоки формируют случайные числа и

привязывают

их к определенным

точкам на оси времени.

Первоначально рассмотрим работу блоков 1-4.

Генератор 4 равномерно распределенных случайных чисел формирует равномерно распределенные случайные числа в диапазоне 0-2, где п - число разрядов генератора 4. При этом

0 в каждом такте опроса генератора 4 в каждом его разряде формируется с вероятностью, равной 0,5. Сигналы с выходов генератора 4 поступают на первые входы элементов И 3i.

5 на вторые входы которих поступают

сигналы с выходов элементов ИЛИ 2,. , на входы которих, в свою очередь, подаются сигналы с предыдущих элементов И, либо выходов регистра 1

0 кода. На выходе последнего оператором может быт1 задан любой код.

Пуст имеется сигнал только на п-ом выходе регистра 1 кода. Тогда через элемент ИЛИ 2„ подготавлива5 ется к срабатыванию элемент И Зц, который срабатывает каждый раз, когда возникает сигнаш на п-ом выходе генератора 4. Поскольку этот сигнал возникает с вероятностью, равной

0 О/5, то на выходе элемента И Зр будет иметь место бернулиевская последовательность импульсов с вероятностью, равной 0,5. Для такого потока распределение числа импульсов, возникших на постоянном интервале С , включающем несколько тактов к опроса генератора 4 описывается биномиальным законом распределения

Р(е) с|.(1 - )% (1) где Рц(Е) - вероятность появления

0событий (импульсов) за

К тактов опроса генератора 4 ;

Р - параметр распределения. Случайное число опросов К генера5 тора 4 до появления следующего импульса, f.e. по существу, длительность интервала между импульсс1ми, выраженная через число тактов К, для такого потока описывается геометрическим распределением

- р)К

(2)

pj,(e) р(1 - РГ

где Ру(е) - вероятность того, что до

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

Для рассмотренного выше случая в выражениях (1) и (2) параметр Р имеет значение, равное 0,5.

Если сигнал будет не на п-ом выходе регийтра 1 кода, а на (n-l)-OM его выходе, то импульсы на выходе элемента И ЗА, будет появляться с вероятностью Р 0,5-0,5 (0,5)- 0,25. В выражениях (1) и (2) параметр Р при этом примет 5 значение Р 0,25. Если сигнал 1 в регистре 1 кода перемещать из одного разряда в другой в направлении к его началу параметр Р в выражениях (1) и (2) будет уменьшаться в геометрической прогрессии, т.е. Р (0,5) . В пределе, когда из регист ра кода вообще будет вытолкнута распределение (1) будет стремиться к пуассоновскому А 4 где Р((й) .- вероятность того, что з К опросов генератора 4 появится ровно 2 импульсов потока; Д. - парс№5етр (интенсивность потока. Распределение.интервалов времени между импульсами при этом будет стремиться к распределению f (t) Х - е-- (4) где t - значение интервала времени между импульсами потока; А. - параметр (интенсивность) по тока. Таким образом, меняя местоположе ние Ч в регистре кода, можно н выходе элемента И 3 получать случайные стаци9нарные ординарные потс ки в заданном классе распределений :Изменяю1цихся в диапазонах от (1) до (2) до соответственно (3) и (4) Сформированный на выходе элемент И ЗУ, случайный поток имеет самосто тельное практическое приложение и м жет быть применен для мрделирования различного рода случайных, однородных, стационарных, ординарных петоков. Интенсивность потока задается частотой опросов генератора 4. Способы формирования случайных чисел. Первоначально рассмотрим случай когда переключатель 7 замыкает контакты d , t , а переключатель 13 разомкнут (фиг. 2). Случайный поток импульсов с выхода элемента И Зр (фиг. 2а) поступает на первые входы элементов И 5 и 6. На вторые входы этих элемен- тов поступают потенциалы высокого уровня с выходов элементов задержки соответственно 10 и Ц. Элементы 9-11 зсщержки образуют трехфазный мультивибратор, на выходах которого последовательно во времени формируются три интервала времени (фиг. 26,6,г), длительность каждого из которых может регулироваться блоком задания параметров .элементов 12 задержки. Для облегчения дальнейшего изложения будет выделен фрагмент регшизации случайного потока с выхода элемента И 3f| и перенумерованы все импульсы в выделенном отрезке време ни (фиг. 2а) . Интервалы с выходов элементов 9-11 задержки формируются во времени независимо от случайного потока (фиг. 26,6,г). Следовательно, совпадение импульсов потока с этими интервалами является случайным. В момент формирования интервала времени с выхода элемента 9 никаких действий не производится. Этот интервал необходим для обеспечения отсутствия последействия в выходном потоке чисел (фиг. 25). По окончании интервала времени с выхода элемента 9 задержки запускается элемент 10 задержки, который формирует на своем выходе интервал времени, предназначенный для считывания и привязки к очередному импульсу потока сформированного в предыдущем цикле случайного числа в счетчике 8 (фиг. 26). Производится эта привязка благодаря тому, что высоким уровнем потенциала с вы- хода элемента 10 задержки открыт элемент И 5 и первый же после срабатывания элемента 10 задержки импульс потока проходит через элемент И 5 и переключатель 7 на считываиощий вход счетчика 8. Накопленное к этому моменту Времени число в счетчике считывается и выдается на выход генератора. Остаток времени интервала с выхода элемента 10 задержки также способствует отсутствию последействия в выходном потоке чисел. Таким образом участки подсчета импульсов из случайного первичного потока разделены с двух сторон пассивными участками, что обеспечивает отсутствие последействия, но снижает быстродействие. Однако эти участки можно уменьшить при помощи блока 12 до желаемой величины. После окончания интервала времени с выхода элемента lO задержки запускается элемент 11 задержки, который фО1 лирует интервал времени, предназначенный для формирования очередного случайного числа путем подсчета числа импульсов первичного потока на згщанном детерминированном интервале (фиг. 2г) . В течение этого интервёша открыт элемент И 6, через который импульсы с выхода элемента И Зп поступгиот на счетный вход счетчика 8. На фиг. 2г это импульсы l;6j 7, 8; 14, i5, 16,17, 18. В частности импульсы 6, 7, 8, накопленные в счетчике В считываются затем при возбужденном элементе 10 задержки импульсом 10 потока (фиг. 2В,Э). Структура выходного потока для рассмотренного случая, приведена на фиг. 2 „ Рассмотрим свойства того потока.

Этот поток является потоком без последействия, стационарным, неординарным. Он может быть задан системой из двух законов распределений первый из которых описывает интервал времени L- между неординарными событиями, а второй - случайное число m в одном событии.

Из описания первичного потока (фиг. 2а) Ьидно, что он является стационарным потоком Пальма, КОТОЕЯЛ подвергается р-преобразованию (фиг. 2ft), причем видно, .что р«1. При таких условиях прореженный поток (фиг 2BJ приближается к простейшему, даже если первичный йоток и не был пуассоновским, т.е. описывался выражением (2). Следовательно интервалы времени имеют показательное распр1еделение (4) . Случайное же число m может .задаваться либо выражением (1), либо выражение (3) в зависимости от кода регистра 1 кода.

Работа генератора при замкнутом переключателе 13 поясняется диаграммой, приведенной на фиг. 3. В этом случае элемент 10 задержки сбрасывается (прекращает формировать Интервал времени) первым же импульсом первичного потока, прсяяедшим через элемент И 5 (фиг. ЗВ). При этом структура потока 1практически не изменяется, но повышается быстродействие генератора за счет уменьшения интервалов.

Работа генератора в случае, когда переключатель замыкает контакты Б-6, а переключатель 13 разомкнут, поясняется диаграммой, приведенной на фиг. 4. В этом случае считывание состояний счетчика осуществляется по переднему фронту импульса с выхода злемента 9 задержки, т.е. случайные числа m с выхода счетчика 8 следуют через детерминированные интервалы t.; , формируемые элементаivM задержки, в этом режиме работы генератора величины, импульса с выхода элемента 9 задержки может быть уменьшена до величины, необходимой для считывания кода счетчика 8, а с выхода элемента 10 сведена к нулю Для этого можно такясе замкнуть переключатель 13.

Выше рассмотрена работа генератора для случая, когда длительности интервалов времени элементов задержек больше средней длительности интервалов времени между импульсами первичного потока. Рассмотрим работ генератора для случая, когда интервалы времени элементов задержек меньше интервалов времени между импульсами первичного потока. При это переключатель 7 замыкает контакты а-Ь, а переключатель 13 разомкнут (фиг. 5) ..

В этом режима работы генератора интервалы времени Т; при любом первичном потоке стремятся к показательному распределению. Распределение случайного числа m импульсов на случайном интервале 1:. вэтом случае определится как случайная функция От случайного аргумента.

Для наиболее распространенного случая, когда первичный поток является пуассоновским, закон распределения случайной величины m описывается распределением Паскаля с

/ч

т.е.

параметром А

ХРл+М / ХР т

Р («гг V -i: ---1-1

(5) т ,

(т О, 1, 2,...)

(,)

де Р

- вероятность того, что

m за случайный интервал времени t на счетный вход счетчика 8 поступит ровно m импульсов; m - случайное число импульсов в одном неординарном событии выходного потока;

К - интенсивность первичного пуассоновского потока;

Р - вероятность попадания импульса первичного потока в счетчике 8; / - параметр выходного потока - потока неординарных событий с интервалами времени Т.- . Параметры X и /i связаны между соой соотношением

(6)

1

де Pq - вероятность попадания импульса первичного потока на счетный вход счетчика 8, т.е. вероятность считывания, кода счетчика в течение интервсша времени atij элемента 10 задержки.

Рп подсчитываютВероятности Р и ся соответственно по формулам

Р.. (7)

At-i+uti +utij

р . . (8)

1 где At, AtQ, ut3 -.интервалы времени, фopмиpye ыe соответственно элементами 11, 10, 9 задержки.

С учетом (6), (7), (8) выражение (5) можно преобразовать к видам

ро I Ол Atn

р ( ) Ч 1 Р- Л

(9)

РШ S - , PitPa/

р ,,) , Atg ,./ jLti- (10)

m -lAt., + At iAAt +/Stl/

как видно из выражения (10), интервал времени utij, формируемый элементом 9 задержки, не влияет на параметры выходного потока. Поэтому д «повышения быстродействия в данном режиме работы генератора он может быть сведен к нулю. Менйя соотнсмиение между интервалами времени At utii можно менять параметр выходног Потока. Математическое ожидание случайного числа m определится по формуле , Ч дисперсия определится по формуле Mtm ( + 1) (12) Таким образом, предлагаекый генератор позволяет формировать случайные числа с различным распределением на случайном интервале также с различным распределением. Кроме . того, генератор позволяет получить стационарные неординарные потоки случайных чисел с различными распре делениями интервалов и чисел. Формула изобретения Генератор случайного потока случайных чисел, содержащий генератор равномерно распределенных случайных чисел, выходы которого, кроме первого, соединены с первыми входами соответствующих.разрядных элементов ;И, разрядные элементы ИЛИ, регистр и два элемента И, отличающийся тем, что, с целью ynpowe ния, в него введены три элемента за держки, счетчик, два переключателя и блок задания параметров элементов задержки, выходы регистра соединены с первыми входами разрядных элементов ИЛИ соответственно, втоЕяле входы которых соединены с вы ходами разрядных элементов И предн дущего разряда соответственно, а выходы разрядных элементов ИЛИ соединены со вторыми входами элементов И последующего разряда соответственно, первый выход генератора равномерно распределенных случайных чисел соединен со вторым входом элемента ИЛИ первого разряда, выход элемента И последнего разряда соединен с первыми входами первого и второго элементов И, выходы которых подключены соответственно к первому , входу первого переключателя и к счетному входу счетчика, выходы которого являются выходами генератора, выход первого элемента задержки соединен со вторым входом первого переключателя и с входом второго элемента задержки, выход которого соединен со вторым входом первого элемента И и с входом третьего эле|Мента задержки, выход которого соединен со вторым входом второго элемента И и с входом первого элемента задержки, управляющие входы элементов задержки подключены к выходам блока задания параметров элементов задержки, выход первого переключателя подключен к входу Сброс счетчика и к входу второго переключателя, выход которого подключен к входу Сброс второго элемента задержки. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельстве СССР № 175314, КЛ. G 06 F 7/58, 1964. 2.Авторское свидетельство СССР .W 127863, КЛ. G 06 F 7/58, 1959 (прототип).

4/г

-

тпт W -4

/7 IJft / iT /7 fe t I I.

iLU

.1 le f7fd I I

Те WIV fS 17 W

/ 2 J

I 1 I. f 11

6 -L

a

7 2 J f 1

1 /г /j|Al

IL.

Л

I

ь

Щ-ГГ

i/DwIffW 1/7 «

7 A7;7

ll

U 4HJi fff f .rf Г6 rs т ) t