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

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

Цель изобретения - упрощение генератора.

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

Генератор случайного марковского процесса содержит блок 1 управления, генератор 2 случайных чисел, блок 3 памяти указателей- начала строк, счетчик 4, блок 5 памяти кодов состояний, блок 6 памяти элементов строк, блок 7 сравнения, выходной регистр 8 памяти.

Блок 1 управления содержит генератор 9 тактовых импульсов, динамический D-триг- гер 10, срабатывающий по заднему фронту тактового импульса, элемент ИЛИ 11, инвертор 12 и три элемента И 13-15.

Блоки 3, 5 и 6 памяти предназначены для хранения в сжатой форме стохастической матрицы переходов. Считывание информации из блоков 3, 5 и 6 памяти происходит при поступлении соответствующих адресов на их адресные входы

Счетчик 4 предназначен для хранения и формирования адреса, по которому осуществляется обращение к блокам 5 и 6 памяти.

Блок 7 сравнения выполняет сравнение чисел, поступающих от генератора 2 случайных чисел и от блока 6 памяти элементов строк, вырабатывая признак «sЈC либо «.

Выходной регистр 8 памяти предназначен для хранения текущего состояния цепи.

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

Пусть задан марковский процесс, описываемый конечным множеством состояний

00

ел

сд

, ,n-1 и стохастической матрицей переходов ,||, где P,k - вероятность перехода за один такт из состояния

3...

s, в состояние i, ,n-I; a,-2 , an, - целое.

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

.e||, , n-s;

RHISJI;

,ll, , dn2,

где d - степень разряженности матрицы Р. Координата q вектора Q содержит суммарное число ненулевых элементов строк Ю генератора 2 случайных чисел. По заднему

В начальный момент времени, до прихода первого тактирующего сигнала от/ генератора 9 тактовых импульсов, динамический D- триггер 10 для определенности находится в нулевом состоянии.

Первый тактирующий сигнал от генератора 9 тактовых импульсов через элемент И поступает на управляющий вход

матрицы Р, предшествующих строке 1, т. е.

qi N0;

+ Ni;

qn i q;i21r:M«-2,

где NO, NI,..., число ненулевых элементов строк 0,1,..., n-2 матрицы P.

Перейдем от стохастической матрицы Р к матрице Р ,

Ч), если P,0; где P lk -к20

EP,Y, если Р,Ј0.

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

Из матрицы Р построчно выписывают в вектор R ненулевые элементы Р, А; в век- тор Т - индексы к столбцов ненулевых элементов.

Вектор Q загружается в блок 3 памяти указателей начала строк, содержащий n ячеек разрядностью Iog2 dn2.

Вектор R загружается в блок 6 памяти , элементов строк, содержащий dn2 ячеек разрядностью т, причем в память записыфронту тактового сигнала триггер 10 переключается в единичное состояние.

После запуска по сигналу от блока 1 управления датчик 2 равномерно распреде- , г ленных на отрезке (0,1) случайных чисел вырабатывает m-разрядное двоичное число и величина х. подается на вторую группу входов блока 7 сравнения. Блок 7 сравнения может вырабатывать признак « (число от генератора 2 случайных чисел меньше или равно, чем число, получаемое от блока 6 памяти элементов строк) либо признак « (число от генератора 2 случайных чисел больше, чем число, получаемое от блока 6 памяти элементов строк).

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

В результате изменения содержимого счетчика 4 одновременно срабатывают блоки памяти 5 и 6: на первую группу входов блока 7 сравнения поступает очередное зна30

генератора 2 случайных чисел. По заднему

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

В начальный момент времени, до прихода первого тактирующего сигнала от/ генератора 9 тактовых импульсов, динамический D- триггер 10 для определенности находится в нулевом состоянии.

Первый тактирующий сигнал от генератора 9 тактовых импульсов через элемент И поступает на управляющий вход

генератора 2 случайных чисел. По заднему

0

фронту тактового сигнала триггер 10 переключается в единичное состояние.

После запуска по сигналу от блока 1 управления датчик 2 равномерно распреде- г ленных на отрезке (0,1) случайных чисел вырабатывает m-разрядное двоичное число и величина х. подается на вторую группу входов блока 7 сравнения. Блок 7 сравнения может вырабатывать признак « (число от генератора 2 случайных чисел меньше или равно, чем число, получаемое от блока 6 памяти элементов строк) либо признак « (число от генератора 2 случайных чисел больше, чем число, получаемое от блока 6 памяти элементов строк).

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

В результате изменения содержимого счетчика 4 одновременно срабатывают блоки памяти 5 и 6: на первую группу входов блока 7 сравнения поступает очередное зна0

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

ваются только числители а, дробей вида Р, с4.2-.

40

чение ненулевого элемента строки а матрицы Р ; на входы блока 3 памяти постуВектор Т загружается в блок 5 памяти 35 пает К°Д возможного будущего состояния 5ц,. кодов состояний содержащий dn2 ячейки раз-Вновь срабатывает блок 7 сравнения.

Если блок 7 сравнения опять вырабатывает признак «, процесс увеличения счетчика 4 и чтения блоков 5 и б памяти повторяется, вновь срабатывает блок 7 и т. д.

Если вырабатывается признак «, очередной тактовый импульс генератора 9 через элемент И 15 поступает на вход записи регистра 8 памяти и фиксирует в нем код следующего состояния sfe. Этот же тактовый импульс поступает на установочный вход счетчика 4 и фиксирует индекс первого ненулевого элемента матрицы Р строки w, который к этому времени появился -на выходах блока 3 памяти указателей начала строк.

Одновременно по заднему фронту этого же тактового импульса динамический D-триг гер 10 переключается в нулевое (исходное состояние, поскольку на вход D-триггера через инвертор 12 и элемент ИЛИ 11 поступает инвертированное значение признака сравнения.

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

45

рядностью Iog2n. Например, для матрицы Р из табл. 1 матрица Р имеет вид, представленный в табл. 2.

Вектор Q представлен в табл. 3, а векторы R и Т - в табл. 4.

Перед началом работы Q, R, Т вычисляются и загружаются в соответствующие блоки 3, 5 и 6 памяти (на фиг. 1 устройство загрузки не показано).

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

В выходной регистр 8 памяти загружают код f состояния s/. В счетчик 4 загружают координату q/ BeKTOpaQ (на фиг. 1 устройства загрузки не показаны). При этом на выходах блока 6 памяти элементов строк 0 появляется координата , т. е. первый ненулевой элемент строки f матрицы Р который поступает на первую группу входов блока 7 сравнения. Одновременно на выходах блока 5 памяти кодов состояний появляется код возможного будущего состоя- 55 ния sa(), а на выходах блока 3 памяти указателей начала строк - индекс первого ненулевого элемента строки а матрицы Р

С приходом очередного тактового импульса триггер 10 опять переключается в

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

С приходом очередного тактового импульса триггер 10 опять переключается в

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

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

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

О О

64

О

651

Т024

О

О

J9

32 О

О О О О

13

32 О

О О

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

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

Таблица 1

3

24

3

6

О

о о

512

О

О

1013 1024 О

1007 1024 О

О 93

256 О

Ii

64

О

373

1024

О

О О О О О

О О 17

131

1024 О

О

О 651

О О

1024 ОО

1024 175 О

1024 ОО

О О

45 64

О 11

1024 О

О

О О О

О 1 О

о

о

О 1

4 5

R 131 1024 651 1024 17 1024 175 1024 608 1024 652 1024 11 1024 720 1024 Т14 27 06 05 23 46 15 06

Таблица 2

О О О 1 О О 1 О

О О 1

О О

1

о 1

о 1 о о о о о о

Таблицы 3

Таблица 4 10 11 12 13 14 15

0U8. 2