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

(21) (22) (46) кий нич р они ССР1973,ССР1969.РКОВСК Г ГОСУДАРСТВЕННЫЙ НОМИТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТПРИ ГКНТ СССР А ВТОРСНОМУ СВИДЕТЕЛЬСТВ(71) Кишиневскии политех есинститут им. С.Лазо(54) ГЕНЕРАТОР СЛУЧАЙНОГО МАПРОЦЕССА(57) Изобретение относится к авт тике и вычислительной технике и можетиспользоваться для генерации входныхпоследовательностей или стохастическомконтроле дискретных объектов, Цельизобретения - упрощение устройствадля моделирования цепей Маркова. Длядостижения поставленной цели в устройство введены два блока памяти 10 и11, схема сравнения 6, два накапливающих сумматора 4 и 7, мультиплексор5, счетчик 12, при этом осуществляетсяснижение объема памяти, необходимогодля хранения квазинапряженных стохастических матриц при сильном разбросе значений вероятностей переходов,Блок управления работает по приведенному алгоритму и реализован как автомат Мура. 2 ил.Изобретение относится к автоматикеи вычислительной технике и может использоваться для генерации входныхпоследовательностей при стохастическом контроле дискретных объектов,Цель изобретения - упрощение устройства для моделирования цепей Мар-.кова.На фиг. 1 представлена структурная 10схема предлагаемого генератора, нафиг. 2 - алгоритм работы блока управления,Генератор случайного марковскогопроцесса содержит блок 1 управления, 15; дешифраторы 2 и 3 накапливающий сум матор 4, мультиплексор 5 схему 6сравнения, накапливающий сумматор 7фгенератор 8 равномерно распределенныхчисел, блок 9 памяти блок 10 памяти 20частоты появлений, блок 11 памяти элементов строк, счетчик 12 и регистр 13.Генератор работает следующим об, разом.Пусть задан марковский процесс, ,25описываемый конечным множеством состоянии 8 Б 1р 1 Орп 1 и стохастической матрицей переходов Р = Р"111 ), где Р, - вероятность перехода эаодин такт из состояния з, в состояние з 3=0,п, Р;" = М.; 2где с; - целое, щ - параметр, определяющий точность представления элементов матрицы.Матрица Р хранится в сжатом видев виде векторов ( = 1 с 1 цЦ , К = 11 геи т = 11 г .Вектор Ц загружается в блок 9 памяти.Вектор К загружается в блок 10 па. -мяти частоты появлений.4 ОВектор Т загружается в блок 11 памяти элементов строк, причем в памятьзаписываются только все - 1, где еечислители дробей вида Се = о 2е фПеред началом работы векторы Я,К, и Т вычисляются и загружаются всоответствующие блоки 9-11 памяти(устройство загрузки не показано), Фоновый элемент со знаком ",-" записывается в дополнительном коде в ре-.гистр 13Начальное 1 остояние з цепи задается следующим образом, В накапливающий сумматор 4 загружают код Г состояния з . При этом на выходе блока9 памяти появляется координата ц,т.е, указатель начала строки з вблоках 10 и 11 памяти. На этом процесс загрузки исход-ных данных завершен.Блок 1 управления представляет собой микроцрограммный автомат с состояниями а а а а , а , а . иработает по алгоритму представленному на фиг, 2,После загрузки начального состояния блок 1 управления находится всостоянии а. С приходом первого тактирующего сигнала в блоке управленияна его выходе "Запуск" и седьмом выходе появляется сигнал "1", которыйпоступает на вход "Опрос генератора8 равномерно распределенных чисел ина управляющий вход счетчика 12, Приэтом генератор 8 равномерно распре"деленных чисел вырабатывает щ-разрядное двоичное число Е = х 2 и)величина х подается на второй входсхемы 6 сравнения. Одновременно всчетчик 12 записывается координатапо которой выполняется обращениек блоку О памяти частоты появленийи к блоку 11 памяти элементов строк.На выходе блока 10 памяти частотыпоявлений появляется координата г,соответствующая первому элементу сжатой строки Р, а на выходе блока. 11памяти элементов строк появляется координата С, соответствующая первомуэлементу строки Р . Сигнал в счетчик12 также подается на стробирующийвыход генератора с тем, чтобы указать, что получено очередное состояние цепи Маркова,Очередной тактовый сигнал устанавливает блок 1 управления в состояниеа.С приходом следующего тактовогосигнала будут поданы управляющиесигналы на первый управляющий входмультиплексора 5, на первый управляющий вход накапливающего сумматора4, на первый управляющий вход накапливающего сумматора 7, При этом внакапливающий сумматорзаписывается считанная из блбка 11 памяти элементов строк координатавектора Т,которая поступает на первый вход схе"мы 6 сравнения, а в накапливающий сумматор 4 - координата г которая поступает на блок 9 памяти,Очередной тактовый сигнал в зависимости от признака сравнения, поступающего от схемы 6 сравнения, переключает блок 1 управления в одно изследующих состояний: при признаке03 состояние а,. Если схема б сравнения вырабатыв а е т признак сравнения " = , т о вна капливающем сумматоре 4 хранитсякод состояния цепи , увеличенный наединицу, поэтому блок 1 управления ,по приходу тактового сигнала , переходит в с о с т ояние а ,55 14534(число от генератора 8 равномернораспределенных чисел больше числа отнакапливающего сумматора 7) - в состояние а при признаке "=" (числоот генератора 8 равномерно распределенных чисел равно числу от накапли- .вающего сумматора 7) - в состояниеа, при признаке" (число от генератора 8 равномерно распределенных 10чисел меньше числа от накапливающегосумматора 7). - в состояние аВ состоянии аг из блока 1 управления при приходе очередного тактовогосигнала подается управляющий сигнал 15в сче.чик 12, в результате чего егосодержимое увеличивается на единицу,Из блоков 10 и 11 памяти считываютсяочередные координаты г и С строки Р .По заднему Фронту тактового сигнала 20блок 1 управления переходит в состояние а .При этом в;дддаются сигналына первый .управляющий вход мультиплексора 5, на первый управляющий входнакапливающего сумматора 7, на второй управляющий вход накапливающегосумматора 4 соответственно, Тем самым в накапливающем сумматоре 4 путем сложения координат вектора К формируется номер возможного будущего 30состояния цепи Маркова, а в накапливающем сумматоре 7 хранится очереднаякоордината вектора Т.В зивисимости от признака сравнения с приходом тактирующего сигналапосле состояния аэ блок 1 управленияпереходит либо в состояние аг(признак), либо в состояние а (признак1"="). либо в состояние а (признак) 40Таким образом, смена состоянийа -а обеспечивает поиск в сжатойг Эстроке Р такой координатывектора Т. для которой х с сз,Если х = -, блок 1 управления 45после состояния а или а, с приходомтактового сигнала перейдет в состояние а. При этом будут выработаны управляющие сигналы на второй управляющий вход накапливающего сумматора 4и на второй управляющий вход мультиплексора 5, которые сформируют в накапливающем сумматоре 4 очередное состояние цепи Маркова,которого надинается очередной циктд работы генератора.1.,сли х с В и коорддднята ь соот ветствует базовому элементу либо подстроке, состоящей иэ ровно одного фонового элемента, т,е, г = 1, на выходе дешифратора 2 вырабатывается "1",и после состояния ац или а по заднему Фронту тактируюшего сигналаблок 1 управления также переходит в состояние аЕсли х с С , но координата соответствует подстроке иэ фоновых элементов с длиной больше 1, т.е,1, блок 1 управления с приходом тактирующего сигнала после состояния а, или а, переходит в состояние а,.В состоянии а с приходом очереднсго тактирующего сигнала выдаются сигналы; на второй управляющий вход накапливающего сумматора 4, на второй управляющий вход накапливающго сумматора 7, на второй управляюдций вход мультиплексора 5, чем обеспечивается последовательное формирование в накаддливающи смматоре 4 номеров возможных будущих состояний цепи, которые быдп сжаты д которые в явном виде не хранятс;, 1 тдддавременно из содержимого накапливающегосумматора 7 вычитается Фоновый элемент Ь , Формиру.,: тем самым промежуточные модифицированные значения вероятностей переходов именно в те состояния,. номера которых хранятся в накапливающем сумматоре 4.С приходом тактового сигнала иэ состояния а блок 1 управления может перейти в одно иэ состояний а, а, либо а . Если схема б сравнения вырабатывает признак сравнения )", в накапливающем сумматоре 4 сформирован код следующего состояния цепи Маркова, и блок 1 управления с появлением тактового сигнала переходит вС приходом очередного тактового сигнала блок 1 управления из состояния а переходит в состояние а, сЕсли схема б сравнения вырабатывает признак сравнения "с", то возможны два случая.03 14534Если признак выработаны для состояния в , т.е, подстрока из фоновых элементов находится в начале строки Р и следующим состоянием це 5 пи Маркова будет состояние в на вью ф ходе дешифратора 3 вырабатывается ев ц1, и блок 1 управления с приходом тактового сигнала переходит в состояНие а 10В противном случае блок 1 управления остается в состоянии а и вновь из накапливающего сумматора 7 вычи: - тается фоновый элемент, из накапливающего сумматора 4 вычитается едини Ца анализируется признак сравнения И, т.д. Цикл выработки очередного состоя,ния цепи Маркова завершается с переходом блока 1 управления в состояние ав, 11 ри этом сигнал на информационном выходе генератора указывает, что получено очередное состояние цепи.25 Главным технико-экономическим преиМуществом предлагаемого генератора по сравнению с известным является с жение объема памяти, необходимогоя хранения квазиразряженных стохастнческих матриц переходов при силь- нЬм разбросе значений вероятностей переходов. Формула изобретения Генератор случайного марковского процесса, содержащий генератор равномерно распределенных случайных чисел, регистр, блок управления, первый дешифратор и блок памяти, о т л и ч а ющ и й с я тем, что, с целью упрощения, он содержит блок памяти частоты появлений, блок памяти элементов строк 445 схему сравнения, два накапливающих сумматора, второй дешифратор, мультиппексор, счетчик, выход которого соединен с адресными входами блока памяти частоты поя:вления и блока памяти50 эпементов строк, выход блока памятичастоты появления соединен с входомпервого дешифратора и первым информационным входом мультиплексора, выходблока памяти элементов строк соединен с первым информационным входомпервого накапливающего сумматора,торой информационный вход которогосоединен с выходом регистра, выходпервого накапливающего. сумматорасоединен с первым входом схемы сравнения, выход которой соединен с первым логическим входом блока управления, выход Запуск которого соединен с входом "Опрос" генератораравномерно распределенных .случайныхчисел,-выход которого соединен с вторым входом схемы сравнения; выходпервого дешифратора соединен с вторым логическим входом блока управления, выход мультиплексора соединен синформационным входом второго накапливающего сумматора, выход которогоявляется информационным выходом генератора и соединен с входом второгодешифратора и адресным входом блокапамяти, выход которого соединен с информационным входом счетчика, выходвторого дешифратора соединен с третьим логическим входом блока управления, второй информационный входмультиплексора соединен с задатчикомконстанты "1", первый выход блокауправления соединен с первым управляющим входом первого накапливающегосумматора, второй выход блока управления соединен с вторым управляющимвходом первого накапливающего сумматора, третий и четвертый выходыблока управления соединены соответственно с первым и вторым управляющимивходами мультиплексора, пятый и шестой выходы блока управления соединенысоответственно с первым и вторым управляющими входами второго накапливающего сумматора, седьмой выход блока управления является стробирующимвыходом генератора и соединен с управляющим входом снетчика, восьмойвыход блока управления соединен стактирующим входом счетчика.1453403 Составитель Д.феликсонТехред Л.Олийнык Корректор В, Бутяга Редакто уп 6 46 Подписно ка ВНИИ с удар с л. Проектная,изводственно-полиграфическое предприятие, г. Ужгор Тираж 667енного комитета п 13035, Москва, Жизобретениям и открытиям при ГКНТ ССС Раушская наб., д, 4/5