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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники, является усовершенствованием генератора по ант.св. № 1278842, и может быть использовано для моделирования гсвязных цепей Маркова. Цель изобретения расширение функциональных возможностей за чет обеспечения возможности формирования г-связанного случайного марковского процесса. Генератор содержит блок 1 синхронизации, регистр 2 памяти, датчик 3 равномерно распределенных случайных чисел, группу блоков 4 памяти, группу преобразователей 5 код - вероятность , блок 6 связности.Поставленная цель достигается за счет введения новых блоков и функциональных связей, 2 ил,, 1 табл. (Л

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПжЛИН

„„ЯО„„ИЗО95 (5I )4 06 7 58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ; -":

Р. 4

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ (61) 1278842 (2.1) 4206668/24-24 (22) 04.03.87 (46) 15.10.88. Бюл. К 38 (7!) Кишиневский политехнический институт им. С ° Лазо (72) В.И. Борщевич, В.д. Жданов, В.В. Сидоренко, Г ° К. Бордян и Е.В. Морщинин (53) 681.3(088.8) (56) Авторское свидетельство СССР

11 1049903, кл. 6 06 F 7/58, 1982.

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

В 1278842, кл. G 06 F 7/58, 1985. (54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО

ПРОЦЕССА (57) Изобретение относится к области вычислительной техники, является усовершенствованием генератора по ант.св.

Ф 1278842, и может быть использовано для моделирования r- связных цепей

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

"-связанного случайного марковского процесса. Генератор содержит блок 1 синхронизации, регистр 2 памяти, датчик 3 равномерно распределенных случайных чисел, группу блоков 4 памяти, группу преобразователей 5 код — аероятность, блок 5 связности. Поставленная цель достигается за счет вве- а дения новых блоков и функциональных ф связей ° 2 ил,, 1 табл.

1430952

Р($, /С )...Р($„„ /С )

Р(Б /C„); ...,Р(Б /C ) С„, Р($, /С ),Р($„/С„1г ), ° ..,P($„,/Ñ„, ) Изобретение относится к вычислительной технике и может быть использовано для моделирования простых и сложных (r-связных) цепей Маркова, а также в качестве специализированного стохастического генератора тестовых последовательностей в составе систем стохастического функционального контроля дискретных объектов, включая микропроцессорные, Цель изобретения — расширение функциональных возможностей генератора за счет обеспечения возможности формирования r-связного случайного марковского процесса, На фиг. 1 и 2 изображена структурная схема предлагаемого генератора.

Генератор содержит блок 1 синхронизации, регистр 2 памяти, датчик 3 равномерно распределенных случайных чисел, группу блоков 4 памяти, группу преобразователей 5 код-вероятность, блок 6 связности И выходы 7.

Блок 6 связности содержит регистр 8 25 памяти, группу элементов И 10 и группу регистров 9.

Генератор работает следующим образом.

Пусть задана r-связная цепь Марко- 30 ва, имеющая конечное множество состояний $=(S;1, и в этой цепи для всех последовательностей предшествующих состояний длины r (цепочки С,. дли", Р ( ны r) определены и 2 распределения: условных вероятностей Р »;, т,е, вероятность перехода определенного сложного состояния С.1 за один такт из состояния S» в состояние $1, где х=О, I n-g"-1 п1 t=0; п2"-1; . Е Р ; =1.

t=O

Считая цепочки С» текущими состояниями r-связной цепй Маркова, а состояния S. — следующими состояниями

1 цепи, описание марковского процесса осуществляется подобно описанному в прототипе, В начальный момент времени (до

55 прихода первого тактирующего сигнала от блока 1) регистр 2 памяти для оп: ределенности находится в нулевом состоянии, а в группу регистров 9 (для

В принятых обозначениях задание

r--связной цепи Маркова означает, что задана таблица, в которой в левом столбце перечислены все цепочки С<, в правом — соответствующие им плотность распределения условных вероятностей. Для случая г=1 цепь Маркова является простой, однородной цепью.

Количество распределений лишь в самом общем случае будет равно числу г цепочек С, которое равно п 2 . Во многих практически важных случаях для некоторых цепочек распределения могут совпадать, поэтому число Т различных распределений удовлетворяет соотношению Т"и 2, При этом количество групп блоков 4 памяти будет соответствовать значению Т, т,е. имеем оптимальные аппаратурные затраты, Каждому состоянию $„ цепи Маркова ставится в соответствие К-разрядное двоичное число (номер состояния)

Ь, Ь ...Ь (b е 10,1) (b, — старший разряд числа из числовой последовательности 0,1,2,,....,n-1. Каждому сложному состоянию С1 марковского процесса ставится в соответствие М-разрядное двоичное число (номер цепочки)

b Ь,...,Ь из числовой последовательности О,!,2,...........,n.2 -1.

Количество разрядов (бит), необходимое для представления каждого из номеров состояний $,...,S < r-связной цепи

Маркова, равно К=1о п; а для представления каждого из номеров цепочки

M-разрядное двоичное число равно

М=r log zn. определенности) записано начальное значение цепочки С .

Сигнал с первого выхода блока 1 инициирует работу датчика 3 раномерно распределенных случайных чисел.

Сигнал со второго выхода блока 1 управления, осуществляет запись номера следующего состояния SI, сформированного поразрядно на выходах преобразователей 5 код-вероятность, в регистр 2 памяти. При этом номер сос3 14309 таяния S. с выходов регистра 2 намя I ти записывается в регистр 9.1 группы. Одновременно текущее состояние с выходов регистра 9.т группы по тому я же сигналу переписывается в регистр

9.i-1 группы (Х=1 r-2) и на выходах последнего появляется значение данного текущего состояния Б; „. Таким образом, на выходе блока 6 связности появляется значение цепочки С .

Пусть в некоторый момент времени регистры памяти группы и регистр 2 памяти содержит номер (Ь,Ь,1. ° .b )1, т,е, моделируемый марковский процесс находится в сложном состоянии С, который поступает на соответствующие адресные входы всех блоков 4.1,... ...4.К памяти.

Дальнейший процесс формирования следующего состояния описан в прототипе.

Сформированное значение номера (b

4 ды преобразователей 5 .1 ....,5. К кодвероятность и т,д.

Таким образом, происходит моделирование r-связного марковского процесса с конечным числом состояний и, Дальнейший процесс в генераторе продолжается с формирования следукнцего состояния г-связного случайного м"-.ðêoâñêñão процесса аналогично вьппеизложенному.

Ф о ð м ул а и з о б р е ò е н и я

Генератор случайного марковского процесса по авт. -в, Р 1278842, о тл и ч а ю шийся тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности формирования r-связного случайнога марковского процесса, в него дополнительно введены группа регистров, группа элементов И, второй регистр памяти, разрядные выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых подключены к входам синхронизации соответствующих регистров группы. разрядные выходы i-ro регистра группы соединены с одноименными разрядны-. ми входами (ik!)-.го регистра группы, вторые входы элементов И группы подключены к второму входу блока синхронизации, разрядные выходы регистров группы ", îåäèíåíû со старшими разрядами адресных входов соответствующих блоков памяти, информационный вход первого регистра группы соединен с выходом первого регистра памятИ, информационный вход второго регистра является входом заданной связности генератора, !

430952

Составитель И. Столяров

Редактор А, Ревин Техред Л.Сердюкова Корректор И. Пожо

Заказ 5344!51

Тираж 704

Подписное

B1!MHIIH Государственного комитета СССР по делам изобретений открытий

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная,