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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных-объектов. Целью изобретения является повышение точности формирования случайного марковского процесса. Для достижения поставленной цели в генератор введены регистр 7 сдвига, группа элементов И 8, элемент И 9, второй датчик 11 случайной двоичной цифры, мультиплексор 12, элемент ИЛИ-НЕ 13, элемент ИЛИ 14, накапливающий сумматор 15. Очередное состояние марковского процесса вырабатывается путем сравнения случайных чисел, ваемых датчиком 5, с элементами модифицированной матрицы переходных вероятностей и генерацией равномерно распределенных чисел, полученных путем случайного половинного деления с помощью регистра 7 сдвига и датчиков 10 и 11. 2 ил. (Л

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

СОЦИО ЛИСТ ИЧЕСНИХ

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

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

Н А BTOPCKOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4642374/24 (22) 24 ° 01,89 (46) 07,01.91 Бюл. И 1 (» ) Кишиневский политехнический институт им. С.Лазо (72) А.А.Гремальский и С.N.Àíäðîíèê (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 1453403, кл . С 06 F 7/58, 1987.

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

ltd 1531093, кл. С 06 F 7/58, 1988. (54) ГЕНЕРАТОР СЛУЧАЙНОГО ИАРКОВСКОГО

ПРОЦЕССА (57) Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов.

„„SU„„1619262 A 1

Целью изобретения является повышение точности формирования случайного марковского процесса. Для достижения поставленной цели в генератор введе" ны регистр 7 сдвига, группа элементов И 8, элемент И 9, второй датчик 11 случайной двоичной цифры, мультиплексор 12; элемент ИЛИ-НЕ 13, элемент ИЛИ 14, накапливающий сумматор 15. Очередное состояние марковского процесса вырабатывается путем сравнения случайных чисел, вырабатываемых датчиком 5, с элементами модифицированной матрицы переходных вероятностей и генерацией. равномерно распределенных чисел, полученных пуе тем случайного половинного деления с помощью регистра 7 сдвига и датчиков 10 и 11. 2 ил.

1619262

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

Цель изобретения — повышение точности формирования случайного марковФ ского процесса.

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

Генератор случайного марковского процесса содержит счетчик 1, блоки

2- 4 памяти, датчик 5 равномерно распределенных случайных чисел, схему 6 сравнения, регистр 7 сдвига с выходами 7.1 старших раз-.ядов и 7.2 младшего разряда, блок 8 элементов И, элемент И 9, датчики 10 и 11 случайной двоичной цифры, мультиплексор 12, элементы ИЛИ !3 и ll4, накапливающий сум" матор 15 и блок 16 управления.

Счетчик 1 предназначен для хранения и формирования адреса, по.которому осуществляется обращение к блокам 3 и 4 памяти. Блоки 2-4 памяти предназначены для хранения в сжатой

1 форме стохастической матрицы переходов. Считывание информации из блс— ков 2-4 происходит при поступлении соответствующих адресов на их адресные входы.

Регистр 7 сдвига предназначен для

35 хранения и сдвига в сторону младшего разряда информации, поступающей на его информационный вход.

Накапливающий сумматор 15 предназначен для формирования и хранения 40 текущего состояния цепи. Кроме того, код текущего состояния цепи является адресом, по которому происходит обращение к блоку 2 памяти.

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

В состоянии а блок 16 управления выдает; сигналы "Запись " в счетчик и "Опрос" датчи «а 5.

В состоянии а блок 16 управпения вь;дает сигнал "Сброс" на накапливающий сумматор 15.

В состоянии а блок 16 управления выдает сигналы "Вход 1" на мультиплексор 12; "Сложить" на накапливающий сумматор 15 и "+1" в счетчик 1.

В состоянии а блок 16 управления выдает .сигналы: Запись" в регистр 7 и "Опрос" датчиков 10 и 11. !

3 состоянии а блок 16 управления выдает сигнал "Сложить" на накапливающий сумматор 15.

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

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

Пусть задан марковский процесс описываемый конечным множеством состояний S = (sIII i = О, и-1 и стохастической матрицей переходов Р = //P I// и хп, где р, — вероятность перехода за один такт из состояния s. в состояние s, i,g = О, п-1, р, =ф11 2 ", ф, — целое, m — - параметр, определяющий точность представления элементов стохастической матрицы переходов °

Матрица P хранится в сжатом виде в виде векторов Q = //(j //, R =

//r //, Т = //t //.

Векторы Q, R и Т получаются следующим образом. устанавливают q> = 0 Сжимают строку Ро матрицы Р. Для этого в строке выделяют подстроки Р, P о .Р из последовательно расположенных о друг за другом одинаковых элементов.

Для каждой подстроки Р вычисляется

К к о чиспо 1(Р ) входящих в нее элементов, о

Просматривая строку Р слева направо, в координаты г„,г,г ...,., Го э Г19 С Ф, ° ° ° Векторов R и т последовательно выписывают: координату г<— длину подстроки P, уменьшенную на

К о к единицу, т.е. величину 1(P )-1; в координату t< — сумму всех элементов строки Р от Р до PoI, т.е. величиО 00 ну . P, где h — ичдекс столбца

К послеДнего элемента подстроки Р, Пусть, при сжатии строки ? s R ь и Т были выписаны. по Р значении, где

Ь, — число подстрок в строке Ро .

Устанавливают q< Щ . А!.алогично строке Р сжимают строку Р и в вектоО рах R и Т выписывают соответствующие значения, Пусть, — число подстрок строки PI.

Устанавливают q = q< +P,. Аналогичным образом сжимают строки Р, 1619262

P>,....,Pn,, определяя значение координат r р г ..., ., г

tp. В, t tp

При этом

qy qz +Pz3

qq q3 + Ðóю

° ° ° ° ° ° ° ° ° ° ° т ф 10 ь-(Ч n- + и-

Вектор Q загружается в блок 2 памяти. Вектор R загружается в блок 3 памяти, Вектор Т загружается в блок 4 памяти, причем в память заносятся значения 0, где 0(в — числители дробей виде t 2

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

Число координат вектора Ч равно и.

Числа координат вектора R и вектора Т зависят от средней длины (т.е. от числа элементов) 1 подстрок вида р матрицы P. Вектор R(T) содержит столько координат, сколько подстрок вида P, можно выделить в матрице P. Число подетрок определяется как и /1, где n — общее число элементов матрицы P. 30

Координаты q вектора Q принимают значения в диапазоне от 0 до n /1.

Следовательно, разрядность блока 2 памяти, в котором хранится вектор Q определяется как j logan /1, где

) 1 обозначает ближайшее целое в сторону увеличения.

Координаты т вектора R принимают значения от 0 до п-2. Следовательно, разрядность блока 3 памяти, в кото- 40 ром хранится вектор R определяется как (log ï-1L .

Коордийаты t вектора Т имеют разрядность ш. Следовательно, суммарный объем памяти предлагаемого генера- 45 тора составляет Ч и ° j log тР/1 (+

2n

+ (J log n-1 Г + m) бит.

Начальное состояние sf цепи Маркова задается следующим образом. В накапливающий сумматор 15 загружается код f состояния sf. При этом на выходе блока 2 памяти появляется координата qf, т.е. указатель начала строки Р< в блоках 3 и 4 памяти. На этом процесс загрузки исходных данных завершен.

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

"Пуск" блок 16 управления переходит в состояние а и вырабатывает управляющие сигналы, Сигнал "Запись" поступает на синхронизирующий выход генератора, указывая, что на его информационном выходе установлено состояние sf. При этом в счетчик 1 записывается координата gf,ïoñòóïàþùàÿ.. с выхода блока 2 памяти. Изменение содержимого счетчика 1 запускает процесс чтения из блоков 3 и 4 памяти. На выходе блока 3 памяти появляется координата r вектора К, т.е. значение длины подстрок P, уменьшенное на единицу, а о на выходе блока 4 памяти — значение соответствующей координаты вектора Т, h т. е. сумма вида P где ho

У

)=о индекс столбца правого элемента подо строки Р . Датчик 5 вырабатывает на своем выходе некоторое случайное число х.

После состояния а< блок 16 управления переходит в состояние а и содержимое накапливаюшего сумматора 15 равно нулю.

В зависимости от признака сравнения блок 16 управления переходит в состояние а либо в состояние а+

Допустим, что схема 6 сравнения выработала признак " ) ", т.е. случайное число х с выхода датчика 5 равномерно распределенных случайных чиh сел больше, чем число Р с =о выхода блока 4 памяти. Тогда блок 16 управления переходит в состояние а и выдает управляющие сигналы Вход 1 и и !

11 3I на мультиплексор 12. Сложить на накапливающий сумматор 15 и "+1 " в о счетчик 1, При этом число 1(Р )-1 с выхода блока 3 памяти передается на информационный вход накапливающего сумматора 15, сигнал "1" с выхода элемента ИЛИ 14 поступает на вход переноса накапливающего сумматора 15, в накапливающем сумматоре 15 выполняется операция сложения и его содержи мое становится равным (1(Р )-1) + ) о т !(1(Р ) h +1 = и где h — инО 1 Э 1 декс столбца левого, элемента подстроки,. следующей за подстрокой Р, т,е.

1619262 индекс столбца левого элемента подl строки P . Одновременно содержимое счетчика 1 увеличивается на единицу.

Изменение содержимого счетчика 1 вновь запускает процесс чтения из бло5 ков 3 и 4 памяти. При этом на выходе блока 3 памяти появляется очередная координата r вектора R т.е. знаt чение длины подстроки Р, уменьшен- 1 нсэ на единицу, а на выходе блока 4

hi памяти — значение,0 Р, где h !)=o индекс столбца правого элемента под,1 строки Р„ . Схема 6 сравнения выраба 15 тывает признак "Й" либо ">", Если схема 6 сравнения вырабатыh1 вает признак " ) " т.е. х ),".Я Р

3=0 3 и для подстроки Р блок !6 управле- 20 ния вновь вырабатывает управляющие сигналы "Вход 1" на мультиплексор 12

"Сложить" на накапливающий сумматор 15 и "+1" на счетчик 1 (состояние а ).

При этом в накапливающем сумматоре 15 записывается значение Ь + (1(P )- I )+

+1 = h (h< - индекс столбца левого элемента подстроки, следующей за подстрокой Р, т. е. индекс столбца левого элемента подстроки Р а содер- 0 э жимое счетчика 1 увеличивается на единицу. Изменение содержимого счетчика 1 вновь запускает процесс чтения из блсков 3 и 4 памяти и т.д.

Если же схем.л 6 сравнения вырабаты-15 вает признак "«(", блок 16 управления переходит в состояние а!. Таким образом, к моменту, когда блок 16 управления переходит в состояние а, в накапливающем сумматоре !5 нахо- 40

1( дится индекс h столбца левого зле3 мента первой подстроки Р для котоФ

h) рой х,>Р (Ь - индекс столбца 45 о у первого элемента подстроки Р ), а на выходе блока 3 памяти — зйачение длины 1(Р ) подстроки P,, умень1 шенной на единицу, т.е. значение (1(Р 6 )-1) 50

В состоянии а блок 16 управления выдает управляющие сигналы "Запись" в регистр 7 сдвига и "Опрос" датчи" ков !Ои 1 1 случайной двоичной цифры

При этом в регистр 7 сдвига с выха55 да блока 3 памяти записывается значение у 1 (P )-1, а датчики 10 и 11, независима друг ат друга, вырабатывают на своих выходах равно(

f . Если Р, = О, указанный код нулевой, Если же Р0 = 1, на информационный вход накапливающего сумматора 15 через элементы И группы элементов И 8 и мультиплексор 12 подается код с выхода 7.1 старших разрядов регист- ра 7 сдвига, т,е. содержимое регистра 7, деленное на 2. Следовательно, на информационный вход накапливающего сумматора 15 поступает код

Р ((у0/2)),где P ) обозначает ближайшее целое в сторону уменьшения.

Одновременно на вход переноса накапливающего сумматора 15 через элемент ИЛИ 14 поступает значение с выхода элемента И 9. Если Р = О, на вход переноса, очевидно, поступает

fi значение нуля, Если же P0 = 1, на вход переноса накапливающего сумматора 15 через элемент И 9 и элемент ИЛИ 14 с выхода 7.2 подается значение младшего разряда регистра 7 сдвига, т.е. остаток от деления содержимого и регистра 7 на 2. Другими словами, на вход переноса накапливающего сумматора 15 поступает код

Р (y nod2} где mod †. знак операции вычисления остатка от целочисленного деления.

Таким образом, в результате опера" ции сложения содержимое А накаплиC вающего сумматора 15 становится равным (о + PÎ Е ь/2 )+Ро(y шой2}, где А — предйдущее содержимое накапливающего сумматора 15, =.е. и

А = h, Р - двоичная цифра на вйходе дат:ика !О случайной двоичной цифры; (у /2 ) - код, поступающий с выхода 7.1 регистра 7 сдвига, Р двоичн. я цифра на втором выходе дат" чика ll случайной двоичной цифры; (у©mod2} — значение младшего разряда с выхода 7.2 младшего разряда регистра 7 сдвига.

1619262

В зависимости от значения сигнала

I на выходе элемента HJIH-НЕ 13 после состояния ао блок 16 управления переходит в состояние а либо в состоя5 ние а!.

Допустим, что на выходе элемента ИЛИ 14 присутствует сигнал "0".

Следовательно, хотя бы один из старших разрядов с выхода 7.1 регистр 7 сдвига отличен от нуля, т.е. (yg/2/ d й. Блок 16 управления пере- ходит в состояние а и выдает управляющие сигналы "Сдвиг" на регистр 7 сдвига и "Опрос" датчиков 10 и 11 рав-15 новероятной двоичной цифры. При этом в регистре 7 сдвига выполняется сдвиг и его содержимое становится равным 1 у/2 . На выходах датчиков 10 и ll появляются случайные двоичные 20

< !! цифры Р1 и Р> соответственно. После состояния а6 блок 17 управления вновь переходит в состояние а и выдает управляющий сигнал "Сложить" на накапливающий сумматор 15. При этом содер- 25

7 il

1 (Pg )-1 = А; Ao р ((уо/21)» А(= Aî + Po ((Уо 21 ) + î (yоmod2);

° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° (I y - /2J ); Aê= Aê + Pk,{(y„, 2J ) + Р,", (у, >mod2) у у вл

I а ее ° ° у

В состоянии ау блок 16 управления выдает управляющие сигналы "Запись" в счетчик 1 и "Опрос" датчика 5.При

35 этом сигнал на синхронизирующем выходе генератора указывает, что на его информационном выходе получено очередное состояние з цепи Маркова; в счетчике I запйсывается значение ко40 ординаты и, поступающее с выхода блока 2 памяти, и начинается новый цикл работы генератора.

Таким образом, процесс порожде"

45 ния очередного состояния s цепи Маркова при текущем состоянии sf выполняется .в два этапа: первый — этап поиска в сжатой строке Ру подстроки Р такой, что

50 р1 оке р1 второй — этап равномерной генерации состояния s< из множества состояний

}1 а й1 а 11 „.

55 и т.д. до тех пор, пока все старшие разряды с выхода 7.1 регистра 7 сдвига станут равными нулю. При этом на выходе элемента ИЛИ 13 установится сигнал "1" и блок 16 управления перейдет в состояние а<.

К моменту перехода блока 16 управления в состояние а1 в накапливающем сумматоре 15 будет зафиксировано случайное число

Ав = А +.Zs

Ф где Ао = Ь, - Po ((уо 2g) + Pî (yc mod2) +

+ ° ° ° + Р к- (1ук-г Й3 ) +

+ Р"к-а(ук-а mod2) + Р к- ((ук-<П3)+

+ Рк-1 (у„mod2) °

Из способа получения числа Z следует, что 0 < Z < yо и причем закон распределения случайного числа Z является равномерным.

Очевидно, число A также является случайным и равномерным распределено в диапазоне hg,...,h II .

Ц

Случайное число Я, Я = А 1, является кодом следующего состояния цепи

Маркова. жимое накапливающего сумматора 15 становится равным

t р

А А, + py ((yq/2) ) а у (у, mod2), где А

I — предыдущее содержимое накапливающего сумматора 15; (jy,/2)) — код, поступаюиий с вюкоИ да 7.1 регистра 7 сдвига;

P (Р ) — двоичная цифра на выхо1 1 де датчика 10 (11)(y

Если на выходе элемента ИЛИ )3 присутствует сигнал "0", т е хотя бы один из разрядов выхода 7.1 регистра 7 сдвига отличен от нуля, блок 16 управления вновь переходит в состояHHQ а ° а и т д

Таким образом, смена состояний а <- а блока 16 управления обеспечивает формирование в регистре 7 сдвига и в накапливающем сумматоре 15 следующих значений: (Выполнение первого этапа обеспечи- . вается сменой состояний а,а,а» а выполнение второго, этапа — сменой состояний а,а,а < блока 16 управления.

1619262

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

Генератор случайного марковского процесса, содержащий блок управления, три блока памяти, счетчик, схему сравнения, датчик равномерно распределенных случайных чисел и датчик случайной двоичной цифры, причем вход „пуска генератора является входом пуска блока управления, первый выход которого является синхронизирующим выходом генератора и соединен с входом записи счетчика, выход которого соединен с адресными входами первого и второго блоков памяти, выход первого блока памяти со.единен с первым информационным входом схемы сравнения, выход которой соединен с первым входом задания логически..: условий блока управления, второй выход которого соединен с входом опроса датчика равномерно распределенного ) случайного числа, выход которого соеди-, нен с вторым информационным входом схемы сравнения, третий выход блока управления соединен со счетным входом счетчика, информационный вход которого соединен с выходом третьего блока памяти, четвертый выход блока управления соединен с входом опррса датчика случайной двоичной цифры, отличающийся тем, что, с целью повышения точности формирования случайного марковского процесса, в него введены второй датчик случайной двоичной цифры, регистр сдвига, два элемента ИЛИ, блок элементов И, мультиплексор, элемент И и накапливающий сумматор, причем выход второго блока памяти соединен с.первым инфюрмационным входом мультиплексора и с информационным входом регистра сдвига, вход записи которого соединен с пятым выходом блока управления, шестой выход которого соединен с входом сдвига регистра сдвига, выход старших разрядов которого соединен с информационным входом блока элементов И и с входами первого элемента ИЛИ, инверсный выход которого соединен с вторым входом задания логических условий блока управления, четвертый выход которого соединен с входом опроса второго датчика случайной двоичной цифры, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом младшего разряда регистра сдвига, выход первого датчика случайной двоич2О ной цифры соединен с управляющим входом блока элементов И, выход которого соединен с вторым информационным входом мультиплексора, выход которого соединен с первым информационным входом накапливающего сумматора, второй информационный вход которого соединен с выходом второго элемента ИЛИ, седьмой выход блока управления соединен с входом записи накапливающего сумматора, вход разрешения сложения. которого соединен с восьмым выходом блока управления, девятый выход которого соединен с управляющим входом мультиплексора и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом элемента И„ выход накапливающего сумматора является информационным выходом генератора и соединен с адресным входом третьего блока памяти, 1619262

Составитель Д.Феликсон

Техред М.Дидик Корректор Н.Ревская

Редактор А.Мотыль

Заказ 48 Тираж Подписное

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

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

1роиэводственно-иэдателы кий комбинат "Патент", г. Ужгород, ул, 1 агарияа, 101