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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для моделирования простых и сложных (r-свнзных) цепей Маркова и для генерации входных последовательностей при стохастическом контроле дискретных объектов. Цель изобретения - расширение функциональных возможностей генератора за счет введения г-связности на уровне классов эквивалентности состояний цепи Маркова. Генератор содержит блоки 3,4, 5 и 9 постоянной памяти, счетчик 1, генератор 2 случайных чисел, группу регистров 6, регистр 8, блок, 10 управления. 4 табл., 2ил. , ;. .; ... - .

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

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

РЕСПУБЛИК (я)5 G 06 F 7/58

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (2 1) 4660358/24 (22) 09.03.89 ° (46) 07.02.92. Бюл. М 5 (71) Кишиневский политехнический институт им. С.Лазо (72) A.A.Ãðåìàëüñêèé и С.М.Андроник (53) 681.3(088.8) (56) Авторское свидетельство СССР

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

Маркова. Генератор содержит блоки 3. 4, 5 и 9 постоянной памяти, счетчик 1, генератор 2 случайных чисел, группу регистров 6, регистр 8,,блок 10 управления. 4 табл., 2 ил.

1711155

20

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

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

На фиг.1 представлена структурная схема генератора; на фиг.2 — блок-схема алгоритма работы блока управления, Генератор случайного марковского процесса (фиг,1) содержит счетчик 1, управляемый генератор 2 случайных чисел, узел формирования указателей начала строк, выполненный в виде блока 3 постоянной памяти, узел формирования кодов состояний, выполненный в виде блока 4 постоянной памяти, узел формирования элементов строк, выполненный в виде блока 5 постоянной памяти, группу регистров 6,.образованную регистрами 6,1, 6.2..., 6.r, блок сравнения 7 двоичных чисел, регистр 8, узел формирования класса эквивалентности, выполненный в виде блока 9 постоянной памяти, и блок 10 управления.

Счетчик 1 предназначен для хранения и формирования адреса, по которому осуществляется обращение к блокам 5 и 4 памяти, Счетчик 1 имеет управляющие входы "1" и

"Прием".

Управляемый генератор 2 случайных чисел вырабатывает m-разрядные двоичные числа "", z = x 2; 0 z 1. Случайное число

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

Блоки 3-5 памяти предназначены для хранения в сжатой форме стохастической матрицы переходов, Считывание информации из блоков 3 — 5 памяти происходит при поступлении соответствующих адресов на их адресные входы, Группа регистров 6 предназначена для формирования и хранения последовательности классов экВиВалентнОсти длины г предшествующего сложного состояния многосвязной цепи Маркова. При этом на

-.екотором такте t в регистрах 6.1,...6.г хранится в регистре 6.1 — номер (код) класса эквивалентности, к которому принадлежит состояние цепи Маркова. генерируемое в такте (t-1); в регистре 6.2 — номер (код) класса эквивалентности. к которому принадле>кит состояние цепи Маркова, генерируемое в такте (t-2) и т.д., в регистре 6.r — номер (код) класса эквивалентности, к которому принадлежит состояние цепи Маркова, генерируемое в такте (t-r).

Разрядность каждого из регистров

6.1„,.6,r равна!О92К где k — число классов эквивалентных состояний цепи Маркова.

Прием информации в регистры 6.1, . „6.r осуществляется при поступлении на их соответствующие управляющие входы сигнала "Прием" от блока 10 управления, Выходы регистров 6.1, ..., G,r образуют адресный вход блока 3 памяти указателей начала строк, Блок 7 сравнения двоичных чисел выполняет сравнение гл-разрядных чисел, поступающих от управляющего генератора 2 случайных чисел и от блока 5 памяти элементов строк 4 вырабатывает признак" " либо

II ) N

Регистр 8 предназначен для хранения текущего состояния марковского процесса.

Запись информации в регистр 8 осуществляется по сигналу "Прием", поступающему на его управляющий вход, Блок 9 предназначен для преобразования кода состояния цепи Маркова в номер (код) клааса эквивалентности. к которому принадлежит соответствующее состояние.

Разрядность входных слов блока 9 равна

logan, где и — число состояний многосвязной цепи Маркова, а разрядность выходных слОВ logzk.

При этом число ячеек памяти равно и и в каждую из них записывается номер соответствующего класса, В зависимости от особенностей конкретного применения reнератора блок 9 можно реализовать и в виде комбинационной схемы, получаемой в соответствии с известными методами синтеза переключательных схем, Блок 10 управления предназначен для реализации алгоритма работы генератора и полностью определяется блок — схемой алгоритма (фиг.2), Блок 10 управления представляет собой управляющий автомат с состояниями а1, az, аз, а4, структура которого получается в соответствии с каноническими методами синтеза.

В состоянии а1 блок 10 управления выдает сигнал "Пуск" на управляемый генератор 2 случайных чисел, в состоянии а2 блок

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

1, в состоянии аз блок 10 управления выдает сигнал "Прием" в регистр 8 и на группу регистров 6, в состоянии а4 блок 10 управления выдает сигнал "Прием" в счетчик 1, Генератор работает следующим обра1711155

Пусть задана r-связная цепь Маркова, ИМЕЮЩаЯ П СОСтОЯНИй So, S1,..., Вл-1, И В Этай цепи для всякой последовательности состояний длины г(цепочки Ci длины r) определены.устные вероятности вида Pi!(sl/С1) где

Г

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

Во многих практически важных случаях множество состояний $ - (sl}; j - О, и-1 разбивается на классы (подмножества) эквивалентности, т.е.„

S = SoUÁ1u...uSk-: где k — число классов.

При этом сОстОЯниЯ sj u sj ЯвлЯютсЯ эквивалентными, т.е, принадлежат одному и тому же классу лишь в том случае, ес1и любая строка Сп табл.1, где Cm — цепочка, содержащая хотя бы одно вхождение зь совпадает с соответствующей строкой С1 табл.1, где C1 — цепочка, получаемая из Cm заменой s1 íà sl.

Если выполняется условие k < п, задание r-связной цепи Маркова можно минимизировать.

Для минимизации формы задания гсвязной цепи на основе табл.1 составляют табл.2„, строки которой помечен ы цепочками вида С1, l = О, k -1.

Цепочки С1 представляют собой последовательности классов эквивалентносту длины r, При этом каждой цепочке вида С соответствует множество цепочек вида (С1}!, получаемых из Ci путем перебора возможных вариантов замен! 1 каждого из классов эквивалентности 2о,,S1,..., Яп на соответствующие им состояния. Строки табл, l,ñîîòветствующие цепочкам (С1}!, совпадают.

Каждая строка Сt табл, 2 содержит условные вероятности вида Р1;(3!/(.1), причем

Р1!(з!/С1)=Рц(з!/С1), где С1 — одна из цепочек состояний иэ множества „(Ci}l,соответствующих цепочке классов С1, т.е. табл.2 получается из табл,1 путем извлечения по одной строке из каждого множества вида {Ci}l строк..Очевидно, число строк табл.2 равно k и, поскольку k < n, число

П1 строк табл.2 в (—, раз меньше. чем число

k строк табл.1.

Например в табл.3 задана двухсвязная цепь Маркова с множеством состояний S = {so, з1, s2, з3), Множество состоЯний

qo=0;

q1= No, q2 = q1+N11 чп-1 = qn-2+ Nk — 2

45 г

ГдЕ No, й1,. „МК вЂ” г — ЧИСЛО НЕНУЛЕВЫХ ЭЛЕментов строк 0.1...., k -2 матрицы P.

Перейдем от стохастической матрицы Р кматрице Р = I! Р ц I !

О,если Рц=О

Pi °, если Pi! 0. с °

Векторы R и Т получаются следующим образом.

Из матрицы P построчно выписывают в вектор R ненулевые элементы Р1!; в вектор Т— индексы столбцов j ненулевых элементов, S разбивается на k = 2 класса эквивалентности,, !о = (So, S1}:

S1= {зг, зз), 5 Минимизированная форма рассматриваемой двухсвязной цепи Маркова приведена в табл.4. При этою, цепочке классов эквивалентности Co = < So, Яо > соответствует множество цепочек состоя10 нии (Cj}o = (Со=<Заза>, С1=, C4=

= , С = <з1зг>} л

Цеоочке 6 = <оо1> соответстеувт множество (Cl}1=(C2=. С3 = <зозз>, 15 CS =<З1З2>, Cr=}. ЦЕПОЧКЕ C2 = <51Бо> соответствует множество

{Ст)2 = (С8 = <згура>, С9 = <згз1>, С12 =

= 13 = Я81 }.

Цепочке С3 = соответствует множе-20 во

{С1}3 - (C10=, C11=. С14

=, C15=).

Считая цепочки С1 текущими состояниями r-связной цепи Маркова, а состояния si—

25 следующими состояниями цепи, описание марковского процесса осуществляется подобно известному. При этом табл.2 рассматривают как разряженную матрицу P = I Р1! I I. число строк которой равно k", а число столбЗО цов — л. Матрица P хранится в сжатой форме в виде векторов

О= I!qi II.l=î,k 1;

R= !!гь!!;

Т = !т I I, h О, бп", 35 где d — степень разряженности матрицы Р.

Координаты с!1 вектора 0 содержат суммарное число ненулевых элементов строк матрицы Р, предшествующих строке l, т.е, 1711155 а нэ выходах блока 9 памяти — код класса эквивалентности Sy, к KoTopol j QTHocMTcA состояние зч цепи Маркова.

I-Ia этом процесс загрузки исходных данных завершен, Работа генератора csoдится к реализации алгоритма управления (фиг,2).

С приходом на управляющий вход генератора сигнала "Пуск" блок 10 управления переходит в состояние at и вырабатывает управляющий сигнал "Пуск". управляемого генератора 2 случайных чисел. На выходе управляемого. генератора 2 случайных чисел вырабатывается некоторое случайное число х, которое подается на вторую группу входов блока 7 сравнения двоичных чисел., В зависимости от признака сравнения блок 10 чправления переходит в состояние аз г ибо в состояние аг.

Если вырабатывается признак и>", т.е.

x > rq! (значение первого ненулевого эле40

Вектор О загружается в блок 3 памяти указателей начала строк, содержащий k" ячеек раарядностью logqdk п, Вектор R загружается е блок памяти алементое строк,содаржаитииб k п ячеек б разрядностью m, причем в память записываются только числители а!!. уменьшенные ь на единицу, дробей вида Р II = а !!2

Вектор Т загружается в блок 4 памяти кодов состояний, содержащий б Ic и ячеек 10 разрядностью Iogzn.

Перед началом работы векторы Q, R, Т вычисляются и загружаются в соответствующие блоки 3-5 памяти (устройство загрузки не показано), 15

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

В регистры 6.1...„6,г загружают коды классов эквивалентности,„обоазующих некоторую цепочку С = , 20 принятую эа начальную, причем sf S„. При этом в регистр 6.1 загружают код класса эквивалентности SU, в Ä 6.2 — код .класса эквивалентности Sc и т.д,,в„регистр б,r — код класса эквивалентности S>. В ре- 25 гистр 8 загружают код f состояния sf, а в счетчик 1 — координату qi вектора О (устройства загрузки не показаны). При этом на выходах блока 5 памяти элементов строк появляется координата rqi, т.е. первый нену- 30 левой элемент строки-! матрицы Р, который поступает на первую группу входов блока 7 сравнения двоичных чисел. Одновременно нэ вь1ходэх блока 4 памяти кодов состояний появляется код ч (индекс столбца первого. 35 ненулевого элемента строки матрицы Р) возможного будущего состояния sv (ч = \g «), I мента строки I матрицы P), блок 10 управления переходит в состояние аг и выдает сигнал н+1н в счетчик 1, При этом содержимое счетчика 1 увеличивается на 1, т.е. становится равным ц!+1. Изменение содержимого счетчика запускает процесс чтения блоков 4 и 5 памяти. На выходе блока 5 памяти элементов строк появляется координата гя! -!- !, т.е. второй ненулевой эле1 мент строки I матрицы Р, а на выходе блока

4 памяти кодов состояний появляется код

w (индекс столбца второго ненулевого элемента строки матрицы Р) возможного будущего состояния sQw=tgt+1), который поступает на входы регистра 8 и на входы блока 9 памяти, Вновь срабатывает блок 7 сравнения двоичных чисел. Если блок 7 сравнения двоичных чисел опять вырабатывает признак " > ", блок 10 управления остается в состоянии az и вновь выдает сигнал н+1н в счетчик 1. В результате содержимое счетчика 1 увеличивается еще на 1, процесс чтения блоков 4 и 5 памяти повторяется, вновь срабатывает блок 7 сравнения двоичных чисел и т,д.

Если же при первом сравнении вырабатывается признак " ", блок 10 управления переходит в состояние аз и выдает управляющий сигнал "Прием" в регистр 8 и в группе регистров 6. При. этом в регистр 8 фиксируется код v следующего состояния sv цепи

Маркова, в регистр 6.1 фиксируется код у класса эквивалентности Sy, к которому относится состояние sv и который поступает с выходов преобразователя 9 кодов, в регистры 6.2, 6.3,..., б.r фиксируются коды ч, с, ..., Ь классов эквивалентности Sv, Sc, 5ьг которые поступают с выходов регистров

6,1, 6.2,..., G.ã-1 соответственно. Таким образом, в регистры 6.1,..., б,г фиксируется

НЕКОтОРаЯ ЦЕПОЧКа Cp= <ЯЬ, Б,"., 5c, Sk, 5у>, Изменение содержимого регистров

6,1,.„ б.r запускает процесс чтения блока

3 памяти указателей начала строк. На выходе блока 3 памяти указателей начала строк появляется координата qp вектора О, которая поступает на информационные входы счетчика 1, и блок 10 управления переходит в состояние а4.

В состоянии а4 блок 10 управления выдает управляющий сигнал "Прием" в счетчик 1, фиксируя в нем координату о!у вектора О, При этом на выходах блока 5 памяти элементов строк появляется координата qp, j.å. ненулевой элемент строки р матрицы Р) на выходах блока 4 памяти кодов состояний появляется код р(индекс столбца первого ненулевого элемента стро10

1711155

Таблица 1

Р Snn-1/Со

P s1/Co

P So/Со

P So/С1

Р Snn-1/С.

P s1/Ñ1

Р sn-1/С вЂ” i) P 8,/С„ -1

Р s1/Ñn — 1

Спг-1

Таблица 2

Pз1/ о

P в1/

P Sn-1/ о

Sn-1/ о

So/ o

Р so/ о о

P (So/(4ñ — 1) Р (sn-1/

Р s1/Ñk -1

Г

n — 1

Таблица 3 ки р матрицы P ) возможного будущего состояния S< на выходах блока 9 памяти г рявляется код ф класса эквивалентности Б „к которому относится состояние 3, блок 10 управления переходит в состояние а1. На 5 этом цикл выработки очередного состояния цепи Маркова завершен, С состояния а1 блок 10 управления начинает цикл выработки следующего состояния цепи Маркова, запуская вновь управляемый генератор 10

2 случайных чисел и т.д:

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

Генератор случайного марковского процесса, содержащий узел формирования ука-, 15 зателей начала строк, выполненный в виде первого блока постоянной памяти, узел формирования кодов состояний, выполненный в виде второго блока постоянной памяти, счетчик, генератор случайных чи- 20 сел, узел формирования элементов строк, выполненный в виде третьего блока постоянной памяти, блок сравнения и блок управления, вход логических условий ко,.орого соединен с выходом блока сравне- 25 ния, первый и второй выходы блока управления подключены соответственно к входу установки и счетному входу счетчика, выход которого соединен с адресными входами второго и третьего блоков постоян- 30 ной памяти, выход которого подключен к первому входу блока сравнения, второй вход которого соединен с выходом генератора случайных чисел, вход запуска которого подключен к третьему выходу блока управления. выход первого блока постоянной памяти соединен с информационным входом счетчика, вход пуска генератора является входом пуска блока управления, отличающийся тем, что, с целью расширения функциональных возможностей путем введения r-связности на уровне классов эквивалентности, в генератор введены регистр, узел формирования класса эквивалентности, выполненный в виде четвертого блока постоянной памяти, и группа регистров. информационный вход каждого из которых, кроме первого, соединен с выходом предыдущего регистра группы, выходы регистров группы подключены к соответствующим разрядам адресного входа первого блока постоянной памяти, четвертый выход блока управления соединен с входами синхронизации регистров группы и регистра, выход которого является выходом генератора. выход второго блока постоянной памяти подключен к информационному входу регистра и к адресному входу четвертого блока постоянной памяти, выход которого соединен с информационным входом первого регистра группы.

Таблица 4

1711155

Продолжение табл. 3

1711155

Фиг. 2

Составитель И. Загорбинина

Техред М.Моргентал Корректор О. Кундрик

Редактор А. Козориз

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

Заказ 340 Тираж Подписное

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

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