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

4

о: О Ф

NJ

tfJuf I

Изобретение относится к вычислительной технике и может быть использовано для моделирования простьпс и сложных (г-связных) цепей Маркова, а также в качестве специализированного стохастического генератора тестовых последовательностей в составе систем стохастического функционального контроля дискретных объектов включая микропроцессорные,

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

На фиг. 1 и 2 изображена структурная схема предлагаемого генератора.

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

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

Пусть задана г-связная цепь Марко- ва, имеющая конечное множество состояний , и в этой цепи для всех последовательностей предшествующих состояний длины г (цепочки С,, дли ны г) определены п 2 распределения- условных вероятностей Рf;, т.е. вероятность перехода определенного сложного состояния С за один такт тояния Si в состояние Si, где ,

n-lj n-2 -l ;

г(-2 -1

t 0

.

5

0 5

О

0

5

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

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

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

Количество разрядов (бит), необходимое для представления каждого из номеров состояний Sj,,. . . ,8 (,-f г-связной цепи Маркова, равно а для представления каждого из номеров цепочки М-разрядное двоичное число равно .

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

Си. P(s,.,),,p(s,/c,.,r.,),...,p(s,.,/c,.,r:.)

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

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

определенности записано начальное значение цепочки С j..

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

Сигнал со второго выхода блока 1 управления .осуществляет запись номе- ра следующего состояния S , сформированного поразрядно на выходах преобразователей 5 код-вероятность, в регистр 2 памяти. При этом номер соетояния с выходов регистра 2 памяти записывается в регистр 9.1 группы. Одновременно текущее состояние с выходов регистра 9.я группы по тому же сигналу переписьшается в регистр 9.1-1 группы {Х, г-2) и на выходах последнего появляется значение данного текущего состояния S,-.. Таким образом, на выходе блока 6 связности появляется значение цепочки С|.

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

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

Сформированное значение номера (b:,b 2. . .bf, ) СОСТОЯНИЯ Sj записывается в регистр 2 памяти при помощи тактирующего сигнала, поступающего со второго выхода блока 1 и поступает на входы первого регистра 9 группы. Полученное значение номера (b,b.2... ...b)t цепочки С поступает на.адресные входы всех блоков 4 ,1 .......4,К

памяти, обеспечивая подготовку пере- .хода процесса в следующем такте из сложного состояния С в некоторое состояние S с вероятностью Р. ° ределяемое новьгм значением случайных чисел, поступающих с группы выходов датчика 3 равномерно распределенных случайных чисел и кодов вероятностей появления логической i в каждом разряде (b...b), считываемых из соответствующих ячеек блоков 4...,. ...4.К памяти на соответствующие вхо30952 .

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

Так№5 образом, происходит моделирование г-связного марковского про- цесса с конечным числом состояний п,.

Дальнейший процесс s генераторе продолжается с формирования следукнце- 10 го состояния г-связного случайного марковского процесса аналогично вьппе- изложенному.

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

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

памяти, разрядные выходы которого соединены с первыми входами соответствую- лщх элементов И группы, выходы которых подключены к входам синхронизации соответствующих регистров группы.

разрядные выходы i-ro регистра труп- пы соединены с одно1-1менными разрядными входами (14-)-го регистра группы, вторые зходгл элементов И группы подключены к второму входу блока синхронизации, разрядные выходы регистров группы соединены со старшими разрядами адресных входов соответствующих блоков памяти, информационный вход первого регистра группы соединен с

выходом первого регистра памяти, информационный вход второго регистра является входом заданной связности генератора,

VUB.2