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

 

Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации случайных марковских процессов, описанных квазиразряженными матрицами при стохастическом контроле логических объектов . Цель изобретения - повышение быстродействия генератора. Для достижения поставленной цели в генератор введены накапливающий сумматор-вычитатель, элемент ИЛИ, регистр сдвига. Выработка очередного состояния цепи Маркова выполняется путем просмотра модифицированных строк матрицы переходных вероятностей методом половинного деления. 2 ил.

„„SU„„1619263

СОВа СОВЕТСНИХ

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

РЕСПУ БЛИН

А1 щ) G 06 F 7/58

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

s. 50i4":- . : .

rig jill }! ) . 1 е ХЕЛь!О Е!;А

Н А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ

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

r1O ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 464237$/24 (22) 24.01.89 (46) 07.01.91. Бюл. Р 1 (71) Кишиневский политехнический институт им. С.Лазо (72) А.А.Гремальский и С.М.Андроник (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 290281, кл. G 06 F 15/36, 1970.

Авторское свидетельство СССР . Ф 1453403, кл. G 06 F 7/58, 1987. (54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО ПРОЦЕССА (57) Изобретение относится к автоматиИзобретение относится к автоматике и вычислительной технике и может использоваться для генерации случайных марковских процессов, описанных квазиразряженными матрицами при стохастическом контроле дискретных объектов.

Целью изобретения является повышение быстродействия генератора за счет направленного перебора элементов матрицы переходных вероятностей.

На фиг.l представлена структурная схема генератора; на фиг.2 — блоксхема алгоритма работы блока управлеHHH °

Генератор случайного марковского процесса содержит блок 1 управления, дешифратор 2, счетчик 3, схему 4 сравнения, накапливающий. сумматор 5, датчик 6 равномерно распределенных случайных чисел, регистр 7 памяти, блок 8 памяти с выходами 8.1 старших разря2 ке и вычислительной технике и может использоваться для генерации случайных марковских процессов, описанных квазиразряженными матрицами при стохастическом контроле логических объектов. Цель изобретения — повышение быстродействия генератора. Для достижения поставленной цели в генератор введены накапливающий сумматор-вычитатель, элемент ИЛИ, регистр сдвига.

Выработка очередного состояния цепи

Маркова выполняется путем просмотра модифицированных строк матрицы переходных вероятностей методом половинного деления. 2 ил. дов и 8.2 мпадших разрядов, блок 9 памяти с выходами 9.1 старших разрядов и 9.2 младшего (нулевого) разряда, блок 10 памяти элементов строк, >,ы накапливающий сумматор-вычитатель ll, ©1 элемент ИЛИ 12, регистр 13 сдвига с выходами 13.1 старших разрядов и 13,2 1 р младшего (нулевого) разряда.

Блок 1 управления обеспечивает управление процессом порождения случайного марковского процесса и представляет собой микропрограммный автомат с жесткой логикой,. реализующий алгоритм управления, блок-схема которого приведена на фиг.2.

Блок I управления имеет множество внутренних состояний (а, а<, а, а э, а, а, а а, а, °

В состоянии а блок 1 управления выдает сигнал "Запись" в регистр 13 сдвига и в накапливающий сумматорвычитатель 11 °

1619263

В состоянии aI блок 1 управления выдает сигналы: "Запуск" на датчик 6 равномерно распределенных случайных чисел и "Сложить" на накапливающий сумматор-вычитатель 11.

В состоянии а блок 1 управления выдает сигнал "Запись" в счетчик 3 и в накапливающий сумматор 5.

В состоянии а блок 1 управления выдает сигналы "Сдвиг" на регистр 13 сдвига и "Сложить" на накапливающий сумматор-вычитатель 11.

В состоянии а блок 1 управления выдает сигналы "Сдвиг" на регистр 13

15 сдвига и "Вычесть" на накапливающий сумматор-вычитатель 11.

В состоянии а„ блок 1 управления выдает сигнал "Съ жить" на накапливающий сумматор-вычитатель 11.

В состоянии аб блок 1 управления выдает сигнал "Запись" в счетчик 3 и в накапливающий сумматор 5.

В состоянии а7 блок 1 управления выдает сигналы Вычесть" на счет- 25 чик 3 и "Сложить" на накапливающий сумматор 5.

Накапливающий сумматор 5 предназначен для формирования и хранения модифицированных элементов стохастической матрицы переходов. При подаче управляющего сигнала "Запись" на накапливающий сумматор 5 в нем записы" вается информация, поступающая с выхода блока 10 памяти элементов строк.

При подаче на накапливающий сумматор 5 управляющего сигнала "Сло:кить" к текущему его значению добавляется значение регистра 7.

Блоки.8-10 памяти предназначены

40 для хранения в сжатой, форме стохастической матрицы переходов. Считывание информации иэ блоков 8-10 памяти происходит при поступлении соответствующих адресов на их адресные входы.

Накапливающий сумматор-вычитатель 11 предназначен для формирования и хранения адреса, по которому осуществляется обращение к блокам 9 и 10 памяти.

Регистр 13 сдвига предназначен для хранения и сдвига в сторону .млад- 50 шего разряда информации, поступающей на его информационные входы. Запись и сдзиг информации в регистр 13 осуще11 Н ствляется по сигналам Запись и

"Сдвиг" соответственно, поступающимна его управляющие входы, Генератор работает следующим образом.

Пусть задан марковский процесс, описываемый конечным множеством состояний S = (Я; i = О, и - 1 и стохастической матрицей переходов

Р = lj Р, Ij, где Р," — вероятность перехода за один такт из состояния

S, а состояние Sj х,з = О, и — l

P = 0, 1 2, где g,<1 — целое, m :параметр, определяющий точность представления элементов матрицы P.

Стохастическая матрица Р хранится в сжатом виде в виде векторов

v = tlu

jj q (j;

jj rI,jl1

R = Ц г jjð

Т = tj tÄjj.

Векторы 7, Qs Rs R и Т получают ! таким образом, что устанавливают

q = О, r = О, r, = О, t, О. Сжимают строку Р матрицы P. Для этого в строке Р, выделяют подстроки P (2 <о

Р,..., P из последовательно расположенных друг за другом фоновых элементов. Пусть в строке Ро Ко подстрок и о базовых элементов. Устанавливают о K 0 + $о °

Просматривая строку Р слева направо, в координаты rI,r<,....,r, т2,...,tI tq векторов R, R

1 I и Т последовательно выписывают:

C( если встречается подстрока Ро а = 1, К„, в R выписывают h+ l, в

R . .выписывают 1, а в Т выписывают

<Р,где h — индекс столбца

1 =О последнего элемента подстроки Ро; если встречается базовый элемент

Р<„, в R выписывают g + l в R выпи3 сывают О, а в Т выписывают Р с, l

ЬО где g — индекс столбца, где находится элемент P т. е. g = j, Пусть при сжатии строки P в R

R и Т были выписаны по значений.

Устанавливают q = Po + 1, r p „ О, °

rrp 1 = О, t, = О, Аналогично строке Рц сжимают строку Р, . Пусть в строке Р, К1подстрок и, базовых элементов. Устанавливач, =к,+,.

Просматривая строку P слева нас право в векторах R,R и Т выписывают соответствующие значения. Пусть при этом в векторах R,R и Т запиf саны по Р1 значений.

161926

Устанавливают q = P + P + 2

2.

1"< . > Oo+8 t2 . I

Pot)

Аналогичным образом сжимают стро- 5 ки Р, P,...., Р и, определяя значения координат r3 + pо+p + Ф > ° )4+ p,< p, )- r tp,t p,â

" " р-1- -) РР " 0

1

Г ) ), . гpztptp

° ° ° °,г 1,.,р л p („ ) 1 а также

" .+Д, З ° Pot%i++ "P,tg, . ро 81> pzt5 " (3аФ,+."tp t(5-1)

При этом

Я )о+ p + 1".г. + 3 q< +

+p +);

q - о+ ф + Ь+Pg+ 4= )з Р "

° ° °

=р. +P +P + " /3

+ " » Чл-а +)ï-а + а также 25

V2 Kz + +)т!

3 3 1

° ° °

) К +

rpe K< II < K> II K л-1 30 — число подстрок и число базовых элементов строк 2,3,...,п — 1 соответственно.

Векторы V u Q загружают в блок 8 памяти. При этом координаты Vp

1 = О,l 2,...,n — 1 записываются в

35 поле старших: разрядов (им соответствует выход 8.1), а координаты ц — в поле младших: разрядов (им соответствует выход 8.2) блока 8 памяти. 40

Векторы R u R загружают в блок 9 памяти. При этом координаты r записываются в поле старших разрядов (им соответствует выход 9.1), а координаты r — в поле нулевого разряда

45 (им соответствует выход 9.2) блока 9 памяти.

Вектор Т загружается в блок 10 памяти элементов строк, причем в память записываются только числители ()(», уменьшенные на единицу, дробей

-IVI вида и = М),< 2

Перед началом работы векторы V, R R и Т вычисляются и загружаются

l в соответствующие блоки 8-10 памяти (на фиг.l устройство загрузки не показано). Фоновый элемент с знаком записывается в дополнительном коде в регистр 7.

6

Начальное состояние S цепи задается следующим образом.

В счетчик 3 загружают код f состояния Sg При этом на выходе 8.1 блока 8 памяти появляется координата

V (число подстрок и базовых элемен1 тов строки Р ), а на выходе 8.2 появляется координата q (указатель начала строки Р в блоках 9 и 10 памяти.

На этом процесс загрузки исходных данных завершен.

Работа генератора сводится к реализации алгоритма управления, представленного на фиг.2, После загрузки начального состояния блок 1 управления находится в состоянии ао и появляется сигнал, который поступает на управляющие входы

"Запись" регистра 13 сдвига. и накапливающего сумматора-вычитателя 11 °

При этом в регистр 13 сдвига записывается координата Ч вектора V а в накапливающем сумматоре-вычитателе !1 записывается координата о вектора Q.

После этого блок 1 управления переходит в состояние а<. В состоянии а1 подается управляющий сигнал "Запуск" на датчик 6 равномерно распределенных случайных чисел, управляющий сигнал "Сложить" — на накапливающий сум- . матор-вычитатель ll. При этом датчик 6 вырабатывает m-разрядное двоичное число Z = х 2 и величина х

1 подается на вторую группу информационных входов схемы 4 сравнения. Одновременно в накапливающем сумматоревычитателе 11 формируется текущий адрес А, по которому выполняется обрашение к блоку 9 памяти и к блоку 10 памяти элементов строк. На выходах блока 9 памяти появляются координаты

r и г, а на выходе блока 10 памяти появляется координата t, Эти координаты находятся по адресу А = r. +

+)1) /2 + С, где С о — значение младшего разряда регистра 13 сдвига, Блок 1 управления переходит в состояние а, в котором подается управляющий сигнал Запись" в счетчик 3 и в накапливающий сумматор 5. При этом в счетчик 3 записывается считанная из блока 9 памяти координата r вектора R, которая поступает на блок 8 памяти, а в накапливающий сумматор 5 координата вектора Т, которая поступает на первый вход схемы 4 сравнения.

1619263

В зависимости от значения сигналов с выхода схемы 4 сравнения, с выхода

9.2 блока 9 памяти и с выхода элемента ИЛИ 12, поступающих на соответствующие логические входы блока 1 управ" ления, он устанавливается в одно из следующих „состояний: при признаке

" ) " (число от датчика 6 равномерно распределенных случайных чисел больше числа от накапливающего сумматора 5) и сигнале "0" на выходе элемента

ИЛИ 12 устанавливается состояние а, при признаке " ) " и сигнале "1" на выходе элемента ИЛИ 12 устанавливается состояние а, при признаке " (" (число от датчика 6 равномерно распределенных случайных чисел меньше числа от накаплив ющего сумматора 5) и сигнале "О" с выхода элемента

ИЛИ 12 устанавливается состояние а 1, при признаке =" (число от датчика 6 равномерно распределенных случайных чисел равно числу от накапливаюг:,его сумматора 5 либо при приз" наке "(" и сигналах "1" и "0" на выходе элемента ИЛИ 12 и на выходе 9.2 блока 9 памяти соответственно устанавливается состояние à, при признаке " " и сигналах "1" на выходе элемента ИЛИ 12 на выходе 9,2 блока 9 памяти устанавливается состояние ау, В состоянии аз подается управляю" щий сигнал "Сдвчг" на регистр 13 сдвига и управляющии сигнал Сложить

11 и 35 на накапливающий сумматор-вычит"тель ii. В .результате этого в накапливающем сумматоре-вычитателе 11 формируется новый адРес А . На выходах 40 блока 9 памяти и выходе блока 10 памяти элементов строк появляются новые координаты r,r u t., которые

I находятся по адресу А < = А + Г V /4j +

+ С

Блок 1 управления вновь перехо" дит в состояние а . Вновь подается управляющий сигнал "Запись" в счетчик 3 и в накапливающий сумматор 5.

При этом в счетчик 3 записывается считанная из блока 9 памяти новая

50 координата r вектора R, которая по" ступает на блок 8 памяти, а в накапливающий сумматор 5 — новая координата t вектора Т, которая поступает на первый вход схемы 4 сравнения.

Вновь срабатывает схема 4 сравненчя, в зависимости от признака сравнения и от значений сигналов на выходе элемента ИЛИ-НЕ и на выходе 9.2 блока 9 памяти, вновь блок 1 управления устанавливается в одно из состo

HHHH

Пусть блок 1 управления переходит в состояние а,1, В состоянии а+ подается управляющий сигнал "Сдвиг" на регистр 13 сдвига и управляющий сигнал

"Вычесть" на накапливающий сумматорвычитатель 11. В результате в накапливающем сумматоре-вычитателе 11 формируется новый адрес А . На выходах блока 9 памяти и выходе блока10 памяти элементов строк появляются координаты r,r и t, находящиеся по адресу А = А - 7 /8 — — С ° Блок 1 управления переходит в состояние а, в котором выдается соответствующий управляющий сигнал, фиксирующий в счетчике 3 и в накапливающем сумматоре 5 вновь считанные координаты r и t, а блок 1 управления вновь переходит в одно из состояний а аф а5 а7 ая

Пусть блок l управления переходит в состояние а (код 0101). Управляющий сигнал подается на управляющий вход "Сложить" накапливающего сумматора-вычитателя ll. В результате в накапливающем сумматоре-вычитателе 11 формируется новый адрес Ау (А = А + С ), так как на выходе

13.1 ре истра 13 сдвига устанавливается нулевой код, который соответствует первому элементу сжатой строки P ., Считываются блоки 9 и 10 памяти,а блок 1 управления переходит в состояние а .

В состоянии а выдается управляю" щий сигнал Запись", фиксирующий в счетчик 3 и в накапливающем сумматоре 5 считанные координаты r u t. В зависимости от значения сигнала на выходе 9.2 блока 9 памяти, блок 1 управления переходит в состояние а (на выходе 9 ° 2 — "0") либо в состояние а

7 (на выходе 9.2 — "1"), Таким образом, смена состояний а - а обеспечивает поиск в сжатой строке Р матрицы P такой координаты t1, вектора Т, для которой х с t

Поиск координаты t g осуществляется не последовательным перебором координат t вектора Т, а методом половинного деления.

Если х = tg, блок 1 управления после состояния а перейдет в состояние а>, При этом будет выработан управляющий сигнал "Вычесть" на счет1б!9263

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

Если х c C g и координата t> соответствует базовому элементу либо подстроки, состоящей ровно из одного фонового элемента (на выходе 9,2 блока 9 памяти сигнал "О" ), после cocto яния а либо а блок 1 управления переходит в состояние аб.

Если же х а t, но координата соответствует подстроке из фоновых элементов с длиной больше 1 {на выходе 9.2 блока 9 памяти сигнал "1"), блок 1 управления после состояния а или а переходит в состояние а .

В состоянии а> выдается сигнал

"Сложить" на накапливающий сумматор 5 и сигнал "Вычесть" на счетчик 3. Этим обеспечивается последовательное формирование в счетчике 3 номеров возможных будущих состояний цепи, которые 25 были сжаты и которые в явном виде не хранятся. Одновременно из содержимого накапливающего сумматора 5 вычитается значение фонового элемента $,ôîðмируя, тем самым, промежуточнше модифи30 цированные значения вероятностей переходов именно в те состояния, номера которых вырабатываются в счетчике 3.

Из состояния а> блок 1 управления

35 может перейти в одно из состояний а»,, а либо а .

Если схема 4 сравнения вырабатывает признак сравнения " ", в счетчике 3 сформирован код следующего со- 40 стояния цепи Маркова и блок управления переходит в состояние а

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

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

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

Маркова будет состояние Sä,íà выходе

55 дешифратора 2 вырабатывается сигнал

"1", а блок 1 управления переходит в состояние а .

В противном случае блок управления остается в состоянии а и с приходом очередного тактового сигнала вновь из счетчика 3 вычитается единица, из накапливающего сумматора 5 вычитается фоновый элемент, анализируется признак сравнения и т.д.

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

При этом сигнал на стробирующем выхо„де генератора указывает, что получено очередное состояние цепи.

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

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

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

3639263

l2 адресным входом третьего блока памяти и информационным входом дешифрато" ра, выход которого соединен с вторым входом задания логических условий

5 блока управления, пятый выход которого является стробирующим выходом генератора и соединен, с входами разрешения записи регистра сдвига и накапливающего сумматора-вычитателя, выход которого соединен с адресными входами первого и второго блоков памя-, ти, выход. старших разрядов третьего блока памяти соединен с информационным входом регистра сдвига, выход ко- 3g торого соединен с первым информаци-! онным входом накапливающего сумматора-вычитателя, второй информационный вход которого соединен с выходом младших разрядов третьего блока памяти, выход старших разрядов регистра сдвига соединен с входом элемента ИЛИ, выход которого соединен с третьим входом задания логических условий блока управления, шестой выход которого соединен с входом разрешения сложения накапливающего сумматора-вычитателя, вход разрешения вычитания которого соединен с седьмым выходом блока управления, восьмой выход которого соединен с входом сдвига регистра сдвига.

1619263

Пусн,Прцеи 8регистпр а д и Внакаллийющиц . сумматор-Рычылаmen h г нарегисю,а О ипу нанокйллиии аимюлаабькислиФель Ф.Прием 8счетчик 3 и о накаттбоющии

СуюкаяарЮ

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

Техред M.Äèäüïñ Корректор С,Шевкун

Редактор А.Мотыль

Заказ 48 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

ыюд г ементаgep -и

1Г.,Сложапъ" на накаалцбающий сужапюр- Ьчилалмь

Яуиесщыю

cvemvuw, л жить"на наколЖАыщий щима

-аычилазель И ,.уапрк "генеджч жт Е.Прием"б счеп юл,У и бнакаплидающии ауюгамор Х

> Прижал. срайчения

6иг коаетсл и

„ьачеюь "на.Фа"каллибакпций ам мющр - и чила= .тем ff

АИДУ емен паии-и

0 А/хдд ьг

„8ь честь "насчетчи

3 „слолчипи на цакапли8ающод суюмап ор 5

> ратно срабненця .

Фасад

Яиа,пррапаоа г