Генератор случайного процесса Советский патент 1980 года по МПК G06F1/02 G07C15/00 

(54) ГЕНЕРАТОР СЛУЧАЙНОГО ПРОЦЕССА

1

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

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

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

Наиболее близким техническим решением к изобретению является управляе№ай генератор потоков случайных событий, содержащий последовательно соединенные блок ввода, выполненныйна датчиках потоков случайных импульсов с рёгулируёМЕЗМи интенсивностями, блок схем совпадения,шифратор,регистр номера схем совпадения,схему блокировки, выход которой подключен к общему входу блока схем совпадения.Генератор формирует случайные события в результате случайных испытаний, заключающихся в одновременном отпирании по

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

5 блока ввода. Генератор импульсов и счетчик преобразуют полученное случайное число в случайный временной интервал 2.

Недостаток генератора состоит в

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

Цель изобретения - расширение

25 функциональных схем возможностей генератора за счет формирования однородных цепей Маркова с непрерывным и дискретным временем и конечным множеством состояний, последовательнос30тей случайных чисел с заданной не744532стацйонарност ью воспроизводимой функции распределения при автомати ёс 1 о | управлении параметрами и видом воспроизводимых генератбром процессов. . Для достижения поставленной цели в генератор случайного процесса, содержащий группу датчиков потоков слу чайных импульсов, выходы которых под ключены ко входам элементов И группы соответстванно, выходы которых через шифратор соединены со входами регист ра памяти, выходы которого являются выходами генератора и подкл|очены ко входам элемента ИЛИ, управляющий вход элементов И группы подключен к выходу блока задания длительности испытания, введены блок управления, регистр адреса и группу блоков памяти, выходы которых соединены с управ ля1ощими входами датчиков потоков случайных импульсов Группы соответственно , а входы бло|с6ё памяти группы через регистр адцэеса cbejoEHHeHia с группой выходов блока управления сбОтШ стйеняо, вход которого соедин С выходом элемента ИЛИ, первый и второй выходы блока управления соединены соответственно со входом задания длительнос,ти испыта с уп равляюшм 1входо памяти, а группа в ходов блока управл Шдкйючена соотвеггственно к выхо Ййм Датчиков потоков случайных импул сов .... Кроме того, каждый датчик потоков случайных импульсов содержит последо вательно соединенные генератор случайных импульсов,, вероятностный (1,т)-полюсник, группу элементов И, элемент ИЛИ, выход которого Является вйхрдом датчика, а управляющие входы груНгйаэлёментов. И являются управляю щими входами датчика. . Автоматическое управление генератором .предлагается организовать, вопервых, за счет изменения содержимого блоков памяти, что позволяет управлять интенсивностью датчиков потоков случайных импульсов, а, следов Тёльно и вероятностными характеристик ами фбрмир5гемых случайных процессов, во-вторых, за счет изменения программы функционирования блока управления, что дает возможность настраивать генератор на воспроизведение однородных цепей Маркова с дискретным и непрерывным временем, последовательности случайных чисел с заданной Нбст ацион арностью воспроиз в одимой функции распределения, п независимых последовательностей случайных чисел с заданными функциями распределения, где п - количество блоков --.„„- -., На прёдст авлё на структурная схема устройства. . Генератор содержит группу 1 элеме гоз и, шифратор 2, регистр 3 памятиэлемент 4 ИЛИ, блок 5 задания длительности испытания, блок 6 управления, регистр 7 адреса, блок 8 памяти, датчики 9 потоков случайных импульсов, количество которых равно числу состояний цепи Маркова, и каждый из котоptsx содержит генератор 10 случайных импульсов, вероятностный (1,т)ПО.ПЮСНИК И с импульсными выходами, группу 12 элементов И, дополнительный вход которого подключен к входу управления интенсивностью датчика 9 потока случайных импульсов, элемент 13 ИЛИ, выход которого является выходом датчика 9 потока случайных импульсов.. Последовательно соединенные группы 1 элементов И, шифратор 2, регистр 3 памяти, элемент 4 ИЛИ проводят и регие трируют случайные испытания. Структура случайного испытания в предлагаемом генераторе не отличается от структуры испытаний известного и заключается в одновременном отпирании элементов И группы 1 с последующей фиксацией в регистре 3 номера элемента И группы 1, через который с момента начала испытания прошел первый импульс датчиков 9 потоков случайных импульсов. Поэтому, справедлива математическая модель генератора; устанавливающая зависимость интенсивности датчиков 9 потокрв случайных импульсов от функции плотности воспроизводимого генератором распределения. Входы блока 6 управления подключены к выходу элемента 1 И и выходам датчиков 9 потоков случайных импульсов с регулируемыми интенсивностями. Блок б управления в соответствии с программой функционирования и сигналами на входах анализирует текущее состояние генератора, устанавливает новое содержимое регистра 7 , выходы которого подключены к общим адресным входам блоков 8 памяти, и управляет блоком 5задания длительности случайного испытания. Тем самым, выполняется автоматическое считывание кодов из блоков 8 памяти, определяющих либо вероятности переходов цепи Маркова, в соответствии с текущим состоянием цепи, либо функцию распределения случайных чисел при воспроизведении ста- , ционарных или нестационарных последовательностей. Выходы блоков 8 памяти подсоедингейы к входам регулирования интенсивности соответствующих датчиков 9 потоков случайных импульсов. Каждый датчик 9 потоков случайных импульсов с регулируемой интенсивностью содержит последовательно соединенные генератор 10 случайных ййпульсОв; вероятностный (1,т)-полюсник 11 с импульсными -выходами, группа 12 элементов И, вторые входы которого подключены к входу регулирования интенсивности датчика, элемент 13 ИЛИ, выход которого является выхо дом датчика, что позволяет изменять в произвольный момент времени интенсивность импульсного потока на выходе датчика в зависимости от цифровых сигналов на входе. Работа устройства при формировани независимых последовательностей случайных чисел с заданными функциями распределения заключается в следующе Если генератор настроить на п рас пределений, то датчики 9 потоков случайных импульсов формируют на выходе простейшие импульсные потоки,. Тогда для настройки генератора на п распределений с функциями плотности f(x), задаваемыми вероятностями , определяем по формуле РК; Г х,.1 где К - номер распределения, К 1,п i - номер интервала кванто ва ния плот ности распределения, i i, п , причем интервал квантования .e-const номера i, необходим и не зависит от датчиустановить интенсивности дц ков 9 потоков случайных импульсов м -Р.; 21 Л Значение л ц; записывается в блоке памяти таким образом, что индекс i соответствует номеру .блока 8 памяти, а индекс К - адресу ячейки вблоке. Например, значения д,;, i 1,п,задающие плотность распределения с номером 1, записываются в первые ячейки всех п блоков 8 памяти, а номер блока определяется значением i. Так как аналогичные адресное входы блоко 8 памяти объединены, то при возбужде нии одного из адресных входов, из всех блоков 8 памяти считываются зна соответствующие плотности чения Я, распределения с номером К. датчики. 9 потоков случайных импул сов выполнены таким образом, что позволяют получать линейную зависимость интенсивности потока на выхо на входе упде от значения кода я равления интенсивностью, вследствие чего достигается простота настройки и управления генератором. Генератор 10 потока случайных импульсов выраба тывает последовательность случайных импульсов с постоянной интенсивность /Up, которые поступают на вход вероятностного (1,т)-полюсника 11 с импульсными выхода.ми, формирующего слу чайные импульсные потоки с интенсивностями/Uj /Uo- 2j, где з - номер импульсного выхода (1 ,гп)-полюсника; j ,. Импульсные выходы вероятност ного (1,т)-полюсника 11 подключены к первым входам блока 12 элементов И, вторые входы которого подключеньГк выходам соответгствующего блойа 8 памяти, причем на входы элементов И . группы 12 с номером j поступают соответственно импульсный поток с j-to ВЫХОДА вероятностного (1,т)-полюсника 11 и двоичная цифра j-ro разряда числа с выхода блока 8 памяти. Элемент 13 ,ИЛИ, выход которого является выходом датчика 9 потока случайных импульсов, выполняет сумирование потоков с выходом группы 12 элементов И. Таким образом, интенсивность потока на выходе .датчика 9 потоков случайных импульсов определяется выражением . где aj - двоичное значение j-ro разряда числа с выходасоответствующего блока 8 памяти. .В этом случае зависимость интенсивности потока на . выходе датчика 9 потоков случайных импульсов от значения числа с выхода блока 8 памяти носит линейный характер. Рассмотрим работу генератора с момента, когда в блок б управления поступают сигналы внешнего управления, задающие плотность распределения с номером Е . В регистре 7 адреса устанавливается триггер с номером и вырабатывается разрешающий сигнал на 6-выходе, В блоках 8 памяти из ячеек с номером В считываются числа Ag-, которые поступают на входы регулирования интенсивности датчиков 9 и устанавливают заданную интенсивность случайных импульсных потоков, Блок б управления вырабатывает сигналы, по которым сбрасывается в содержимое регистра 3, блок 5 длительности случайного испытания открывает группу 1 элементов И и,тем саким; начинает случайное испытание. Первый прошедший через элементы И группы 1, случайней импульс датчиков 9 потоков случайных импульсов проходит через шифратор 2 и устанавливает в регистре 3 код, соответствующий номеру сработавшего элемента И группы 1. При установке в регистре 3 хотя бы одного триггера срабатывает элемент Г 4 ИЛИ, выходной сигнал которого поступает в блок б управления, блок 5 задания длительности испытания закрывает группу 1 элементов И, тем самым, прекращает случайное испытание. Значение случайного числа считывается с регистра 3. При запуске на формирование следующего значения случайного числа блок 6 управления снова вьарабатывает сигналы, по которым сбрасывается в О содержимое регистра 3, блок 6 задания длительности испытания открывает группу 1 элементов И, начинается случайное испытание и т.д. 6 течение генерирования последовател ности чисел с заданной функцией содержимое регистра 7 адреса не изменяется. При необходимости переключе ния генератора на формирова.ниё случайных чисел с другим, отличным от текушего номером функции распределения, в блок б управления поступают сигналы вйТёШнего управления, по которым в регистре 7 адреса возбуждае ся соответствукмаий выход, из блочков 8 памяти выбирается новое значение Як;, изменяются интенсивности датчиков 9 потоков случайных импульсов и т.д. Сигналы внешнего управления вы даются как из , так и вводятся с фотосчйтывагоших или других устройств ввода. Так как в йроцессе моделирования как правило, требуется несколько независиМЬис последовательностей случайных чисел с различными функциями распределения, то производительность гёнёратора в этом режиме значительно выше , Чем у одйоканального датчика случайных потерь с автоматическим управлением из-за потерь времени на перезапись блоков памяти в процессе моделирования. Рассмотрим работу генератора при формирован ии последовательности случайных чисел с заданной функцией нестационарности. В отличие от предыдущего режима генератор вырабатывает только одну последовательность случайных чисел, Но содержимое регистра 7 адреса, а следовательно, и считываемые из блоков 8зйачения KJ изменяются по npiorpaMMe, задаваемой в блоке 6 управления сигналами внешнего управления. Программаизменения содержимого регистра 7 адреса может не учитывать состояние генератора в пре дыдупше моменты времени. В этом случае сигналы с выходов датчиков 9 блоком 6 управления игноркруются. Если ripeдьадущие состояния генератора учитываются, то сигналы с выходов датчиков 9 блоков б управления обрабатываются в соответствии с программой изменения адресов. Рассмотрим работу генератора при моделировании однородных цепей Марко ва с дискретным временем и конечным множеством состояний. Пусть цепь Маркова имеет конечное множество из п состояний. Тогда для надстройки на заданные вероятностные харайтёристики цепи достаточно загрузить в блоки 8 памяти датчики зна чения ве роятностей перехода из стохастической матрицы П цепи. Причем, если в матрице ,-. П - (Pij )г текущее состояние цепи 1, i . 1, ; определяет номер строки матрицы П, ;последуюшее состояние цепи р, j 1 определяет номер столбца в матрице П, то при записи в блоки 8 памяти везначение j определяроятностей Р ет номер блока, а значение i - номер ячейки в блоке. Следовательно, при возникновении разрешающего сигнала на выходе регистра 7 адреса с номером г, -г i,n , с выходов блоков 8 памяти на входы регулирования интенсивности датчиков 9 потоков случайных импульсов числа , в результате чего интенсивности Л) случайных потоков на выходах датчиков 9 задаютсяи, таким образом, вероятность Pj того, что в результате случайного испытания в регистре 3 установится значение j,определяется значением вероятности перехода цепи Маркова, Рассмотрим работу генератора, когда в блок б управления поступят сигнала внешнего управления, по которым в регистре 7 устанавливается адрес, определяющий начальное состояние цепи Маркова. Поступает сигнал внешнего управления на генерирование следующего состояния цепи. Блок б управления вырабатывает сигнгипы, по которым сбрасывается в О регистр 3, блок 5 длительности случайного испытания открывает группу 1 элементов И,и тем самым, начинает случайное испытание. Первый пришедший с момента начала испытания импульс датчиков 9 потоков Случайных импульсов проходит через группу 1 элеме1 -гов И, шифратор 2 и устанавливает в регистре 3 код, который соответствует следующему состоянию цепи Маркова. Одновременно этот же случайный импульс поступает на адресные входы блока б управления, который устанавливает в регистре 7 новое значение адреса, срабатывает элемент 4 ИЛИ, блок 5 длительности испытания закрывает элементы И группы 1. Хотя на адресные входы блока б управления поступают случайные импульсы датчиков 9, содержимое регистра 7 адреса не изменяется. По новому значению адреса в регистре 7 считывается новая Строка переходных вероятностей матрицы П из блоков 8 памяти.. С поступлением сигнала внешнего управления на моделирование следующего состояния цепи блок 5 длительности случайного испытания сбрасывает в О регистр 3, открывает 31лементы И группы 1, и цикл работы повторяется. Рассмотрим работу генератора при моделировании однородной цепи МарiKOSa с непрерывным временем и конеч1ным множеством состояний. Функционирование устройства не отличается от предьщушего режима за исключением того, что группа 1 элементов И с момента начала моделирования постоянно открыта, а по каждому поступающему с выходов датчиков 9 случайному импульсу в регистре 3 изменяется значение кода состояния цепи Маркова. Одновременно, каждый случайный импульс датчиков 9 поступа ет на сшресные входы блока б управления, выходные сигналы которого устанавливают в регистре 7 адрес, по которому из блоков 8 памяти считываются значения вероятностей перехода Pjj , соответствующие новому состоянию цепи Маркова, Сигналы с выхода элемента 4 ИЛИ в этом режиме игнорируются. Программой функционирования вблоке 6 управления задаются различ ные комбинации рассмотренных режимов, например/ на некоторых отрезках случайный, процесс моделируется как цепь Маркова, на других - как нестационарный с заданными характеристиками нестационарности и т.д. Предлагаемый генератор случайного процесса может быть, использован как самостоятельное устройство для формирования случайного процесса. Однако, наиболее эффективно его применение совместно.с управляющей ЭЦВМ или машиной общего назначения, что дает возможность разгрузить ЭЦВМ от доста точно трудоемкой программной имитации случайных процессов,, а формирование таких процессов возложить на : предлагаемый генератор. Это повышает производительность системы при решении задач статистического моделирования и поз,воляет автоматизироват процесс управления устройством. Широкие возможности автоматического управления как вероятностными харак теристиками случайных процессов, та и видом воспроизводимого процесса (цепи Маркова, нестационарные после довательности и т,д.) выгодно отли чают предлагаемый генератор-от известных устройств. Анализ показывает, что предлагае мый генератор случайного процесса о ладает максимальным быстродействием по сравнению с известными, так как в структуре генератора применена сх ма быстрого случайного испыт.ания, наиболее эффективно используются . датчики потоков случайных импулбсов блока ввода. Например, при моделировании цепи Маркова с непрерывным временем каждый случайный импульс блока ввода вызывает сменусостояни цепи. Однотипность применяемых блоков (датчики потоков случайных импульсо с регулируемыми интенсивно стями, блоки памяти) позволяет конст руировать основные узлы генератора в виде интегрсшьннх модулей и выполнить весь генератор на нескольких платах. Небольшие размеры и достаточно широкие функциональные возможности предлагаемого генератора делают перспективным его использование в качестве специализированного модуля в процессорах ЭЦВМ, Формула изобретения 1.Генератор случайного процесса, содержащий группу датчиков потоков случайных импульсов, выходы которых подключены ко входам элементов И группы соответственно, выходы которых через шифратор соединены со-входами регистра памяти, выходы которого являются выхЬдами генератора и подключены ко входам элемента ИДИ, управляющий вход элементов И группы подключен к выходу блока задания длительности испытания, отличающий с я тем, что, с Целью расширения функциональных возможностей генератора за счет моделирования марковс;ких процессов, он содержит блок управления, регистр адреса и группу блоков памяти, выходы которых соединены с управляющими входами датчиков пото.ков случайных импульсов группы соответственно, а входы блоков памяти группы через регистр адреса соединены с группой вйходов блока управления соответственно, вход KQxoporb соединен с выходом элемента ИЛИ, первый и второй выходы блока управления соединены соответственно со входсял блока задания длительности испытания и с управляющим вхопам регистра памяти, а группа входив блока управления подключена соответственно к выходам датчиков потоков случайных импульсов. 2,Генератор поп.1, отличающийся тем, что каждый датчик потоков случайных импульсов содержит последовательно соединенные гёнёратОр случайных импульсов, вероятностный (1,т)-полюсник, группу элементов И и элемент ИЛИ, выход которого является выходом датчика, а управляющие входы труппы элементов И являются управляиядими входами датчика.1 Источники информации, принятые во вйимание при экспертизе 1,Авторское свидетельство СССР № 504196, кл. G Об Р 1/02, 1975. 2.Авторское свидетельство СССР 344431, кл. G Об F 1/02, 1971 (прототип),