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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК я)ю 6 06 Е 7/38 ПИСАНИЕ ИЗОБРЕТЕНИЯ стиО ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К АВГОРСКОМУ СВИДЕТЕЛЬС(71) Кишиневский политехнический итут им. С,Лазо(56) Авторское свидетельство СССРМ 1531093, кл, 6 06 Р 7/58, 1988,Авторское свидетельство СССРМ 1619262, кл. 6 06 Р 7/58, 1989,(54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРСКОГО ПРОЦЕССА Ж 1711156 А 1(57) Изобретение относится к автоматике и вычислительной технике, может быть использовано для моделирования простых и сложных (г-связных) цепей Маркова, а также для генерации входных последовательностей при стохастическом контроле дискретных объектов. Цель изобретения - расширение функциональных возможностей генератора за счет введения г-связности на уровне классов эквивалентных состояний цепи Маркова, Генератор содержит блоки 9, 11, 12 и 14 по- стоянкой памяти, блок 1 управления, дешифраторы 2 и 8, мультиплексор 10, счетчик 15, накапливающие сумматоры 3 и 5, регистр 7 памяти, группу регистров 13, 4 табл 2 ил.Изобретение относится к автоматике и вычислительной технике и может использоваться для моделирования простых и сложных (г-связных) цепей Маркова. а также для генерации входных последовательностей 5 при стохастическом контроле дискретных объектов, включал микропроцессорные.Цель изобретения - расширение функциональных возможностей генератора за счет введения г-связности на уровне клас сов эквивалентных состояний цепи Маркова.На фиг.1 представлена структурная схема генератора; на фиг.2 - блок-схема алгоритма работы блока управления. 15Генератор случайного марковского процесса (фиг,1) содержит блок 1 управления, дешифратор 2, накапливающий сумматор 3, блок 4 сравнения, накапливающий сумматор 5, генератор 6 равномерно рэспреде ленных случайных чисел, регистр 7 памяти, дешифратор 8, узел формирования класса эквивалентности, выполненный в виде блока 9 постоянной памяти, мультиплексор 10, узел формирования частоты появлений, вы полненный в виде блока 11 постоянной памяти, узел формирования элементов строк, выполненный в виде блока 12 постоянной памяти, группу регистров 13, узел формирования указателей начала строк, выполнен иый в виде блока 14 постоянной памяти, и счетчик 15.Блок 1 управления предназначен для реализации алгоритма работы генератора и полностью определяется блок-схемой алго ритма и представляет собой микропрограммный автомат с жесткой логикой, имеющей состояния а 1, а 2,.а 7. Структура блока 1 управления получается в соответствии с каноническими методами синтеза. 40В состоянии а; блок 1 управления выдает сигналы Прием" - в счетчик 15, "Пуск" - в генератор 6 равномерно распределенных случайных чисел. В состоянии а 2 блок 1 управления выдает сигналы: "Вход 1" - на 45 мультиплексор 10, "Прием" - . в накапливающие сумматоры 3 и 5.В состоянии аз блок 1 управления выдает сигнал "+1" в счетчик 15, В состоянии а 4 блок 1 управления выдает сигналы: "Вход 50 1" - на мультиплексор 10, "Сложить" - в накапливающий сумматор 3, "Прием" - в накапливающий сумматор 5.В состоянии ав блок 1 управления выда- ет сигналы: "Вход 2" - иа мультиплексор 10, 55 "Сложить" - в накапливающий сумматор 3. В состоянии эб блОк 1 управления выдает сигнал "Прием" на группу регистров 13, В состоянии а 7 блок 1 управления выдает сигналы: "Вход 2" - иа мультиплексор 10,"Сложить" - в накапливающие сумматоры3 и 5.Дешифраторы 2 и 8 служат для выявленил случая, когда на их входы подаетсякод единицы, Накаплива.ощий сумматор 3предназначен для формирования и хранения текущего состояния цепи. Накапливающий сумматор 3 имеет управляющие входы"Прием" и "Сложить". При подаче на накапливающий сумматор 3 управляющего сигнала "Прием" в нем фиксируется информация,поступающая с выхода мультиплексора 10.При подаче управляющего сигнала "Сложить" на накапливающий сумматор 3 к текущему его значению добавляется значениечисла, поступающего с выхода мультиплексора 10,Блок 4 сравнения выполняет сравнениечисел, поступающих от накапливающегосумматора 5 и от генератора 6 равномернораспределенных случайных чисел, вырабатывая признаки"", " ", "=",Накапливающий сумматор 5 предназначен для формирования и хранения модифицированных элементов стохастическойматрицы переходов. Накапливающий сумматор 5 имеет управляющие входы "Прием"и "Сложить". При подаче управляющего сигнала "Прием" на накапливающий сумматор5 в нем записывается информация, поступающая с выхода блока 12 памяти элементовстрок. При подаче на накапливающий сумматор 5 управляющего сигнала "Сложить" ктекущим его значениям добавляется значение регистра 7,Генератор 6 предназначен для формирования равномерно распределенныхслучайных чисел Е;, Е;=Х; 2 , ОЕ1,Случайное число Е появляется на выходегенератора 6 равномерно распределенныхслучайных чисел при поступлении на егоуправляющий вход сигнала "Пуск" от блока1 управления,Регистр 7 служит для хранения значения фонового элемента стохастической матрицы переходов. взятоо со знаком "-" изаписанного в дополнительном коде.Блок 9 предназначен для преобразования кода состояния цепи Маркова в номер(код) .класса эквивалентности, к которомупринадлежит соответствующее состояние,Разрядность ьходиых слов блока 9 равнаО 9 гп, где п число состояний многосвязнойцепи Маркова. а разрядность выходныхслов - 1 оцгК где- число классов эквивалентных состояний цепи Маркова, При этомчисло ячеек памяти равно и и в каждую иэних записывается номер соответствующегокласса. В зависимости от особенностей конкретного применения предлагаемого уст 1711156ройства преобразователь 9 кодов можно реализовать и в виде комбинационной схемы, получаемой в соответствии с известными методами синтеза переключательных схем,Мультиплексор 10 поедназначен для подключения к входу накапливающего сумматора 3 выхода блока 11 памяти частоты появлений (на управляющие входы мультиплексора 10 подается сигнал "Вход 1"), либо константы "-1", получаемой путем подключения всех разоядов вторсго входа мультиплексора на логическую единицу (на управляющие входы мультиплексора 10 подается сигнал "Вход 2"),Блоки 11, 12 и 14 памяти предназначены для хранения в сжатой форме стохастической матрицы переходов. Считывание информации из блоков 11, 12 и 14 памяти происходит при поступлении соответствующих адресов на их адресные входььГруппа регистров 13 предназначена для формирования и хранения последовательности классов эквивалентности длины г, При. этом на некотором такте 1 хранится: в регистре 13.1 - номер (код) класса эквивалентности, к которому принадлежит состояние цепи Маркова, сгенерированное в такте (т); в регистре 13.2 - номер (код) класса эквивалентности, к которому принадлежит состояние цепи Маркова, сгенерированное в такте (-2) и т,д.; в регистре 13, г - номер (код) класса эквивалентности, к которому принадлежит состояние цепи Маркова, сгенерированное также в такте г. Разрядность каждого из регистров 13.1.13, г равна 1 о 92.Прием информации в регистры 13.1.13. г осуществляется при поступлении на их соответствующих управляющих входах сигнала "Прием" от блока 1 управления. Выходы регистров б группы образуют адреснь 1 й вход блока 14,Счетчик 15 предназначен для хранения и формирования адреса, по которому осуществляется обращение к блокам 11 и 12 памяти. Счетчик 15 имеет управляющие входы "+1" и "Прием". При подаче на счетчик 15 управляющего сигнала "Прием" в нем фиксируется информация, поступающая с выхода блока 14, При подаче управляющего сигнала "1" на соответствующий вход счетчика 15 его содержимое увеличивается на единицу.Генератор работает следующим образом,Пусть задана г-связная цепь Маркова, имеющая и состояний з 0, з 1, , з,-1, и в этой цепи для всякой последовательности состояний длин ы г (цепочки С длины г) оп ределе 5 10 15 20 25 30 35 40 45 50 55 ны условные вероятности вида Р(з/С), где= О, и -1, ) = О, и.В принятых обозначениях задание гсвязной цепи Маркова означает, что заданатабл.1, в которой в левом столбце перечислены все цепочки Сь в правом - соответствующие им плотности распределенияусловных вероятностей,Для случая г = 1 цепь Маркова являетсяпростой однородной цепью. Во многихпрактически важных случаях множество состояний Я = (зД, ) = О, иразбивается наклассы (подмножества) эквивалентности,Л л лЯ = Зо О Я 0О Я 1,где К - число классов.При этом состояния, з и з 1 являются эквивалентными, т.е. принадлежат одному итому же классу лишь в том случае, если любая строка Сь табл,1, где Сь - цепочка, содержащая хотя бы одно вхождение зьсовпадает с соответствующей строкой Стабл.1, где Са - цепочка, получаемая иэ Сьзаменой з на Я;Если выполняется условие 1и, задание г-связной цепи Маркова можно минимизировать. Для минимизации форма заданияг-связной цепи на основе табл.1 составляютв табл,2, строки которой помечены цепочками вида С, а.=0, к,Цепочки Сд представляют собой последовательности классов эквивалентностидлины г. При этом каждой цепочке вида Ссоответствует множество цепочек вида(С)а, получаемых из Са путем перебора всевозможных вариантов замены каждого изклассов эквивалентности 50, 51 Йк- насоответствующие им состояния. Очевидностроки табл.1, соответствующие цепочкам(С)а, совпадают;Каждая строка С табл,2 содержит условные вероятности вида Ра(51/Са), причемР,1(з;/С.) = ад/С),где С - одна из цепочек состояний из множества (С)а, соответствующая цепочкеклассов С.Таким образом, табл,2 получается изтабл,1 путем извлечения по одной строке изкаждого множества вида (С)а строк. Числострок табл,2 равно к" и поскольку 1 и, числои гстрок табл,2 в ( - ) раз меньше, чем числострок табл.1.Например, в табл:3 задана 2-связнаяцепь Маркова с множеством состояний Я=(зо,зь з 2, зз).Множество состояний 5 разбивается на 1=2 класса эквивалентностизо=(з 0, з 1);з=(ы, зз 1,Минимизированная форма рассматриваемой 2-связной цепи Маркова приведенав табл,4, При этом цепочке классов эквиваЛЕНтНОСтИ Со=8 о, Зо СООтВЕтСтВУЕт МНОжЕство последовательностей состояний 5=8332, С 15=8383).Считая цепочки Са текущими состояниями г-связной цепи Маркова, а состояния3 - следующими состояниями цепи, описание Марковского процесса осуществляетсяподобно известному. При этом табл,2 рассматривают как квазиразряженную матрицу Р =Ро, число строк которой равноМ, а число столбцов ь, Матрица Р хранитсяв сжатой форме в виде векторов С =-98,В =гьи Ть,Векторы О, В и Т получаются следующим образом,Устанавливаем до=О.Сжимаем строку Ро (т.е, строку, соответствующую цепочке Со) матоицы Р. Для этогов строке Ро выделяем подстроки Ро, Ро 351 2РК из последовательно расположенных одинза другим фоновых элементов. Для каждойподстройки Рвычисляется число (РГ)входящих в нее фоновых элементов Ь.Просматривая строку Ро сл.,ва направо, 40В КООРДИНатЫ Го, Г 1, Гг.то, 11, 12,.ВЕКтОров Р и Т последовательно выписывают: 1)если встречается подстройка иэ элементовЛ в й выписывают (Р.", ), а в Г выписываютРоо,о - . огде к индекс столбца последнего элементаподстройки Ро; 2) если встречается базовыйэлемент Ро 1, в Я выписывают 1, а в Т выписываютРоо,Хо =о, где 9 - индекс столбца, где находится элемент Ро), т.е. к=).Пусть, при сжатии строки Ро, в К и Т 55были выписаны по Ро значений. Устанавливаем 91= Д.Аналогично строке Ро сжимаем строкуР 1(т,е. строку соответствующую цепочке С 1 )и в векторах й и Т выписываем соответствующие значения. Пусть при этом в векторахй и Т были выписаны по 31 значений,Устанавливаем 92=91+/31.Аналогичным образом сжимаем строкиР 2(С 2), Рз(СЗ), Рф), где=к-, определяязначения координат1 до еГ р о е (ЬЕ 1 р фр( о е (Ъ+ (Ъ1рЪо е , ер- ф рра такжеА=9.2+ ф 1-2Вектор О загружается в блок 14 памяти.Вектор Я загружается в блок 11 памяти частоты появлений,Вектор Т эагруркается в блок 12 памятиэлементов строк, причем в память записыващтся только значения вида аь 1, где а-числители дробей вида 1 -- а г 2 ,Перед началом работы векторы О, В и Твычисляются и загружаются в соответствующие блоки 14, 11 и 12 памяти (устройствозагрузки не показано), Фоновый элемент сознаком "-" записывается в дополнительномкоде в регистр 7,Начальное состояние 8; цепи задаетсяследующим образом. В накапливающийсумматор 3 загружают код 1 состояния Я 1,При этом на выходе блока 9 появляется кодкласса эквивалентности, к которому относится состояние Я.В регистры 13.113, г загружают кодыклассов эквивалентности, образующих некоторую цепочку С =Я- Я 3 ,принятую за начальную, причем Як Я, Приэтом в регистр 13,1 загружают код классаэквивалентности, к которому принадлежитсостояние Я, т,е, Я в регистр 13.2 - кодкласса эквивалентности 3;, и т.д в регистр13,г - код класса эквивалентности Я , Навыходе блока 14 памяти появляется координата да вектора О.На этом процесс загрузки исходныхданных завершен. Работа генератора сводится к реализации алгоритма управления(фиг.2).С приходом на управляющий вход генератора сигнала "Пуск" блок 1 управленияпереходит в состояние а 1 и вырабатываетуправляющие сигналы "Прием" в счетчик5 и "Пуск" генератора б равномерно распределенных случайных чисел. При этом всчетчик 15 записывается координата д, агенератор б вырабатывает ль-разрядноедвоичное число Е 1=х 1 2и величина х 1 подается на второй вход блока 4 сравнения, 171115645 50 55 Изменение содержимого счетчика 15 запускает процесс чтения из блоков 11 и 12 памяти. На выходе блока 11 памяти частоты появлений появляется координата г 9 а на выходе блока 12 памяти элементов строк - координата т 9 а, соответствующие первому элементу сжатой строки Ра(Са), координата г 9 подается на вход дешифратора 2 и на первый вход мультиплексора 10, а координата с 9 а - на первый вход накапливающего сумматора 5, Сигнал "Прием" в счетчик 15 также подается на управляющий выход генератора с тем, чтобы указать, что получено очередное состояние цепи Маркова, Блок 1 управления переходит в состояние а 2.В состоянии а 2 блок 1 управления выдает управляющие сигналы "Вход 1" на мультиплексор 10, "Прием" в накапливающий сумматор 3 и "Прием" в накапливающий сумматор 5. В результате в накапливающем сумматоре 5 фиксируется считанная из блока 12 памяти элементов строк координата т 9 а вектора Т. которая поступает на первый вход блока 4 сравнения, а в накапливающий сумматор 3 - координата г 9 которая поступает на вход блока Я и на вход дешифратора 8,В зависимости от признака сравнения и значения сигнала на выходе дешифратора 2 блок 1 управления переходит в одно из следующих состояний; при признаке (число от генератора б равномерно распределенных случайных чисел больше числа от накапливающего сумматора 5) - в состояние аз; при признаке (число от генератора б равномерно распределенных случайных чисел меньше числа от накапливающего сумматора 5 и на выходе дешифратора 2 сигнал "0") - в состояние а 7; при признаке "=" (число от генератора б равномерно распределенных случайных чисел равно числу от накапливающего сумматора 5 или при признаке и сигнале "1" на выходе дешифратора 2) - в состояние аь. В состоянии йз блок 1 управления выдает управляющий сигнал "+1" в счетчик 15, в результате чего его содержимое увеличивается на единицу, т,е, становится равным 9 а+1, Изменение содержимого счетчика 15 запускает процесс чтения иэ блоков 11 и 12 памяти, на выходах которых появляются очередные координаты векторов й и Т, т.е. КООРДИНатЫ ГЯа+1 И т 9 а+1 СООТВЕТСТВУЮЩИХ второму элементу сжатой строки Р, и блок 1 управления переходит в состояние а 4.В состоянии а 4 блок 1 управления выдает управляющие сигналы "Вход 1" на мультиплексор 10, "Сложить" в накапливающий сумматор 3 и "Прием" в накапливающий 10 15 20 25 30 35 40 сумматор 5, Тем самым в накапливающий сумматор 3 путем сложения координат гцв и г 9+1 вектора В формируется номер (код) возможного будущего состояния цепи Маркова, а в накапливающем сумматоре 5 фиксируется очередная координата тра+1 вектора Т.В зависимости от признака сравнения и от значения сигнала на выходе дешифратора 2 после состояния а 4 блок 1 управления переходит либо в состояние аз (признак ), либо в состояние а 7 (приэнак и "0" на выходе дешифратора 2), либо в состоя. ние а 5(признак "=" или признак и "1" на выходе дешифратора 2,Таким образом, смена состояний аз, а 4 обеспечивает поиск в сжатой строке Р такой координаты с вектора Т, для кото .ой х 1тс,Если х,=1, или хт и координата 1 с соответствует базовому элементу подстройки, состоящей ровно из одного фонового элемента. т.е. г=1, блок 1 управления после состояния а 2 или а 4 переходит в состояние а 5 и вырабатывает управляющие сигналы "Вход 2" на мультиплексор 10 и "Сложить" в накапливающий сумматор 3. При этом в накапливающий сумматор 3 формируется очередное состояние злу цепи Маркова, Код Я состояния Яа поступает на вход блока 9, на выходе которого появляется код ф класса эквивалентности Я, к которому относится состояние з,и который поступает на вход регистра 13.1 группы, Блок 1 управления переходит в состояние а 6.В состоянии а 6 блок 1 управления выдает управляющий сигнал "прием" на группу регистров 13. При этом в регистр 13.1 фиксируется код ф класса эквивалентности Я, в регистры 13.2, 13,3, 13,г - коды ю, Л .,д классов эквивалентности з, Я , , которые поступают с выходов регистров 13.1, 13.2.13 гсоответственно.Таким образом, в регистры 13.1, 13.2 13.г фиксируется некоторая цепочка С =Яс, Я .,Я 1, Б . Изменение содержимого регистров 13,1 13.г запускает процесс чтения блока 14. На выходе элемента 14 памяти появляется координата р векторэ О, которая поступает на информационный вход счетчика 15, и блок 1 управления переходит в состояние а 1, с которого начинается очередной цикл работы генератора.Если же х 1тс, но координата 1 с соответствует подстройке из фоновых элементов(гс1) и выход дешифратора 2 установлен в "0"), блок 1 управления после состояния ал или а 2 переходит в состояние а 7, 171 115 б 1210 15 20 25 30 В состоянии а 7 блок 1 управления выдает управляющие сигналы "Вход 2" на мультиплексор 10, "Сложить" в накапливающий сумматор 3 и "Сложить" в накапливающий сумматор 5, чем обеспечивается последовательное формирование в накапливающем сумматоре 3 номеров (кодов) возможных будущих состояний цепи, которые были сжаты и которые в явном виде не хранятся, Одновременноизсодержимого накапливающего сумматора 5 вычитается значение фонового элемента Ь, формируя тем самым промежуточные модифицированные значения вероятностей переходов именно о те состояния, номера которых хранятся в накапливающем сумматоре 3,Из состояния а 7 блок 1 управления может перейти в одно из состояний а 5. а 6 либо а 7, Если блок 4 сравнения вырабатывает признак сраонения в накаливающем сумматоре 3, формируется код следующего состояния цепи Маркова и блок 1 управления переходит в состояние аб.Если блок 4 сравнения вырабатывает признак сравнения "=", то в накапливающем сумматоре 3 хранится код очередного состояния цепи Маркова, увеличенный на "1", поэтому блок 1 управления переходи 1 в состояние 85.Если же блок 4 сравнения вырабатывает признак сравнения , то возможны два случая. Если признак выработан для состояния э 1, т,е. подстройка из фоновых элементов находится в начале строки и следующим состоянием цепи Маркова будет состояние эо, на выходе дешифратора 8 вырабатывается "1" и блок 1 управления переходит в состояние а 5.Б противном случае, блок 1 управления остается в состоянии а 7 и вновь из накапливающего сумматора 5 вычитается значение фонового элемента, из накапливающего сумматора 3 вычитается 1, анализируется признак сравненияи т,д.Цикл выработки очередного состояния цепи Маркова завершается с переходом блока 1 управления в состояние а 1. При этом сигнал на управля 1 ощем выходе генератора указывает, что получено очередное состояние цепи,Формула изобретения Генератор случайного марковского процесса, содержащий узел формирования указателей начала строк, выполненный в виде первого блока постоянной памяти, счетчик, мультиплексор, узел формирования частоты появлений, выполненный в виде второго блока постоянной памяти, генератор равномерно оаспределенных случайных чисел, узел формирования элементов строк, выполненный в виде третьего блока постоянной памяти, первый накапливающий сумматор, блок сравнения и блок управления. первь 1 й и второй выходы которого соединены соответственно с установочным и со счетным входом счетчика, информационный входкоторого подключен к выходу первого блока постоянной памяти, а выход соединен с адресными входами второго и третьего блоков постоянной памяти, вход пуска генератора является входом пуска блока управления, третий выход которого подключен к входу запуска генератора равномерно распределенных случайных чисел, выход которого соединен с первым входом блока сравнения, выход которого соединен с первым входом логических условий блока управления, четвертый и пятый выходы блока управления соединены соответственно с входами записи и разрешения сложения первого накапливающего сумматора, выход которого является выходом генератора, выход второго блока постоянной памяти подключен к первому информационному входу мультиплексора, выход которого соединен с информационным входом первого накапливающего сумматора, первый управляюьций вход мультиплексора подключен к шестому выходу блока управления, о т л и ч а ю щ и й с я тем, что,с целью расширения функциональных воэможностей путем введения г-связности на уровне классов эквивалентных состояний цепи Маркова, в генератор введены второй накапливающий сумматор, регистр памяти, доа дешифратора, группа регистров и узел формирования класса эквивалентности, выполненный в виде четвертого блока постоянной памяти, выход которого соединен с информационным входом первого регистра группы, выход каждого регистра группы, кроме последнего, подключен к информационному входу последующего регистра группы. выходы регистров руппы соединены с соответствующими разрядами адресного входа первого блока постоянной памяти, выход второго блока постоянной памяти подключен к входу первого дешифратора, выход которого соединен с вторым входом логических условий блока управления, седьмой и восьмой выходы которого подключены соответственно к второму управляющему входу мультиплексора и к входам синхронизации регистров группы, второй информационный вход мультиплексора является входом задания сигнала "-1" генератора, выход первого накапливающего сумматора соединен с адресным входом четвертого14 1711156 Таблица 1 Таблица 2 Таблица 3 Таблица 4 блока постоянной памяти и с входом второго дешифратора, выход которого подключен к третьему входу логических условий блока управления, выходы третьего блока постоянной памяти и регистра памяти соединены с информационными входами второго накапливающего сумматора, входы записи и разрешения сложения которого подключены к девятому и десятому выходам блока управления, выход второго накапливающе го сумматора соединен с вторым входомблока сравнения.Составитель Л. Загорбининадактор А, Козориз Техред М,Моргентал Корректор О, Кундрик и ГКНТ ССС Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гага 01 з 340ВНИИП Тираж Подписноедарственного комитета по изобретениям и открыт 113035, Москва, Ж, Раушская наб 4/5