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

(504 СОЬ Р 7 58 НАЯЫ 1 БОЗ САНИЕ ИЗОБРЕТЕН ЬСТВУ 24-2 тик использоваться для генерации входных.последовательностей при стохастическом контроле дискретных объектов.Цель изобретения - расширение функциональных возможностей генератора засчет получения случайных процессов,описываемых стохастическими матрицамипереходов, не являющимися квазиразряженными, Введение в генератор датчика 8 равновероятной двоичной цифры,двух счетчиков 7,9 и схемы сравнения11 позволяет достигнуть поставленнуюцель без увеличения объема оборудования и снижения быстродействия. 2 ил. Бю 4 олитехнический ин Лазомальск8.8)е свидеС 06 Р ий ельство СССР 15/ЗЬ, 1969,ьство СССР 7/58, 1987ЙНОГ РКОВСКОГО сится втомаГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР Н АВТОРСКОМУ СВИ(57) Изобретение от вычислительнои технике и можеПзобрете 1 ие относится к автоматике н цсг 1 исли: ельной технике и можетиспо.1 ьзоватьсн цлн генерации входныхг 1 рследоцате 11 ьнос гей при стохастическем сп гроле дискретных обьектов,11 е 111 из о ретепин - расширение функциональных возможностей генератора1 а счет получения случайных процессов, описываемых стохастическими матР 11 цами перс.,оров, не являюпимися квазирпзряже 1 шыми.Па фиг. 1 представлена структурнаясхем генератора; на фиг. 2 - блоксхема алгоритма работы блока управлепця,Геерагор случайного марковскогопроцсссэ сспп п 1,111 11 ервый счетчик 1,".1 ок 2 цамнги, блок 3 памяти, блок 4памнги, гецератор 5 равномерно расф 2011 ц:1 елецць 1 х чисел первую схему 6сравнения, торой счетчик 7, датчикБ равновероятной двоичной цифры, третий счет сцк 9, 0,11 ок 10 управления,тору 1 о схема 1 сравнения. 25Блоки 2 - 4 памяти предназначены,1 лн храп ц 11 н в сжатой форме стохастической м; грицы переходов.Блок 10 управления предназначендля реализации алгоритма работы генератора и определяется блок-схемойалгоритма (с 11 иг. 2) . Блок 1 О управления представляет собой управляющийавтомат с состонци 11 ми а 1, а 1аба уБ сс 1 столниибиток 10 управле 35ния выдает сигналы "Прием" в счетчик 1 "13 ск" генератора 5.Б состоянии а блок 10 управленияМвыдае" сигналы "Прием" в счетчик 7,+ 1 в счетчикБ состоянии а блок 10 управлениявыдает сигнал "+1" в счетчик 7.Б состоянии а блок 10 управлениявыдает сигнал "Прием" в счетчик 9,Б состоянии а блок 10 управлениявыдает сигналы "+ 1" в счетчик 9, "Опрос" датчика Ы,Б состоянии а блок 10 управлениявыдает сигн"л "1.1" в счетчик 7.Б состоянии л, блок 10 управлениявыдает с 11 гнал "Сброс" счетчика 7,Схема 11 сра 1.нения предназначеналл.1 срав:1 е 1 гия чисел, поступавших избло 1 са 3 памя 1 си и с выхода счетчика 9,Схема 11 сравнения вырабатывает приз 55ц ак "=";и 1 бо Ф"Генератор работает следующим образомПусть задац мнрковс кий процесс,описываемый конечным множеством состояний Ы =з , 1 = О, пи стохастической матрицей переходов Р= 11 Р, (, где Р, - вероятность перехода из состояния з, н состояние в= 0 и1 = ос 2ос" - це 1 % 11 1) Флое; щ - параметр, Определяющий точцость представления элементов матриЦЬ 111 агрица Р хранится в сжатом нидев виде векторов Ц = 1 Ч 1; К = 11 гбТ = 1 г )Бек горы Ц, К и Т получаются следующим образом,Устанавливаем Чо = О, Сжимаемстроку р, матрицы Р. Для этого востроке рвыделяем подстроки Ро Рор, , цз последовательно распо-,ложенных один за другим одица 1 совыхэлементов. Просматривая строку рослева направо, в координаты гг ,г, Г, г ,векторов К и.Тпоследовательно выписывают:в координату г - индекс 1 с столбцакк,последнего элемента подстроки рон координату г 1,- сумму всех элементов строки р- от роь до р т евеличинуР,С 11 О 1Пусть при сжатии строки р в К иоТ аь 1 писаны по о значений, где /3, -число подс грок ц строке р , Устанаволиваем Ч;Аналогично р сжимаем строку р,и в векторах К и Т выписываем соответствующ 11 е значения. Пусть , - числоподстрок строки РУстанавливаем Ч = Ч 1 + 8Аналогичным образом сжимаем строкиО,р определяя значения коор 1динат г,г г р 1 +гф,+р,+,вг,р,+р,1,,гр, ,+,1, а также 1 1о+(,Ф 1 ъ+1 3 фр г 1 ъо. 1При этОм Ч, = Ч 2 + 2Ч = Ч +еЧ 11.= Ч о. я. + ( о-аБектор Ц загружается в блок 4 памяти, вектор К - в блок 3 памяти, вектор Т - в блок 2 памяти, причем в память заносятся значения М гдесо - числители дробей вида г = юс 2Разрядность и число слов блоков2 - 4 памяти определяются из следующих рассуждений,5 15Число координат вектора Ц равно и.Число координат вектора Р и вектораТ зависят от средней длины (т.еотчисла элементов) 1 подстрок вида р".1матрицы Р. Вектор К(Т) содержит столько координат, сколько подстрок видар можно выделить в матрице Р. Число1Я.,подстрок определяется как и /1, гдеи - общее число элементов матрицы Р.Я Координаты Ч вектора Ц принимаютгзначения в диапазоне от 0 до и /1.Следовательно, разрядность блока 4памяти, в котором хранится векторопределяется как )1 оя и /1, гдетообозначает ближайшее целое в сторонуувеличения.Координаты г вектора К принимаютзначения от 0 до и, Следовательно,разрядность блока 3 памяти, в которомхранится вектор К, определяется как11 ор и.Координаты с вектора Т имеют разрядность ш,Начальное состояние Б цепи Маркова задается следующим образом.В счетчик 7 загружается код Е состояния Б . При этом на выходе блока4 памяти появляется координата Ят.е, указатель начала строки р вблоках 2 и 3 памяти. На этом процессе загрузки исходных данных завершен,Работа генератора сводится к реализации алгоритма управления (фиг. 2)С приходом на управляющий вход генератора сигнала "Пуск" блок 10 управления переходит в состояние а ивырабатывает управляющие сигналы"Прием" в счетчик 1, "Опрос" датчика5 равномерно распределенных случайныхчисел,1Сигнал поступает на стробирующийвыход генератора, указывая что на егоинформационном выходе установленосостояние в . При этом в счетчик 1записывается координата Ч, поступающая с выхода блока 4 памяти. Изменение содержимого счетчика 1 запускает процесс чтения из блоков 2 и 3 памяти. На выходе блока 2 памяти появляется координата т вектора К, т.е. индекс столбца правого элемента цеопочки р, а на выходе блока 3 памяти - значение соответствующей координаты вектора Т, т,е. сумма вида ,) р , Датчик 5 вырабатываетво И50 55 Таким образом, к моменту, когда блок 10 управления переходит в состояние а, в счетчике 7 находится индекс Ь правого элемента послепней подстроки р, для которой х) . рФсо И а на выходе блока 3 памяти - индекс Ь следующей подстроки р такой, что х 6ро 31093она своем выходе некоторое случайноечисло хВ зависимости от признака сравнения блок управления переходит в5,состояние а либо в состояние ат.Допустим, что первая схема 6 сравнения выработала признак " Й ", т.е.Ихр . Блок 10 управления пере 10 =оходит в состояние а и выдает сигнал"Сброс" счетчика 7. При этом, содержимое счетчика 7 станет равным нулю,а на выходе блока 3 памяти установлен индекс Ь правого элемента перовой подстроки р строки р . Блок 10управления переходит в состояние а 4,Допустим, что первая схема 6 сравнения выработала признак " ) , т.е.случайное число х с выхода латчикаи5 больше, чем числор с выхоо:ода блока 2 памяти. Тогда блок 10 управления переходит в состояние а и25 выдает управляющие сигналы Приемв счетчик 7 и "+1" в счетчик 1. Приэтом в счетчике 7 с выхода блока 3памяти записывается индекс Ь правоьго элемента подстроки р, а содержимое счетчика 1 увеличивается на 1.Изменение содержимого счетчика 1вновь запускает процесс чтения изблоков 2 и 3 памяти. При этом на выходе блока 3 памяти появляется ин 1лекс Ь правого элемента строки р,а на выходе блока 2 памяти - значениеЬр для подстроки р . Перваяо.:о фсхема 6 сравнения вырабатывает приз 40 нак "( " либо " ". Ес вырабатывается признак " г ", т.е. К ),К. Р для,о,:оподстроки р, блок управления опятьвырабатывает управляющие сигналы45 Прием в счетчик 7 и +1 в счетчик1 (состояние а) и т.д. Если же вырабатывается признак "с ", блок 10 управления переходит в состояние аВ состоянии а блок 1 О управления задает сигнал "+1" в счетчик 7, увеличивая тем самым индекс Ь на единицу. Блок 10 управления переходит в состоя 5 ние аТаким образом, к моменту перехода в состояние а в счетчике 7 находитфся индекс Ь" столбца первого (левого) элемента подстроки р, а на выходе блока 3 памяти - индекс Ь столбца правого (последнего) элемента подстроки рВ состоянии а блок 10 управления выдает сигнал "11 рием" в счетчик 9. При этом в счетчик 9 переписывается содержимое счетчика 7, т,е. в счетчик 9 записывается значение индекса Ь" первого элемента подстроки р.Вторая схема 11 сравнения, айали 1эируя индекс Ь , поступающий со счетчика 9, и индекс Ь, поступающий с выхода блока 3 памяти, вырабатывает признак "=" либоПредположим, что вторая схема 11 сравнения выработала признак "=. тонзначит, что Ь = Ь, т.ецепочка р состоит из одного элемента. Следовательно, очередным состоянием цепи Маркова будет состояние в 1,. При этом блок 10 управления вновь переходит в состояние а, и выдает сигналы Прием" в счетчик 1 и "Пуск" генератора 5, Одновременно сигнал поступает на стробирующий выход генератора, указывая, что на информационном выходе генератора со счетчика 7 посту пает очередное состояние вЬ цепи Маркова.Предположим, что вторая схема 11н40 сравнения вырабатывает признак Это означает, что ЬЬ и следующимсостоянием цепи Маркова будет одно из состояний в ,нву в 1 р при чем указанные состояния являются рав 45 новероятными (цепочка р состоит из одинаковых элементов). При признакена выходе второй схемы 11 сравнения блок 10 управления переходит в состояние а и вырабатывает управляющие сигналы Опрос датчика 8 и +1 50 в счетчик 9. При этом на выходе датчика 8 с вероятностью 1/2 вырабатывается значение "1", а содержимое счетчика 9 становится равным Ь + 1.Если выход датчика 8 равен "1", блок 10 управления переходит в состояние а и вырабатывает сигнал "+1" вбсчетчик 7. Если же выход датчика 8 равен "0", увеличение содержимогосчетчика 7 не выполняется. Т;.ким бразом, при каждом опросе датчика 8 содержимое счетчика 7 с вероятностью1/2 увеличивается на единицуПосле анализа выход датчика 8 иувеличения при необходимости содержимого счетчика 7 выполняется сравнение текущего содержимого счетчика 9и выхода блока 4 памяти,Вторая схема 11 сравнения, сравнивая содержимое счетчика 9, т.е.значение Ь +1, со зна 1 ением с выхода блока 3 памяти, т.е. со значением Ь, вырабатывает признак "=" либоснЕсли вырабатывается признакблок 10 управления переходит в состояние а , вырабатывая сигналы "Прием"в счетчик 1 и "Пуск" датчика 5. Сигнал одновременно поступает на стробирующий выход генератора, указывая,что на его информационном выходе установлен код (,) следующего состоянияБр цепи Маркова. На этом цикл выработки очередного состояния цепи Маркова завершен, С состояния а 1 блок10 управления начинает цикл выработки следующего состояния цепи Маркова, эаписыва в счетчик 1 значениекоординаты ис выхода блока 4 памяти и т,д,Если же вырабатывается признакблок управления вновь переходитв состояние а 5, увеличивает содержимое счетчика 9 и осуществляет опросдатчика Ц, Если на входе датчика 8выработалась "1", содержимое счетчика 7 увеличивается на единицу, а впротивном случае остается без изменений и т.д. Таким образом, последовательный опрос датчика 8 и увеличениесодержимого счетчика 7 выполняетсядля Ь , Ь" + 1Ь . При этом всчетчике 7 формируется число Я , равномерно распределенное в интервалеЬ .Ь, которое является кодом следующего состояния цепи.Предлагаемый генератор позволяетполучать случайныепроцессы,описывае-.мые не только квазиразряженнымиматрицами, как в известном,но и случайные процессы, описываемые матрицами, содержащие любые повторяющиеся элементы .При этом расширение функциональныхвозможностей достигается без увеличения объема оборудования и снижениябыстродействия,Ф орм у л а и з о б р е т е и и яенератор случайного маркОвского процесса, содержащий датчик равномерно распределенных случайных чисел,5 блок управления, три блока памяти, схему сравнения и счетчик, причем вход пуска генератора соединен с входом пуска блока управления, первый логический вход которого соединен с выходом Больше схемы сравнения, первый информационный вход которой соединен с информационным выходом датчика равномерно распределенных слу,чайных чисел, вход опроса которого соединен с первым выходом блока управления, второй выход которого является стробирующим выходом генератора и соединен с установочным входом счетчика, счетный вход которого соединен с третьим выходом блока управления, выход первого блока памяти соединен с информационным входом счет" чика, выход которого соединен с адресными входами второго и третьего 25 блоков памяти, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных воэможностей за счет получения случайных процессов, описываемых стохастическими матрицами перехо дов, не являющимися квазиразрвкенными, в него введены второй и третий счетчики, вторая схема сравнения и датчикравновероятной двоичной цифры, причемвыход второго блока памяти соединен свторым информационным входом первойсхемы сравнения, выход третьего блока памяти соединен с информационнымвходом второго счетчика и первым информационным входом второй схемы сравнения, выход "Равно" которой соединен с вторым логическим входом блокауправления, четвертый выход которогосоединен с входом опроса датчика равновероятной двоичной цифры, выход которого соединен с третьим логическимвходом блока управления, пятый выходкоторого соединен с входом обнулениявторого счетчика, выход которого является информационным выходом генератора и соединен с адресным входом первого блока памяти и информационнымвходом третьего счетчика, вход записи которого соединен с шестым вь.ходомблока управления, седьмой выход которого соединен с входом записи второго счетчика, счетный вход которогосоединен с восьмым выходом блока управления, девятый выход которого соединен с счетным вкодом третьего счетчика, выход которого соединен с вторым информационным входом второй схе.мы сравнения.1531093 а.2 оставитель Д. Феликсехред М.Ходанич едакт улл ктор М. Пож оизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 Заказ 8028/50 Тираж,668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5