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

Изобретение относится к области вычислительной: техйнки предназначено для моделирования потоков случайных чисел с требуемыкгй законами распределения марковских процессов и может быть использовано при Построении вероятностных вычисли- те-пьных устройству а также в качестве специаяизированйого стохастического блока, подключенного к вычислительным машинам общего назначения, Известно устройство, содержащее генератор равномерно распределенных случайных чисел, схему срав1 ения, блок памяти, генератор тактовых им пульсов, специализированный дешифратор, регистр формирования случайного числа, входные и выходные вентили till Недостатком устройства являеТсй узкая специализация, так как оно позволяет формировать только случайные числа с требуемыми законами распределения, но не позволяет мирова ь более сложные случайные пр цессы, например марковские. Известно устройство содержащее блок управления, генератор равномер но распределенных случайных чисел f блок сравнения, блок памяти, три регистра 21, Устройство позволяет формироват15 в режиме разделения времени несколь ко последовательностей случайных чи сел с заданными законами расйределё ния и марковские процессы. Недостатком данного устройства является невозможность программного управления при постоянном объеме па мяти числом моделируемых законов распределения и разрядностью фбрмируемых случайных чисел, связностью цепей Маркова и числом их состояний что ограничивает efo функциональные возможности. Наиболее близким к предложенному по технической сущности является генератор случайных процессов, содержащий генератор тактовых импульсов, регистр сдвига, три элемента И генератор равномерно расп)еделенных случайных чисел два блока элементов НЕ, блок :элементов И, шифратор), ((коммутатор, элемент НЕ, регистр , блок памяти, блок сравнения С Известный генератор Может формировать в режиме разделения времени потоки случайных чисел с заданными законами распределения, последовательности кодов, задающих цепи Маркова, Недостатками устройства являются ,невозможНойть формирования полумарковскиХ-случайных процессов ; слутчайных процессов с заданной функцией нестационарности i сложность управления устройством (настройкой ), Цель изобретения - расширение функциональных возможностей уст ройства за счет увеличения класса воспроизводимых статистических характеристик , Йоставленная цель постигается тем/ что в генератор случайных прО цессов, содержащий генератор тактовых импульсов выход которого соединен с входом генератора равномерно распределенных случайных чисел, выхода которого соединен с первым входом блока сравнения, второй вход koToporo подключен к выходу первого блока памя±и, введены регистр команд, блок задания адреса и второй блок памяти Первой выход которого являе ся выходом генератора и подключен к первому входу блока задания адреса выход которого сЗоединен с. входом первого блока памяти , выХоД блока сравнени} со- еДинен с первым входом второго блока памяти, второй Вход которого Подключен к выходу генератора тактовых импульсов, выход регистра ко- Манд соединен с вторым входом блока задания адреса и с третьим входом второго блока памяти, второй выход которого соединен с третьим входом блока задания адреса. На фиг; 1 приведена структурная схема генератора ; на фиг. 2 - структурная схема блока задания адреса ; На фиг, 3 - структурнай схейа второго блока памяти. Генератор содержит генератор i равномерно распределенных случайных чисел, блок 2 сравнения, блок 3 памяти, блок 4 задания адреса, блок 5 памяти, генератор 6 тактовых импульсов, регистр 7 команд. Блок 4 задания адреса содержит коммутатор 8, блок элементов И 9, регистр 10, блок 11 элементов ИЛИ. Блок 3 памяти содержит первый регистр 12, второй регистр 13, блок элементов ИЛИ 14. В основу работы устройства положен метод условных вероятностей, заключающийся В преобразовании последовательности равномерно распределенных случайных чисел в последовательность Случайных чисел х с заданной функцией распределения Г(Х). Устройство запускается на генерацию каждого числа сигналов (импульсом), приходящим на вход блока 3 памяти. Процедура получения т-разрядного случайного числа х состоит из Последовательного формирования значений г, i 1 т , разрядов случайного числа, путем сравнения на каждом -м шаге равномерно распределенного 1исла - и значения условной функции распределения F( - 1), определяющей вероятность того, что примет значение равное единице, при условии, что на предыдущих i-1 шагах сформировано значение х - li При этом, если выполняетсй Р(г,/Х| - 1)/|, (1 то г 1, в противном случае г 0. Формирование значений г в соответствии с (l) является функцией блока 2, который на каждом такте ра боты устройства сравнивает равномер расттределенное число |j , поступающе с выхода генератора 1 на его первый вход, со значением условной функции распределения F( j - 1) , поступа ющим с блока памяти 5 на его второй вход. Расширение функциональных воэмож в предлагаемом устройстве достигается благодаря командному уп равлению видом формируемого случайного йроцесса и разрядностью формируемых слу1айных величин. Регистром команд стохастического генератора йвляется регис±р 7i Собственно команйа состоит Иэ 1етырех полей, первое из koToptsix содержит указатель разрядности Ар формируемых случайных величин, который передается 6 блок 3, второе, третье и четвертое поля содержат соответстве но начальный адрес загрузки Аj| значений УСЛОВНЫХ фуйкций распредеЛе.нйя .F (г/х ) в блок & памяти, затель сдвига А(, маску А. Случайное т-раЗрядное число фое мируетсй й- блоке 3 в Лмладший р)азрядах регистра 13 за цикл, содерука щйй m тактов. Для этого-i erMcTp 12 имеет пбрвЬ1й Информационный вхой, второй вход синхронизации записи, третий вход сДвига на одйй разряд в сторЬну младших, первый Информаци онный вахоД второй выход переноса из младшего разряда при сдвиге Ре гистр 13 имее первый вход разрешбгйия записи по S-входам, третий вхоД синхронизации записи, четвертый информаиионный вход записи tiu S-sxoдам, второй вз4од сброса. Tak как S-входы триггеров регистра 13 соедйнены с выходами соответствующие раз ,Ридов регистра 12, то при постуПлёйии управляющих сигналов на первый гИ второй входы регистра 13 6н выпол няет операцию Логического сложения своего предыдущего содержимого с содержимым регистра 12. .Блок 14 на двухвходовых элементах ИЛИ и выполняет операцию логйческо- го сложений содержимого регистров. 12 и 13. Процедура фop шpoвaния случййного числа выполняется следующим образом. I По сигналу, поступающему на вход блока 3, сбрасывается в нуль содержи моё регистра 13, в регистр 12 записывается указатель Ар, содержащий .единицу только в разряде, соответствующем старшему разряду формируемого случайного числа. Так, еели необходимо формировать числа разностью m 4 при разрядности регистра 13.п 3, двоичное значение Ар 00001000, при га 6 А - 00100000. на каждом 1-м такТе блок 2 к моменту появления импульса генератора 6 в соотвётствии с (11 вырабатывает значение г. Если при п - 8 и m б на первом такте « 1, то по сигналу генератора 6 содержимое регистра 12, равное 00100000, записывается по S-входам в регистр 13, если г., О, то запись не выполняется, т.е. в конце такта содержимое регистра 13 равно OOh OOOOO. По заданному фронту импульса генератора 6 содержимое регистра 12 сдвигается на рдин разряд и становится равным 00010000. Если блок 2 вырабатывает значение Tg, то аналогично описанному в регистре 13 формируется число, равное ООГ1,Г20000. Таким образом, после m 6 тактов содержимое регистра 13 равно , где шесть младших разрядов содержат искомую случайную величину. При этом по задHeNiy фронту последнего шестого импульса генератора б из младшего разряда регистра 12 выдвигается единица/содержимое регистра становится равным нули, а на втором выходе рёгистра возникает сигнал переноса, который служит указателем момента . сжончайия формирования случайного Чиспа. Последующие импульсы ген раторй 6 никакого влияния на содержимое регистров 12 и 13 не оказывают. Для настройки устройства на форьгарование случайных величин с заданиями вероятностными характ.ерИстиКами в блок 5 памяти записываются множества значерий условных функций распределения F (г/х , где j - номер распределения. На Кё1ждом i -м такте работы устройства из блока 5 йыполйяётся считывание значения F yji/ адреС которого определяется логичес КИМ сложением начального адреса загруэки распределения Ал, текущего содержимого регистров 12 и 13, а при формировании состояний Марковекого процесса - и предыдущего сос ояйия S процесса, хранящегося в регистре 10 При формировании случайных чисел содержимое регистра 10 должно быть нулевым. Адрес памяти формируется в блоке 4, который содержит блок 11, выполненный на трёхвходовых элементах ИЛИ, на первые, вторые и третьи вхоДы которых поступают соответствено логическая сумма содержимого регистров 12 и 13 и с выхода блока 3, начальный адрес загрузки А из регистра команд 7, предшествующее состояние марковского процесса S из регистра 10 блок 9 двухвходовых элементов И, на первые и вторые входы которых поступают соответстйенно маска А(ц из регистра Команд 7 и число с выхода коммутатора 8, который поступающее на его первый вход число передает на. вход со сдвигом в сторону старших разрядов, вели

Распределение

чина Которого определяется указателем числа сдвигов А, поступаю1цим на его второй вход из регистра команд 7.

Устройство при формировании последовательности - двухразрядных случайных чисел, задаваемой условной функцией распределения F(r/x), работает следующим образом.

Пусть разрядность -регистра 13 п 4 и загрузка блока памяти 5 выполнена согласно табл. 1.

Таблица IV

В

ГЕНЕРАТОР СЛУЧАЙНЫХ ПРОЦЕССОВ, содержащий генератор тактовых импульсов выход которого соединен с входом генератора равномерно распределенных -случайных чисел, выход КОТОРОГО соединен с первым входом блока сравнения, второй ёход которого подключен к выходу первого блока памяти , отличающиеся тем, что, с целью расвгарения функциональных возможностей генератора за счет увеличения класса воспроизводимых статистических характеристик,он содержит регистр команд, блок задания адреса и второй блок памяти, первый выход которого является выходом ге- . нератора и подключен к первому входу блока задания адреса, выход которого соединен с входом первого блока памяти, выход бло«а сравнения соединен с первым входом второго блока памяти , второй вход которого подключен к выходу генератора тактовых импульсов, выход регистра команд соединен с вторым входом блока за(Л .Дания адреса и с третьим входом вто.рого блока памяти, второй выход.коа торого соединен с третьим входом блока задания адреса.

Адрес ячейки 0001 -0010 двоичный 0000 Содержимое ) ячейки

Распределение Адрес ячейки 1001 1010 двоичный. 1000

В обозначении F г - 1) А,В/ индексы распределения , i - номер такта, двоичное значение случайного числа, сформированного в регистре 13 на (i- l)-м такте.

Пусть далее регистр 10 обнуляется, в регистр команд 7 записывается Aji 0000, что соответствует начальному ёшресу загрузки распределения В в блок 5, указатель разрядности Ар 0100, маска А,, 0000 (указатель сдвига А при нулевой маске безразличен).

В начале такта генератор 1 вырабатывает число р., по импульсу, поступающему на вход блока 3, сбрасывается в нуль регистр 13, в регистр 12 записывается Блок 4 формирует адрес памяти который образуется в результате логического сложения содержимого регистров 10, 12 и 13 и поля АЛ команды,-и на перл вом шагечравен 0100. Из блока 5 считывается Р®Д.Г4,). Блок 2 сравнивает с Р (г)в соответствии с прависвободные

лом 1 и вырабатывает г. По сигналу генератора б в регистр 13 записывается код , содержимое регистра 12 сдвигается на один, разряд, генератор 1 формирует число - втором такте блок 4 вырабатывает адрес, равный , из блока 5 выполняется считывание значений условной функции распределения F (Г2,)), блок 2 формирует г„ и т.д. После третьего такта треЗс младших разрядах регистра 12 сформировано искомое случайное число.

ЕСЛИ необходимо формирование случайных чисел с распределением А, то в регистр команд 7 записывается А 1000, что соответствует начальному адресу загрузки распределения А в блою. 5, А| 0010, A,in 0000. В начале такта генератор 1 формирует число , по сигналу на входе сбрасывается в нуль регистр 13, в регистре 12 записывается Ар. Аналогично предыдущему блок 4 формирует адрес, который в этом случае равен p h /OOOjF VjJOlO) f( Р(1зГОО))У(()| ООН 0100 0101 ОНО 0111 1011 1100 1101 1110 1111

Устройство 1ФИ моделирований срс тоянйй двухсвязной цепи Маркова, . описываемой матрицей переходных дё Ьятносте Й Efе+НК) ,,4j работает следующим об|)айоМ4

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

Начальный

адрес .

области ДВОИЧНЫЙ 000000 000100 001000 OOilOO бЮоОО ;Ййожёствб дво«чное 1Ноо,йй) бЫ (йьв

Начальный

адрес об-

- - . - .

двоичный 100000IbOlbo 101060 101100 llOOOO Множество - Гне ,J3 - двоичнае 4«io,oor ,toV

% регистр коМё«1д 7 записывается Ау 000000, Ар. 000010, Маска A,j 111100, указатель АС 000000 указывающий Что ко.ммутатор 8 должен передавить код со сдвигом , на два разряда в стороиу старошх. На чальное состояние, процесса (двоичное } записывается в старшие .разряды регистра 10. По сигналу, поступающему на вход 15, сбрасывается в нуль регистр 13, в регистр 12 за-г1исывается Ajj. Блок 4 формирует Начальный адрес памяти, которьИй определйется логической суммой Со- . держимого регистра 10 - регйстЕ а 12 - .QOOOIO, регистра 13 000000,.. Поля А Команда ОООООО. . ; и равен 1.0. Из области пгимятн блЬ--: ка 5, содержащей значения множес ; ва (Н rSrSrlrPj, считывается . И г°г|г|г|(Ц). Далее аналогично ttpeдыдущек за два такта в мпадитх разрядах регистра 13 формируется слу чайное число, являющееся очередном состоянием марковского процесса

ьдвЛЙрование которого сводится к :формирований случайной величййы К ic функцией распределения В j 1C, ;к-1 V41 гйе Ifj - предьтойцие состояния цепи Перед началом работы генё5 ратора каждой |,j строке матрицы . становится в соответствие урйов,ная функция распределения Htj(г/х), множества значений которой . записываются в блок памяти 5. Для , 10 приведенного случая зе грузка энаЧё .й НИИ {FtjJ в области ПМ4ЯТЙ блока 5 можетбыть выполнена согласно

Т а б ли ц а 2

010100 011000 OlllOO

110100 111000 llllOO

ОбООг Гя. По окончании формирования ниела на втором выходе регистра 12 вырабатывается сигнал, по коTot oMy азраз1ается запись кода в

5 регистр 10. К этому моменту на выходе ;блока 11 присутствует число г г2гРг г г, передаваемое кЬммутатором 8 на вход блока 9 со сдвиf OM на два разряда в сторону стар0ших. Блок 9 выполняет логическое сложение йода r|rPr3rjOO и значе; Ния маски Ал(ц 111100. Полученная

|сукма tgr rjjrn- записываете в реггистр 10.

s

По следукадему импульсу на входе 15 сбрасывается Нуль в регистр 13 в регистр 12 записывается АО. Влок 4 формирует адрес, равный 10 Из области памяти блок 5,, со0держащей fraoжecтвo , считывается Нг|гд1г г( Далее аналогично предыдущему формируется новое состояние цепи 0000г г|. При достаточном объеме памяти

5 блока 5 генератор может быть наст- («о .- ,tl} - {И-гд,и ,floK Н.,, {Щл IH.f-il

роён на воспроизведение нескольких цепей Маркова. В этом случае номер цепи указывается полем А команды. Так,.если необходимо моделировать две двухсвязных цепи Маркова с матрицами , pPpjk, В 1,4, то объем блока 5.должен бытьне менее 128 ячеек. Значения Н P,jj могут записываться с началного адреса 0000000, значения {. - с адреса 1000000. Для формирования состояний цепи в в регистр 7 необходимо записать команду, содержащую Ац 1000000, Ар 0000010, А 0111100, А 0000010.

Устройство при моделировании полумарковского случайного про01000 ото

00100

00000

. . в регистр команд 7 записыва- ется Af 10000, А f 00010, А„ 01100, Ag OOOio. В регистр 10 записывается код Ог Г200/ где - начальное состояние процесса, по сигналу на входе 15 начинается цикл формирования очередного соетояния процесса, сбрасывается в нуль регистр 13. в регистр 12 записывается Ар, Блок 4 формирует адрес, равный по которому с итывается Н (r-jf . За два такта в регистре 13 формируетсй следующее состояние процесса . На выходе блока 11 присутствует число , которое сдвигается коммутатором 8, логически умножается на маску А бло ком 9. Полученный код по сиг налу с второго выхода регистра 12 записывается в регистр 10. На этом формирование очередного состояния марковского процесса оканчивается. . Далее в регистр 7 записывается .А 00000, А OllOO., At 00000, Ар 00010. По сигналу на входе Ij начи-нается цикл формирования времени нахождения процесса в текущем состоянии . Сбрасывается в нуль регистр 13, в регистр 12 записывается А, блок 4 формирует адрес, равный . Аналогично предыдущему в регистре 13 формируется число, явцесса, описываемого матрицей переходных вероятностей fpjhj, j, h 1,4 и множеством функций распределения F j (t) времени нахождения процесса в состоянии j, ( время нахождения процесса и любом из состояний кодируется двухразрядным двоичным числом), работает следующим образом.

Перед началом работы устройств каждой функции Fj(t) ; в каждой строке матрицы Р ставится в соответствие условная функция распределения F.- (г/х) и Hj (г/х). Значения условных функций распределени записываются в блок памяти 5, например, согласно табл. 3.

Т а б л и ц а 3

10100 11000 11100

10000

t -t-li

H(r/x ) ляющееся временем нахождения процесса в состоянии . И конце цикла по сигналу иа втором-выходе регистра 12 сформиройанЬое к этому моменту на выходе блока § число . записывается в регистр 10 tla этом формирование времени нахождения процесса в текущем состоянии окайчивается. Перед Началом Моделирования следующего состояния процесса восстаИаЁЛивае ся содержимое регистра 7 (АЦ 10000, Ар 00010, АС 00010/ А 01100 4 По сигналу на входе 15 приводятся в исходное состояние регистры 13 и 12, блок 4 формирует адрес lr§r|lO, из блока 5 считывается Й(г-,)и т.д. Предложенный генератор может быть использован при формировании случайных чисел с заданной функцией нестационарности,. определяемой последовательностью ( программой) изменения во Времени функций распределения. . Пусть в процессе формирования двухзарядных случайных чисел необходимо в соответствии с заданной программой чередовать распределения FJ (r/x),j Г78. В этом случае загрузка блока 5 может быть вь(полненасогласно табл. 4. ,. В регистр 7 записывается KOMttt|да;- указывакадая начальнь й зй рузКй дерйого распределейнй фррм1 рЬвйНия Случайного числа не jb л1ичается о рассмотренного ранее В момент смены распределений в реги р 7 записывается новая команда, Указыва1ш;ая начальный адрес очередйргр распределения. При использовании в составе . сложной Многокомпонентной системы Например модели стохастической генератор яйляется уэлоМ/ поставлймйШМ случайные числа в различные блоки модели. Запросы от блокоб Модели поступают в случайные момент времени, при этом каждый j-й зйпрос формирования случайного ч«4с йй или последовательности чисел с соответствующим ему распределением FJ (г/х). В .этом режиме каиядому виду запросов ставится в соответствие определенна команда. Обслуживание запроса сводится к записи в регистр 7 команды,соответствующей данному запросу, и формированию случайных чисйй в соответствий с установленМой командой. Причем, запросу моЖет соответствовать команда, задающа режим формирований состоя-, НИИ марковского илиполумарковско го случайных процессов. ; При работе во всех рассмотренЙых йыше режимах возможна сйтуа-: ция, когда в блоке 5 загружено йесkoAbko множеЬтв F- и возникает Необходимость замены множества {(Л, загруженного с адреса А} на Множество {Рр}« В предлагаемом уст ройстве в отличие от прототипа Данная Процедура выполняется весьма просто ввиду того, что значения множества расположены в одной области памяти блока 5. Операция загрузки Fp сводится к записи предварительно упорядоченных элементдв множества в (Fej блок 5, начиная с адреса Ац в .порядке возрастания адресов. Для этого в регистр 7 записывается команда с А, А; АН, сбрасываютТаблиц.а4 ся в нуль регистры 10, 12 и 13. После записи каждого элемента Р(г/х; содержимое регистра 10 увеличивается на единицу, в результате чего адресуется следующая ячейка блока памяти. 5. В основу алгоритма работы уст:р 5йства может быть положен метод « врйтных функций или его комбиная с методом условных вероятностей.. .. Реализация блоков предлагаемоГО устройства не имеет отличительных особенностей. Все блоки {. кроме блока 7 J устройства могут быть йыполнены на микросхемах 155 серии согласно РТМ. Используются готовые функциональные узлы, имеющиеся в этой серии. Предпочтительнее использовать генератор равномерно распределенных чисел комбинированного типа. Блок сравнения 2 выполняется как комбинационный сумматор на микросхемах 155 ИМЗ ,11ли .Блок памяти 5 (в за-.висимости от Объема требуемой памяти) может быть реализован на микросхемах 155 РУ2, 541 КР1А, 541 KPlE, Ж, И, К, генератор тактовых импульсов легко реализуется на микросхе мах 155 ЛАЗ, регистр команд 7 может быть как наборным (тумблерным), так и в интегральном исполнении 155 ИР1, 155 ИР13, Коммутатор 8 собирается. Йй микросхем 155 КПЗ (155КП7), блок схем И 9.- из микросхем 155 ЛИ1. Регистры 10 ..и 12 выполняются на 155 ИР1, а регистр 13 - на 155 ИР13 согласно PTM -Блок схем ИЛИ 14 набран из мийросхем 155 ЛЛ1, блок схем ИЛИ 11 ИЗ микросхем 155ЛЛ1, 155ЛРЭ. Так . kaK детализация блоков устройства выполнена до функциональных узлов, имеКяцихся S составе серии, то реализаЦия блоков по приведенным данным не вызывает затруднения. Таким образом, предложенный стохас тический генератор обладает рядом технических преимуществ перед известны, так как позволяет формировать потоки случайных чисел с заданными

функциями распределения, последовательности состояний односвязных и многосвяэных. Цепей Маркова, Bpei aных параметров и состояний полумарковских процессов, потоки случайных чисел с заданной нестационарностЬю (программой изменения функций распределения J. При этом за счет страничной; организации и разме щения значений условной функции распределения, относящейся к одному распре делению, в одной или нескольких смежных станицах памяти существенно упрбщается процедура настройки устройства на формирование случайных последовательностей с заданными вероятностными свойствами.

Предложенное устройство реализует принцип командного управления

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

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