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

 

Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов. Цель изобретения - расширение функциональных возможностей генератора за счет получения случайных процессов, описываемых стохастическими матрицами переходов, не являющимися квазиразряженными. Введение в генератор датчика 8 равновероятной двоичной цифры, двух счетчиков 7,9 и схемы сравнения 11 позволяет достигнуть поставленную цель без увеличения объема оборудования и снижения быстродействия. 2 ил.

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

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

РЕСПУБЛИК (191 (11) (504 G06 F 7 58

ВСЕСОЮЗНАЯ. 1Ей"Г il. !::,Л Б1М

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

fl0 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР. (21) 4404663/24-24 (22) 04.04.88 (46) 23.12.89. Бюл. Р 47 (71) Кишиневский политехнический институт им. С. Лазо (72) A.А. Гремальский (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 290281, кл. G 06 F 15/ЗЬ, 1969.

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

М 1453403, кл..G ОЬ Е 7/58, 1987. (54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО

ПРОЦЕССА (57) Изобретение относится к автома2 тике и вычислительной технике и может

\ использоваться для генерации входных. последовательностей при стохастичесI ком контроле дискретных объектов.

Цель изобретения — расширение функциональных возможностей генератора за счет получения случайных процессов, описываемых стохастическими матрицами переходов, не являющимися квазиразряженными. Введение в генератор датчика 8 равновероятной двоичной цифры, двух счетчиков 7,9 и схемы сравнения

11 позволяет достигнуть поставленную цель без увеличения объема оборудования и снижения быстродействия. 2 ил.

3 1531093 4

Изобрете111e относится к автоматике н вья исли ель»ой технике и может испо.1ь зо в атьс н лля ге»ер ации входных г1оследовлте11ьностей при стохастическем «оптроле дискретных обьектов, ll-:1h Hэ0 ретеяин — расширение функциональных возможностей генератора .1л сч:" получения случайных процес. .)» описываемых стохлстическими мат- 10 р11цлми перс.,оров. не являющимися ква3111);1З Р Я:Д(Е1Ш ЫМ11 .

Ил фиг. l редставленл структурная схемл венер торн; нл фиг. 2 — блоксхема лггопитмл работы блока управле- 15

»11Я .

Ге»оратор случайного марковского процсссл с1«:. 1!),111 11еряый счетчик 1, . 1ок 2 плмнти, блок 3 памяти, блок 4 плмяти, генерл1ор 5 равномерно рас

1 1) i".>1еле ни»1х чисел „первую схему 6 сравнения, »торой счетчик I, датчик рав новероятной двоичной цифры, тре. тий счет ик 9. 0.11ок 1О управления, )тop„-.î схема 1 { срлвне»ия. !

>локи 2 — 1 памяти предназначены ,111» xpat«»11я в сжатой форме стохастической 11;.fðHöû переходов.

Блок 10 управления предназначен для реализации алгоритма работы генератора и определяется блок-схемой алгоритма (11)иг. 2) . Блок 10 управления пред<.танлчет собой управляющий автомат с сос он»иями а,, а,...,лв, л

Б состоянии л< блок 10 управления ныдле1 сигналы "Прием" в счетчик 1„ "13.ск" генератора 5.

Б сос" îÿíèè л„ блок 10 управления выдле " сигналы "Прием" в счетчик 7, + 1 в c ÷e f ÷èê 1 .

Б состоянии л блок 10 управления выдает сигнал "+1" в счетчик 7.

Б состоянии л блок 10 управления выдает сигнал "Прием" в счетчик 9, Б состо) нии л блок 10 управления выдает сигналы "+ 1" в счетчик 9, нОпрос датчика {я.

Б coc тоя»HH лЬ блОк 10 упрлвл!= HHH выдает сигн л "1-1" в счетчик 7.

Б состоянии л., блок 10 управления выдает с11гнлл "С{)рос счетчика 7, Схема 11 сра.. нения предназначена лл.! срлв11е11ия чисел, поступающих из блока 3 плмят1 и с выхода счетчика 9

Схема 11 сравнення вырлбатывлет приз

II I! iII

»ак =;и! бо

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

Пусть злдл Марков! кий процесс, описывлемый1 конечным множество! состояний S = з {, i = О, п-1 и стохастической млтрицей переходов P

= j(p, ((, где р, — вероятность перехода из состояния s; н состояние s

- III

i, j = 0, и-1; 1 ;, = о, ° 2; ое, — целое; m — параметр, олредел)яющий точность представления элементов матриЦЬ1 ° !

1л1рицл P хранится в сжатом ниде в виде векторов Ц = II с{„ II К = (I r {{

Т = 1{г ((Бе«горы (), К и Т получаются следующим образом.

Устанавливаем q р = О. Сжимаем строку р, матрицы Р. Дяя этого в о строке р„ выделяем подстроки р,, ро, р„,... из последовательно распо-, ложенных один за другим одинаковых элементов. Просматривл, строку р о слева направо, в координаты г,, т,...,Г Г{р с ... векторОв К и.Т последов лтельно выписывают: в координату т — индекс Е столбца к к. последнего элемента подстроки р р н координату rk сумму всех элементов строки р„- от р до р „, т.е.

b величину р .о Ч

Пусть при сжатии строки р в К и о

Т выписаны по (эр значений, где /3,— число подстрок н строке р, Устанлво ливаем q;

Аналогично р сжимаем строку р и в векторах К и Т выписываем соответствующ11е значения. Пусть 1 — число подстрок строки р(°

Устанавливаем q = q{ + p, .

Аналогичным образом сжимаем строки !,г),),...,р„1 определяя значения коор-! д"нат ъ +Р ° (),"{l +! l .. yrpeip+pit

rp.hp+р, гь р,,, +В а так — {Ъ Ф {, у { .) {,+ ° 1 ° э "{ )о+ {3, + { )

p o+{l,t h) +! l ° ° ° l r p)o+ (Ъ,+, ...,1 ()и °

Пр! этОм !-,ъ q 2 + 12

Ц,, = (+

° ° ° ° ° Ф ° ° ° ° ° °

Ч „., = Ч и- ). + 9 !)-а

Бектор Ц загружается в блок 4 памяти, вектор К вЂ” в блок 3 памяти, вектор Т вЂ” в блок 2 памяти, причем в память заносятся значения оС 1, где

-m с и — числители дробей вида с = р(п 2

Разрядность и число слов блоков

2 — 4 памяти определяются из следующих рассуждений.

5 15

Число координат eexropa Q равно и.

Число координ, т вектора Р и вектора

Т зависят от средней длины (T ° е ° от числа элементов) 1 подстрок вида р".

1 матрицы Р. Вектор К(Т) содержит столь ко координат, сколько подстрок вида р! можно выделить в матрице P. Число

Я. . подстрок определяется как и /1, где и — общее число элементов матрицы P.

Координачы q вектора Ц принимают г значения в диапазоне от 0 до п /1.

Следовательно, разрядность блока 4 памяти, в котором хранится вектор определяется как ) log n /1 (, где ) ( обозначает ближайшее целое в сторону увеличения.

Координаты r вектора К принимают значения от 0 до п-1. Следовательно, разрядность блока 3 памяти, в котором хранится вектор К, определяется как

) log и(.

Координаты с вектора Т имеют разрядность m.

Начальное состояние S цепи Маркова задается следующим образом.

В счетчик 7 загружается код Е состояния S . При этом на выходе блока

4 памяти появляется координата q,, т.е. указатель начала строки р в блоках 2 и 3 памяти. На этом процессе загрузки исходных данных завершен.

Работа генератора сводится к реализации алгоритма управления (фиг. 2)

С приходом на управляющий вход генератора сигнала "Пуск" блок 10 управления переходит в состояние а< и вырабатывает управляющие сигналы

"Прием" в счетчик 1, "Опрос" датчика

5 равномерно распределенных случайных чисел. !

Сигнал поступает на стробирующий выход генератора, указывая что на его информационном выходе установлено состояние s< . При этом в счетчик 1 записывается координата qg, поступающая с выхода блока 4 памяти. Изменение содержимого счетчика 1 запускает процесс чтения из блоков 2 и 3 памя ти. На выходе блока 2 памяти появля ется координата r вектора К, т.е. индекс столбца правого элемента цео почки р, а на выходе блока 3 памяти — значение соответствующей координаты вектора Т, т, е. сумма вида,7 . р . Датчик 5 вырабатывает

q=о И

Таким образом, к моменту, когда блок 10 управления переходит в состояние а, в счетчике 7 находится индекс h правого элемента послепней подстроки p>, для которой х) р

Ф

$cP а на выходе блока 3 памяти — индекс

h следующей подстроки р такой, что х g, р . о

31093 6 на своем выходе некоторое случайное число х, В зависимости от признака сравнения блок управления переходит в

5, состояние а либо в состояние ат.

Допустим, что первая схема 6 сравнения выработала признак " Й ", т.е.

H х « р . Блок 10 управления пере10 1=0 ходит в состояние а и выдает сигнал

"Сброс" счетчика 7. При этом, содержимое счетчика 7 станет равным нулю, а на выходе блока 3 памяти установлен индекс h правого элемента перо подстроки . р строки р . Блок 10 управления переходит в состояние а, Допустим, что первая схема 6 сравнения выработала признак " ), т.е. случайное число х с выхода датчика

I h

5 больше, чем число р с выхоg=о да блока 2 памяти. Тогда блок 10 управления переходит в состояние а и

25 выдает управляющие сигналы "Прием" в счетчик 7 и "+1" в счетчик 1. При этом в счетчике 7 с выхода блока 3 памяти записывается индекс h правоь го элемента подстроки р, а содержимое счетчика 1 увеличивается на 1.

Изменение содержимого счетчика 1 вновь запускает процесс чтения из блоков 2 и 3 памяти. При этом на выходе блока 3 памяти появляется инl лекс h правого элемента строки р, а на выходе блока 2 памяти — значение

h р для подстроки р . Первая ч=о сЧема 6 сравнения вырабатывает приз40 нак "(" либо " " Е вырабатываh ется признак "г ", т.е. х ), р для ч=о подстроки р, блок управления опять вырабатывает управляющие сигналы

45 Прием в счетчик 7 и +1 в счетчик

1 (состояние а ) и т.д. Если же вырабатывается признак " (", блок 10 управления переходит в состояние а

1531093

В состоянии а», блок 10 управления задает сигнал "+1" в счетчик 7, увеличивая тем самым индекс h на единицу.

Блок 10 управления переходит в состоя5 ние а

Таким образом, к моменту перехода в состояние а в счетчике 7 находитф ся индекс h" столбца первого (левого)

1 элемента подстроки р, а на выходе блока 3 памяти — индекс h столбца правого (последнего) элемента подстроки р

В состоянии а блок 10 управления выдает сигнал "Прием" в счетчик 9.

При этом в счетчик 9 переписывается содержимое счетчика 7, т.е. в счетчик 9 записывается значение индекса

h первого элемента подстроки р .

Вторая схема 11 сравнения, айалиl1 эируя индекс h поступающий со счетчика 9, и индекс h поступающий с выхода блока 3 памяти, вырабатывает признак — либо э

Предположим, что вторая схема 11 сравнения выработала признак "= . то

Н значит, что h = h, т.е ° цепочка р состоит из одного элемента. Следовательно, очередным состоянием цепи

Маркова будет состояние s>. При этом блок 10 управления вновь переходит в состояние а, и выдает сигналы Прием" в счетчик 1 и "Пуск" генератора

5. Одновременно сигнал поступает на стробирующий выход генератора, указывая, что на информационном выходе генератора со счетчика 7 посту пает очередное состояние sh цепи Маркова.

Предположим, что вторая схема 11 н и 40 сравнения вырабатывает признак ф

Это означает, что h < h и следующим

II состоянием цепи Маркова будет одно из сОстОяний 8 1 »» sg" » i ° » $, » при чем указанные состояния являются рав45 новероятиыми (цепочка р состоит из одинаковых элементов). При признаке на выходе второй схемы 11 сравнения блок 10 управления переходит в состояние а ° и вырабатывает управляющие сигналы "Опрос" датчика 8 и "+1" 50 в счетчик 9. При этом на выходе датчика 8 с вероятностью 1/2 вырабатывается значение "1", а содержимое счети чика 9 становится равным h + 1.

Если выход датчика 8 равен "1", блок 10 управления переходит в состояние а и вырабатывает сигнал "+1" в б счетчик 7. Если же выход датчика 8 равен "0", увеличение содержимого счетчика 7 не выполняется. Т;.ким образом, при каждом опросе датчика 8 содержимое счетчика 7 с вероятностью

1/2 увеличивается на единицу °

После анализа выход датчика 8 и увеличения при необходимости содержимого счетчика 7 выполняется сравнение текущего содержимого счетчика 9 и выхода блока 4 памяти.

Вторая схема 11 сравнения, сравнивая содержимое счетчика 9, т.е. значение h +1, со зна4ением с выII хода блока 3 памяти, т.е. со значением h, вырабатывает признак "=" либо пСн

Если вырабатывается признак блок 10 управления переходит в состояние а, вырабатывая сигналы "Прием" в счетчик 1 и "Пуск" датчика 5. Сигнал одновременно поступает на стробирующий выход генератора, указывая, что на его информационном выходе установлен код (д следующего состояния

Бд цепи Маркова. На этом цикл выработки очередного состояния цепи Мар1 кова завершен. С состояния а блок

10 управления начинает цикл выработки следующего состояния цепи Маркова, эаписыва» в счетчик 1 значение координаты q с выхода блока 4 паМЯТИ И T,Ä, Если же вырабатывается признак блок управления вновь переходит в состояние а5, увеличивает содержимое счетчика 9 и осуществляет опрос датчика Ц. Если íà в плоде датчика 8 выработалась "1", cодержимое счетчика l увеличивается на единицу, а в противном случае остается без изменений и т.д. Таким образом, последовательный опрос датчика 8 и увеличение содержимого счетчика 7 выполняется для h,,h" + 1,...,h, При этом в счетчике 7 формируется число Q, равномерно распределенное в интервале

Н

h . ..h которое является кодом следующего состояния цепи.

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

При этом расширение функциональных возможностей достигается без увеличения объема оборудования и снижения быстродействия.! 531()93

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

I åHåðàòoð случайного маркОвского процесса, содержащий датчик равномерно распределенных случайных чисел, 5 блок управления, три блока памяти, схему сравнения и счетчик, причем вход пуска генератора соединен с входом пуска блока управления, первый логический вход которого соединен с выходом Больше схемы сравнения, первый информационный вход которой соединен с информационным выходом датчика равномерно распределенных слу,чайных чисел, вход опроса которого

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

1531093 фиа. 2

Составитель Д. Феликсон

Техред М.Ходанич Корректор М. Пожо

Редактор И. Шулла

Заказ 8028/50 Тираж,668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород,. ул. Гагарина, 101