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

1

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

Цель изобретения - упро1цение генратора.

На фиг. 1 нзобралсена структурная ,схема генератора случайного марковского процесса на фиг„ 2 - структур нал схема преобразователя код-веро- ят1юсть;- на фиг„ 3 - электрическая схема генератора слз чай.ного марковского г/роцесса; на фиг, 4 - элс ггри- ческая схема преобразователя роятность.

FeifepaTop случайного марковского процесса содержит блок 1 си11хрони- зации, регистр 2 памяти, датчик 3 равпомерно распределенпых случа11ньгх

чисел, гру1ит:у блоков 4,

,4Л.

памяти, группу преобразователей 5.1 5 о 1,, о ,., 5 „k код-вероят.ность,

Калу.|;ый преобразова ге:.(ь 5 код-ве- роятность группы 5 .15,,.,... 5. k (фиг. 2)

содерлсчт сумматор б и э.памент ПЛИ 7„

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

Блок 1 синхронизации (фиг, 3) содержит генератор 8 тактовых, импульсов, счетный триггер 9, элементы .И 10 и 11,

Датчи.с 3 равномерно распределенных случайных чисел содерлшт регистр 12 сдвига с цепью обратной связи,, Сформированной путем выиолнепи} .но- гической операции ИСЮПО ЧЛКЛДЕЕ ИЛЛ над его 13--м и 31-м разрядам-: при помощи элемента 13 ИСКГ1ЮЧА ОЩ.ЕЕ 1ШИ, выход которого соединен с информационным входом первого разряда регистр 12 сдвига.

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

Пус ть задан марковский процесс, описываемьш конечным множеством сое тояний , , п

и стохастической матрицей переходов Р II PjglJ 5 где P;f, - вероятность пере- хо,да за один такт из состояния

2

состояние SP, i, 1 -OjU-l

n-l

2: P.,

двоичное число номер состолги- я (b, ,

,b,) i, bj6 0,1,

к

:тарJ S . 3- J

П1ИЙ разряд ЧИСЛЕ. из числовой последовательности 0;1,2,..,,, Количество разрядов (бит), необходимое Д.ЛЯ представления каждого из номеров состояний Sj ,,.,53 цепи Маркова,

k 1ор,п„

Выходной рег.истр 2 памяти, имею1ЦИЙ k раз эядов, предназначен д.ля Х1)анения номера текущего состояния цепи Маркова, являющегося одновремеи- по адресом ячейки блока 4,1 и старшей частью адреса ячеек блоков 4.2,,,,,,4,k памяти, необходимого для формирования номера случайного состояния цепи Маркова, Количество преобразователей 5 код-вероятност1, необходимое для построения генератора,

-равно k.

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

нии

1 0,11-1 из состояния S

.5

0

5 0

i-ой строкой (Р: ,. . . ,Pj.,.,, переходов Р. Форькирозание номера следующего состоя ия может осуществляться поразряд,но и тогда упом.япутое сложное событие молсет быть представлено как совокупность элементарных событий: формирование значения калэдо- го разряда bu, номера (Ъ, jb,.-. bj,)g с„чеду1о.ще1 О события Sg в зависимости как от номера текущего события (Ь( jbg ,. о,/Ь,); , так и от реализации случайного процесса формггрования значений всех разрядов (Ь, ,., „,,b,;)g предшествующих ()-My разряду. Направление поразрядного формировани; -- о .г с 1 арше:го разряда Ь к младшему Ъ,. Так как старший разряд b, не имеет предшествующего разряда, для него двойная зависимость выра кается в одиночную (только от номера i текущего состояния Si)„

При переходе к упомянутым э.пемен- тарныл 1 соб,ыти.ям необходимо стохасти- ческзпо матр1,(цу переходов Р прообразовать в стохастическ .ио матри.цу А зн.зче-ний ус.повных вероятностей появления логической 1 в разряде;

J+1

.номера СОСТО.ЯНИЯ Sg в зависимости от номера текущего состояния Sj и логических знамений предшествующих л тарших разрядов (b|,.,.,b:

Столбец А; матрицы А //а,// , , , i 0,n-1 соответствует состоянию с Sj и формируется путем преобразования строки исходной матрицы переходов Р.

При1.этом элемент стобца А; содержит значение вероятности появле- 10 ния логической 1 в старщем разряде Ь, номера состояния Sg.

Элементы а

2.1

содержат

значения условных вероятностей появления логической 1 во втором разряде bj номера состояния Sp при условии, что разряд Ь( принял значени логических О и 1 соответственно. Элементы а j ,,,,,a j 1(; содержат значения условных вероятностей появления логической разряде номера состояния Sg. Их количество равно 2 . Суммарное количество элементов столбца составляет 2 -1, Для получения значения элемента а

Ml

необходимо строку Р/ матрицы Р

разделить на две половины: Р

нулевую

чР;п, и единичну о Р,- ,... ,Р; Тогда а. - Р.„- cyi-iMa вероятное 1К

тей единичной половины.

Для получения значения элемента а2 необходимо полученную ранее нулевую половину разделить две половины: нулевую и единичную Р.п ,. „ , ,Р; п .,

сн

Тогда

V

а

2,

Р:с

Р;

о- а

i-0

Для получения значения п,.- необходимо полученную ранее для а,; единичную половину также разделить на две половины: нулевую Р-л , . . . ,Pji п, и единичную Р. ,

„ i

Тогда

гм

P.D

а,.

Н

I П-1

6 2

Для получения каждого следующего значения aj. каждая из полученных

3

на предьщущем шаге половина делится пополам, выбирается ее единичная половина и суммируются значения вероятностей P;g , вошедших в нее. Полученная сумма нормируется по сумме значений вероятностей исходной половины. Вычисления завершаются при достижении значения d 2 -1.

5

0

5

0

5

0

5

0

5

Например, марковский процесс имеет восемь состояний и описьшается матрицей переходов Р, представленной в табл. 1.

После преобразования указанной матрицы Р получена матрица А условных вероятностей появления логической 1 в каждом разряде bj номера каждого состояния Sg, которая представлена в табл. 2.

Блок 4.1 памяти предназначен для хранения значений кодов условных вероятностей появления логической 1 в старшем разряде Ь, номера состояния. Число ячеек блока 4.1 памяти

1

равно числу столбцов 2 матрицы А, причем содержимое ячеек, расположенных последовательно по адресам Г 0,1,...,п-1, соответствует значениям элементов о((о ,... ,. строки А, этой матрицы. Выбор ячеек осуществляется при помош адресных входов, подключенных к выходу выходного регистра 2 памяти.

Содержимом}, ячеек блока 4.2 памяти соответствуют значения элементов строк А2 и A3 матрицы А , задающие значения условных вероятностей логической 1 в следующем, младшем разряде Ь2 номера состояния. Для обеспечения выбора одной из строк А2 и A3 блок 4.2 памяти содержит дополнительный адресньй вход, подключенный к выходу преобразователя 5.1 код-вероятность, при помоп1;и которого учитывается текущее значение разряда Ь, (условие) формируемого номера состояния SP .

С

Содержимому ячеек блока 4.3 памяти соответствуют значения элементов строк А4, А5, А6, А7 матри1да А , за- даюБще значения условных вероятностей появления логической 1 в разряде bg номера состояния. Для обеспечения выбора одной из указанных строк блок 4.3 содержит два дополнительных адресных входа, подключен- .ных к выходам преобразователей 5.1 и 5.2 код-вероятность, при помош которых учитываются текущие значения разрядов Ь, и Ь формируемого номера состояния Sf. .

Содержимому ячеек блока 4 (j+l) памяти соответствуют элементы строк ,. . . ,A2Jti, , задающие значения, условных вероятностей появления логи- ра зряде Ь;

ческой 1

1-и

номера состояния. Для обеспечения выбора одной из указанный строк блок 4.(j+1) со5

дершгт j дополиительньк ад.ресньпс входов, подключенных к выходам пре- образовлтелей 5 ,1 ,. ,., 5 , j код-вероятность, прн помощи KOTopp.ix учитываются текур-гне зтгачения разрядов b.,,.,,bj формируемого номера состояния Sg ,,

Для обеснечения выбора ячеек блоков 4 .,2,, . „, j4„k памяти, соотлетству- юцих номеру столбца матр1- цн А j груп пы старших адресных входов упомянутых 6;i iOKon памяти соединены одио тгмвнпыми разрядами между собой и под ключень к соответс зугащим разрядам вькода выходного регпстр.а. 2 памяти,

о

12

Л занисьшаго гся в блоков 4 ,1 , . . ,,. f Jc памяти л виде тсодов уп равлеп1- я П 5еобразовател5гм, 1 5.1 ,, ,. ,, ,5 код-вероятность 5 котор- е форг- ируют логические пна-геттия разря/тол Ь , .. . , номера следуюитего состояния Sn мар- кб7; ск:ог о ироцесса с }- ероят1м-.1СтямИр i-taTpT ueii Л ,

- о, /лос1 5ал1ие зна илний т ероятнос- тей c(j, осуществляется исходя состояния С

где с;

:;

m - разрядное .и,елое д5О1- чиое чи;сло. ) зна че.нмя 0,,,х.1П- Ц га 3 ада в т 1 р е б у емую т очл о с т} . пр е о б р а з о- вания код- вероятноеть,, равную 1/2 in; pel одноразрядное двоичное число значение которого оггределяется с. дующим оС разом: р(у| 1. если а j,- 1,. т,е, появление лошческол 1 в некотором разряде о

а 1. - I , I -e..

о 1

в разряде доллсно ,1ть Беро1гт ос. или невозможиьи (при этом - О, следовательн-о,, и.(Хд.; 0) с.обытиеь;,.

Значения

3аииеываются в М11.ад)яии

разряд кода вероятности. Это значение, )юда1 аемое на Jiepjryio группу вхс дов гфеобраз(.пча .геля 5 ,;i гсод-вероят- пость,, доллсно поступать на .второй :

ВХОД лох ического элемента H.llVi 7, обе обеспечива.я реализацию достоперн.ого

события а () с т о X а с т.ич е ; к о г 6 О

AI, 0, (.кедуюпще гп разрядов разряда Bi .кода вероятности исполь - эуются дл.я .яггписи значени ; ul,,,. , разряды KO voporo сдвинуты влево на один

(/.

I ири р,; ;; j и

Н 1

:рг и. и

разряд (.(.JO3Towy значен.ия

t.ii

умножаются на

Значение э .гог части

20

788426

кода, постунавт на первую группу входов п1.-разр7{дного д.воичного сумматора 6 преобразователя 5 код-вероятность. Для кодирования значения веро5 ятностей , ячейки блоков 4.1,...,,4,k памяти должны содержать т+1 разрядов, В таблс 3 нре.дставлены значения четырех разрядных кодов вероятностей О.,., получети ьгх в эезультате кодироваtO ПИЯ еодерйммого табл. 2.

Если для построе тия блоков 4 ,1, , . ., 4 .k памяти исполт:|3у1отся интегральные схемрл типа (155РУ2,, то приведен.ные в табл. 3 значения дов необходимо проинвертироззать перед записью в ячейки, так как в тход- ной каскад эт лх интегральных схем является и:ивертиру7опг1г. Младшему правому разряд у кода вероятности соот- ветству :Т G утса.з пнной ин7 егральт- ой схекгз.В начальный момент , до прихода первого трактующего сигнала от блока 1 . триг1 .р 9 для определе - ности па: содится в нь левом сосм -оянни, регистр 12 датчика 3 равномерно распределенных случаГнгых чисел - в произвольном еостоянии, выходной регистр 2 памяти для стределепности 30 }- нулевом состоянии.

25

5

0

5

0

5

Генератор 8 вг.грабатывает на своем В1мходе нев:рерь:вну1о последовательность сигна.чов со скважнсстыо два, которые гфеобразукггся н два сдвинутых по фазе сигнала со скважностью четыре счч.ма.смых с зькодов ло.гич ЗС. элеь)е;1тов и 10 ; 11, Преобразова- ч.ие ос .у1 ествляетс.я пп.и номоип-т счетного тт.1иггера 9, обесвечизаюцтего ком- мута.и, каждого очередног-о сигнала генератора 8 на. одкн из вьпсодо.в блока 1 ,

Сип ал с первого выхода блока 1.т.1П.-и.;иирует работу 3 ра.вномер но ра.с.пределе.чных чисел. При этом регистр 12 т енератора. М гтоследова- тельнсстей осуществляеч кольцевой с;двиг и.11форман,и.И5 заггнеапной j;a нем. Нелщу з.яачениями 13-го и 31-го разрядов указанн.ого регистра выполняется логическая операция MCiaiKMAIOlliEE ИЛИ при n.,H элемента 13, результат записыва ется з первый разряд регистра 12.,

Сигнал с второго выхода блока 1 управления осуществляет запись номера следующего состояния 5р, сформированного поразрядно на выходах преобразователей 5 код-вероятность в выходной регистр 2 паняти. Один такт работы устройства сострит из двух тактов генератора 8 тактирующих сиг- Ьалов.

Пусть в некоторый момент времени выходной регистр 2 памяти содержит номер (Ь| , bj, ,. . . ,Ь|) , т.е. моделируемый, .процесс находится в состоянии S. При выходе из блока 1 управления очередного тактирующего сигнала датчик 3 равномерно распределенных случайных чисел вырабатывает на группах 1 .2,.. ., k выходов т-разрядных чисел (в примере - три тре :разрядных числа) .Значение вероятности каждого числа

равно 2

Калодое из указанных случайных чисел поступает через соответствующие вторые группы входов преобразователей 5,1,,..,5.k на вторые группы входов т разрядных сумматоров 6.

Номер (Ь, ,Ь,,. .. ,Ь) состояния S; поступает на соответствующие адресные входы всех блоков A.1,...,4.k памяти, обеспечивая конкретизацию условия выборки номера столбца матрицы А . При этом из блока А.1 памяти происходит считывание ячейки, определяемой номером состояния S;, содержимое которой является кодом вероятности 2d,.+ ,; появления логической 1 в разряде Ь, номера следующего состояния Sg.

Если элемент - указанного кода вероятности равен логической 1, то на выходе преобразователя 5,1 код-вероятность произойдет установка логической 1 с ве роятностью достоверного события a,j 1, обеспечиваемое логическим элементом ИЛИ 7, независимо от состояния выхода переноса сумматора 6. В противном случае, когда О, сумматор 6 осуществляет арифметическое сложение значения с га-.раз- рядным двоичном числом и на выходе переноса сумматора 6 появляется значение разряда Ь| с вероятностью появления логической 1 , которое

через логический элемент ИЛИ .7 поступает на выход преобразователя 5.1 код-вероятность. Таким образом, обеспечивается формирование значения разряда Ь( номера состояния Sg с вероятностью появления логической 1, лежащей в диапазоне 0.,.1 включительно Использование известного преобразователя код-вероятность, состоящего

только из сумматора, не позволяет перекрыть указанный диапазон значений вероятности логической 1, так как при этом максимальная величина вероятности ограничена значением

1 .

fO

По окончании формирования полученное значение разряда Ъ поступает на соответствую1цие адресные входы

всех следующих блоков 4.2,,.. ,4.k памяти, что обеспечивает конкретизацию дополнительного условия выборки адресов ячеек этих блоков в зависимости от конкретного значения разряда Ь.. Эти условия становятся полностью определенньми только для бло- ка 4.2 памяти, у которого иъшется всего один дополнительный адресный

вход условия реализации значения т предшествующего разряда Ь, . Из блока 4.2 памяти происходит считывание ячейки, определенной номером состояния S; и сформированным стохастическим значением разряда Ь, , содержимое которой является кодом условной вероятности 2(,.+ р,) появления логической 1 в разряде Ь номера состояния SP. Код вероятности поступает

на первую группу входов преобразо- вателя 5.2 код-вероятность, которьй осуществляет стохастическое формирование значения разряда Ь номера состояния So. Процесс формирования значения разряда Ъ аналогичен изложенному процессу формирования значенргя разряда Ь,.

Таким образом, процесс 4)ормирования номера состояния развивается последовательно по направлению от старшего разряда Ь|. к младшему bj асинхронно, так как время установки значения каждого разряда Ь: зависит

только от времени чтения блоков 4.1 4 . 1,... ,4 . j памяти и задержки преобразователей 5.1,..., 5.k код-вероятность соответствуюп1;их предшествующих разрядов Ь| ,...,bj. При этом

на первую группу входов преобразователя 5.k код-вероятность поступает код вероятности появления логической 1 в разряде Ъ, считываемой из ячейки блока 4.k памяти, адрес которого определен номером состояния 5 и сформированными значениями всех предшествующих разрядов Ь ,...,Ь,, номера состояния Sg. На выходе преобразователя 5.k код-вероятность устанавливается стохастическое значе- 5ше. разряда bj,

Сформ Ерозанное значение номера (Ь. ,.,-. ,b),.)jj состоя -пш S ( записывается на В1 1ходт1ой регистр 2 памяти при помощи трактиру.ющего сигнала поступающего с второго блока I т; поступает на вглход генератора, запертая процесс перехода моделируемого мар

ковского процесса из состоя и.я S| в состо.япие Sg с задаппотт вероятностью Р . Полученное значение номера (Ь J 5 5 Ь|-)р состояния SP поступает на адресные входы блоков А о 1, , .., 4 ,k памяти, обеспечивая под-готовку перехода проп,есса в следующем такте из состояния S,-, в некоторое состоя -п-те S: . с вероятностью Р„ определяемое новым значением случайных чисел, поступающих с rpyrni выходов датчика 3 равномерно расп.реде

.пе.П1ы.х случайных чисел и код.ов веро- йтностей .появления логическо.й 1 з калсдом разряде (Ь ,,. , „ Ъ,/) , счи.тывае- мых из соответствующих я чеек блоков 4.1, с.,4/л памяти па соответствующие входы преобразователей . 3,1,,,,, ,4,k код-веро-ятность и ТоД.

Таким образом, нроисходтгг моделирование случайного марковского процесса с конечн:/им числом состояний п.

Суммарный объем памяти группы блоков 4.1.0,о,4,k памяти, в которые записаны коды вероятностей,, соответст -. вуюпще элементам матрицы А /д - п () (m-s- t) . бит, (Зб ьем матричной памяти, в кот орую заниса-нь; элементы матрицы В предлгггаемог о устро11ства,

т - о П

составляет V г . П--1 ,. J. т+ ,4.k памяти Уд V,

Наибольший эффект от примен еи.ия предлагаемого генератора случайн.ого марковского процесса досттггается в системах задаваемых стохасти шским матрицам переходов, значе и-1я вероятностей пере.ходоз которых ле л;ат в тяи- рокск дпапазоне чисел н:а отрезке

(О, 0,1) у Тов при СИЛЬНО ОТ::(ЛОНе1-П1И

раснр; деленяя веролткостей Е строках матрицы Р от равномернот о. Так, нап- piiMep, в случае, когда m - 10 н

при -,

log,,n

блоков 4.1,

log п. Поэтому суммарньгй объем

VB 2 logoii

m 8, что соответствует процессу моделирования потока случайньк микрокоманд микропроцессора, относительное сокращение объема памяти составляет

VB 2 logoii

Уд (n-1)(m+1)

зависит от in показательно нейно.

т- 40,

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

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

0

5

НИН, он содержит группу блоков па- 5 -мяти и группу преобразователей код- вероятность, выходы которых соединены с выходами соответстБ тощ1-гх: разрядов регистров памяти ..выход которого соединен с первьп-ш адресными вхо- да№-1 блоков памяти группы, выходцы которых соединены с вход,а:-1И задания вероятности соотватствующи;;;: преобразователей 1.од вероятность групшз, информацио И1ые входы которых подклю- чепы к выходам датчика равномерно }:)а.спределенн 11х случайных чисел со- ответственно/ выход j-ro лреобразова- теля код-вероятность (, , k - число блоков памяти в группе) соединен с (j-J-l)-bM адоесным входом , начиная с (j + O-ro, блоков памяти, группы.

2„ Генератор по п, 1,, от л и - ч а ю щ н и с я тем, что ка;кдый пре- образо.ватель код-;веро.гп ность содер- элемент ИЛИ и с у -:маторз выход гге- реноса которог о соединен с первым входом элемента ШБ-,, второй вход которого совместно с .нервьы входом сум- ьзатора является yr;paвляюlo fм входом преобразо.вателя, информационньм входом которого является второй вход суьшатора, - выход элемента ИЛИ является выходом преобразователя.

0

5

0

11

1278842

12 Таблица 1

О

О

1/8

3/8

3/8

О

О

5/8

7/8

О

1/8

О

О

О

О

О

/8

/8 -

о о

3/8

1/8

О

2/8

О

О

О

3/8

О

О

1/8

О

1/8

3/8

О

О

О

О

1/8

О

7/8

О

1/8

О

О

3/8

О

3/8

О

О

о

5/8

О

1/8

О

3/8

О

О

Таблица 2

1/8 О 1 1 О о о

1 о

5/8

О

О

о 1

1/2

1/4

1

О

1

О

1/4

1/4 1/2 О О

о

1/2 О

3/4 1 1 О

1 о

1/2

1 О

о о о

7/8 О

3/8

О

О

О

О

о

о

Таблица 3

Фиг. 2

fpus. 6

On, If

Состаивтель A. Кардсов Редактор Л. Гратилло Техред в.Кадар Корректор И. Муска

Заказ 6839/47Тираж 671 Подписное

ВНИИШ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

HaZ

Фиг.Л

Изобретение относится к области автоматики и вычислительной техники и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов. Цель изобретения - упрощение генератора. Генератор содержит блок 1 управления, выходной регистр 2 памяти, датчик 3 равномерно распределенных случайных чисел, группу блоf.f Ч.2 tt.K ков преобразователей 5 код-вероятность. Вместе с очередным тактовым сигналом блока 1 управления датчик 3 вырабатывает km-разрядных случайных чисел, поступающих на вторые входы преобразователей 5.-Номер текущего состояния марковского процесса поступает с выхода регистра 3 на группы адресных входов всех блоков 4 памяти. Из блока 4.1 считывается код вероятности первого бита номера нового состояния процесса и поступает на первую группу входов преобразователя 5.2, на выходе которого формируется значение этого бита, которое поступает на адресные входы блоков 4.2,...,4.k памяти. Код вероятности второго бита поступает с выхода блока 4.2 памяти на группу входов преобразователя 5.2 и т.д.. Процесс продолжается асинхронно, последовательно, поразрядно-и завершается после формирования k-ro бита записью номера нового состояния в регистр 2. 1 з.п. ф-лы, 4 ил. 3 табл, 5/«б Л дмад ю 00 00 4 to J gJ