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

00

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

со

00

.1

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

Це.чь изо ретемия - расширение фун |;иональных аозможностей генератора ча счет получения случайных процессов, onHCbinaef-ttjix стохастическими ма рицами переходов, не являюгдимися ква зиразряженными.

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

Генератор случайного марковского процесса coJiO i - первьк счетчик 1 , 2 naMHTti, блок 3 памяти, блок 4 памяти, генератор 5 равномерно рас - ирелеленных чисел,, первую схему 6 срлвнения, нторок счетчик 7, датчик 8 равновероятной двоичной цифры, третий счет ик 9. О.пок 10 управления, вторую схема 11 сравне)1ия.

Блоки . 4 памяти предназначены ,щя храненпп в сжатой форме стохастической м; -трицы переходов.

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

В состоянии а илок 10 управле- ния выдает сигналы Прием в счетчик 1, П;. ск генератора 5,

В состоянии а блок 10 управления выдае сигналы Прием в счетчнк 7, ,+1 в счетчик 1 ,

В состоянии а, блок 10 управления выдает сигнал +1 в счетчик 7,

В состоянии а блок 10 управления выдает сигнал Прием в счетчик 9,

В состоянии а 5 блок Ю управления выдает сигналы +1 в счетчик 9, Опрос датчика 8,

В состоянии а блок 10 управления выдает сигнгш fl в счетчик 7,

В состоянии п.. блок 10 управления выдает сигнал Сброс счетчика 7,

Схема 1i сраьнения предназначена для сравнения чисел, поступаюш,их из блока 3 памяти и с выхода счетчика 9 1 1 сравнения вырабатывает признак либо V.

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

Пусчъ задан марковский процесс, описываемый конечным множеством состояний S {s;l|, i О, п-1 и стохастической матрицей переходов Р

iPll

, где Р;: - вероятность перехода из состояния s l в состояние-Sj , i, j 0, п-1 ; P;J cxl ;j - ; oi ;j - целое; m параметр, определяющий точность представления элементов матриЩ-,

Матрица Р храиится в сжатом виде в виде векторов Q || q || ; R || г j |1 ; Т 11 с Л ,

Векторы Q, R и Т получаются следующим образом.

Устанавливаем q 0, Сжимаем строку рр матрицы Р, Ппя этого в строке РО выделяем подстроки р, Р, , ., , , р , . ., из последовательно распо-. ложенных один за другим одинаковых элементов. Просматривая строку р слева Направо, в координаты г.,, г,, г,,.,,-с, г, t 2, . , . векторов R и.Т последов ательно выписывают:

в координату индекс k столбца последнего элемента подстроки

в )соординату сумму всех элементов строки р от Р( до рр, т,е.

величину

Ь

Г-Р,

.О

Пусть при сжатии строки р в R и Т выписаны по ft значений, где р,,- число подстрок в строке р , Устанав

ливаем

ч; Р

о

Аналогично р. сжимаем строку р и в векторах R и Т выписываем соот- BBTCTByTODUie значения. Пусть А,- число подстрок строки р,

Устанавливаем q q Аналогичным образом сжимаем строки 1Р,,, , , ,РП , определяя значения координат т:., , .., + .-..+Pi (Ьо(г, + ,fto+p.-,-,+fin-,

+ O, fbo+p. ., -fii ,,41 ...., С (Ъо+ (%,,,.. ,+ (in-l

При ЭТОМ q J ч 7.

q., q, + 3

qn- Tn-i +

Вектор (J загружается в блок A памяти, вектор R в блок 3 памяти, вектор Т - в блок 2 памяти, причем в па- кчть заносятся значения Ле - числители дробей вида с ь

Разрядность к число слов блоков 2-4 памяти определяются из следующих рассуждений.

Число координат вектора Q равно п. Число коорданат ректора Р и вектора Т зависят от средней длины (т.е. от числа элементов) 1 подстрок вида p-J матри1ц 1 F. Вектор R(T) содержит столь- KQ координат, сколько подстрок вида р| можно выделить в матрице Р. Число .подстрок определяется как nVl,

10

15

на своем выходе нек число X.

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

Допустим, что пе нения выработала пр

h X р. . Блок 1

ходит в состояние а

Сброс счетчика 7. жимое счетчика 7 ст а на выходе блока 3 лен индекс h

вой подстрок,, .1..

управления переходи

Допустим, что пе нения выработала пр 20 случайное число х I

5 больше, чем число

да блока 2 памяти. равления переходит 25 выдает управляющие Б счетчик 7 и +l этом в счетчике 7 с

памяти записывается

го элемента подстро мое счетчика 1 увел

30

где п - общее число элементов матрицы Р.

Координачъ q вектора Q принимают значения в диапазоне от О до п /1. Следовательно, разрядность блока 4 памяти, в котором хранится вектор Q, определяется как log , где J обозначает ближайшее целое в сторону увеличения.

Координаты г вектора R принимают значения от О до п-1. Следовательно, разрядность блока 3 памяти, в котором хранится вектор R, определяется как .

Координаты с вектора Т имеют разрядность га.

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

В счетчик 7 загружается код f состояния S. При этом на выходе блока

4памяти появляется.координата Qf,- т.е. указатель начала строки р. в блоках 2 и 3 памяти. На этом процессе загрузки исходных данных завершен.

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

С приходом на управляющий вход ге- 35 , выходе блока 2 нератора сигнала блок 10 управления переходит в состояние а и вырабатывает управляющие сигналы Прием в счетчик 1, Опрос датчика

5равномерно распределенных случайных

чисел.

I

I

Сигнал поступает на стробирующий выход генератора, указьшая что нд его информационном выходе установлено состояние s. При этом в счетчик 1 записьшается координата qf, поступающая с выхода блока 4 памяти. Изменение содержимого счетчика 1 запускает процесс чтения из блоков 2 и 3 памя- |ти. На выходе блока 2 памяти появля- ется координата г вектора К, т.е. индекс столбца правого элемента цеправ

подстроки .р°

Изменение содержимо вновь запускает про блоков 2 и 3 памяти ходе блока 3 памяти ,

деке h правого элем

h

40

нак

p. для подст

1 -.0

схема 6 сравнения вы либо .

ется признак , т

,

подстроки р. , блок у вырабатывает управля 45 Прием в счетчик 7 1 (состояние а) и т батывается признак равления переходит в

50

Таким образом, к блок 10 управления п яние в}, в счетчике декс h правого эле

для к

почки р,, а на выходе блока 3 памяти - значение соответствующей координаты вектора Т, т.е. сумма виЦда X.

0

р. . Датчик 5 вырабатывает i,

0

5

на своем выходе некоторое случайное число X.

в зависимости от признака сравнения блок управления переходит в состояние а либо в состояние a-f.

Допустим, что первая схема 6 сравнения выработала признак , т.е.

h X р. . Блок 10 управления пере V oходит в состояние а и выдает сигнал

Сброс счетчика 7. При этом, содержимое счетчика 7 станет равным нулю, а на выходе блока 3 памяти установлен индекс h

вой подстрок,, .1.. .jjji,«4n нf

управления переходит в состояние а

Допустим, что первая схема 6 сравнения выработала признак , т.е. 0 случайное число х с выхода датчика I h

5 больше, чем число р с выхо. (

да блока 2 памяти. Тогда блок 10 управления переходит в состояние а и 5 выдает управляющие сигналы Прием Б счетчик 7 и +l в счетчик 1. При этом в счетчике 7 с выхода блока 3

памяти записывается индекс h право а

го элемента подстроки р., а содержимое счетчика 1 увеличивается на 1.

0

правого элемента перподстроки .р° строки р, . Блок 10

4

, выходе блока 2

Изменение содержимого счетчика 1 вновь запускает процесс чтения из блоков 2 и 3 памяти. При этом на выходе блока 3 памяти появляьтся ин- ,I

деке h правого элемента строки р.,

памяти - значение

h

, выходе блока 2

нак

p. для подстроки р, . Первая

1 -.0

схема 6 сравнения вырабатывает приз- либо . Если вырабатываhется признак , т.е. к

,

подстроки р. , блок управления опять вырабатывает управляющие сигналы Прием в счетчик 7 и +1 в счетчик 1 (состояние а) и т.д. Если же вырабатывается признак , блок 10 управления переходит в состояние а,.

Таким образом, к моменту, когда блок 10 управления переходит в состояние в}, в счетчике 7 находится индекс h правого элемента последней

- 4- для которой х 2- PJ

CJ.-0 V а на выходе блока 3 памяти - индекс

подстроки

h подстроки

п

что X 21 PJ :,.0

Н 1

В соЬтоянии а блок 10 управления задает сигнал в счетчик 7, увелчивая тем самым индекс h на единиц Блок 10 управления переходит в состоние а

Ч- Таким образом, к моменту перехода

в состояние а в счетчике 7 находится индекс h столбца первого (левого элемента подстроки р, а на выходе блока 3 памяти - индекс h столбца правого (последнего) элемента подстрки р .

В состоянии а4. блок 10 управления выдает сигнал Прием в счетчик 9. При этом в счетчик 9 переписывается содержимое счетчика 7, т.е. в счетчик 9 записывается значение индекса h первого элемента подстроки р.

Вторая схема 11 сравнения, анализируя индекс h , поступающий со счет

сравнения выработала признак - значит, что h h, т.е. цепочка р

35

чика 9, и индекс h, поступающий с выхода блока 3 памяти, вырабатывает признак либо i.

Предположим, что вторая схема 11 25

Это fl

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

Предположим, что вторая схема 11 сравнения вырабатывает признак . Это означает, что h h и следующим состоянием цепи Маркова будет одно

из состояний , Sy, ,...,8Ц, ПрИчем указанные состояния являются равновероятными (цепочка р состоит из одинаковых элементов). При признаке V на выходе второй схемы 11 сравнения блок 10 управления переходит в состояние а и вырабатывает управля

Если вырабатывается признак , блок К) управления переходит в состоя ние а, вырабатывая сигналы Прием в счетчик 1 и Иуск датчика 5. Сигнал одновременно поступает на стробирующий выход генератора, указывая, что на его информационном выходе установлен код со следующего состояния Su3 цепи Маркова. На этом цикл выра отки очередного состояния цепи Маркова завершен. С состояния a блок 10 управления начинает цикл выработки cлeдyюD eгo состояния цепи Марко40

30

ва, записывая в счетчик 1 значение

координаты q CJ с выхода блока А памяти и т.д.

же вырабатывается признак /, блок управления вновь переходит в состояние а;, увеличивает содержимое счетчика 9 и осуществляет опрос датчика И. Если на датчика 8 выработалась 1, содержимое счетчика 7 увеличивается на единицу, а в противном случае остается без изменений и т.д. Таким образом, последовательный опрос датчика 8 и увеличение содержимого счетчика 7 выполняется .J для h, h + l,...,h . При этом в

счетчике 7 формируется число СО , равномерно распределенное в интервале , я . ,

п ...п, которое является кодом следующего состолтдая цепи.

Предлагаемьй генератор позволяет

ющие сигналы Опрос датчика 8 и 4-1 50 получать случайные процессы,описывае-.

в счетчик 9. При этом на.выходе датчика 8 с вероятностью 1/2 вырабатывается значение 1, а содержимое счетчика 9 становится равным h 1.

Если выход датчика 8 равен 1, блок 1() управления переходит в состояние ag и вырабатывает сигнал +1 в счетчик 7. Если же выход датчика 8

8

5

5

равен О, увеличение содержимого счетчика 7 не выполняется. Таким образом, при каждом опросе датчика 8 содержимое счетчика 7 с вероятностью 1/2 увеличивается на единицу.

После анализа выход датчика 8 и увеличения при необходимости содержимого счетчика 7 выполняется сравнение текущего содержимого счетчика 9 и выхода блока 4 памяти.

Вторая схема 11 сравнения, сравнивая содержимое счетчика 9, т.е. значение h -t-l, со значением с вы- 5 хода блока 3 памяти, т.е. со значением h, вырабатывает признак либо i.

Если вырабатывается признак , блок К) управления переходит в состояние а, вырабатывая сигналы Прием в счетчик 1 и Иуск датчика 5. Сигнал одновременно поступает на стробирующий выход генератора, указывая, что на его информационном выходе установлен код со следующего состояния Su3 цепи Маркова. На этом цикл выра отки очередного состояния цепи Маркова завершен. С состояния a блок 10 управления начинает цикл выработки cлeдyюD eгo состояния цепи Марко0

0

0

ва, записывая в счетчик 1 значение

координаты q CJ с выхода блока А памяти и т.д.

же вырабатывается признак /, блок управления вновь переходит в состояние а;, увеличивает содержимое счетчика 9 и осуществляет опрос датчика И. Если на датчика 8 выработалась 1, содержимое счетчика 7 увеличивается на единицу, а в противном случае остается без изменений и т.д. Таким образом, последовательный опрос датчика 8 и увеличение содержимого счетчика 7 выполняется J для h, h + l,...,h . При этом в

счетчике 7 формируется число СО , равномерно распределенное в интервале , я . ,

п ...п, которое является кодом следующего состолтдая цепи.

Предлагаемьй генератор позволяет

0 получать случайные процессы,описывае-.

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

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

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

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

а

I %ск I 1

Прим о счетчик i Пуск генератора 5

Чг

ирием о счетчик 7 +Г д счетчик 1

,ЧГ

8 счетчик 7

1

прием о счетчик 9

«5

Опрос датчиков + счетчик 9

счетчик

Сброс C4emwfta 7