Генератор случайного марковского процесса
Изобретение относится к автоматике и вычислительной технике и может быть использовано для моделирования простых и сложных (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=
=
Цеоочке 6 = <оо1> соответстеувт множество (Cl}1=(C2=
{Ст)2 = (С8 = <згура>, С9 = <згз1>, С12 =
=
Цепочке С3 =
{С1}3 - (C10=
=
Считая цепочки С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,г загружают коды классов эквивалентности,„обоазующих некоторую цепочку С =
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
