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

 

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

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

Республик

« >744532 (63) Дополнительное к ввт. свид-ву (22) Заявлено 050478 (21) 2602866/18-24 (5 ) М ХЛ

G F 1/02

G О7 С iS/OO с присоединением заявки 89 . (23) Приоритет

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

СССР по делам изобретений н открытий

Опубликовано 3006,80, Бюллетеиь )4о 24

Дата опубликования описания 3006ЯО (53) УДК681 325 (088. 8), (72) Авторы изобретения

Э . А „Баканович, В. И. Новиков, И.A. Орлов и С.Ф. Костюк (71) 3a яв ит ель

Минский радиотехнический институт (54) ГЕНЕРАТОР СЛУЧАЙНОГО ПРОЦЕССА

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

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

Этот генератор содержит датчики пуансоновских случайных импульсных потоков, блоки проведения случайных испытаний, блоки анализа результата случайных испытаний, блоки преобразования случайных величин в случайные числа или в случайные значения параметров импульсных потоков (1), Основной неДостаток зтого генератора состоит в том, что он не позволяет формировать марковские процессы с конечным множеством состояний.

Наиболее близким техническим решением к изобретению является управляеьвйй генератор потоков случайных событий, содержащйй последовательно соединенные блок ввода, выполненный- ЗО на датчиках потоков случайных импульсов с регулируемыми интенсивностями, блок схем совпадения, шифратор, регистр номера схем совпадения, схему блокировки, выход которой подключен к общему входу блока схем совпадения. Генератор формирует случайные события в результате случайных испытаний, заключающихся в одновременном отпирании по общему входу блока схем совпадения и установки в регистре кода, соответствующего номеру схемы совпадения, через которую прошел первый с момента начала испытания импульс датчиков блока ввода. Генератор импульсов и счетчик преобразуют полученное случайное число в случайный временной интервал f2) °

Недостаток генератора состоит в том, что он не позволяет генерировать марковские процессы с конечным множеством состояний с дискретным и непрерывным временем.

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

744532

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

Для достижения поставленной цели в генератор случайного процесса, содержаший группу датчиков потоков случайных импульсов, выходы которых под-, ключены ко входам. элементов И группы соответственно, выходы которых через шифратор соединены со входами регистра памяти, выходы которого являются выходами генератора и подключены ко входам элемента ИЛИ, управлявший вход элементов И группы подключен к выходу блока задания длительности испытания, введены блок управления, регистр адреса и группу блоков памяти, выходца которых соединены с управляьиаими входами датчиков-потоков случайных импульсов группы соответ- 20 ственно, а входы блокой памяти группы через- регистр адреса соедииенй с группой выходов блока управления соответств енно, вход которого соединен с- выходом элемента ИЛИ, первый и р второй выходы блока управления соединены соответственно со входом блока задания длительности испытаиия и с управлявшим входом регистра памяти, а группа входов блока управления подключена соответственно к выхо дам" "датчиков потоков случайных импульсов.

Кроме того, каждый датчик потоков случайных импульсов содержит последовательно соединенные генератор случайных импульсов, вероятностный (l,m)-полюсник, группу элементов И, элемент ИЛИ, выход которого является выходом датчика, а управляюшие входы группы элементов. И являются управляю- 40 шими входами датчика.

Автоматическое управление генера— тором .предлагается организовать, вопервых, за счет изменения содержимого блоков памяти, что позволяет управлять интенсивностью датчиков потоков случайных импульсов, а, следова- тельно, и вероятностными характеристи*ами форыируемых случайных процес-сов, во-вторых, за счет изменения программы функционирования блока управления, что дает возможность наст раивать генератор на воспроизведение однородных цепей Маркова с дискретным и непрерывным временем, последо вательности случайных чисел с заданной нестационарностью воспроизводимой функции распределения, п независимых последовательностей случайных чисел с заданными функциями распределенйя, где n — количество блоков щ памяти.

На чертеже представлена структурная схема устройства.

Генератор содержит- группу 1 элемен тов И, шифратор 2, регистр 3 памяти. элемент 4 ИЛИ, блок 5 задания длительности испытания, блок 6 управления, регистр 7 адреса, блок 8 памяти, датчики 9 потоков случайных импульсов, количество которых равно числу состояний цепи Маркова, и каждый из которых содержит генератор 10 случайных импульсов, вероятностный (1,m)— полюсник ll с импульсными выходами, группу 12 элементов И, дополнительный вход которого подключен к входу управления интенсивностью датчика 9 потока случайных импульсов, элемент

13 ИЛИ, выхоД которого является выходом датчика 9 потока случайных импульсов., Последовательно соединенные группы 1 элементов И, шифратор 2, регистр

3 памяти, элемент 4 ИЛИ проводят и регистрируют случайные испытания.

Структура случайного испытания в предлагаемом генераторе не отличается от структуры испытаний известного и заключается в одновременном отпирании элементов И группы 1 с последуюшей фиксацией в регистре 3 номера элемента И группы 1, через который с момента начала испытания прошел первый импульс датчиков 9 потоков случайных импульсов. Поэтому, справецлива математическая модель генератора, устанавливаюшая зависимость интенсивности датчиков 9 потоков случайных импульсов от функции плотности воспроизводимого генератором распределения.

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

7 адреса, выходы которого подключены к обшим адресным входам блоков 8 памяти, и управляет блоком 5 задания длительности случайного испытания.

Тем самым, выполняется автоматическое считывание кодов из блоков 8 памяти, определявших либо вероятности переходов цепи Маркова, в соответствии с текушим состоянием цепи, либо функцию распределения случайных чисел при воспроизведении стационарных или нестационарных последовательностей. Выходы блоков 8 памяти подсоединены к входам регулирования интенсивности соответствуюших датчиков 9 потоков случайных импульсов.

Каждый датчик 9 потоков случайных импульсов с регулируемой интенсивностью содержит последовательно со- единенные генератор 10 случайных ийпульсов; вероятностный (l,m)-полюсник 11 с импульсными"выходами, группа 12 элементов И, вторые входы которого подключены к входу регулирова144532 ния интенсивности датчика, элемент

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

Работа устройства при формировании независимых последовательностей случайных чисел с заданными функциями распределения заключается в следующем. 0

Если генератор настроить íà и распределений, то датчики 9 потоков случайных импульсов формируют на выходе простейшие импульсные потоки..

Тогда для настройки генератора на п распределений с функциями плотнос ти fx(х), задаваемыми вероятностями

Рк,, определяем по формуле

p„, = 1 f, (.) d

Х;1 где К вЂ” номер распределения, К = 1,у, 1 — номер интервала квантования плотности распределения, i = i.n, причем, интервал квантования ьх-х;-х; 1>con5t 25 и не зависит от номера i необходимо установить интенсивности Эк, датчиков 9 потоков случайных импульсов и к к< ЗО

Значение л„„записывается в блоке 8 памяти таким образом, что индекс соответствует номеру, блока 8 памяти, а индекс К вЂ” адресу ячейки в блоке, например, значения я,<,i = i n, зада- 35 ющие плотность распределения с номером 1, записываются в первые ячей-, ки всех и блоков 8 памяти, а номер блока определяется значением i. Так как аналогичные адресные входы блоков 4О

8 памяти объединены, ro при возбуждении одного из адресных входов, иэ всех блоков 8 памяти считываются значения 1„;, соответствующие плотности распределения с номером К. 45

Датчики 9 потоков случайных импульсов выполнены таким образом, что позволяют получать линейную зависимость интенсивности потока на выходе от значения кода y „. на входе уп- 5О равления интенсивностью, вследствие чего достигается простота настройки и управления генератором. Генератор

10 потока случайных импульсов вырабатывает последовательность случайных импульсов с постоянной интенсивностью которые поступают на вход вероятностного (1,))1)-полюсника 11 с импульсными выходами, формирующего случайные импульсные потоки с интенсивностями 1 = )l, ° 2j, где g — номер 60 импульсного выхода (1,m)-полюсника1

= 1,m,. Импульсные выходы вероятностного (1,m) -полюсника 11 подключены к первым входам блока 12 элементов И, вторые входы которого подключены к 65 выходам соответствующего блока 8 памяти, причем на входы элементов И группы 12 с номером j поступают соответственно импульсный поток с g-го вйхода вероятностного (1,m)-полюсника 11 и двоичная цифра 3-го разряда числа с выхода блока 8 памяти. Элемент 13 ИЛИ, выход которого является выходом датчика 9 потока случайных импульсов, выполняет сумирование потоков с выходом группы 12 элементов И. Таким образом, интенсивность потока на выходе, датчика 9 потоков случайных импульсов определяется выражением п

p (=,Å dl) pl) ) где а) — двоичное значение j-ro разряда числа с выхода соответствующего блока 8 памяти. В этом случае зависимость интенсивности потока на выходе датчика 9 потоков случайных импульсов от значения числа Л „„ c выхода блока 8 памяти носит лйнейный хар акт ер .

Р ас смотрим р а боту ген ер ат ор а с момента, когда в блок 6 управления поступают сигналы внешнего управления, задающие плотность распределения с номером 1

В регистре 7 адреса устанавливается триггер с номером 1 и вырабатывается разрешающий сигнал на (; -выходе.

В блоках 8 памяти из ячеек с номером

1 считываются числа Ag; которые поступают на входы регулирования ийтенсивности датчиков 9 и устанавливают заданную интенсивность случайных импульсных потоков. Блок 6 управления вырабатывает сигналы, по которым сбрасывается в 0 содержимое регистра 3, блок 5 длительности случайного испытания открывает группу 1 элементов И и,тем саум; начинает случайное испытание. Первый прошедший через элементы И группы 1, случайный импульс датчиков 9 потоков случайных импульсов проходит через шифратор 2 и устанавливает в регист- ре 3 код, соответствующий номеру сработавшего элемента И группы 1. При установке в регистре 3 хотя бы одного триггера срабатывает элемент .4 ИЛИ, выходной сигнал которого поступает в блок 6 управления, блок 5 задания длительности испытания закрывает группу 1 элементов И, тем самым, прекращает случайное испытание. Значение случайного числа считывается-с регистра 3.

При запуске на формирование следующего значения случайного числа блок 6 управления снова вырабатывает сигналы, по которым сбрасывается в 0 содержимое регистра 3, блок

6 задания длительности испытания открывает группу 1 элементов И, начинается случайное испытание и т.д.

7445 32

Ь течение генерирования последовательйости чисел с заданной функцией содержимое регистра 7 адреса не изменяется. При необходимости переключения генератора на Формирование случайных чисел с другим, отличным от текущего номером функции .распределения н блок 6 упранления поступают т сйгналы внешнего управления, по которым в регистре l адреса нозбуждается соответствующийвыход, из блоков

8 памяти выбирается новое значение

К изменяются интенсивности датчи)() ков 9 потоков случайных импульсов и т. д. Сигналы внешнего управления выдаются как иэ ЭВМ, так и вводятся с фотосчитывающих или других устройств

ВВ ода ° так как н процессе моделирования, как правило, требуется несколько независиМых последовательностей случайных чисел с различными Функциями 2О распределения, то производительность

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

Рассмотрим работу генератора при формировании последовательности случайных чисел с. заданной функцией нестационарности, В отличие от предыдущего режима генератор вырабатывает только одну последовательность случайных чисел, но содержимое регистра 7 адреса, а

- следовательно, и считынаемые из блоКоВ 8 зйачения 5g, изменяются по программе, задаваемой н блоке 6 управления сигналами внешнего управления. Программа изменения содержимого регистра 7 адреса . может не учитывать состояние генератора н пре дыдущие моменты времени. В этом случае сигналы с выходов датчиков 9 блоком 6 управления игнорируются.

Если йредыдущие состояния генерато- 45 ра учитываются, то сигналы с выходов датчиков 9 блоков б управления обрабатываются в соответствии с программой изменения адресов.

Рассмотрим работу генератора при 50 моделиронайии однородных цепей Маркова с дискретным временем и конечным множ ством состояний.

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

П= (Р ),. текущее состояние цепи 1, 3..= l,è определяет номер строки матрицы

П ,последующее состояние цепи j, ) = fq, определяет номер столбца в матрице 6

П, то при записи н блоки 8 памяти вероятностей Р;, значение 3 определяет номер блока, а значение i — номер ячейки н блоке, Следовательно, при возникновении разрешающегo сигнала на выходе регистра 7 адреса с номеpoM r, r = 1 n, с выходов блоков 8 памяти на входы регулирования интенсивности датчиков 9 потоков случайных импульсон числа Р„, в результате чего интенсивности А случайных потоков на выходах датчиков 9 задаются

P„) и я

3-J и, таким образом, вероятность Р> того, что в результате случайного испытания н регистре 3 установится значение j, определяется значением

Р„ нероятности перехода цепи Маркова.

Рассмотрим работу генератора, когда в блок 6 управления поступят сигналы внешнего управления, по которы-л н регистре 7 устанавливается адрес, определяющий начальное состояние цепи

Маркова. Поступает сигнал внешнего. управления на генерирование следующего состояния цепи. Блок 6 упранления вырабатывает сигналы, по которым сбрасывается в 0 регистр 3, блок

5 длительности случайного испытания открывает группу 1 элементов И,и тем самым, начинает случайное испытание.

Первый пришедший с момента начала испытания импульс датчиков 9 потоков случайных импульсов проходит через группу 1 эneMe>:ãoâ И, шифратор 2 и устанавливает и регистре 3 код, который соответствует следующему состоянию цепи Маркова. Одновременно этот же случайный импульс поступает на адресные входы блока 6 управления, который устанавливает в регистре 7 новое значение адреса. срабатывает элемент 4 ИЛИ, блок 5 длительНости испЫтания закрывает элементы И группы 1. Хотя на адресные входы блока б управления поступают случайные импульсы датчиков 9, содержимое регистра 7 адреса не изменяется. По новому значению адреса н регистре 7 считывается новая строка переходных вероятностей матрицы П из блоков 8 памяти.

С поступлением сигнала внешнего управления на моделирование следующего состояния цепи блок 5 длительности случайного испытания сбрасывает в 0 регистр 3, открывает элементы И группы 1, и цикл работы повторяется.

Pассмотрим работу генератора при моделировании однородной цепи Мар1 кона с непрерывным временем и конечным множеством состояний °

744532

Функцйонирование устройства не отличается от предыдущего режима за исключением того, что группа 1 элементов И с момента начала моделирования постоянно открыта, а по каждому поступающему с выходов датчиков 9 случайному импуль=y в регистре

3 изменяется значение кода состояний цепи Маркова. Одновременно, каждый случайный импульс датчиков 9 поступает на адресные. входы блока б управления, выходные сигналы которого устанавливают в регистре 7 адрес, IIo которому иэ блоков 8 памяти считываются значения вероятностей перехода

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

Предлагаемый генератор случайного процесса. может быть использован как самостоятельное устройство для формйрования случайного процесса. Однако, наиболее эффективно его применение совместно с управляющей ЭЦВМ или машиной общего назначения, что дает возможность разгрузить ЭЦВМ от достаточно трудоемкой программной имитации случайных процессов,. а формирование таких процессов возложить на предлагаемый генератор, Это повышает производительность системы при решении задач статистического моделирования и позволяет автоматизировать процесс управления устройством. !6ирокие возможности автоматического управления как вероятностными характеристиками случайных процессов, так и видом воспроизводимого процесса (цепи Маркова, нестационарные последовательности и т.д.) выгодно отличают предлагаемый генератор от известных устройств.

Анализ показывает, что предлагаемый генератор случайного процесса об» ладает максимальным быстродействием по сравнению с известными, так как в структуре генератора применена схема быстрого случайного испытания, наиболее эффективно используются, датчики потоков случайных импульсов блока ввода. Например, при моделировании цепи Маркова с непрерывным временем каждый случайный импульс блока ввода вызывает смену состояния цепи, Однотипность применяемых блоков (датчики потоков случайных импульсов, с регулируемыми интенсивностями, блоки памяти) позволяет конструировать бсновные узлы генератора в виде интегральных модулей и выполнить весь генератор на.нескольких платах. Небольшие размеры и достаточно широкие функциональные воэможности предлагаемого генератора делают перспективным его использование в качестве специализированного модуля в процессорах ЭЦВМ.

)0

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

1. Генератор Случайного процесса, содержащий группу датчиков потоков случайных импульсов, выходы кото15 рых подключены ко входам элементов

И группы соответственно, выходы которых через шифратор соединены со вхо20

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

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

2. Генератор по п.l, о т л и ч а-. ю шийся тем, что каждый датчик потоков случайных импульсов содержит последовательно соединенные генератор случайных импульсов, вероятностный (l,m)-полюсник, группу элементов И и элемент ИЛИ, выход которого является выходом датчика, à управляющие входы группы элементов И являются управляющими входами дат55 чика. 1

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

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

9 504196 кл, G Об F l/02, 1975 °

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

9 344431i кл, G 06 F 1/02, 1971 (прототип) .

744532

Составитель A.Карасов

Редактор A,Äîëèíè÷ Техред M.Ïåòêî Корректор М.Демчик

Заказ 3792/ll Тнраж 751 Подписное

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

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

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