Вероятностный автомат Советский патент 1990 года по МПК G06N7/08 G06F17/00 G06F17/18 

i1 ,4П (

«-Я

«- /гКЙ

- л51 1

W/r

о

S

(Л

-И

:

I

Дли,, А. .jy

35

эо

35 30

г1зобретение относится к вычислительной технике и системам управления. Цель изобретения - повьшение достоверности моделирования стохастических объектов о Вероятностный автомат содержит блок 2 задания переходных вероятностей, блок 3 задания законов распределения, блок 4 генерации случайного кода, коммутатор 5, блоки 6, 10 буферной памяти, элемент ИЛИ 9, блоки 11 управления переключениями, входы и выходы устройства Веро- ятностньш автомат позволяет определить время своего пребывания в глу- бинном состоянии на основе матриц переходных вероятностей бинарных оце- нок выходных состояний, формируемых объектами внешней среды 1 ЗоП ф-лы, 10 ило, 1 табЛо

/2у « /Z

11

м

т

/5

- ъ

7/,

;&i/j.-/

10

1608684

Изобретение относится к вычисли- i тельной технике и системам управления и может быть использовано для моделирования процессов функционирования стохастических объектов, представляе- ;мых в виде двухуровневого автомата, в котором автомату верхнего уровня подчинены автоматы низшего уровня ; (подавтоматы)о

При смене состояний подавтоматов считается, что автомат находится в глубоком состоянии. Переход от одного подавтомата к другому осуществляет автомат верхнего уровня по заданной логике и в соответствии с мат- рицей переходных вероятностей

Цель изобретения - повьшение достоверности моделирования стохастических объектов

На фиг о 1 приведена структурная схема вероятностного автомата; на фиг6 2 - функциональная схема блока задания переходных вероятностей; на фиго 3 - функциональная схема блока , задания законов распределений; на фиг о 4 - функциональная схема блока генерации случайного кода; нафиг„5- функциональная схема коммутатора; на иго 6 - функциональная схема первого блока буферной памяти; на фиг 7- ункциональная схема второго блока буферной памяти; на фиго 8 -. функциоальная схема блока управления пере- i ключениями; на фиг,, 9 - граф-схема,

15 м

т 20 И

д п и 25 тр

30

оясняющая функ1ронирование автомата;. 35 а фиго 10 - временные диаграммы. Вероятностньй автомат содержит

эл

ав ни ны цы

ни сл пе пр ав

группу первых установочных входов

,. П -

I;: - 1|| (i,j 1 ,k) автомата, блок 2 задания переходных вероятностей,блок

3задания законов распределений, блок

4генерации случайного кода, коммутатор 5, первый блок 6 буферной памяти, группу вторых установочных входов

7 7ц , группу выходов ЗД-Б автомата,; элемент ИЛИ 9, второй блок 10 буферной памяти, блок 11 управления переключениями, первый 12 и второй 12, входы задания состояний автомата

Блок 2 задания переходных вероятностей содержит регистры 13, памяти (КхК) групп информационных вы ходов (i,j f7k)

Блок 3 задания законов распределен НИИ содержит () групп jiepBbix эле- ментов И 15|j-15); (i,j 1,k), группу управляющих входов 16 -16 jf, узлы;

1744 - 17кксравнения, К групп выходов

10

18,;-18, (,k) блока 3, К групп вторых элементов И 19,-19 jj (), группу вторых информационных входов ,

Блок 4 генерации случайного кода содержит управляющий вход 21, первых элементов И , второй элемент И 23, генератор 24 пуассоновс- кого потока импульсов, циклически зам- кнутьй регистр 25 сдвига, кодер 26 двоичного кода

Коммутатор 5 содержит управляющий вход 21, элементы ИЛИ , эле- 15 менты И 284-23.., группу выходов 29,-: 29,0 / .

Первьй блок 6 буферной памяти содержит первые элементы ИЛИ 30;,-30., триггеры 31 -31;, вторые элементы 0 ИЛИ ,0

Второй блок 10 буферной памяти содержит первый информационный вход 33i первый элемент ИЛИ 34, группу вторых информационных входов 35 35,, 5 триггеры; , вторые элементы ™ 374-37,„, группу выходов

Блок 11 з равления переключениями (фиго 8) содержит элемент ИЛИ 39 и

0

5

0

элементы И ,, ,

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

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

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

0

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

Вероятностный автомат работает следующим образом

1еред началом работы автомата по зым установочным входам 1 записы- в блок 2 задания переходных коды вероятностей приве ден|ной матрицы переходных вероятнос- Исходная матрица переходных ве- poя гнocтeй автомата имеет вид

пер

ваю гея

вер оятностей

Пе

TOtдетмат

цес са

ЯН1:ЯМИ

MOf. елирование ствляется- пa яти

ния It

По группе первых установочных вхо- доЕ I j- I; в регистр 13 J блока 2 загщсан код вероятности Р Pj(+ Pig +Р

-ГГ ,j о

Вероятностный автомат моделирует функционирование стохастического про- (объекта) с глубокими состо- В каждом глубоком состоянии

функционирования осуще- ВТорЪ1М блоком 10 буферной и блоком 11 сигналов управле- переключениями Модель смены состояний определяется, переходных вероятностей а процесс смены глубоких со4т ояний моделируется блоком 4 гене- случайного кода, блоком 3 за- законов распределений, коммута- 5 и первым блоком 6 буферной Если автомат находится в i-м состоянии, то на выходе будет выходной сигнал у| тем, как описьшать работу ав- ата, сделаем его формальное опре- ениео Здесь рассматривается авто- Мура

гхубоких мат рицей

1(1

рагии дария

TOIOM

пакятис rj убоком авт омата

ед

;Ук) SK

Н02

Х, S Y, П.

g..

к

где X - множество входных сигналов, причем X (х, Хй), где сигнал х,. - додается на вход 12;,, сигнал х, - на s . - мно- (Же0тво состояйий автомата; Y(y,y2 ,с-.

- множество выходных сигналов; - функция выходов, реализующая од- начное отображение S . - Y, причем

есхи автомат находится в подмножестве

086.84

10

15

-

состояний , то на выходе автомата будет сигнал у;; П - функция дов, задаваемая матрицей переходных вероятностей || ,( и таблицей переходов , причем если кадцое множество состояний S имеет элементы S |, S , о ,, S и автомат, находясь в состоянии S , получил сигнал х, то следующее состояние S е s выбирается в соответствии с матрицей /| Р, : |/

Автомату AI, сопоставляются подавтоматы А( х, S , у- , все автоматы , АХ ны Тсе, отличаются лишь обозначением состояний. Тогда функция переходов автомата АК| задается в виде таблицы переходов (см таблицу), где под обозначением W понимается выход из авто20 мата и определение последующего состояния в соответствии с матрицей переходных вероятностей (|Pij//

Функция переходов автомата Ау представлена в таблице

25

I/ П - причем

автоматы , , . о о ,А(| изоморф35

0

5

0

5

На граф-схеме автомата (фиго 9) с глубокими состояниями каждая ветвь (S - S ,„ ) графа соответствует полуавтомату А J,. о Автомат назван автоматом с глубокими состояниями, так как при получении сигналов х, |(поо1Црения) он переходит в состояние SJjj и при получении сигнала х (наказание) он переходит в состояние с индексом, на единицу меньшим, Тое автомат сйособ р запоминать действия, за которые, он п лучает поощрение Число m называется глубиной памяти Данная величина выбцт рается для моделирования конкретного объекта

Перед началом дроцесса моделирования на один из входов 7j группы подается импульс, определяющий, что выбра- но i-е начальное состояние . Пусть (фиг 10) импульс подан на вход 7 в момент времени t. Тогда в первом блоке 6 буферной памяти (фиГвб) импульс с входа 7 через элемент ИЛИ1

ЗО установит триггер 31

160 в единичное

|-состояниео На еди1шчном выходе триг- гера 312 установится потенциал, по переднему фронту которого через элементы ИЛИ 304, триггеры 31;,, 315-31 1 установятся в нулевые состояния С выхода 16 первого блока 6 буферной памяти будет подан потенциал на выход 8 автомата (на выходе автомата установлен выходной сигнал у,,), на вход 16 группы управляющих входов блока 3 задания законов распределений Также по переднему фронту сигнала с выхода 16 блока 6 через элемент ИЛИ 9 во втором блоке 10 бу ферной памяти будет установлен в единичное состояние триггер 36 (сигнал :подан от входа 33 через элемент ИЛИ 34, фиго 7)о По переднему фронту потенциала с единичного выхода триггера 36 , через элементы ИЛИ будутV установлены в нулевые состояния триггеры 36 второго блока 10 буферной памятио Кроме того, на выходе 38 ;| блока 10 будет установлен потенциал о

Блок 11 сигналов управления переключениями реализует функцию переходов П j в соответствии с таблицейоАв- томат функционирует в дискретные мо

менты времени t

о

J у о о о

Логическая

функция, определяющая нахож;: ение автомата в состоянии S , определяется

F s(t+1) Х; s (t)+S 2(t)4o „ „

+s;(t),

где Sj(t) - j-e состояние в предпест- вующий момент времени t. Логические функции, определяющие нахождение автомата в состоянии S ( ,ia-1) , определяются

)

F sj (t+1) ),

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

.к;

.подавтоматов А

к; t

определяется

FW x,S

Пусть, как показано на фиг 10, в следующий такт времени tj по входу 12 постуш л сигнал Тогда в блоке 11 в соответствии с функцией (t+1 ) 55 будет сформирован сигнал ререключе- ния автомата в состояние Действи-т тельно, в блоке 11 имеется потенциал

5

8

на выходе 38 i, который через элемент ИЛИ 39 будет подан на второй вход элемента И 40 f,,.,,, При подаче на первый вход элемента И 40 |Потенц1{ала от входа 12, на выходе 35 блока 11 будет сформирован сигнал, подаваемый на вход 35 блока 10 памяти,, Передним- фронтом потенциала триггер 36 блока

10будет установлен в единичное состояние. По переднему фронту с его единичного выхода через элемент ИЛИ 37 триггер 36 будет установлен в нулевое состояние

Пусть в такт времени t вновь пост JTEIHT сигнал X о В блоке 11 будет сформирован сигнал З тгравления переключениями вновь по функции. (t+1 Я и триггер 36 блока 10 памяти вновь останется в единичном состоянии

Пусть в такт времени t поступил по входу 12 сигнал х. Тогда в блоке

11будет сформирован сигнал управления переключением в соответствии с

5 функцией (t+1 Л Потенциал имеется на входе 38 блока 11 и подан сигнал на вход 12,0 На выходе будет сформирован сигнал, который будет подан на вход 33jj,.| второго бло0 ка 10 буферной памяти, по переднему фронту которого триггер 36,блока 10 будет установлен в единичное состоя0

5

0

5

ниео В такт t постзтшт сигнал по входу 12 и автомат будет переведен в состояние Sl

ni

будет а

Пусть, начиная с такта t , следовать серия из m сигналов Xj по входу 12,2 автомата Тргда,, в соответствии с функцией F Sj(t+1)j ,, автомат будет переведен в состояние S При поступлении очередного сигнала по входу 12 в блоке 11 будет сформирован сигнал управления переключением в соответствии с функцией FT-/. Деист- 5 вительно, в блоке 11 будет открыт элемент И 40 и сигнал сформирован на выходе 21 блока 11

Сигнал с выхода 21 блока 11 подается на управляющие входы 21 блока 4 Q генерации случайного кода и коммутатора 5 о

В блоке 4 (фиг 4) потенциалом по входу 21 открываются элементы И 22 j и закрывается элемент И 23 „ Генератор 24 пуассоновского потока импульсов имеет частоту, превышающую частоту импульсов на входе 21 Таким образом, п момент опроса на любом из выходов регистра 25 потенциал фиксиг

pye pye

па, вал дет

гея равновероятно о Кодер 26 коди- г унитарный код в двоичный код чис- равномерно распределенный в интер- г (0,1)о На выходах 20 блока 4 бу- сформирован код случа шого числа Этот код подается на группу вторых информационных входов блока 3 задания законов распределений

Сак как на входе 16 имеется по-t- тендиал, то в блоке 3 будут открыты элементы И 15,-15-,и на первые входы узл эв 17„-172|, сравнения будут поданы

второй строки матрицы выхэдов 14„ -1 АО 1/блока 2

21 э . р 4- И

Ч( 2( 2.г

l/ptj /I

с J

.+ Г

2k

А

lycTb код числа А Pgo А Р

Г3( 22 23 Тот 13. на выходах узлов 1 yg к сравненияход как нен

с в:

24 2К 20

будет потенциал, но только на вы- 3. 1824 блока 3 будет потенциал, так

потенциал с выхода узла 1 срав- ш закроет элементы И l,: 15 коммутаторе 5 (фиг, 5) сигнал 25 сода 18 через элемент ИЛИ 27

и элемент И 28 пройдет на выход 29 )ступит на вход 29 первого блока,

и п

6 бферной памяти В блоке 6 через

+РО, +Р.

. +Р,, +Р„

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

элемент Ш1Н 30 триггер 31 по перед- зо входам элемента ИЛИ, выход нему фронту сигнала будет установлен в единичное состояние Передним фронт

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

том

Ш шульса с выхода триггера 31

чер(1з элемент ИЛИ 32, триггер 31 будет

установлен в нулевое состояниес

На )ыходе 8 автомата будет установ-

лен

потенциал, что говорит о наличии

на &ГО выходе сигнала у. Через эле- мён ИЛИ 9 триггер 36 второго блока 10 ()уферной памяти будет переведен в единичное состояние Теперь будет осуцествлено моделирование при сигнал ; на выходе автомата Длительъ сигнала у определило во време- нк 1|1ребьшания автомата в глубоком сое

.

оянии, определенном множеством

ероятностный автомат позволяет

определить время своего пребывания

риц

оце

мых

Ф о

щии

НОС

лубоком состоянии на основе мат- переходных вероятностей бинарных :ок выходных состояний, формируеобъектагси внеинег среды.

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

о Вероятностный автомат, содержат блок задания переходных вероят- ей, блок задания законов распре-

20

25

10

15

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

5

0

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

2 Автомат по п 1, о т л и ч а ю-г щ и и с я тем, что блок управления переключениями содержит элемент ИЛИ 5 и т+1 элементов И, причем информационные входы i-x (i 1,m) элементов И подключены к входам элемента ИЛИ, выход которого подключен к информаци-

0

11

1608684

ониому входу (т+1)-го элемента И, управляющий вход которого подключен к первому входу задания состояний авто- :мата блока, второй вход задания состояний автомата которого подключен к

fl f

11 41

ф

ПзГ1

/

41

/ /

12 72

/.

12

ф

ф ф

, ii f г,/7

% .л-/ W V Г f Ф

i I y%2

«.;,

Фиг,

. 12

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

/V

i2 п

iff 4ff

Ф /..Ф

LjSn

ъ

(ilr/4

сзш

vF W/r/ -/%/f

Г Т.-Т

/ 20220п игЛ

Фиг. 6

35f 33

и

3

38

35t

,r

ШигЛ

38i 38t 38з 38

фиг. 8

383

ff35m

38/jj

38/n-i 38flft

J5

J5/77

m-1

Составитель С Колесник Put.lO

Редактор Н. Тупица Техред А.Кравчук Корректор О. Кравцова

1608684