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

19) ЕТЕЛЬСТВУ пользовано для морелирован сложных (г-связных) цепей М генерации входных последа при стохастическом контрол обьектов. Цель изобретения функциональных возможнос ра за счет введения г-связно классов эквивалентности со Маркова. Генератор содерж 5 и 9 постоянной памяти, сч ратор 2 случайных чисел, г . ров 6, регистр 8 блок 10 упра .2 ил. ический инсти он о СССР 1989.НОГО МАРКО к авто может тике и ть исСОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ АВТОРСКОМУ(54) ГЕНЕРАТОР СЛУЧАЙСКОГО ПРОЦЕССА(57) Изобретение относитсвычислительной технике и(я)5 6 08 Р 7/58 ЕТЕНИ ия простых и аркова и для вательностей е дискретных - расширение тей генератости на уровне стояний цепи ит блоки 3, етчик 1, генеруппу региствления. 4 табл.,10 20 30 35 50 зом,Изобретение относится к автоматике и вычислительной технике и может быть использовано для моделирования простых и сложных(г-связных) цепей Маркова, а также для генерации входных последовательностей при стохастическом контроле дискретных обьектов, включая микропроцессор.Цель изобретения - расширение функциональных возможностей генератора за счет введения г-связности на уровне классов эквивалентности состояний цепи Маркова.На фиг.1 представлена структурная схема генератора; на фиг.2 - блок-схема алгоритма работы блока управления,.Генератор случайного марковского процесса (фиг,1) содержит счетчик 1, управляемый генератор 2 случайных чисел, узел формирования указателей начала строк, выполненньй в виде блока 3 постоянной памяти, узел формирования кодов состояний, выполненный в виде блока 4 постоянной памяти, узел формирования элементов строк, выполненный в виде блока 5 постоянной памяти, группу регистров б,.образованнуа регистрами 6,1, 6,2, б.г, блок сравнения 7 двоичных чисел, регистр 8, узел формирования класса эквивалентности, выполненный в виде блока 9 постоянной памяти, и блок 10 управления,Счетчик 1 предназначен для хранения и формирования адреса, по которому осуществляется обращение к блокам 5 и 4 памяти, Счетчик 1 имеет управляющие входы "1" и "Прием",Управляемый генератор 2 случайных чисел Вырабатывает а-разрядные двоичные числа 2, 2= х 2 ; Ог1. Случайное число г появляется на выходе управляемого генератора 2 случайных чисел при поступлении на его управляющий вход сигнала "Пуск" от блока 10 управления,Блоки 3-5 памяти предназначены для хранения в сжатой форме стохастической матрицы переходов, Считывание информации из блоков 3 - 5 памяти происходит при поступлении соответствующих адресов на их адресные Входы,Группа регистров б предназначена для формирования и хранения последовательности классов экВиВалентнОсти длины г предшествующего сложного состояния многосвязной цепи Маркова. При этом наекотором такте 1 в регистрах 6.1,б.г хранится в регистре 6,1 - номер (код) класса эквивалентности, к которому принадлежит состояние цепи Маркова, генерируемое в такте (1-1); в регистре 6.2 - номер код) класса эквивалентности, к которому принадлежит состояние цепи Маркова, генерируемое а такте(т) и т.д., в регистре б.г- номер(код)класса эквивалентности, к которому принадлежит состояние цепи Маркова, генерируемое в такте (1-г). Разрядность каждого из регистров 6.1,.6,г равна О 92 К где- число классов эквивалентных состояний цепи Маркова.Прием информации в регистры 6.1,. , б.г осуществляется при поступлении на их соответствующие управляющие входы сигнала "Прием" от блока 10 управления, Выходы регистров 6.1, , б,г образуют адресный вход блока 3 памяти указателей начала строк,Блок 7 сравнения двоичных чисел выполняет сравнение гл-разрядных чисел, поступающих от управляющего генератора 2 случайных чисел и от блока 5 памяти элементов строк 4 вырабатывает признак" " либо) йРегистр 8 предназначен для хранения текущего состояния марковского процесса. Запись информации в регистр 8 осуществляется по сигналу "Прием", поступающему на его управляющий вход,Блок 9 предназначен для преобразования кода состояния цепи Маркова а номер код) клааса эквивалентности, к которому принадлежит соответствующее состояние. Разрядность входных слов блока 9 равна 1092 п, где и - число состояний многосвязной цепи Маркова, а разрядность выходных слов 092 к.При этом число ячеек памяти равно и и в каждую из них записывается номер соответствующего класса, В зависимости от особенностей конкретного применения генератора блок 9 можно реализовать и в виде комбинационной схемы, получаемой в соответствии с известными методами синтеза переключательных схем,Блок 10 управления предназначен для реализации алгоритма работы генератора и полностью определяется блок - схемой алгоритма (фиг.2), Блок 10 управления представляет собой управляющий автомат с состояниями а 1, а 2, аз, а 4, структура которого получается в соответствии с каноническими методами синтеза.В состоянии а 1 блок 10 управления выдает сигнал "Пуск" на управляемый генератор 2 случайных чисел, в состоянии а 2 блок 10 управления выдает сигнал "+1" а счетчик 1, в состоянии аз блок 10 управления выдает сигнал "Прием" в регистр 8 и на группу регистров 6, в состоянии а 4 блок 10 управления выдает сигнал "Прием" в счетчик 1,Генератор работает следующим обра 1711155Пусть задана г-связная цепь Маркова,имеющая и состояний зо, з 1 зп, и в этойцепи для всякой последовательности состояний длины г(цепочки С длины г) определены цц 1 вные вероятности вида Рц(з/С) гдеФ1 = О, и -1, ) = О, п,В принятых обозначениях задание гсвязной цепи Маркова означает, что заданатабл.1, в которой в левом столбце перечислены все цепочки Сь в правом - соответствующие им плотности распределенияусловных вероятностей. Для случая г = 1цепь Маркова является простой однородной цепью.Во многих практически важных случаяхмножество состояний Я " (8 Д; ) - О, и разбивается на классы (подмножества) эквивалентности, т.е.з = фойовь,-:где М - число классов.При этом состояния з и з являютсяэквивалентными, т.е, принадлежат одномуи тому же классу лишь е том случае, ес илюбая строка Сп табл,1, где Сп - цепочка,содержащая хотя бы одно вхождение зь совпадает с соответствующей строкой Стабл.1, где С - цепочка, получаемая из Сепзаменой з на 81.Если выполняется условие Мп, задание г-связной цепи Маркова можно минимизировать.Для минимизации формы задания гсвязной цепи на основе табл.1 составляюттабл.2, строли. щорой помечен ы цепочкамивида С 1, = О, 1 -1.Цепочки 1 представляют собой последовательности классов эквивалентностудлины г, При этом каждой цепочке вида Ссоответствует множество цепочек вида(С)1,получаемых из С путем перебора возможных вариантов замены каждого из классовэквивалентности 1 о 31, Ь на соответствующие им состояния. Строки табл,1,соответствующие цепочкам (С 1)1, совпадают.Каждая строка С 1 табл, 2 содержит условные вероятности вида Р;(зр(.), причемР 1(з/11)ее Рн(81/С 1),где С - одна из цепочек состояний иэ множества (С)1,соответствующих цепочкеклассов С,т,е. табл.2 получается из табл,1 путем извлечения по одной строке из каждого множества вида (Сф строкОчевидно, число строктабл.2 равно К и, паскальу Ми, числоп 1строк табл.2 в ( - , раз меньше, чем число1(строк табл.3.Например е табл,З задана двухсвязная цепь Маркова с множеством состояний 3 =(зо, з 1, 82, з 3), Множество состояний40 ао= О;Ц 1= йо,Ц 2 = Ч 1+тв 1 СЬ- = а+ йк - 2,45 ггде йо, й 1,. Мк - 2 - число ненулевых элементов строк 0.1, Кматрицы Р.Перейдем от стохастической матрицы Рк матрице Р=Р 150О,если Рц=ОтР, если Ря ФО. Векторы В и Т получаются следующимобразом,Из матрицы Р построчно выписывают ввектор В ненулевые элементы Рл; в вектор Т -индексы столбцов ) ненулевых элементов,3 разбивается на К = 2 класса эквивалентности ,о = (зо 81):31=(зг, зз),5 Минимизированная форма рассматриваемой двухсвязной цепи Маркова приведена в табл.4. При этом цепочке классовэквивалентности Со =Яо, Яосоответствует множество цепочек состоя 10 нии(С 1)3 - (С 1 о=8282, С 11=згзз. С 4- =8382, С 15=8383).Считая цепочки 6 текущими состояниями г-связной цепи Маркова, а состояния 8 в25 следующими состояниями цепи, описаниемарковского процесса осуществляется подобно известному. При этом табл.2 рассматривают как разряженную матрицу Р =Ря.число строк которой равно 1", а число столбЗО цов - л. Матрица Р хранится в сжатой формее виде векторовО - ц , - О,к,й= гь;Т=ь, Ь =О, бп",35 где д - степень разряженности матрицы Р.Координаты сл вектора О содержат суммарное число ненулевых элементов строкматрицы Р, предшествующих строке 1, т.е,Вектор О загружается в блок 3 памятиуказателей начала строк, содержащий К"ячеек раарядностью Юртскгп,Вектор й загружается е блок памятиалементое строк,содаржаитии О к и ячеек бразрядностью гп, причем в память записываются только числители а 1, уменьшенныеьна единицу, дробей вида Р 1 = а 2Вектор Т загружается в блок 4 памятикодов состояний, содержащий б М п ячеек 10разрядностью оргп.Перед началом работы векторы О, В, Твычисляются и загружаются в соответствующие блоки 3-5 памяти (устройство загрузки не показано), 15Начальное состояние з 1 цепи задаетсяследующим образом,В регистры 6.16,г загружают кодыклассов эквивалентности,образующих некоторую цепочку С = Яа, Бь с. Бо, 20принятую эа начальную, причем зьБ. Приэтом в регистр 6. загружают код классаэквивалентности Яц, в регистр 6.2 - код.класса эквивалентности Я и т,дврегистр6,г - код класса эквивалентности 5 В регистр 8 загружают код 1 состояния з, а всчетчик 1 - координату ц вектора О (устройства загрузки не показаны). При этомна выходах блока 5 памяти элементов строкпоявляется координата гак т,е. первый ненулевой элемент строкиматрицы Р, которыйпоступает на первую группу входов блока 7сравнения двоичных чисел. Одновременнона вь 1 ходах блока 4 памяти кодов состоянийпоявляется код ч (индекс столбца первого. 35ненулевого элемента строкиматрицы Р)возможного будущего состояния зч (ч = щ ),а на выходах блока 9 памяти - код классаэквивалентности Яу, к которо / относитсясостояние зч цепи Маркова. 40На этом процесс загрузки исходныхданных завершен, Работа генератора сводится к реализации алгоритма управления(фиг,2).С приходом на управляющий вход генерагора сигнала "Пуск" блок 10 управленияпереходит в состояние а 1 и вырабатываетуправляющий сигнал "Пуск" управляемогогенератора 2 случайных чисел. На выходеуправляемого. генератора 2 случайных 50чисел вырабатывается некоторое случайное число х, которое подается на вторуюгруппу входов блока 7 сравнения двоичныхчисел.,В зависимости от признака сравнения 55блок 10 чправления переходит в состояниеаз г ибо в состояние а 2.Если вырабатывается признак и", т,е.хгц (значение первого ненулевого элемента строкиматрицы Р), блок 10 управления переходит в состояние а 2 и выдает сигнал н+1 н в счетчик 1, При этом содержимое счетчика 1 увеличивается на 1, т.е. становится равным ц+1. Изменение содержимого счетчика запускает процесс чтения блоков 4 и 5 памяти. На выходе блока 5 памяти элементов строк появляется координата гсу+1, т,е. второй ненулевой эле 1мент строкиматрицы Р, а на выходе блока 4 памяти кодов состояний появляется код а(индекс столбца второго ненулевого элемента строкиматрицы Р) возможного будУщего состоЯниЯ зурне=т 9+1), котоРый поступает на входы регистра 8 и на входы блока 9 памяти,Вновь срабатывает блок 7 сравнения двоичных чисел. Если блок 7 сравнения двоичных чисел опять вырабатывает признак "", блок 10 управления остается в состоянии а 2 и вновь выдает сигнал н+1 н в счетчик 1. В результате содержимое счетчика 1 увеличивается еще на 1, процесс чтения блоков 4 и 5 памяти повторяется, вновь срабатывает блок 7 сравнения двоичных чисел и т,д.Если же при первом сравнении вырабатывается признак "", блок 10 управления переходит в состояние аз и выдает управляющий сигнал "Прием" в регистр 8 и в группе регистров 6. При. этом в регистр 8 фиксируется код ч следующего состояния зч цепи Маркова, в регистр 6,1 фиксируется код у класса эквивалентности Зу, к которому относится состояние зч и который поступает с выходов преобразователя 9 кодов, в регистры 6.2, 6,3 6.г фиксируются коды ч, с, , Ь классов эквивалентности 5 ч, Вс, Фьг которые поступают с выходов регистров 6,1, 6.2.6.гсоответственно. Таким образом, в регистры 6.1 б,г фиксируется некоторая цепочка Ср= Яь, Б,., 1 с, Бо, 1 у, Изменение содержимого регистров 6,1, .6,г запускает процесс чтения блока 3 памяти указателей начала строк. На выходе блока 3 памяти указателей начала строк появляется координата рр вектора О, которая поступает на информационные входы счетчика 1, и блок 10 управления переходит в состояние а 4.В состоянии а 4 блок 10 управления выдает управляющий сигнал "Прием" в счетчик 1, фиксируя в нем координату сР вектора О, При этом на выходах блока 5 памяти элементов строк появляется координата гор, т.е. ненулевой элемент строки р матрицы Р) на выходах блока 4 памяти кодов состояний появляется код р(индекс столбца первого ненулевого элемента стро1711155 дактор А, Козори Заказ 340 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раущская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина оставитель И. Загорхред М.Моргентал ина Корректор О, Кундрик