Генератор случайного полумарковского процесса

 

Изобретение относится к вычислительной технике и может быть использовано при построении .имитационных моделей систем, работающих в условиях случайных возмущений, и для моделироиания различных физических процессов с дискретным фазовым пространством. Цель изобретения - расширение функциональных возможностей за счет генерирования случайного процесса с заданным вероятностным распределением длительности нахождения процесса в каждом из его состояний. Цель достигается введением в устройство трех ключей 8, 9, 10, элемента ШШ-НЕ 14, второго блока 12 памяти, счетчика 13, блока 11 ключей, элемента ИЛИ 7. Длительность состояний процесса, подчиненная требуемому закону распределения , формируется путем подсчета количества тактов работы генератора в счетчике и сравнения подсчитанного количества с распределенным по заданному закону числом, формируемым из равномерно распределенного числа с помощью второго блока памяти. 2 ил. СО

СООЗ СОВЕТСКИХ

СОЩМЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) А1 (59 4 G 06 F.? 58

ОПИСАНИЕ ИЗОБРЕТЕНИ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4100409/24-24 (22) 07.08.86 (46) 29.02.88. Бюл. В 8 (72) Ю.П. Рьппков, А.Ю. Шевченко и А.В. Михалев (53) 681.3(088.8) (56) Авторское свидетельство СССР

N 902014, кл. G 06 F 7/58, 1980.

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

У 1070548, кл. G 06 F 7/58, 19ф2, (54) ГЕНЕРАТОР СЛУЧАЙНОГО ПОЛУМАРКОВСКОГО ПРОЦЕССА (57) Изобретение относится к вычислительной технике и может быть использовано при построении имитационных моделей систем, работающих в условиях случайных возмущений, и для моделирования различных физических процессов с дискретным фазовым пространством.

Цель изобретения — расширение функциональных возможностей за счет генерирования случайного процесса с заданным вероятностным распределенйем длительности нахождения процесса в каждом из его состояний. Цель достигается введением в устройство трех ключей 8, 9, 10, элемента ИЛИ-НЕ 14, второго блока 12 памяти, счетчика 13, блока 11 ключей, элемента ИЛИ 7. Длительность состояний процесса, подчиненная требуемому закону распределения, формируется путем подсчета количества тактов работы генератора в счетчике и сравнения подсчитанного количества с распределенным по заданному закону числом, формируемым из равномерно распределенного числа с помощью второго блока памяти, 2 ил. 1377853

В начальный момент времени до при-.

35 хода первого тактирующего сигнала от блока 1 регистр 5 устанавливается в начальное состояние, регистры 3, 6 и счетчик 13 устанавливаются в нулевое состояние. На выходе элемента ИЛИ-НЕ появляется "1" и ключи 8-10 открыты, .

Блок 1 начинает выцавать на своих выходах тактирующие сигналы. Сигнал с второго выхода блока 1 через элемент ИЛИ 7 иницийруетработу датчика

2 случайных чисел, на выходе которого появляется m-разрядное двоичное число r = С 2 . Сигнал с четвер4 того выхода блока 1 через открытый ключ 8 инициирует запись величины

С,в регистр 3 памяти, Величина С

1 является номером столбца блока 4 памяти. Сигнал с третьего выхода бло-, ка 1 через открытый ключ 10 инициирует запись в регистр 6, хранящуюся в регистре 5 (согласно начальной установке этот номер равен i). По номеру столбца С,,и номеру строки (i) в блоке 4 памяти возбуждается ячейка, содержимое которой и будет равно ноИзобретение относится к вычислительной технике и может быть использовано при построении имитационных моделей систем, работающих в условиях случайных возмущений, и для моделирования различных физических процессов с дискретным фазовым пространством.

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

На фиг. 1 приведена блок-схема предложенного генератора; на фиг. 2 схема блока управления. 15

Генератор содержит блок 1 синхронизации, датчик 2 равномерно распределенных случайных чисел, регистры

3-6, элемент ИЛИ 7, ключи 8-10, блок

11 ключей, блок 12 памяти, счетчик 20

13, элемент ИЛИ-НЕ 14. Блок 1 содержит генератор 15 тактовых импульсов и счетчик l6, Генератор работает следующим образом. 25

Пусть моделируется случайный процесс с. и состояниями .. В каждом из сос-тояний процесс может находиться 1 тактов, причем 1 — дискретная случайная величина с распределением вероят-30 ностей И(1). Вероятности перехода из

i-го состояния в к-е заданы матрицей

//Р;„ //, причем Р;-„= О, i = 1, п, так как по истечении случайного количества тактов, распределенного по закону Ы(1) процесс из всякого i-го состояния обязательно переходит в новое состояние, номер которого не равен i.

Заданная вероятность перехода моделируемого процесса из одного состояния в другое обеспечивается специальной конструкцией блока 4 памяти.

Длительность состояний процесса, подчиненная требуемому закону распределения, формируется путем подсчета количества тактов работы генератора в счетчике 13 и сравнения подсчитанного количества с распределенным по заданному закону числом, формируемым на выходе блока 12 памяти.

Каждая i-я строка блока 4 памяти содержит 2. ячеек, где m — разрядность случайного числа на выходе датчика 2, причем каждая из них рассчи тана на хранение целого. числа, не превьппающего п. Все 2 ячеек разбиты на п групп таким образом, что количество ячеек а;„, (к = 1, п) в каждой группе пропорционально с коэффициентом 2 значением вероятностей P. к,, расположенных в 1-й строке матрицы

//Р;„ //. Другими словами, Р,-„= а . 2,. В ячейки первой группы записаны номера "1", в ячейки второй группы— номера "2" и т.д, до п. Всего в блоке 4 памяти содержится и строк.

Блок 12 памяти предназначен для преобразования ш-разрядных двоичных чисел, распределенных по равномерному закону в интервале 0,2 — 1l в P-разрядные (P < m) двоичные числа, имеющие закон распределения, близкий к требуемому N(1). Он представляет со" бой дискретный аналог нелинейного безынерционного преобразователя, с помощью которого. равномерно распределенная случайная величина известным образом может быть преобразована в случайную величину с требуемым законом распределения.

1 !

Регистр 3 предназначен для хранения случайного числа, являющегося номером (адресом) столбца блока 4 памяти. Регистр 6 предназначен для хранения .номера (адреса) строки блока

4 памяти. В регистре 5 хранится счи- " танный из матричной памяти номер состояния генерируемого процесса.

1377853

40 меру состояния генерируемого процесса. Предположим, что это состояние имеет номер к. Вероятность реализации k-ro состояния при условии что

5 в регистре 6 содержится номер i, будет равна Р,<, Действительно., выбор из матричной памяти k-го номера состояния означает, что величина С

1 попала в k-ю группу ячеек i-й строки. 10

В k-й группе содержится а; ячеек.

Вероятность того, что равномерно распределенное в интервале 0,2 — 11 число примет одно из а значений, к равна a;„ Л P„„ I5

Одновременно с выбором из блока 4 памяти номера состояния сигнал с третьего выхода блока 1 открывает блок 11 ключей и через открытый ключ

9 и элемент ИЛИ 7 инициирует работу датчика 2 случайных чисел. Случайное число Ct, через блок 11 ключей поступает на вход 12 блока памяти, где преобразуется в число 1, которое заносится в вычитающий счетчик 13. На входе элемента ИЛИ-НЕ 14 появляется

"О" и ключи 8-10 закрываются.

Сигнал с первого выхода блока 1 обеспечивает запись выбранного из блока 4 памяти номера состояния выходного регистра 5, разрядные выходы которого являются выходом всего устройства. Одновременно этот же сигнал поступает на вход счета счетчика

13 и уменьшает его содержимое на единицу. На пятом такте генератора 15 35 тактирующих сигналов счетчик-делитель

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

Рабата генератора на,следующем такте зависит от значения числа, содержащегося в счетчике 13. Если содержимое счетчика равно нулю, та на выходе элемента ИЛИ-НЕ 14 присутствует "i ключи 8-10 открыты, и работа 45 генератора протекает описанным образом. Если содержимое счетчика больше нуля, то на выходе элемента ИЛИ-НЕ сохраняется "0" и ключи 8-10 закрыты.

Сигнал со второго выхода блока управ- 50 ления через элемент ИЛИ 7 инициирует работу датчика 2. -Однако сигнал с четвертого выхода блока 1 через закрытый ключ 8 не проходит.и содержимое регистра 3 остается таким же, 55 как и на предыдущем такте, Сигнал с третьего выхода блока 1 также не проходит через закрытый ключ 10 и поэтому, во-первых, содержимое регистра 6 остается прежним, ва-вторых, случайное число с выхода датчика 2 через блок 11 ключей не проходит на адресный вход блока 12 и не оказывает влияния на содержимое счетчика 13.

Сигнал с первого выхода блока 1 уменьшает содержимое счетчика 13 на единицу и инициирует запись в регистр

5 содержимого выбранной на этом такте ячейки блока 4 памяти.

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

Состояние моделируемого процесса на выходе устройства будет оставаться неизменным до тех пар, пока содержимое счетчика 13 больше нуля. Поскольку занесенное в счетчик 13 число распределено по закону M(1), та количество тактов, на которых состояние моделируемого процесса будет неизменным, также распределено па закону

И(1}.

Формула из обре т е н и я с %

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

Техред М. Ходанич Корректор M. Пожо

Редактор N. Келемеш

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

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

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

Заказ 875/46

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 мент ИЛИ-НЕ, второй блок памяти, счетчик, блок ключей, элемент ИЛИ, первый вход которого соединен с вторым выходом блока синхронизации, вы" ход элемента ИЛИ соединен с входом

"Опрос" датчика равномерно распределенных случайных чисел, выход которого соединен с информационным входом блока ключей, выход которого соединен с адресным входом второго блока памяти, выход которого соединен с выходом предварительной установки счетчика, счетный вход которого соединен с первым входом блока синхрони-1 зации, выход счетчика подключен к входу элемента ИЛИ-НЕ, выход которого соединен с управляющими входами первого, второго и третьего ключей, информационные входы первого и второго ключа обьединены и подключены к третьему входу блока синхронизации, четвертый выход которого подключен к информационному входу третьего ключа, выход которого подключен к входу синхронизации третьего регистра памяти, выход первого ключа соединен с вторым входом элемента И, выход второго ключа подключен к управляющему входу блока ключей и к входу синхронизации второго регистра памяти.