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

 

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

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

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

РЕСПУБЛИК (51)5 С 06 F 7/58

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

H А BTOPCKOMV СВИДЕТЕЛЬСТВУ л

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

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

ПРИ fKHT СССР (21) 4642373/74 (22) 24.01.89 (46) 30.01.91.. Пюл. (71) Кишиневский политехнический институт им.С.Лазо (72) А.А.Гремальский и С.М.Андроник (53) 681. 3(088.8) (56) Авторское свидетельство ССГР

В 1070548, кл. Г Об F 7/58, 1983.

Авторское свидетельство ССГР

В 1481755, кл. Г Об F 7/58, 1988. (54) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО ПРОПЕССА (57) Изобретение относится к автома„.SUÄÄ 1624446 A 1 тике и вычислительной технике и может использоваться для генерации входных но< ледовательностей при стохастическом контроле дискретных объектов. 1(елью изобретения является повышение быстродейсгвия генератора.

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

1624446

15

25

"О К

NO> N„> >N \-> элементов строк О, 1

IlI>< P °

Координата П век сумму вида число ненулевых и-1 матритора О содержит

1, т.е. ц;

+пи Z о ч„

+ (n

-1) =

Ч n- +n-у

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

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

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

Генератор случайного марковского процесса содержи г блок 1 управления, датчик 2 равномерно рлспределенных случайных чисел, блок 3 памяти с выходами 3.1 старших рл зрядов и 3.2 младших рлзрядов, регистр 7> сдвига с выходами 4. 1 с rаpшиx рл зрядов и

4. 2 — младшего (нулевого) разряда, накапливающий сумматор-вычитатель 5, блок 6 памяти, блок 7 плмяти, ре гистр 8, схему 9 сравнения, элемен т ИЛИ 1О.

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

Блок 1 управления имеет множес r«o

35 внутренних сoc:тояний

В cnc гоянии л блок 1 упрлвления о выдает следующие сигнллы: 40

"Опрос" на датчик 2," "Сложить" на накапливающий сумматор-вычитлгель 5 ..

В состоянии л блок 1 управления выдает следующие сигналы: 45

"Сдвиг" нл регистр 4 сдвигл; "Сложить на нлкапливлю1чий сумматор-вычитатель 5.

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

Сдвиг нл регистр 4 сдвига; "Вычесть" íà íàlccHlëllBëlc>I>lHé сумматор-вычи гатель 5.

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

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

"Запись" в регистр 8, "Запись" в регистр 4 сдвигл и в накапливающий сумматор-вычитатель 5.

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

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

Пусть .задан марковский процесс, ОПИСЫВаЕМЫй КОНЕч«ЫМ МНОжЕСтВОМ COCтояний S = K s ), i = О, п-1 и стохастической млтрицей переходов P = //Г „// где Р, „, — вероятность переходя за один шаг из состояния s в состояние

s„, i,,k = 0, п-1, P1к=О(,к 2 целое. к

Стохастическая матрица P хранится в сжатой форме в виде векторов! е( — !!q,!l, > =о, n->, R = Цг1,/1;

Т = // !//, h = 0 dn+ n, где d — c"I> пень разряженности матрицы Р, (d c пределяется как отношени числа ненуленьгх элементов к общему числу элементов стохастической матрицы переходов).

Координата ll вектopà 1! содержит число ненулевых oлементов строки 1 матрицы Р, т.е °

О

u ll +2=g!+I>+1

0 (46 6 !! I! ся в состоянии л„. Сигнал Опрос поступает на вход датчика 2. Сигнал

"Сложить поступает на суммирующий вход накапливающего сумматора-вычитателя 5. Датчик 2 вырабатываеT

m-разрядное двоичное число z, = х 2

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

9 сравнения двоичных чисел. Одновременно в накапливающем сумматоревычитагеле 5 формируется текущий адрес Ad» по которому выполняется обращение к блоку 6 памяти кодов сосТо яний и к блоку 7 памяти элементов строк. На выходе блоков 7 и 6 памяти появляются координаты r u f спответственно. Эти координаты соответствуют элементу строки f матрицы Р, находя((егося по адресу Ad( (qg + и1/? 3 + c> где сО зн"че ние младшего разряда регистра 4 сдвига, Координата r поступлет нл первую группу информационных входов схемы 9 сравнения двоичных чисел .

Схема 9 сравнения может вырабатывать признак ((число от датчика 2 случайных чисел мены!(е или равно, чем число, получаемое от блока 7 памяти элементов строк), либо ) (число от датчика 2 случайных чисел больше, а чем число, получаемое от блока 7 памяти элементов строк).

О, если Р„= О, к !((+ Р,а,, если Р ф О. у=о (P

1К

40

Ъ 1624(4

Перейдем от стохлсгической матрицы Р к матрице Р = //Р;„ //

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

Иэ матрицы P построчно выписы— вают в вектор R нуль и ненулевые ! элементы P <, в вектор Т нуль и ин!

К дексы столбцов к ненулевых элементов.

Векторы U и О загружают в блок 3 памяти указателей начала строк, содержащий п ячеек. При этом координаты ир, 1 * О, 1, 2, ...,n-1 записываются в поле старших разрядов (им соответствует выход 3.1), л коорди- 20 наты qg — в поле младших разрядов (им соответствует выход 3.2) блока 3 памяти указателей начала строк. Число старших и младших разрядов ячеек блока 3 памяти указателей начала .строк определяется максимальным значением координат векторов U и 0 н составляет ) log и (и) )оy, (d + n) ( соответственно.

Вектор R загружается в блок 7 памяти элементов строк, содержащий

d„ +и ячеек разрядностью m, причем в памяти записывлются только числители 411, уменьшенные на единицу, дробей вида r = di ?

h и 35

Вектор Т загружается в блок 6 памяти кодов состояний, содержлщ((й(1

d1 + п ячеек разрядностью lop„n.

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

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

В регистр 8 загружают код f состояния sy. И регистр 4 сдвига загружают число ненулевых элементов строки

f стохастической матрицы Р (значение координаты и вектора U), л в накап- 50 ливающий сумматор-вычигатель 5 указателя начала строки f — матрицы P (значение координлгы q вектора О).

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

Работа генератора сводится к реализации алгоритма управления (фнг.2). После загрузки нлчлльного состояния блок 1 упрлвле((ия нлходитВ зависимости от значений сигналов, пос гупающих от схемы 9 сравнения двоичных чисел ц с выхода элемента ИЛИ 1О, блок 1 управления становится в одно из следующих состояний: при сигнал "I>олы!(е" на выходе схемы 9 сравнения и сигнллл "0" на выходе элемента ИЛИ 10 (число, хранящееся в старших рлзрядлх регистра 4 сдвига не равно нулю) — в состоянии а(, при сигнлне "Меньше или равно" на выходе схемь(9 сравнения и сигнале "0 на выходе элемента ИЛИ

1Π— в состоянии л ; при сигнале

"Больше" на выходе схемы 9 срлвнения и сигнале "1" на выходе элемента ИЛИ

10 — в состоянии л, при сигнале

"Меньше или равно" нл выходе схемы

9 сравнения и сигнллс "1" нл выходе элемента ИЛИ 10 — B с стоянии л .

Пусть фиксируется с< стояние л (При этом подается управляю((ий сигнал "Сдвиг" нл регистр сдвигл и сигнал !!Сложить Нп нлклп:п(влю(!(ий сумматор-вычитлтель 5. В рсзульглте

1624446

35 этого в накапливающем сумматоре-вычитателе 5 Формируется новый адрес

Adr. На выходе блоков 6 и 7 памяти появляются новые координаты t и r, 5 которые соответствуют элементу строки Г матрицы Р, находящегося по ад— ресу Adr = Adr + (и /4) + 1 . Координата г поступает на первую группу информационных входов схемы 9 сравнения двоичных чисел .

Вновь срабатывает схема 9 сравнения, в зависимости от значения сигналов с выхода схемы 9 сравнения и с выхода элемента ИЛИ 10, вновь устанавливается одно из состояний а,, а, а и a < и T.p. Пусть фиксируется а<.

В состоянии а подается сигнал

"Сдвиг" на регистр 4 сдвига и сиг.Нал "Вычесть" на, накапливающий сумматор-вычитатель 5. При этом в накапливающем сумматоре-вычитателе 5 фиксируется новый адрес Adr. На выходе блоков 6 и 7 памяти появляются координаты t и r, которые соответ- 25 ствуют элементу строки f матрицы (P, находящегося по адресу Adr

Адг — PlJg/о 1 — с . Координата т поступает на первую группу информационных входов схемы 9 сравнения.

В зависимости от значения сигналов на выходе схемы 9 сравнения и на выходе элемента ИЛИ 10 вновь Фиксируется одно из состояний а, а, а а4,и т.д.

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

"Сложить" иа накапливающий сумматор-вычитатель 5. В результате этого в накапливающем сумматоре-вычитателе 5 Формируется адрес Adr, по ко- 40 торому происходит обращение к блокам 6 и 7 памяти. На выходе блоков

6 н 7 памяти появляются координаты и r, которые соответствуют первому ненулевому элементу строки матрицы P, т.е. находящегося по адресу Adr = Adr + с (на выходе 4.1 регистра 4 сдвига поступает ноль).

Блок 1 управления переходит в

СОСТОЯНИЕ ал .

Подается сигнал |Запись" на регистр 8. Этот же сигнал подается иа вход "Запись" регистра 4 сдвига и накапливающего сумматора-вычитателя

5 ° При этом в регистр 8 фиксируется очередное состояние s марковского процесса, в регистр 4 сдвига фиксируется координата п, вектора U (число ненулевых элементов строки И матрицы Р), а в накапливающем сумматоревычитателе 5 записывается коордииага qg вектора О (указатель начала с тр оки матрицы Р) .

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

5 и "Опрос" — на датчик 2. Вновь в накапливающем сумматоре-вычитателе

5 формируется адрес, по которому происходит считывание 6 и 7 памяти, вновь срабатывает схема 9 сравнения.

По признаку сравнения и значению сигнал" "на выходе элемента ИЛИ 10 блок 1 управления вновь переходит и одно иэ состояний а<, а, а, а и т.д.

Таким образом, смена состояний а, — а g обеспечивает логарифмический поиск (мегод половинного деления) очередного состояния марковского процесса, а состояние а4 — Фиксацию найденного состояния.

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

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

ИЛИ,причем третий выход блока управления соединен с входом записи регистра сдвига и с входом разрешения записи накапливающего сумматора-вычитателя, первый информационный вход которого соединен с выходом младптих разрядов третьего блока памяти, выход старших разрядов которого соединен с ииформа1О ционным Входом р(гllc т J> 1 c (Ðè гл в(1хо. 1 которого соединен с вторым инАормлДИОННЫМ ВХОДОМ НЛКЛПЛП1<Л(<11<(ЕГО СУММЛтора-вычитателя, вьг(о11 которого соединен с адресными вх< дами первого и второго блоков памяти, выходы стлрших разрядов регистра сдвига соединены с входами эяемента 1ПИ, инверсный Выход котор< го сое,IIIICII с;<опо;1—

НИ 1 (", 1,Н(П,; Р. О.< ОМ ЭЛ <1;, <<п «(<<1",1«(С КИ.,;

Гдовий блока управ. 1ени11, «етв(ртыи

ВЫХ(;1 КОТОРОI О Г РГI< Ill! PI< Г ВХОДОМ сдвигл pt гистрл с;<вигл, пятый выход блока упрлвдепиp. с< PIIèl