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

 

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

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

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

РЕСПУБЛИК

„„SU„„1481755 А 1 цР4 G 06F 7/58

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4241996/24-24 (22) 11.05.87 (46) 23.05.89. Бюл. № 19 (71) Кишиневский политехнический институт им. С. Лазо (72) А. А. Гремальский и С. М. Андроник (53) 683.3 (088.8) (56) Авторское свидетельство СССР № 451085, кл. G 06 F 15/20, 1974.

Авторское свидетельство СССР № 1070548, кл. G 06 F 7/58, 1984.

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

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

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

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

Блок 1 управления содержит генератор 9 тактовых. импульсов, динамический D-триггер 10, срабатывающий по заднему фронту тактового импульса, элемент ИЛИ 11, инвертор 12 и три элемента И 13 —.15. (54) ГЕНЕРАТОГ СЛ УЧА Й НОГО МА Г КОВСКОГО ПРОЦЕССА (57) Изобретение относится авто.;:,атпке и вычислительной технике и может бhlòü использовано для генерации входных vo;«åдователъностей при стохасти«еском конт1 .о, 1с дискретных объектов. Цель изобретения — упрощение генератора. Для этого в генератор введены функционально ориен; ированные блоки памяти. Генератор слу«айного марковского процесса содержит гс гсратор случа1" ных чисел, блок памяти l казателей начала строк, блок памяти кодов состояний. блок памяти элементов .трон блоки управления, сравнения. с«сТ«. ê: регистр. 2 ил. 4 табл.

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

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

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

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

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

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

S=Is}, i=0,ï — 1 и стохастической матрнцей переходов Р= и Р; 1), где P„— вероятность перехода за один такт из состояния

1481755

i, k=0,п — 1; в состояние P,ì=

=а; .2, а; — целое.

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

Q=llqcll, 1=0, и — s;

R=IIS, 1;

T=ilh,ll, Ь=О, dn, где d — степень разряженности матрицы P.

Координата q, вектора Q содержит суммарное число ненулевых элементов строк матрицы Р, предшествующих строке 1, т. е. с10=0

q !=Мо, q2=qi+ 1 4;

qn — != — Чл — 2+Nn — 2, где N!!, N!, N 2 — число ненулевых элементов строк 0,1,..., и — 2 матрицы P.

Перейдем от стохастической матрицы P к матрице Р =(1Рй!(, 0, если Р !,=0; где Р; = у

ZÓ Р„, есл и Р;!, Ф О. о

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

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

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

Вектор R загружается в блок 6 памяти, элементов строк, содержащий dn ячеек разрядностью m, причем в память записываются только числители а;!, дробей вида

Р; =а ; 2

Вектор Т загружается в блок 5 памяти кодов состояний содержащий dn2 ячейки разрядностью log2n. Например, для матрицы P

I из табл. 1 матрица P имеет вид, представленный в табл . 2.

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

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

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

В выходной регистр 8 памяти загружают код f состояния st. В счетчик 4 загружают координату qt векторами (на фиг. 1 устройства загрузки не показаны). При этом на выходах блока 6 памяти элементов строк появляется координата s), а на выходах блока 3 памяти указателей начала строк — индекс первого ненулевого элемента строки а матрицы P.

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

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

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

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

После запуска по сигналу от блока l управления датчик 2 равномерно распределенных на отрезке (0,1) случайных чисел вырабатывает m-разрядное двоичное число

Z =х ° 2 и величина х,; подается на вторую группу входов блока 7 сравнения.

Блок 7 сравнения может вырабатывать признак «(» (число от генератора 2 слу20 чайных чисел меньше или равно, чем число, получаемое от блока 6 памяти элементов строк) либо признак «)» (число от генератора 2 случайных чисел больше, чем число, получаемое от блока 6 памяти элементов строк) .

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

В результате изменения содержимого счетчика 4 одновременно срабатывают блоки памяти 5 и 6: на первую группу входов блока 7 сравнения поступает очередное значение ненулевого элемента строки а матрицы Р; на входы блока 3 памяти поступает код возможного будущего состояния s .

Вновь срабатывает блок 7 сравнения.

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

Если вырабатывается признак «(», очередной тактовый импульс генератора 9 через элемент И 15 поступает на вход записи регистра 8 памяти и фиксирует в нем код следующего состояния s . Этот же

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

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

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

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

1481755

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

Таблица 1

0 1

2 3

2 3

4 5

893

1024

131 0

1024

1 0 0

0 0

651 0

1024

0 0

373

1024

2 17 0

1024

3 175 0

512

4 0 0

1007

1024

0 0

19 13

337

512

32 32

0 0

163

256

93

256

5 0 0

1013

1024

19

64 единичное состояние, выдается сигнал запуска генератора 2 случайных чисел и т. д.

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

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

6 0 11 0 0

1024

7 45 0 0 0

64 которого соединен со счетным входом счетчика, установочный вход которого соединен с четвертым выходом блока управления, разрядные выходы счетчика подключены к соответствующим адресным входам блока памяти кодов состояний и адресным входам блока памяти элементов строк, информационные выходы которого соединены с первой группой соответствующих информационных входов блока сравнения, вторая группа информационных входов которого соединена с соответствующими информационными выходами управляемого генератора случайных чисел, информационные выходы блока памяти кодов состояний соединены с соответствующими информационными входами регистра и адресными входами блока памяти указателей начала строк, информационные выходы которого,oäê;:K.,åíû к соответствующим информационн=:;. входам счетчика, информационные выходы регистра являются информационными выходами генератора случайного марковского процесса.

1481755.

Та блица 2

2 3

0 0 131 0 0

1024

1 0 0 651 0

1024

2 0 0

0 0

5 0 " 0

Таблицы 3

2 3 4

0 1

14

Таблица 4

0 1 2 3 4 5 6 7 8 -9 10 11 12 13 14 15

R 131 1024 651 1024 17 1024 175 1024 608 1024 652 1024 11 1024 720 1024

T 1 4 2 7 0 6 0 5 2 3 4 6 1 5 0 6

Фиг. 1

17 0

1024

175 0

1024

0 0

6 0 11

1024

7 45 0

19 1

32

0 0

0 0

0 0

0 1

0 0

163 0

256

0 1

Фиг. 2

Состав ител ь Ю. Андреев

Редактор Л. Гратилло Техред И. Верес Корректор С. Черни

Заказ 2690/49 Тираж 669 Подписное

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

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

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