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

 

Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей или стохастическом контроле дискретных объектов. Цель изобретения - упрощение устройства для моделирования цепей Маркова. Для достижения поставленной цели в устройство введены два блока памяти 10 и 11, схема сравнения 6, два накапливающих сумматора 4 и 7, мультиплексор 5, счетчик 12, при этом осуществляется снижение объема памяти, необходимого для хранения квазинапряженных стохастических матриц при сильном разбросе значений вероятностей переходов. Блок управления работает по приведенному алгоритму и реализован как автомат Мура. 2 ил. € (Л

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК цц 4 G 06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4267660/24-24 (22) 24,06.87 (46) 23.01.89. Бюл. М 3 (71) Кишиневский политехнический институт им. С.Лазо (72) А.А.Гремальский и С.M.Àíäðîíèê (53) 681.325(088.8) (56) Майоров С.А,, Новиков Г.Н, Структура электронных вычислительных машин. — Л.: Машиностроение, 1979, с. 384.

Авторское свидетельство СССР

У 451085, кл. С 06 F 15/20, 1973.

Авторское свидетельство СССР

М 290281, кл. С 06 F 15/36, 1969. (54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО

ПРОЦЕССА (57) Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей или стохастическом контроле дискретных объектов, Цель изобретения — упрощение устройства для моделирования цепей Маркова. Для достижения поставленной цели в устройство введены два блока памяти 10 и

11, схема сравнения 6, два накапливающих сумматора 4 и 7, мультиплексор

5, счетчик 12, при этом осуществляется снижение объема памяти, необходимого для хранения квазинапряженных стохастических матриц при сильном разбросе значений вероятностей переходов, Блок управления работает по приведенЖ ному алгоритму и реализован как автомат Мура. 2 ил.

1453403

Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастичес5 ком контроле дискретных объектов.

Цель изобретения — упрощение устройства для моделирования цепей Мар-. кова.

На фиг. 1 представлена структурная >g схема предлагаемого генератора, на фиг. 2 — алгоритм работы блока управления.

Генератор случайного марковского процесса содержит блок 1 управления, 15, дешифраторы 2 и 3„ накапливающий сум матор 4, мультиплексор 5„ схему 6 сравнения, накапливающий сумматор 7, генератор 8 равномерно распределенных чисел, блок 9 памяти„ блок 10 памяти 20 частоты появлений, блок 11 памяти эле ментов строк, счетчик 12 и регистр 13.

Генератор работает следующим об, разом.

Пусть задан марковский процесс,,25 описываемый конечным множеством состояний S = $S;), i = On-1 и стохас" тической матрицей переходов Р = !1Р"11

1) j

: где Р; — вероятность перехода эа один такт из состояния s; в состояние s>,i j=O,n-t, Р;" = о 2 где сС; — целое, m — параметр, определяющий точность представления элементов матрицы.

Матрица P:х:ранится в сжатом виде в виде векторов q = IiqцЦ, R = 1! г,ti и Т = (! Jf

Вектор Ц загружается в блок 9 памяти.

Вектор R загружается в блок 10 па.—

4О мяти частоты появлений.

Вектор Т загружается в блок 11 памяти элементов строк, причем в память записываются только осе — 1, где <е числители дробей вида tе = о 2 е

Перед началом работы векторы Я, R, и Т вычисляются и загружаются в соответствующие блоки 9-11 памяти (устройство загрузки не показано). Фоновый элемент со знаком " .-" записывается в дополнительном коде в ре-. гистр 13 i

Начальное остояние s< цепи задается следующим образом. В накапливающий сумматор 4 загружают код f состояния s . При этом на выходе блока

9 памяти появляется координата q, т.е. указатель начала строки sf в блоках 10 и 11 памяти. На этом процесс загрузки исходных данных завершен.

Блок 1 управления представляет собой микроцрограммный автомат с состояниями а,, а,, а,, а, а, а и работает по алгоритму представленному на фиг, 2.

Ifoc e загрузки начального состояния блок 1 управления находится в состоянии а„. С приходом первого тактирующего сигнала в блоке управления на его выходе "Запуск" и седьмом выходе появляется сигнал "1", который поступает на вход "Опрос генератора

8 равномерно распределенных чисел и на управляющий вход счетчика 12. При этом генератор 8 равномерно распределенных чисел вырабатывает m-разрядное двоичное число Z = х .2 и

J У величина х подается на второй вход ,1 схемы 6 сравнения. Одновременно в счетчик 12 записывается координата по которой выполняется обращение к блоку !О памяти частоты появлений и к блоку 11 памяти элементов строк.

На выходе блока 10 памяти частоты появлений появляется координата r, соответствующая первому элементу сжатой строки Р, а на выходе блока. 11 памяти элементов строк появляется координата С, соответствующая первому элементу строки Р . Сигнал в счетчик

12 также подается на стробирующий выход генератора с тем, чтобы указать, что получено очередное состояние цепи Маркова.

Очередной тактовый сигнал устанавливает блок 1 управления в состояние а .

С приходом следующего тактового сигнала будут поданы управляющие сигналы на первый управляющий вход мультиплексора 5, на первый управляющий вход накапливающего сумматора

4, на первый управляющий вход накапливающегб сумматора 7, При этом в накапливающий сумматор 7 записывается считанная из блбка 11 памяти элементов строк координата t вектора Т, которая поступает на первый вход схемы 6 сравнения, а в накапливающий сумматор 4 — координата r которая поступает на блок 9 памяти.

Очередной тактовый сигнал в зависимости от признака сравнения, поступающего от схемы 6 сравнения, переключает блок 1 управления в одно из следующих состояний: при признаке

03 состояние а,.

Если схема б сравнения вырабаты-!! !! в а е т признак сравнения " =, т о в накапливающем сумматоре 4 хранится код состояния цепи, увеличенный на единицу, поэтому блок 1 управления, по приходу тактового сигнала, переходит в с о с т Ояние а .

14534 (число от генератора 8 равномерно распределенных чисел больше числа от накапливающего сумматора 7) — в состояние а при признаке "=" (число от генератора 8 равномерно распределенных чисел равно числу от накапли- . вающего сумматора i) — в состояние ад, при признаке " (число от генератора 8 равномерно распределенных 10 чисел меньше числа от накапливающего сумматора 7). — в состояние а

В состоянии а из блока 1 управления при приходе очередного тактового сигнала подается управляющий сигнал 15 в счетчик 12, в результате чего его содержимое увеличивается на единицу.

Из блоков 10 и i1 памяти считываются очередные координаты r и " строки Р .

По заднему фронту тактового сигнала 20 блок 1 управления переходит B состояние а . При "òîì в;!даются сигналы на первый .управляющий вход мультиплексора 5, на первый управляющий вход накапливающего сумматора 7, на второй управляющий вход накапливающего сумматора 4 соответственно. Тем самым в накапливающем сумматоре 4 путем сложения координат вектора К фор мируется номер возможного будущего 30 состояния цепи Маркова, а в накапливающем сумматоре 7 хранится очередная координата вектора Т.

В зивисимости от признака сравнения с приходом тактирующего сигнала после состояния а блок 1 управления переходит либо в состояние а (признак

">"), либо в состояние а (признак "="). либо в состояние а (признак !!„ !! ) 40

Таким образом, смена состояний а -а обеспечивает поиск в сжатой

2 Э строке Р такой координаты t> вектоf

PB T ДЛЯ кОТОРОи х С !»»

Если х„= t,, блок управления после состояния а или а, с приходом тактового сигнала перейдет в состояние а . При этом будут выработаны управляющие сигналы на второй управляющий вход накапливающего сумматора 4 и на второй управляющий вход мультиплексора 5, которые сформируют в накапливающем сумматоре 4 очередное состояние цепи Маркова, которого начинается очередной цикл работы генератора. сли х (t 6 H координата t сООТ) ветствует базовому элементу либо подстроке, состоящей иэ ровно одного фонового элемента, т.е, r = 1, на выходе де:ыфратора 2 вырабатывается "1

v, после состояния ац или а по заднему фронту тактируюшего сигнала блок 1 управления также переходит в состояние а

Если х с t но координата соответствует подстроке иэ фоновых элементов с длиной больше 1, т.е, 1, блок 1 управления с приходом тактирующего сигнала после состояния а, или à, :åð,åõîäèò в состояние а,.

В состоянии а с приходом очереднсго тактирующего сигнала выдаются сигналы: на второй управпяющий вход накапливающего сумматора 4, на второй управляющий вход накапливающего сумматора 7, на второй управля!ощий вход мультиплексора 5, чем обеспечивается последовательное формирование в накапливающем сумматоре 4 номеров возможных будущих состояний цепи, которые бы!и. сжаты которые в явном виде не храня-,ñ;, !1дновременно из содержимого накапливающего сумматора ! вычитается фоновый элемент Ь, формиру.", тем самым промежуточные модифицированные значения вероятностей переходов именно в те состояния, номера которых хранятся в накапливя; щем сумматоре 4.

С приходом тактового сигнала из сос-:îÿíèÿ а блок 1 управления .îæåò перейти в одно из состояний а, а, либо a.. . Если схема б сравнения вырабатывает признак сравнения в накапливающем сумматоре 4 сформирован код следующего состояния цепи

Маркова, и блок 1 управления с появлением тактового сигнала переходит в

С приходом очередного тактового сигнала блок 1.управления из состояния а< переходит в состояние а, с!

Если схема б сравнения вырабатывает признак сравнения "(", то возможны два случая.

14534

Если признак "(" выработаны для состояния s т. е, подстрока из фоновых элементов находится в начале строки Р» и следующим состоянием це5 пи Маркова будет состояние s на вью ходе дешифратора 3 вырабатывается

II lt

1, и блок 1 управления с приходом ч актового сигнала переходит в состоя4

В противном случае блок 1 управления остается в состоянии а и вновь

5 из накапливающего сумматора 7 вычи:— тается фоновый элемент, из накапливающего сумматора 4 вычитается едини- 15

Ца анализируется признак сравнения и," т.д.

Цикл выработки очередного состоя-. ,ния цепи Маркова завершается с переходом блока 1 управления в состояние ад, При этом сигнал на информационном выходе генера-ора указывает, что по.лучено очередное состояние цепи.

Главным технико-экономическим преи1 уществом предлагаемого генератора по сравнению с известным является с жение объема памяти, необходимого я хранения квазиразряженных стохастнческих матриц переходов при силь- нЬм разбросе значений вероятностей переходов.

З5

Формула изобретения

Генератор случайного марковского процесса, содержащий генератор равномерно распределенных случайных чисел, регистр, блок управления, первый дешифратор и блок памяти, о т л и ч а юшийся тем, что, с целью упрощения, он содержит блок памяти частоты появлений, блок памяти элементов строк „

45 схему сравнения, два накапливающих сумматора, второй дешифратор, мультиппексор, счетчик, выход которого соединен с адресными входами блока памяти частоты появления и блока памяти

50 эпементов строк, выход блока памяти ! частоты появления соединен с входом первого дешифратора и первым информационным входом мультиплексора выход блока памяти элементов строк соединен с первым информационным входом первого накапливающего сумматора, торой информационный вход которого соединен с выходом регистра, выход первого накапливающего. сумматора соединен с первым входом схемы сравнения, выход которой соединен с первым логическим входом блока управления, выход Запуск которого соединен с входом "Опрос" генератора равномерно распределенных .случайных чисел, -выход которого соединен с вторым входом схемы сравнения, выход первого дешифратора соединен с вторым логическим входом блока управления, выход мультиплексора соединен с информационным входом второго накапливающего сумматора, выход которого является информационным выходом генератора и соединен с входом второго дешифратора и адресным входом блока памяти, выход которого соединен с информационным входом счетчика, выход второго дешифратора соединен с третьим логическим входом блока управления, второй информационный вход мультиплексора соединен с задатчиком константы "1", первый выход блока управления соединен с первым управляющим входом первого накапливающегс сумматора, второй выход блока управления соединен с вторым управляющим входом первого накапливающего сумматора, третий и четвертый выходы блока управления соединены соответственно с первым и вторым управляющими входами мультиплексора, пятый и шестой выходы блока управления соединены соответственно с первым и вторым управляющими входами второго накапливающего сумматора, седьмой выход блока управления является стробирующим выходом генератора и соединен с управляющим входом снетчика, восьмой выход блока управления соединен с тактирующим входом счетчика.

1453403

Составитель Д.Феликсон

Редактор Н.Тупица Техред JI.Олийнык Корректор В, Бутяга

Заказ 7286/46 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4