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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено .300580 (21) 2933417/18-24 с присоединением заявки Нов (23) Приоритет—

Опубликовано070Ю2. Бюллетень Но 17 (5 1 ) М. Кд. з

G F 7/58

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681. 323 (088.8) Дата опубликования описания 070582 (72) Автор изобретения

A Ñ.-Б. Карасов (71) Заявитель Центральное проеквно-конструкторское бюро по..цитатам (54) ГенеРАтОР случАЙнОГО пОтОкА случАЙных

ЧИСЕЛ

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

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

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

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

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

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

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

Для достижения поставленной цели

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

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

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

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

Генератор содержит регистр 1 (кода), выходы которого соединены с первыми входами элементов ИЛИ 2, выходы которых соединены с первыми входами элементов И 3, вторые входы которых соединены с выходами генератора равномерно распределенных случайных чисел 4, а выходы — со вторыми входами элементов ИЛИ 2и,29,... ...,2„. Второй вход элемента ИЛИ 2 соединен с первым выходом генератора равномерно распределенных случайных чисел 4. Выход элемента 3> соединен с первыми входами элементов И 5 и 6, выходы которых соединены соответственно с первым входом переключателя

7,и счетным входом счетчика 8, выходы которого являются выходами генератора. Элементы 9-11 задержки соединены в последовательную замкнутую цепочку, управляющие их входы подключены к выходам блока задания параметров элементов 12 задержки.

Выход элемента 9 задержки соединен со вторым входом первого переключателя 7, выход которого подключен ко входу Сброс счетчика 8.и ко входу второго переключателя 13, выход которого подключен ко входу Сброс элемента 10 задержки, выход которого соединен со вторым входом элемента И 5. Выход элемента

11 задержки соединен со вторым входом элемента И б.

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

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

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

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

10 в каждом такте опроса генератора 4 в к аждом его ра з ряде формируе тс я 1 с вероятностью, равной 0,5..

Сигналы с выходов генератора 4 пос- тупают на первые входы элементов И 3

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

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

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

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

С, включающем несколько тактов К опроса генератора 4 описывается биномиальным законом распределения

Р„(Е) = С. „.Р . (1 — P)" (1) где Р y(0) - вероятность появления

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

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

Р— параметр распределения.

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

Рк(Р) = P(l — Р), (2) где Р (Q ) — вероятность того, что до к очередного появления импульса пройдет Г так55 тов;

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

Если сигнал 1 будет не на

60 и-ом выходе регистра 1 кода, а на (n-1) -ом его выходе, то импульсы на выходе элемента И Зп. будет появляться с вероятностью Р = 0,5 ° 0,5

=(0,5) = 0,25. В выражениях (1) и (2) параметр Р при этом примет значение Р = 0,25.

926656

Если сигнал 1 в регистре 1 кода перемещать из одного разряда в другой в направлении к его началу, параметр Р в выражениях (1) и (2) будет уменьшаться в геометрической прогрессии, т.е. Р = (0,5)

В пределе, когда 1 из регистра кода вообще будет вытолкнута распределение (1) будет стремиться к пуассоновскому

P (0) = —.е

Л

К (3) где Р (0 ), — вероятность того, что за

К опросов генератора

4 появится ровно I? импульсов потокау параметр (интенсивность) потока.

Распределение. интервалов времени между импульсами при этом будет стремиться к распределению

f (t) Л, е-Лc (4) где — значение интервала времени между импульсами потока;

Х вЂ” параметр (интенсивность) потока.

Таким образом, меняя местоположение 1 в регистре кода, можно на выходе элемента И 3 „ получать случайные стационарные ординарные потсУки в заданном классе распределений, .изменяющихся в диапазонах от (1) до (2) до соответственно (3) и (4).Сформированный на выходе элемента

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

Способы формирования случайных чисел.

Первоначально рассмотрим случай, когда переключатель 7 замыкает контакты 4, Ь, а переключатель 13 разомкнут (фиг. 2).

Случайный поток импульсов с выхода элемента И 3 и (фиг. 2а) поступает на первые входы элементов И 5 и 6. На вторые входы этих элементов поступают потенциалы высокого уровня с выходов элементов задержки соответственно 10 и 11.

Элементы 9-11 задержки образуют трехфазный мультивибратор, на выходах которого последовательно во времени формируются три интервала времени (фиг. 26,Ь,ъ), длительность каждого из которых может регулироваться блоком задания параметров элементов 12 задержки.

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

Интервалы с выходов элементов

9-11 задержки формируются во времени независимо от случайного потока (фиг. 2 Ь, Ь, ъ). Следовательно, совпадение импульсов потока с этими

5 интервалами является случайным.

В момент формирования интервала времени с выхода элемента 9 никаких действий не производится. Этот интервал необходим для обеспечения

10 отсутствия последействия в выходном потоке чисел (фиг. 25).

По окончании интервала времени с выхода элемента 9 задержки запускается элемент 10 задержки, который

15 формирует.на своем выходе интервал времени, предназначенный для считывания и привязки к очередному импульсу потока сформированного в предыдущем цикле случайного числа в счетчике 8 (фиг. 28). Производится эта привязка благодаря тому, что высоким уровнем потенциала с выхода элемента 10 задержки открыт элемент И 5 и первый же после срабатывания элемента 10 задержки импульс потока проходит через элемент И 5 и переключатель 7 на считывающий вход счетчика 8. Накопленное к. этому моменту времени число в счетчике счи30 тывается и выдается на выход генератора.

Остаток времени интервала с выхода элемента 10 задержки также способствует отсутствию последействия в выходном потоке чисел. Таким обра35 зом участки подсчета и,ульсов из случайного первичного потока разделены с двух сторон пассивными участками, что обеспечивает отсутствие последействия, но снижает быстро40 действие. Однако эти участки можно уменьшить при помощи блока 12 до желаемой величины.

После окончания интервала време45 ни с выхода элемента 10 задеРжки. запускается элемент 11 задержки, который: формирует интервал времени, предназначенный для формирования очередного случайного числа путем

50 подсчета числа импульсов первичного потока на заданном детерминированном интервале (фиг. 2г). В течение этого интервала открыт элемент И 6, через который импульсы с выхода элемента И Зд поступают на счетный вход счетчика 8. На фиг. 2 это импульсы 1; б, 7, 8; 14, 15, 16 17

18. В частности импульсы 6, 7, 8, накопленные в счетчике 8 считываются затем при возбужденном элементе 10 задержки импульсом 10 потока (фиг. 2B,д).

Структура выходного потока для рассмотренного случая, приведена

6а фиг. 2 .. Рассмотрим свойства

65 ртого потока.

926656

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

ht1 (7)

bt1+Ь 1+btg д1 . (8)

ht1+btg+btg где 1, g t, it g - интервалы времени, формируемые соответственно элементами 11, 10, 9 задержки.

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

Как видно из выраженйя (10), интервал времени bto формируемый элементом 9 задержки, не влияет на паЭтот поток является потоком без последействия, стационарным, неординарным. Он может быть задан системой из двух законов распределений, первый из которых описывает интервал времени ь; между неординарными событиями, а второй — случайное число m в одном событии.

Из описания первичного потока (фиг. 2а). видно, что он является стационарным потоком Пальма, который подвергается р --преобразованию (фиг. 25), причем видно, .что р « l.

При таких условиях прореженный поток (фиг. 28) приближается к простейшему, даже если первичный поток 15 и не был пуассоновским, т.е. описывался выражением (2). Следовательно, интервалы времени ь; имеют показательное распределение (4). Случайное же число m может задаваться, 20 либо выражением (1), либо выражением (3) в зависимости от кода регистра

1 кода.

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

Работа генератора в случае, когда переключатель завыкает контакты

6-8, а переключатель 13 разомкнут, поясняется диаграммой, приведенной на фиr. 4. В этом случае считывание состояний счетчика осуществляется 40 по переднему фронту импульса с выхода элемента 9 задержки, т.е. случайные числа m с выхода счетчика 8 следуют через детерминированные интервалы С„, формируемые элемента- 45 ми задержки. В этом режиме работы генератора величины. импульса с выхода элемента 9 задержки может быть уменьшена до величины, необходимой для считывания кода счетчика 8,. а 50 с выхода элемента 10 сведена к нулю, Для этого можно также замкнуть переключатель 13

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

a-b, а переключатель 13 разомкнут (фиг. 5) .

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

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

Р (С ), (g) (m= О, 1, 2,...) где Рщ(i,) — вероятность того, что за случайный интервал времени ; на счетный вход счетчика 8 поступит ровно m импульсов;

m — случайное число импульсов в одном неординарном событии выходного потока,"

3. — интенсивность первичноFo пуассоновского потока;

Р— вероятность попадания

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

Параметры Л и,и,связаны между собой соотношением

-Ф (6) где Р,1 - вероятность попадания импульса первичного потока на счетный вход счетчика 8, т.е. вероятность считывания кода счетчика в течение интервала времени btq элемента 10 задержки.

926656

Генератор случайного потока случайных чисел, содержащий генератор равномерно распределенных случайных чисел, выходы которого, кроме первого, соединены с первыми. входами соответствующих. разрядных элементов

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

35 раметры выходного потока. Поэтому для ,повышения быстродействия в данном режиме работы генератора он может быть сведен к нулю. Меняя соотношение между интервалами времени ь „ и

bt можно менять параметры выходного цотока.

Иатематическое ожидание случайного числа m определится по формуле

ЛР ЛР Р fata

ЛР 1 Р 1 ht

Дисперсия определится по формуле

D(m) = M(m) ° (M(m) + 1) (12)

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

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

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

1. Авторское свидетельство СССР в 175314, кл. G 06 F 7/58, 1964.

2. Авторское свидетельство СССР

9 127863, кл. G 06 F 7/58, 1959 (прототип).

9 26656

6 г г z

Тираж 732 Подписное.

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

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

Заказ 2982/41

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

Составитель В. Жовинский

Редактор П. Макаревич ТехредХ".. Кастелевич Корректор A. дзятко