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

СОЮЗ СОВЕТСКИКсоциАлистичеснихРЕСПУв Лик С 9 С 1 1)4 06 МИТЕТ СССР ний и ОТНРытииГОСУДАРСТВЕННЫ ПО ДЕЛАМ ИЭОБРЕ 2Р. 1 4 области ется усо по ант.св льзова цепей еский сширениза дче анов вани ского лок 1 яти, дат ных слу памяти тво СССР 8, 1982. о СССР 8, 1985. веоста т вве- а 54) ГЕНЕРАРОЦЕССА МАРКОВСКОГ нальн ОПИСАНИЕ ИЗОБРЕН АВТОРСКОМУ СВИДЕТЕЛЬСТВ(57) Изобретение относится вычислительной техники, явл вершенствованием генератора Ф 1278842, и может быть исп для моделирования г- связных Маркова. Цель изобретения р функциональных возможностей обеспечения воэможности фор г-связанного случайного мар процесса. Генератор содержи синхронизации, регистр 2 пам чик 3 равномерно распределе чайных чисел, группу блоков группу преобразователей 5 ко роятность, блок 6 связности ленная цель достигается за дения новых блоков и функцио связей, 2 ил 1 табл.1430952 Р(Б, /С )Р(Б. /С ) Р(Я /С); ,Р(Б /С ) Р(Я,/С,), Р(Б /С ) С 21, Р(Я, /С),Р(Я/С 2 г,)Р(Я,/С,2 ) Изобретение относится к вычислительной технике и может быть использовано для моделирования простых исложных (г-связных) цепей Маркова,а также в качестне специализированного стохастического генератора тестовых последовательностей в составесистем стохастического функционального контроля дискретных объектов,включая микропроцессорные,Цель изобретения - расширениефункциональных возможностей генератора за счет обеспечения возможностиформирования г-связного случайногомарковского процесса,На фиг. 1 и 2 изображена структурная схема предлагаемого генератора,Генератор содержит блок 1 синхронизации, регистр 2 памяти, датчик 3равномерно распределенных случайныхчисел, группу блоков 4 памяти, группу преобразователей 5 код-вероятность, блок 6 связности И выходы 1,Блок 6 связности содержит регистр 8 25памяти, группу элементов И 10 и группу регистров 9.Генератор работает следующим образом.Пусть задана г-связная цепь Маркова, имеющая конечное множество состояний Я=Я;, и в этой цепи длявсех последовательностей предшествующих состояний длины г (цепочки С,. дли",(ны г) определены и 2 распределения:условных вероятностей Р 1 т,е, веро"ятность перехода определенного сложного состояния С.1 за один такт из состояния Я, в состояние Б;, где х=О,и 2 Г ир 1=0; и 2"-1; .Е. Р; =1.40с:о Считая цепочки С текущими состоя. киями г-связной цепй Маркова, а состояния Б, - следующими состояниями цепи, описание марковского процесса осуществляется подобно описанному в прототипе,В начальный момент времени (до55 прихода первого тактирующего сигнала от блока 1) регистр 2 памяти для определенности находится в нулевом состоянии, а в группу регистров 9 (для В принятых обозначениях задание г-связной цепи Маркона означает, что задана таблица, н которой в левом столбце перечислены все цепочки С, в правом - соответствующие им плотность распределения условных вероятностей. Для случая г=1 цепь Маркова является простой, однородной цепью. Количество распределений лишь в самом общем случае будет равно числуг цепочек С, которое равно и 2 . Во многих практически важных случаях для некоторых цепочек распределения могут совпадать, поэтому число Т различных распределений удовлетворяет соотношению Т"и 2 , При этом количество групп блоков 4 памяти будет соответствовать значению Т, т,е. имеем оптимальные аппаратурные затраты. Каждому состоянию Б цепи Маркова ставится в соответствие К-разрядное двоичное число (номер состояния) Ь,Ь Ь (Ь е 0,1 (Ь, - старший разряд числа из числовой последовательности 0,1,2.,и. Каждому сложному состоянию С 1 марковского про. цесса ставится в соответствие М-разрядное двоичное число (номер цепочки) Ь 1 Ь 2Ь из числовой последовательности 0,1,2,и 2-. Количество разрядов (бит), необходимое для представления каждого из номеров состояний Б Б , г-связной цепи Маркова, равно К=1 о и; а для представления каждого из номеров цепочки М-разрядное двоичное число равно М=г 1 од 2 и. определенности) записано начальное значение цепочки С .Сигнал с первого выхода блока 1 инициирует работу датчика 3 раномерно распределенных случайных чисел.Сигнал со второго выхода блока 1 управления . осуществляет запись номера следующего состояния Б 1, сформированного поразрядно на выходах преобразователей 5 код-вероятность, в регистр 2 памяти. При этом номер сос 3 14309 таяния Б с выходов регистра 2 намяти записывается в регистр 9.1 группы. Одновременно текущее состояние с выходов регистра 9,1 группы по тому же сигналу переписывается в регистр 9,1-1 группы Х=1, г) и на выходах последнего появляется значение данного текущего состояния Б; . Таким образом, на выходе блока 6 связности появляется значение цепочки С.Пусть в некоторый момент времени регистры памяти группы и регистр 2 памяти содержит номер (Ь,Ь 1 Ьщ)1, т,е, моделируемый марковский процесс 15 находится в сложном состоянии С, который поступает на соответствующие адресные входы всех блоков 4.1, 4,К памяти.Дальнейший процесс формирования следующего состояния описан в прототипе.Сформированное значение номера (Ь Ь Ь) состояния Б, записывается в регистр 2 памяти при помощи так тирующего сигнала, .поступающего со второго выхода блока 1 и поступает на входы первого регистра 9 группы. Полученное значение номера Ь,Ь., Ь) цепочки С поступает на,адрес 3 п ные входы всех блоков 4.1,;.4,К памяти, обеспечивая подготовку перехода процесса в следующем такте из сложного состояния С в некоторое состояние Б с вероятностью Р., оп 1 ф 35 ределяемое йовым значением случайных чисел, поступающих с группы выходов датчика 3 равномерно распределенных случайных чисел и кодов вероятностей появления логической "1" в каждом разряде Ь 1 Ь ), считываемых из соответствующих ячеек блоков 4.1 4.К памяти на соответствующие вхо 524ды преобразователей 5 .1 ,5, К кодьероятнэсть и т,д.Таким образом, происходит моделирование г-связного марковского процесса с конечным числом состояний и,Дальнейший процесс в генераторе продолжается с формирования следукнцего состояния г-связного случайного марковского процесса аналогично вьппеизложенному.Ф о р м у л а и з о б р е т е н и яГенератор случайного марковскогопроцесса по авт. .в, У 1278842, о тл и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности формирования г-связного случайного марковского процесса, в него дополнительно введены группа регистров,группа элементов И, второй регистрпамяти, разрядные выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых подключены к входам синхронизации соответствующих регистров группы.разрядные выходы . -го регистра группы соединены с одноименными разрядны-.ми входами (Ф)-го регистра группы,вторые входы элементов И группы подключены к второму входу блока синхронизации, разрядные выходы регистровгруппы соединены со старшими разрядами адресных входов соответствующихблоков памяти, информационный входпервого регистра группы соединен свыходом первого регистра памяти, информационный вход второго регистраявляется входом заданной связностигенератора,1430952 Составитель И. Столяроввин Техред Л.Сердюкова Корректор И, Пожо Редакто Тираж 7 аказ 534451 Подписно графическое предприятие, г, Ужгород, ул, Проектная,оизводственноВ 11 ИИПИ Государственногопо делам изобретений и3035, Москва, Ж, Раушс митета СССоткрытиия наб., д,