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

0}

Is5

й и 4- О5

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

Фиг.1

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

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

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

Генератор случайного марковского процесса содержит блок 1 управления, датчик 2 равномерно распределенных случайных чисел, блок 3 памяти с выходами 3.1 старших разрядов и 3.2 - младших разрядов, регистр А сдвига с выходами 4.1 старших разрядов и 4.2 - младшего (нулевого) разряда, накапливающий сумматор-нычитатель 5, блок 6 памяти, блок 7 памяти, регистр 8, схему 9 сравнения, элемент ИЛИ 10.

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

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

(а0, а ,, яг, а,.

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

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

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

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

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

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

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

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

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

5

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

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

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

Пусть задан марковский процесс, описываемый конечным множеством состояний S fs; i 0 и стохастической матрицей переходов Р . где Р jj, - вероятность перехода за один шаг из состояния s; в состояние

0

Ч

k 0, п-1, Р;к Х1

,-ГГ)

IX

К

tK

- целое.

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

и // и8 // ;

Q /|q,//, 1 0, п-1;

R - II / ;

Т //Ц//, h 0, d + п,

где d - Г;РПОНЬ разряженности матрицы Р, (d определяется как отношение числа нгнулепых элементов к общему числу элементов стохастической матрицы переходов).

Координата и. вектора И содержит число ненулевых элементов строки матрицы Р, т.е..

ио Ко и. К,,

1

11 п-1 Nn-. )

где N0, N,,,...,Nn.( - число ненулевых элементов строк 0, 1,..., п-1 матрицы Р.

Координата о. вектора О содержит сумму вида

uo + U1 f +ий-1 + т еqn a u;

„, о + ui +. -..« n z + (п-1) q n-г + un-2+ 1

5 1

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

О, если Р О,

0

Т

к

если Р. / 0.

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

Из матрицы Р вают в вектор R элементы Р.,

построчно выписы- нуль и ненулевые

, в яектор Т нуль и индексы столбцов к ненулевых элементов

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

Вектор R загружается в блок 7 памяти элементов строк, содержащий d + n ячеек разрядностью тп, причем в памяти записываются только числители dL, уменьшенные на единицу, дробей вида г h dj,. .

Вектор Т загружается в блок 6 памяти кодов состояний, содержащий du + п ячеек разрядностью 1ор,„п.

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

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

В регистр R загружают код f состояния s/. В регистр 4 сдвига загружают число ненулевых элементов строки f стохастической матрицы Р (значение координаты иг вектора U), а в накапливающий сумматор-вьгчитатель 5 указателя начала строки f - матрицы Р (значение координаты q, вектора О). На этом процесс загрузки исходных данных завершен.

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

244466

ся в состоянии а0. Сигнал Опрос поступает на вход датчика 2. Сигнал Сложить поступает на суммирующий вход накапливающего сумматора-вычи- тателя 5. Датчик 2 вырабатывает m-разрядное двоичное число . j х 2 и величина xj подается на вторую группу информационных входов схемы

. Q 9 сравнения двоичных чисел. Одновременно в накапливающем сумматоре- вычитателе 5 формируется текущий адрес Adr, по которому выполняется обращение к блоку 6 памяти кодов состо 5 яний и к блоку 7 памяти элементов строк. На выходе блоков 7 и 6 памяти появляются координаты г и f соответственно. Эти координаты соответствуют элементу строки f матри20 цы Р(, находящегося по адресу Ad p

1i + + С0 гле С0 эначе ние младшего разряда регистра 4

сдвига. Координата г поступает на первую группу информационных входов

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

5

В зависимости от значений сигналов, поступающих от схемы 9 сравнения двоичных чисел ч с выхода элемента ИЛИ 10, блок 1 управления становится в одно из следующих состоя- .- ний: при сигнал Больше на выходе схемы 9 сравнения и сигнала О на выходе элемента ИЛИ 10 (число, хранящееся в старших разрядах регистра 4 сдвига не равно нулю) - в сос5 тоянии а(; при сигнале Меньше или равно на выходе схемы 9 сравнения и сигнале О на выходе элемента ИЛИ 10 - в состоянии а„; при сигнале Больше на выходе схемы 9 сравнения

0 и сигнале 1 на выходе элемента ИЛИ 10 - в состоянии при сигнале Меньше или равно на выходе схемы 9 сравнения и сигнале 1 на выходе элемента ИЛИ 10 - в спсчоянии л.

5 Пусть фиксируется состояние а .

При этом подается управляющий сигнал Сдвиг на регистр 4 сдвига и сигнал Сложить на нлклп швающий сумматор-вьгчитатель 5. R результате

этого в накапливающем сумматоре-вы- читателе 5 формируется новый адрес Adr. На выходе блоков 6 и 7 памяти появляются новые координаты t и г, которые соответствуют элементу строки f матрицы Р , находящегося по адресу Aclr Adr + Cui/ J + Koop- дината г поступает на первую группу информационных входов схемы 9 сравнения двоичных чисел.

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

а, и афи т.д. Пусть фиксируется аг.

2

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

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

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

В состоянии а выдается сигнал Сложить на накапливающий сумма- тор-вычитатель 5. В результате этого в накапливающем сумматоре-вычитателе 5 формируется адрес Adr, по которому происходит обращение к блокам 6 и 7 памяти. На выходе блоков 6 и 7 памяти появляются координаты t и г, которые соответствуют первому ненулевому элементу строки f матрицы Р , т.е. находящегося по адресу Adr Adr + c (на выходе 4.1 регистра 4 сдвига поступает ноль).

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

Подается сигнал Запись на регистр 8. Этот же сигнал подается на вход Запись регистра 4 сдвига и накапливающего сумматора-вьгчитателя 5. При этом в регистр 8 фиксируется очередное состояние марковского процесса, в регистр 4 сдвига фиксирется координата иу вектора U (число ненулевых элементов строки W матри

10

15

20

цы Г), а в накапливающем сумматоре- рычитателе 5 записывается координа- ia qyy вектора О (указатель начала строки матрицы Р).

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

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

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

а - фиксацию най5

0

5

0

5

0

5

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

Генератор случайного марковскотс процесса, содержащий блок управления, первый, второй и третий блоки памяти, датчик равномерно распределенных случайных чисел, регистр и схему сравнения, причем группа выходов схемы сравнения соединена с группой входов задания логических условий блока управления, первый выход которого соединен с входом опроса датчика равномерно распределенных случайных чисел, выход которого соединен с первым информационным входом схемы сравнения, второй информационный вход которой соединен с выходом первого блока памяти, выход второго блока памяти соединен с адресным входом третьего блока памяти и с информационным входом регистра, вход записи которого соединен с вторым выходом блока управления, выход регистра является информационным выходом генератора, о т- л и чающийся тем, что, с целью повышения быстродействия, в него введены регистр сдвига, накапливающий сумматор-вычнтатель и элемент ИЛИ,причем третий выход блока управления соединен с входом записи регистра сдвига и с входом разрешения записи накапливающего сумматора-вьгчитателя, первый информационный вход которого соединен с выходом младптих разрядов третьего блока памяти, выход старших ратрядов которого соединен с информаЦИОННЫМ ВХОДОМ регистра СДВИГа, ПЫХ01Т

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

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

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

входом чад;-.нич -готически условий блок.1 управления, четвертый выхгд которого coe uu OH г входом сдвига регистра сдвига, пятый выход блока управления соединен с входом разрешения сложения накапливающего сумматор-вычитятр.;ч, вход разрешения вычитания к-морого соединен с шестым выходом управления.

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

Сложмть на накапливающий сумматор- вычитатель 5