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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области автоматики и вычислительной техники и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов. Цель изобретения - упрощение генератора. Генератор содержит блок 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

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

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

РЕСПУБЛИК (50 4 G 06 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3891195/24 — 24 (22) 18.05.85 (46) 23.12.86. Бюл. Р 47 (71) Кишиневский политехнический институт им. С. Лазо (72) В.И. Борщевич, И.Ф. Клисторин, В.Д. Жданов и В.В. Сидоренко (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 1051538, кл. С 06 F 7/58, 1982.

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

В 1070548, кл, С 06 F 7/58, 1982. (54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО ПРОЦЕССА (57) Изобретение относится к области автоматики и вычислительной техники и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов. Цель изобретения — упрощение генератора. Генератор содержит блок 1 управления, выходной регистр

2 памяти, датчик 3 равномерно распределенных случайных чисел, группу бло.„Я0„„ 278842 А ков преобразователей 5 код-вероятность. Вместе с очередным тактовым сигналом блока 1 управления датчик

3 вырабатывает km-разрядных случайных чисел, поступающих на вторые входы преобразователей 5. Номер текущего состояния марковского процесса поступает с выхода регистра на группы адресных входов всех блоков 4 памяти. Из блока 4.1 считывается код вероятности первого бита номера нового состояния процесса и поступает на первую группу входов преобразователя 5.2, на выходе которого формируется значение этого бита, которое поступает на адресные входы блоков 4.2,...,4.k памяти. Код вероятности второго бита поступает с выхода блока 4,2 памяти на группу входов преобразователя 5.2 и т.д..

Процесс продолжается асинхронно, последовательно, поразрядно и завершается после формирования k-го бита записью номера нового состояния в регистр 2. 1 з.п. ф-лы, 4 ил. 3 табл.

1278842

Изобретение относится к области автоматики и вычислительной техники и мажет быть использована для моделиРаваНИЯ ОДНОРОДНЫХ МСРКОБСКИХ т?РОцессов а такке I> качестве с«ецналнз> ровакнога стс)хастическога генератора тccTQI>btx Iloc>lt äo?çBTåëbïocòå> t команд и операндов Б составе систем стохастическаго функциональног0 контроля дискретных обьектав, включая микропроцессорные, Цель изобретения — упрощение генератора.

На фиг. изображена структурная схема генератора случайного марковского процесса; на фиг. 2 — структур-. ная схема пре1>бразава ? еля .Iort !; po-

SrT?iQC1 Ь > EtB. )JII 3 Э >»Е?СТ?»>>ЧГ- foltSI

СХЕМа ГЕПЕРатаРа СЛУ)?айКС)ГО ??ВР!»1)ГЗСKo1 o > роцесса;, HB t>)tf1", 4 — элс?;гртическая схема преобразователя кад-вероятность, ГенepBTDp случайного марковского процесса содержит блок 1 синхронизации, регистр 2 памяти, датчик 3 равкамер??о распределенных случайкьгх чисел„ группу блоков 4.!,...„4.1с памяти, группу преобразователей 5.1, 5» 1 о ) k кад Бе>»Оятнас гь

1(а>?сды>1 пре образ окате.,(J> э ко ц-Håроя1 1?ОСTJ> 1 pgfrrfb? ")» 1, »,... 5 !с (0>иг" . 2) со>те1 >! f! сумматор б и элемент 1ШИ 7.

1B?IBPBTo1) слУчаtffror 0 t >BPI3c?гого

ПРОЦЕССа, ИМЕ?ОЩЕГО БОС.С.МЬ СОСТОЯ>НК!й, может быгь изготовлен па схемам, при.веденным на фиг. 3 — 5.

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

10 и 11.

/(с?тч?!>с 3 равномерно распределенньгх случайных чисел coffe?i>lect регистр

12 с.двига с цепь?о Обратной связи, СфОРМИРОВа??НОЙ IIУ»1 e?»r I»»rtlQS>rt<-.??т!К лог-ическойй операции ИСКЛ!11>т1Я!. :!Цй", I, I>l над его 13-м и 3 !-Ь? рс!31!Яда?.?и г?р?! помощи элемента 13 11СКПН?Ъ>1С?1ЦЕГ 1!г1г1, выход которого соединен с информационным входом первого разряда регистра

12 сдвига.

Генератор работает с.т>едующ>п? образом.

Пусть 3B>IBEI мар?сапски?? провfBcс р описываемый конечным множеством состояний S = 1 S;) i = О, и — 1 и стахастическай матрипей переходон Р !! Р (, где Р;р — вероятность пере)3

Хоца За ОДИН ТБКТ ИЗ Cot- ÒÎË???»»>I ») i) —

Б са-.таян??е S 1 1 =-0 и-1 к 2 Р, =

1 . f- 1P — I

»

1;11;-,;ттам.,- состоянию S; >,еш Ма»кока

С ави> CSI Б С Оатт;Етс Тт>ИЕ >К-PBЗРЯДКОС цкаитп?ае !!тс>!ст (т|,!" Б» со с 0>I?t>»тт (>)

1) ... Ь,) >. 1») Я О),) Ь i CTBp шии разряд числа Из чиспавой последовательности О, 1,29 и — 1. 1<0>жчества разряцов (бит) необходимое

p)IrsJ представления ка)кдого из номеров состояний S; . ..,$ „ цепи Маркова, 1с = 1>ор;.и. 2

Выходной рег?"..C.òð Z памяти име>оший 1 1»а зря,"ОБ п1)едка 3 И»)тт»>н дг>?т хранения нал!ера текущег0 состоя?lия цепи Маркова, ягля;ои1егас>: адков;)еме ilo адресом ячейки блока 4.1 памяти и старшей !нетью адреса ячеек бло>сов

2(? 4 ° 2, a „..,,4, ) . п»1мя Ги,:-lеабхаДимоl o ДлЯ с!)о!р>1!Н»овани>1 номера случайного состояния цепи Маркова. 1(аличество преобразователей 5 код-вероятность, кегабходимае для ?rcс гроекия геператopB, 25 !.> ав но 1с, Марковский процесс следует pacci>B .Тривать как паследавателькост?. реB>IH3 BI>HA с".>!учаннь>>» 3аг?искл>ых с)lо.ккых событйй переходаБ ?? од?!с ИЗ састояQI? " > ) ний S- --0 H-1 113 сат t Qst>IH>r . 3 с

" ч С»?г) Впт»?1!И !3 CDQR 1 НОСТ 11» 1» За а ?>>?»>?1!)Г

> -01! сг> j)of t)ò! т Р ... „, 1.!ат>1)и?ть>

>t: DB>JrQäQ>3 1. I)0pi >Ip0>B>trIе кал!ер.. следу?ощего состояния мажет осуществлятьсsr ItopB3ps.-.rq»Q и тогда упал!Янутае

35 сложное сабьггпе может быть ирецставлОБО !сак сОБОкуппаст?> элем»ентаркь?х

CQЙЫТИ1! (II)Op1!>?раБа>?и » НаЧЕНИЯ IСаждО

Г О PBBP>I>.JB Ь, т 1 t?Q! !CPB (» t > Ь,» > a a

Ь ) g следу>ощего события S!) в зависимости как от камера текущего события

»1?1 >Ьд ) à a a»!»> ) > 1аlс и ат 1»Еализс>ции случайнагс процесса о)ар>!»?рава??ия зкачс)пт!Й Бс< >1 pBBpHДОБ {1) < > >> I), ) предше< тву>оших (I+ I ) "-му разряду. 11ап5 равлен>?е fopBÇpslt>íàãо формирования от стаушего PII3P,sl,)tB Ь, к !снацшемУ 1?к Хак как старший разряд Ь, ке имеет г!1>едшествующего разряда „д>?я него двойная зависимость выражается Б одиночную (только ог номера i текущего

СОС 10ЯНИЯ S>)»

При перехода к упомянутьгм элементарн?»!и cQ(7>i> f bIsrt1 ткеобхаДН? !О C 1 Qil»tcTII ческую матр>!Ду Переходов Р прсабразоЗатЬ Б СтакаСТГ!ЕС>СУ?О Л!С>ТР?!>ЗУ Л

Зкат?ЕК??й УСЛОВНЫХ БЕРОЯТНаСТЕй Па?!?>ЛЕНИН >IOI Hт>ЕСIСОЙ 1 H « )с1ЗБя>>С»

Ь „, HOW=I>B састаян>?я S1) Б 3;>B>rcH7278842

30 мости от номера текущего состояния

S и логических значений предшеству» ющих старших разрядов (Ь,,...,Ь )} .

Столбец А, матрицы А //а,//, d=1,2 — 1, = О,п-1 соответствует состоянию

S; и формируется путем преобразования строки P" исходной матрицы пере»» ходов P.

При этом элемент а стобца А; !

» содержит значение вероятности появле- 10 ния логической "1" в старшем разряде

Ь, номера состояния Sg.

Элементы а, и а>, содержат значения условных вероятностей появления логической "1" вб втором раз- 15 ряде b номера состояния S< при условии, что разряд bi принял значение логических "0" и "1" соответственно.

Элементы а 7,...,а j+1, ° содержат значения условных вероятностей появ- 2О ления логической "1" в разряде Ь„, номера состояния S}I. Их количество равно 2", Суммарное количество элеК ментов столбца А составляет 2 -1.

Для получения значения элемента 25 а необходимо строку Р,. матрицы Р

»» 1 разделить на две половины: нулевую

Р„,...,P, и единичную Р;,...,P

Тогда а — — P — сумма вероятносе е=П

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

Для получения значения элемента а, необходимо полученную ранее ну » левую половину разделить снова на две половины: нулевую Р,,} »», 35

I и единичную Р »» .., .Р; п

Тогда

»» — -»

fl — -1 г г с7„=2: 7 ;Е -,Е

»»

Для получения значения а необ3» ходимо полученную ранее для а, единичную половину также разделить на две половины: нулевую }; °,,P;3 „, 1 ò2 и единичную P.g,...,P„„, . 45

"а

Тогда

»»-» n-i

,е ;е е=- „. е -

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

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

После преобразования указанной матрицы P получена матрица А условных вероятностей появления логической

"1" в каждом разряде Ь номера кажJ дого состояния S, которая представлена в табл. 2.

Блок 4.1 памяти предназначен для хранения значений кодов условных вероятностей появления логической 1» в старшем разряде Ь, номера состояния. Число ячеек блока 4.1 памяти к равно числу столбцов 2 матрицы А, причем содержимое ячеек, расположенных последовательно по адресам, 0,1,...,n-7, соответствует значениям элементов й,,...,0„„ „,строки А< этой матрицы. Выбор ячеек осуществляется при помощи адресных входов, подключенных к выходу выходного регистра 2 памяти.

Содержимому ячеек блока 4.2 памяти соответствуют значения элементов строк А2 и АЗ матрицы »», задающие значения условных вероятностей логической "1" в следующем, младшем разряде Ь номера состояния. Для обеспечения выбора одной из строк

А2 и ЛЗ блок 4.2 памяти содержит дополнительный адресный вход, подключенный к выходу преобразователя 5.1 код-вероятность, при помощи которого учитывается текущее значение разряда

Ь, (условие) формируемого номера состояния S .

Содержимому ячеек блока 4.3 памяти соответствуют значения элементов строк А4, А5, Аб, А7 матрицы А, saдающие значения условных вероятностей появления логической "1" в разряде Ь номера состояния. Для обеспечения выбора одной из укаэанных строк блок 4.3 содержит два дополнительных адресных входа, подключен.ных к выходам преобразователей 5.1 и

5.2 код-вероятность, при помощи которых учитываются текущие значения разрядов Ь » и Ь формируемого номера состояния SI».

Содержимому ячеек блока 4 (j+1) памяти соответствуют элементы строк

А,...,A i » задающие значения условных вероятностей появления логической "1" в разряде Ь +< номера состояния, Для обеспечения выбора одной из указанный строк блок 4.()+1) со1278842 дет)7(<ттт 1 допол}73<те<(7>}Гь>х а<угре<.ньтх

Входов, !70д}<Г(!О -УРнJIbJx к выходам Ilpp образ(изателей 5. 1... 5 Ä I код — тзероЯТТIОСТЬ !rPI(ПОМО(К!У J(OT(>PЬ>Х УЧИТЫ

Ба(ОТСЯ ТЕКтГ(!73(Р Hf(a(JBSIIISI !>аЗТ)ЯДОВ

f(),..., !); (!>07)мируемого номера coc " тояния SII

Д}тя обеспечения выбора Ячеек блоков 4 „2... (7, k па!(я ГТ(, соо}ч)етствукщих номеру столбц» матрит(зы А, груп- 10 пы cT(71)JUJ>х H(()7 ccTIJs>x !3<071<) l) У(ТОЛ(Я}3)г (° > I;>T< (> 77 >!:lr r<(Г>7 (. 7P >TT> Ere>rf-:

T."(с(вklttf:!MT(!)а .т)ядами >M(7(юг("> СО бр>Т И ПОДкл}Оче J!bl 7< -QÎTB -"1 c ГБ>7(О(ц}(7 (рл з рядам

Bb1x о/та:(}е тхо(.(}IQ CQ рc.l" > (C. Гт>а 2 г(ак(яти, 1.7

37(ot>BTJ!т«(\ЛР> (e>(TC! (> О, т ° tа .ТТ)7 ТЛ.I с< ( з 3.!Тпс ьrB;>f(>тс я Б я J(3((Iс па>.ЯТН 7; -:,ilгrr„ f(or,-r()B упр а »с (Е } > И Тг) ) Е Г> б 7 Л 3 Г> Л -Т ГЕ> Т с (,:,, 5 1С

}. Кот(!)>i.. е <>>(7777((tp>)>ОТ 20

ЛОТ"31>ТЕСКТ((- > l JTH -TPТ>3(Я PH B)» т> ;0 «> » >,, o > <7

H0>tep С. (Е «г»ЮГ Е> 0 Р Ог Г05<Н}тст Sj: «>ар

КО>< 1< ОГ() > Г) ОЦЕС (Л С },P)7 0(> 0 > «> C! ЯМИ, за . H ьа Яl T t > т))иней (7 .:.(3-(7>i>. -3>>Л 7< !r :ТттОС"2.>

TCH C(g, OC)rI((e(.Т>3ЛЯЕТСЯ ИСК(ОДЯ 11 3 COC (а,„

Гояпия r. =- -"= — "--- .1 -(,<) . где (!.

Щ " p, > 3 (>Я(Öor- if(Ц(3(3 »7>(>7>Г>(7, С(Е т<>Т TJO „ с> т!р)!!<}((Я<а!О(>(ое з (Ге(Г(3 п(ьт 0... 27!! I nl .>()

-"ада("(, Пre()" г(37(>У!О:! 0 3}0<- 1 } j-???? (7(7>7HHC)I

BHHHSI 7(Р,»," . <=р< >. 7((>(Т >з > )!;(137;)r!О / 2 70 .5

C7P,EIOPHЗ P5I >) l lQ(, т >30ИЧ>! OP

<т (ЗНаСТЕТ!I((J (> l QP > ((! () Г((>P Гт(3>(с> \7 i Cfr СJ0>(>ттrt !>С> )Л >С)3((1, ., C.C Tu> (7 Л =»

Т, P . „1<ОЯБТГЕ}1((0, toi«! (Ес <С>(> 73 7(ЕКО тором рл,. ряде 7>„ Дс (7!(lro б ТГ>.;(o .ТO(1

i!Br t>bt7t г:Qiii !TH< л<, >Т, > 1 —..: <) (С;Пт

>r »

<3(>, с ., Т „e, (ro< 7,>(С!Г((JJ(>!Ч(т< Сi(Отт . > Т >ря((- г>олг((>С> б;,> I >, Br роя B !0< .т > (ЫМ «(0

JJ3&I !1!: B0 .b!r0:.".:.! J(U f (.((>с>,.г ЗТО>М Ci > --: О, 0 >

СЛЕДО f3 a Г(. ..>1> 7!O И (V =- (3 ) (.057>JTTIBТс>,,>

31(аЧР}7> Я 7 > 3 (1711(С>>(3(за((» (Я " Л!Т>сТ,(У}(337! f

17аЗРЯЦ 1(C7TJH Б<(PОЯТ!(QCTH „„-! ГÎ Зн(1>(Ение, !(ода О LBT (oc нл и T>>l >«Tý г))у>77(у тз;.0-,45

НОБ ПТ)c>o.>!)H 3< >3«}т:- п<т ), 1 7; >г<- >3PPr) l Г.IIOCTT> .ГОЛ)КН<7 ПО(1 УП<1 Ь 7((сl (3ТО<)ОЙ

ВХОД ЛОГИ>(ЕСТ<О("О =JI(}JJBJTТ-!. Г!!1>с! ((, ОбЕСОС>!3CП<Ес7Ь153«аЯ pPr>гПт53ЬТ>тПЮ >70 "< C,;>:,. Р}(г» 0

СОбнтля (У Г, >); ) --: I ff>ff (7«т, —; f П .30

"с< с .7 oi Lcт. ((тс.

Й> - (l (.,ir! J(сс(О>т<1; re n! !)Л Зпя T(<>i3 >7<7<, TP ((5(1)H » 751 » л .4 (, тс(>тг)» 3 (> P05) т но<- -;7>;c>((» (T "

З>>(О (CS 77)TSI Зс> ПИСИ Зна Tef>7>5< i> „ i, >7аа "«> г г

PSIrlb! S(0ТО)7(i1 C> (7>а ОДИН .).)

7)аЗРЯ>Т (!J(33ТОI <У ЗН -JCT" Уl>НО

)7<а(ОТСГт (l а 2 ) Зна чени 3 ГОЙ ч сlс ти кода поступает на первую группу входов тй-разряцного д}зоич((огo сумматора 6 преобразователя 5 код-вероятность. У)у(я Tco}(Hpoila}IHSI значения вероЯТНОСТЕЙ СТ>, ЯЧЕЙКИ бЛОКОВ Й .1,...,Ч,>с< г(( памяти дол)7(НГ>! содержать т(<+1 разрядов. В табл. 3 представлеш! значения

Ie J1Tpex разргт)7пь<х кодов вероятностей а >., полученных Б результате кодирова(< ( ииЯ с 0)Jep). ".I

Если J(375 Boc Tpoe}!3(sf блоков

А,1,...,J<.1(памяти используются ин(e1 p anBTrI1e Сзх ЬГТ>! CJ(n;3 )(1 5 5))У2 ГО приведе(п(ые:>3 таб,-. 3 значения ко«7(73 <(«}(> Так КаК ВЫХОГт,—

НоН каскад 3 1 их и lTет" >)альных схрМ яв

ЛЯЕ Т (..Я 77. -Г>3(377Т}71)у)О!Тг> Г !, (>!Пад>>}Ему П(7а7>ОМ)г PHBP5r>r) КОДа BÅ "7 )Я f TIOCTT(CÎOÒ—

БP ГСТВ ГЕТ (. (>Г К» ". "(Й ИТТТ т"77а}ТУ т >Й схемы.

77 на f8J(..»(ый л(0 «,РнГГ BT)B е>(и, Дс> т рихода первого трактующегo сигнала

От блока 1 > тригт".р 9 для QT(peqcJIBJTJ!(7CT 1(с>} ОДИ ГCLЯ B ll <(5(ЕТЗОМ COCТ05!If}77(! регистр 1? да (ика 3 равномерно распределетпп(х c,>3ó

гх Тисел — г

fPQTlH13oJiJ>I!0M сос J onnllè ВыхОДнОЙ Ре

1 и(тр 2 па! .ятli для <>пределеннОстн и Ef>JJ7ei >oM (". oi.то. тнпи, Гене )атсч 8 Бьр;блтывает па св ><.М 137>(Х.>ДГ 7}С.Т}рЕ()Ь Бг!) (О ПОСЛЕДОБатЕУ Ь

>!OCT» СИГТ(аУГО СO СК>за)КНССTI>T0 Д33а т" 0 т г)рь}г< -гт) е с>(бт)а " у Ir> (c f> Б > ,>7а СО СКТ<87(l>Îс .ТЬЮ ЧЕ

3 Ьп) Е Г (1> <,-> - тсн T X, С »75 Рlo», Г>0 Тс .(C C

Тг>ГК З;;т.-;,;С "тr>B Ьт(I0 „ j 1 . )!Т)Е()б7)ЛЗO})H(<ТТ(0("V!t С С Б,>(с(<>, r Я П l>ET >",O! >О>;Г;T C>fe <

НОГО т.»! т гет)а э. Обест!Ст< (БО(гсгО кОм

М у" т, 3 7 > 3((0 J(а )К r 0 . («(> (" Р Р P Ц 7 (С) "0 C J I I" Н аЛ сТ генератора 8 на Один пз выходов блсКс3. 1, c !Iep oò 0 выхОДа (3JIOKH 1

iT»i137ииr>)>rPт 77аботу цаi чика 3 ()авномер н() рас3 <)pд(злг>Т<ных тт)lсBJI, >(7)>l 3тс.г"Г р е т I т с т <) (2 . е (Г е р а т с (> а (1 О с 7 (cb>"< o B H

«;!»Br ":, (: 1.1 Осу }УЕР БЛЯс" i i(C>.TBJJBBC:I>

Cpi3JrOpb ацИИ, с>аТГН аннОЙ Iia Н< М, >

j rC .ÆEf7r ЗУ!> "<Риия" ((13 ГО и .. 1 0 pHH "

» цо}3 указа}и>ог<5 «егистра выполняетcsf лот ич(}ока Я Оп("р 111»Я i}CKJ! .:.)"if)IOjjIEj

3707!(1 при !(о on;,H элемента 13 резуль(H T З 71!ТТТСЬ}Б с> Е (C51 Б ПЕРВЫЙ B Ha!)HÄ регистра I2., Сигиan с Бтopuгo выхОДа бло(<а управления осуществляет запись номера следу!Ощего состояния 87, сд)ормиро}занного поразрядно на выходах пре1278842 образователей 5 код-вероятность в выходной регистр 2 памяти. Один такт работы устройства состоит из двух тактов генератора 8 тактирующих сигНалов. 5

Пусть в некоторый момент времени выходной регистр 2 памяти содержит номер (Ь,, Ь,...,Ь ), т.е. моделируемый.процесс находится в состоянии

S;. При выходе из блока 1 управления 1О очередного тактирующего сигнала датчик 3 равномерно распределенных случайных чисел вырабатывает на группах 1.2,...,k выходов m-разрядных чисел (в примере — три трехразрядных числа) . Значение вероятности каждого числа равно 2 . Каждое из указанных случайных чисел поступает через соответствующие вторые группы входов преобразователей 5.1. ..5.k на вторые 20 группы входов тп-разрядных сумматоров 6.

Номер (Ь,,Ь,...,b„) состояния Sj поступает на соответствующие адресные входы всех блоков 4.1,...,4.k

25 памяти, обеспечивая конкретизацию условия выборки номера столбца матрицы . При этом из блока 4.1 памяти происходит считывание ячейки, определяемой номером состояния S;, со- 30 держимое которой является кодом вероятности 2,.+ P, появления логической "1" в разряде Ь, номера следующего состояния S .

Если элемент 8 указанного кода вероятности равен логической "1", то на выходе преобразователя 5. 1 код-вероятность произойдет установка логической "1" с вероятностью достоверного события д, =1, обеспечиваемое

40 логическим элементом ИЛИ 7, независимо от состояния выхода переноса сумматора 6. В противном случае, когда

О, сумматор 6 осуществляет ариф45 метическое сложение значения с m-.ðàçрядным двоичном числом и на выходе переноса сумматора 6 появляется значение разряда Ь, с вероятностью появления логической "1" ---"-, которое

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

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

Щ с. 1 — — -- c 1, 2

По окончании формирования полученное значение разряда Ь| поступает на соответствующие адресные входы всех следующих блоков 4.2,...,4.k памяти, что обеспечивает конкретизацию дополнительного условия выборки адресов ячеек этих блоков в зависимости от конкретного значения разряда Ь . Эти условия становятся полностью определенными только для блока 4.2 памяти, у которого имеется всего один дополнительный адресный вход условия реализации значения т предшествующего разряда Ь . Из блока 4.2 памяти происходит считывание ячейки, определенной номером состояния S; и сформированным стохастическим значением разряда Ь<, содержимое которой является кодом условной вероятности 2M .+ P появления логической "1" в разряде Ь номера состоа яния Яр. Код вероятности поступает на первую группу входов преобразо- „ вателя 5.2 код-вероятность, который осуществляет стохастическое формирование значения разряда Ь номера сос2 тояния S . Процесс формирования значения разряда Ь аналогичен изложен2 ному процессу формирования значения разряда Ь < .

Таким образом, процесс,формирования номера состояния развивается последовательно по направлению от старшего разряда Ь к младшему Ь асинхронно, так как время установки значения каждого разряда b„« зависит только от времени чтения блоков 4.1

4.1,...,4.j памяти и задержки преобразователей 5.1,...,5.k код-вероятность соответствующих предшествующих разрядов Ь<,...,Ь . При этом на первую группу входов преобразователя 5.k код-вероятность поступает код вероятности появления логической "1" в разряде Ь„, считываемой иэ ячейки блока 4.k памяти, адрес которого определен номером состояния S; и сформированными значениями всех предшествующих разрядов Ь<,...,b„, номера состояния S . Ha выходе преобразователя 5.k код-вероятность ус1278842 таиаВЛИ13аЕтСЛ СтОХастт!ЧЕСКОЕ ЗНВЧЕние РазРлца 1)к.

Сформированное зна fell!f0 номера (13,, „,13),.)(состолнил $!) залисызается т!а зыхотт !Ой т)Р Г!!стс) 2 паи" тн fpII

ПОМОщи т1)акт!!ру10!!!ег 0 сиГнала, ПОс I y паl0!Цеl 0 с- нт01) ОГО 6JIOка I - 51 iocTУпа ет на выход I"effef)fiтора, 3ai)ef)J!f,i!if

ПРОЦЕСС ттЕРЯХОПа bfOÖP IÈÐ 0;;О-,-О МаРко!!ского процесса из ос тол!3!)л Si н 10

СОГ ГC)!fit!IÃ . Б о С Зт)па!!ЛО!! НРРОЛТЛОГТЬЮ

:Р„I . Полученное значе .!ия 1!омера (1), !3 г ) г сост0!ill!i)1 S;) пос7 у !)ЯР 73 на ац 3 C. c I:L10 i3)CC3 fi) f . . СЕ:У f)äf) КО)З

4.1,....-;.1с паилтп, обеспечивая под- 15 готонк) перехсда процесс» н следующем такте из состояния 8, г, некоторое () состс)лш!я ".,, с 13еролтнос гью 1. . °

l 3 опредeJIsfc rfo0 Itоныи з !ачением случайП(т!Х ЧИГЕJI !IОС Гттг!!ПО!!!Их С ) P))i!Il 13bl- 20 ходов датчика 8 ра!зномерно p7c It!) åäp—

1 . 1с. .Iпзь)х Глучайных ч)ссе,л Ii кoilc)н 1)c -ро

Г

ii. l1

l 1 IJOC TÐÉ ПОЛНЛР1ПIЛ ЛОГ!! !ЕС. К

4. 1,... »f „1с Itаилтl! Нв соотне ст)зующие !

ЗХОДЫ ПрсОС)ра130вта ГСЛС-И . 3, („..., Ь,1С код-вероятность и т.,ц, TGIcIIt1 О бт)а эои ) п1) О) т Г КОД!!т NOJ tcJIII» . ронанпе слу айног0 маркоззского проЦРССа С КОПЯЧПЬЦ тпlсЛОМ СOCTO)lfJiiiI П е

Суммарный объем памя г!! группы блоКоlз 4. 1 ., > ., ь ф1С IIHMJI I Ê, ь) КОТО;)ьlе Записаны коды вероятностей,, соотв т!с! НУю(!1ИР 3.:!еме!!7 а!т! Ма J PIIJJLI )3 . !! = 3

= и (и-1) (сь)-11) „бит, Объем;IITpif гной !!аилти В кот01) )ПО;.т i!itic!I!J>! -) JfCJ IC!ITbl матРН!!bl 8 НРедлагаРМОГО,»ст1)01iстнff т с) сост;;.Вллс.т Ъ =- 2 и 101 и. Ilooтому

6 т тт п1)и ---- ---.-. - : — — -- ". cyr fr!< рн..;Jf объем

1 01 ;. и !1!+1 блоков Йь. I,...,4.1с паилти 1, „- Ч„.

11а)!бо:-,frï!fili зффе!ст 0)т .!рт.;1!епе!!ил пред)тага! Мого генератора Г»лучайного

btBplc0i3cIccI о процесса до! -.т г;.:.Р.тсл

CH Terfr73f "!адат)аяг!!)Х 0 I 0)ff)С IИЧРГКт)Ь!

МНТР!!ЦН1! ПЕPÑ CÝÄOÍ Зпат Еl!ИЛ :Е: ОЛТ ностей персходон )сот0,.)"!х леж,.i.""г н !)1!!

)тСКР1 т) Па!)аз сне ч!!СГЛ I! а С i рс": Кя (0. 1) т, е, при. сильно:; t .f:,oí;r !I!-ê раси!;, .елe«f; веров;;.о ТР1"::: —.:. Строках матрицы 1- о рван,ar.ÿ1)ftoi 0 1. ак, ;апрИЫяр -„i i ттт,ттт.а; 1СГ)Гfra In = 10 И

m = 8, что соответствует процессу моделирования потока случайных микрокоманд микропроцессора, относительное сокращение объема памяти составллет т? ц, 2 lc .t-t

7)) (и-1) (lit+1)

40, так как 1? зависит от !л показательно, а 17 — ли»el!!f0 формула изобретения

1, Генератор случайного марковского процесса, содержащий блок синхронизации, регистр памяти. датчик равномерно распределенных случайных чисел, вход Опрос" которого подключен к первому выходу блока синхронизапии„ второй вь)ход которого соединен с синхропи3JIJ)yfc!I;l;и входом регистра памяти. Вьгход которого является выходом гене;)атора, о т л и ч а !о— щ и и с !? теи„ что, с цель".0 упроще-нил, он со;зержит группу блоков па.мяти и группу преобразователей коднеролтиость, нь!холы которых соединены с вьгходаии соответствующих раз1)адов рСГисl 3013 памяти,Выход которОго соединен с первыми адресными входами блоко)з !тамяти группь1, ныхоцы которых соединены с входами задания веролтнос "li conтн тстную!!!их преобразователей код-вероятность группы, информационные входы которых подключень! к выходам датчика pai)iforiepllo рас.пределенных случайных чисел соответстнезгно,,ныхэд j-го .преобразова теля кОд не-роятtlocт (1=1 r = 1c число блоков памяти н группе) соеци(j + 1 ) — bill ад-)ес1!ым 13ходои Beg# начиная с (3+1) -го, блоков памяти группы.

2. I Pily ратОр 110 If, 1, ч а и щ и и с л ".еи,, ITo каждый 1реобразователь коц — вероятность содержи г злемент ИЛ11 и "у "иатор н !ход пеРЯНОСа КОТСН)ОГО СОЕД Птяп С ПЕРВЫМ нхо цом э леионта 1ЕП1 ), нтoрoH нхОД кО тOi30ГО с0131 JPст tо (- пc= 1)lзь!и 13хОЦОII сУМ ,и!Ггopcl является управляющим входои преобразо!зателл, и!!формационным входои котс)рого является второй вход сумматора,,гзыход )леиепта ИЛИ является н!!ходом преобразователя.

1278842

Т а б л и ц а 1

5 6

0 7/8 0

0 0

1/8 1/8 3/8

3/8 0

3/8

2/8 0

3/8 3/8

Таблица 2

0 1

5 6

3/8

1/8 1

5/8 0 1 0 1 0 0

1/2 1 0

0 0

7/8 0

0 1/2 0

3/8 0

0 0

0 0

5/8 0

0 0 0 1/8 0

0 3/8 0 0 5/8

3/8 0 0 0 0

1/8 0 0 3/8 1/8

0 1/8 1/8 0 0

0 1/8 7/8 0 0

0 3/8 0 0 0

0 1/Z 1/4 3/4 1

3/4 1/4 1/2 1 0 0

1/2 0 0 0 0 0

1/4 0 1/2 0 0

1278842

Таблица 3

Адрес (А4 А3 A2)

010 011 100 101

000 001 110 111

Блок Адрес

4.1

4. 2 А1--0

А1=1

4.3 АО=О

А1=0

0000 0000 1000 0001 0000 0001 0000 0000

A0=1

A1=0

0000 0000 0000 0000 1000 0000 1110 0000

АО=О

A1=1

0000 0001 0000 0100 0000 1000 0000 0000

A0=1

0010 0001 0000 1000 0100 1100 0001 0110

0000 0000 1100 0100 1000 0001 0000 0000

0001 1010 0000 0001 0000 0001 0000 0000

0001. 0000 1000 0000 0000 0000 0000 0000

1278842

) 278842

На 2

0m

Састаивтель А. Карасов

Техред В.Кадар Корректор И. Муска

Редактор Л. Гратилло

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

ВНИИ?И Государственного комитета СССР по делам изобретений и открытий

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

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