Генератор случайного марковского процесса Советский патент 1991 года по МПК G06F7/58 

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

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

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

Генератор случайного марковского процесса содержит блок 1 управления, дешифратор 2, счетчик 3, схему 4 сравнения, накапливающий сумматор 5, датчик 6 равномерно распределенных случайных чисел, регистр 7 памяти, блок 8 памяти с выходами 8.1 старших разрядов и 8.2 младших разрядов, блок 9 памяти с выходами 9.1 старших разрядов и 9.2 младшего (нулевого) разряда, блок 10 памяти элементов строк, накапливающий сумматор-вычитатель 11, элемент ИЛИ 12, регистр 13 сдвига с выходами 13.1 старших разрядов и младшего (нулевого) разряда.

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

Блок 1 управления имеет множество внутренних состояний Га0, а , а , аэ,

а4, а,

aЈi

а

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

(Л С

оь

СО го

О

03

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

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

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

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

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

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

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

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

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

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

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

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

Р - I PS; И

,ч гДе перехода за один такт

ро

Mi

S: в состояние Sj

го

J

вероятность из состояния -О, п-1,

0

Ч

P{j tfjj 2- 1 , где (X.jj - целое, ш - параметр, определяющий точность представления элементов матрицы Р.

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

Пи,1;

Hell; и п

1 0, n-l;

Г rhl

5

5

0

I nj

Векторы V, Q, R, R и Т получают таким образом, что устанавливают

Сжима- в

% ° го ют строку

строке Р,

0, г 0 0, t0 0.

Р0 матрицы Р. Для этого выделяют подстроки Р,

.

Р.К° из

о

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

о о Оо Просматривая строку Р„

о +

-0 слева на- 0 право, в координаты г( ,г,. . .. ,г, ,

r,...,t4, векторов R, R

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

0|

если встречается подстрока Р0 , а I, К0, в R выписывают h +1, в R выписывают 1, а в Т выписывают

4«/ Р0а гДе, h - индекс столбца

последнего

элемента подстроки Р0 ;

если встречается базовый элемент в R выписывают g +1, в R выпиOJ

сывэют 0, а в Т выписывают

9

00

Loc

45 где g - индекс столбца, где находится

элемент Р,

05

т.е. g J.

Пусть при сжатии строки Рп в R,

R и Т были выписаны по значений. Устанавливают q fi0 1, гк0п О,

0 rfW ° ЬР«-н ° Аналогично строке Р0 сжимают строку Р . Пусть в строке Р-, К подстрок и $, базовых элементов. Устанавливают V.

К

Просматривая строку Р слева на- I т

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

Устанавливают q,

PI + 2 о;

- я + (3, +i, г fe+p)+2 rlW.+ ° tfVp о.

Аналогичным образом сжимают строки Р, РЈ ,...., Р п-1 определяя значения координат гл +(, 3 ,

Г Ро+Р + 4 г (V , |%г+, V гр«+рч М

rpotp« 4(V«(iM) rpotp,+ 3

,4- гро+(3,+(3-г+4 гро-(3,, r(%otp,i-...-tf%n.4+(r,) 5 а также

Сро+|Ь.+ 3 fc Ро+рч + 4Ьр„-ф,-фг-«4

tf,0+3,4p1+5.- tf5e4(31.,-i-A -е(ци) При этом

q5 РО + pi + |%г + 3 q + + Ра + 8

q4 N + + fa + fa + 4 - q3 + Рз + s

ЧГЫ Ре + Р, +/3 + + /3„-2 +

+ (П-1) + /V3L + а также V,

, K2+y2;

v, -к, + у,;

V-1 Кп,

JV«

где К, у , К, ъ ,. .. , К п.| , У d-t число подстрок и число базовых элементов строк 2,3,...,п-1 соответственно.

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

1 0,1,2п-1 записываются в

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

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

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

, уменьшенные на единицу, дробей вида t «h« .

Перед началом работы векторы V, Q, R. R и Т вычисляются и загружаются в соответствующие блоки 8-10 памяти (на фиг.1 устройство загрузки не показано). Фоновый элемент с знаком - записывается в дополнительном коде в регистр 7.

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

В счетчик 3 загружают код f состояния Sj.. При этом на выходе 8.1 блока. 8 памяти появляется координата V ( число подстрок и базовых элементов строки Рр а на выходе 8.2 появляется координата qi (указатель

начала строки Р. в блоках 9 и 10 памяти.

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

Работа генератора сводится к реаг лизации алгоритма управления, представленного на фиг.2,

После загрузки начального состояния блок 1 управления находится в состоянии а0 и появляется сигнал, ко0 торый поступает на управляющие входы Запись регистра 13 сдвига и накапливающего сумматора-вычитателя 11. При этом в регистр 13 сдвига записывается координата Vr вектора V, а в

5 накапливающем сумматоре-вычитателе 1 1 записывается координата q/вектора Q. После этого блок 1 управления переходит в состояние а.В состоянии а( подается управляющий сигнал Запуск

Q на датчик 6 равномерно распределенных случайных чисел, управляющий сигнал Сложить - на накапливающий сум- матор-вычитатель 11. При этом датчик 6 вырабатывает m-разрядное двоичное число ZJ и величина х,

5 л.

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

появляется координата t. Эти коорди- э

на ты находятся по адресу А г;. +

+ С0 , где С0 - значение младшего разряда регистра 13 сдвига.

Блок 1 управления переходит в со- Q стояние ag , в котором подается управляющий сигнал Запись в счетчик 3 и в накапливающий сумматор 5. При этом в счетчик 3 записывается считанная из блока 9 памяти координата г векто- pa R, которая поступает на блок 8 памяти, а в накапливающий сумматор 5 - координата t вектора Т, которая поступает на первый вход схемы 4 сравнения .

0

В зависимости от значения сигналов с выхода схемы 4 сравнения, с выхода 9.2 блока 9 памяти и с выхода элемента ИЛИ 12, поступающих на соответствующие логические входы блока 1 управ ления t он устанавливается в одно из следующих „состояний: при признаке (число от датчика 6 равномерно распределенных случайных чисел больше числа от накапливающего сумматора 5) и сигнале О на выходе элемента ИЛИ 12 устанавливается состояние а,; при признаке. ; и сигнале 1 на выходе элемента ИЛИ 12 устанавливается состояние при признаке fчисло от датчика 6 равномерно распределенных случайных чисел меньше числа от накаплив ющего сумматора 5) и сигнале О с выхода элемента ИЛИ 12 устанавливается состояние а4 ; при признаке м (число от датчика 6 равномерно распределенных случайных чисел равно числу от накапливающего сумматора 5 либо при признаке и сигналах I и О на выходе элемента ИЛИ 12 и на выходе 9.2 блока 9 памяти соответственно устанавливается состояние ag; при признаке l и сигналах 1 на. выходе элемента ИЛИ 12 на выходе 9,2 блока 9 памяти устанавливается состояние а.

В состоянии а з подается управляющий сигнал Сдвиг на регистр 13 сдвига и управляющий сигнал Сложить на накапливающий сумматор-вычит.-1- тель I1. В -результате этого в накапливающем сумматоре-вычитателе 11 формируется новый адрес А. На выходах блока 9 памяти и выходе блока 10 памяти элементов строк появляются новые координаты г,г и t., которые находятся по адресу А А + + + С0.

Блок 1 управления вновь переходит в состояние а. Вновь подается управляющий сигнал Запись в счетчик 3 и в накапливающий сумматор 5.1 При этом в счетчик 3 записывается считанная из блока 9 памяти новая координата г вектора R,которая поступает на блок 8 памяти, а в накапливающий сумматор 5 - новая координата t вектора Т, которая поступает на первый вход схемы 4 сравнения.

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

0

0

элемента ИЛИ-НЕ и на выходе 9.2 блока 9 памяти, вновь блок 1 управления устанавливается в одно из состояний а3,а4,а5,а7, а8.

Пусть блок 1 управления переходит в состояние а, В состоянии а подается управляющий сигнал Сдвиг на регистр 13 сдвига и управляющий сигнал Вычесть на накапливающий сумматор- вычитатель 11. В результате в накапливающем сумматоре-вычитателе 11 формируется новый адрес АЈ. На выходах блока 9 памяти и выходе блока - . 10 памяти элементов строк появ-- ляются координаты г,г и t, находящиеся по адресу А A, ( - С Q. Блок I управления переходит в состояние а-, в котором выдается соответствующий управляющий сигнал, фиксирующий в счетчике 3 и в накапливающем сумматоре 5 вновь считанные координаты rut, а блок 1 управления вновь переходит в одно из состояний

5 ,ag.

Пусть блок 1 управления переходит в состояние ад- (код 0101). Управляющий сигнал подается на управляющий вход Сложить накапливающего Q сумматора-вычитателя II. В результате в накапливающем сумматоре-вычитателе 11 формируется новый адрес AJ (А Ад. + С0) , так как на выходе 13.1 регистра 13 сдвига устанавливается нулевой код, который соответствует первому элементу сжатой строки Рт .« Считываются блоки 9 и 10 памяти,а блок 1 управления переходите состояние ас,

В состоянии а выдается управляю- 0 РГИЙ сигнал Запись, фиксирующий в счетчик 3 и в накапливающем сумматоре 5 считанные координаты г и t. В зависимости от значения сигнала на выходе 9.2 блока 9 памяти, блок управ- 5 ления переходит в состояние а(на выходе 9.2 - О) либо в состояние а7 (на выходе 9.2 - 1).

Таким образом, смена состояний а2. а6 обеспечивает поиск в сжатой строке РЈ матрицы Р такой координаты t вектора Т, для которой xj с t . Поиск координаты ti осуществляется не последовательным перебором координат t вектора Т, а методом половинного деления.

Если xj t, блок 1 управления после состояния а перейдет в состояние ag. При этом будет выработан управляющий сигнал Вычесть на счет5

916

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

ь, с которого начинается очередной цикл работы генератора.

Если х j . t B и координата te соответствует базовому элементу либо подстроки, состоящей ровно из одного фонового элемента (на выходе 9,2 бло- ка 9 памяти сигнал О ), после состояния а блок 1 управления переходит в состояние а.

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

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

10

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

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

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

о

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

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

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

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

мируя, тем самым, промежуточна модифиэд ны с группой входов задания логических

цированные значения вероятностей переходов именно в те состояния, номера которых вырабатываются в счетчике 3.

Из состояния Зу блок 1 управления может перейти в одно из состояний а

35

О;

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

18

либо а

О;

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

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

13 Если же схема

тывает признак случая.

4 сравнения выраба- то возможны два

,

Если признак ; выработан для состояния S

t

т.е. подстрока из фоновых элементов находится в начале строки Рг , то следующим состоянием цепи Маркова будет состояние S0,на выходе дешифратора 2 вырабатывается сигнал 111, а блок 1 управления переходит в состояние а.

35

;

40

45

-

50

оо55

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

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

5

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

во

,Прием 8 регистр 13 и о накапливающий сумматор - вычита- те ль И

,Слджить на накапливающий сумма/пар- -8ычи/патель it. . Ч3апуск генеро/№ а о

,Прием 8 счетчик 3 и 6 накал/н/6ающий СумматррЗ

jcsBm нарегисщр 13 „ ЪычесТль ми. на - ками&ающии awe- ма/nop- &A/wmer- mejttift

„Butvec/я на 3 „ Сложить на HatfonsH/SatcufuJ сумма/пор 5