Вероятностный автомат

 

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

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

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

РЕСПУБЛИК (19) Ц1)5 С 06 Р 15/20

ГОС

ПО И

ПРИ (54) (57) тельн ния.! (2 ) ,(22) (46) (71) инст (72) (53) (56) Ф 12

У 12

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

БРЕТЕНИЯМ И ОТКРЫТИЯМ

НТ СССР

BTOPCHOMY СВИДЕТЕЛЬСТВУ

456295/24-24

6.07 .88

3.11.90. Бып. ) - 43 аганрогский радиотехнический ут им. В.Д. Калмыкова .И. Финаев

681.333(088.8) торское свидетельство СССР

296, кл. G 06 F 15/20, 1988. орское свидетельство СССР

297, кл. G 06 F 15/20, 1984.

ЕРОЯТНОСТНЫЙ АВТОпАТ зобретение относится к вычислий технике и системам управлеель изобретения — повышение достоверности моделирования стохастических объектов. Вероятностный автомат содержит блок 2 задания переходных вероятностей, блок 3 задания законов распределения, блок 4 генерации случайного кода, коммутатор 5, блоки б, 10 буферной памяти, элемент

ИЛИ 9, блоки 11 управления переключениями, входы и выходы устройства. Вероятностный автомат позволяет определить время своего пребывания в "глубинном" состоянии на основе матриц переходных вероятностей бинарных оценок выходных состояний, формируемых объектами внешней среды. 1 з.п. ф-лы, 10 ил., 1 табл.

) 608684

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

При смене состояний подавтоматов считается, что автомат находится в

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

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

На фиг. 1 приведена структурная схема вероятностного автомата; на фиг. 2 — функциональная схема блока задания переходных вероятностей; на фиг. 3 — функциональная схема блока, 25 задания законов распределений; на фиг. 4 — функциональная схема блока генерации случайного кода; на фиг.5— функциональная схема коммутатора; на

Фиг. 6 — Функциональная схема первого блока буферной памяти; на фиг.7— функциональная схема второго блока буферной памяти; на фиг. 8 — Функциональная схема блока управления переключениями; на фиг. 9 — граф-схема, поясняющая функционирование автомата;, 35 на фиг. 10 — временные диаграммы.

Вероятностный автомат содержит группу первых установочных входов

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

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

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

7, -7y, группу выходов 8 -8к автомата, элемент ИЛИ 9, второй блок 10 буферной памяти, блок 11 управления переключениями, первый 12< и второй 12 входы задания состояний автомата.

Блок 2 задания переходных вероятностей содержит регистры 13„,-13хх памяти (KxK) групп информационных вы ходов 14< — 14;" (i,j=Г,k).

Блок 3 задания законов распределе- . ний содержит (К"К) групп первых эле-

55 ментов И 15< -15;„(i,j=1,k), группу управляющих входов 16,-16xr узлы

17н — 17«сравнения, К групп выходов

18 -18,. (i=1,k) блока 3, К групп втлhi kl У рых элементов И 19, -19; .(.i=1,k), группу вторых информациойных входов

20 -20>.

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

Коммутатор 5 содержит управляющий вход 21, элементы ИЛИ 27 -27» элементы И 28 -28, группу выходов 29„29к.

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

ИЛИ 32 32к °

Второй блок 10 буферной памяти со-. держит первый информационный вход 33, первый элемент ИЛИ 34, группу вторых

3 информационных входов 354 -35„„ триггеры; 36< -36 „, вторые элементы

ИЛИ 37 -37» группу выходов 38 -38„„.

Блок 11 управления переключениями (фиг. 8) содержит элемент ИЛИ 39 и элементы И 40 -40,, Первая группа установочных входов автомата предназначена для обеспечения записи в блок 2 задания переходных вероятностей кодов исходной матрицы переходных вероятностей.

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

Вторая группа входов 7 автомата предназначена для задания начального состояния автомата. Группа выходов 8 предназначена для выдачи во внешнюю

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

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

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

5 1608684 6 еред началом работы автомата по состояний Б", то на выходе автомата

ым установочным входам 1 записы- будет сигнал у, ; П „- — функция пере йк ся в блок 2 задания переходных дов, задаваемая матрицей переходных ятностей коды вероятностей приве- вероятностей ((Р; (f и таблицей перехо«.! 5 !! ой матрицы переходных вероятыос- дов, причем если каждое множество сосИсходная матрица переходных ве- тояний S имеет элементы S S,...,S ностей автомата имеет вид и автомат, находясь в состоянии Б, получил сигнал х, то следующее состоР11 Р!2 ... Р, ь аа 2k

К1 k2 -

Р11 ) Р11 +Р12, ° ° ., Р „+Р„+... +Р, Р У Р 21 +Р 2У о о У Р +РУ + ° ° +Рд1

Р„„,Р,! +Р,...,Pk(+PK2+...+Pkk

По группе первых установочных вхо-! п

I ° в регистр 13 !блока 2

1 сан код вероятности P = Р + P + !! 11 !2

+Р," .

Вероятностный автомат моделирует ционирование стохастического проЭ са (объекта) с "глубокими" состоями. В каждом "глубоком" состоянии елирование функционирования осущеляется вторым блоком 10 буферной ти и блоком 11 сигналов управлепереключениями. Модель смены убоких" состояний определяется рицей переходных вероятностей

; ((, а процесс смены "глубоких" тояний моделируется блоком 4 генеслучайного кода, блоком 3 заия законов распределенйй, коммутаом 5 и первым блоком 6 буферной ти. Если автомат находится в i-м убоком" состоянии, то на выходе 8 омата будет выходной сигнал у, . с ед тем, как описывать работу авата, сделаем его формальное опреение. Здесь рассматривается автоМура

AK = (X Б П Ик

K к до за фун це я мо ст ни !!г ма

П со

P да то п

tt ав

Пе то д ма

Х вЂ” множество входных сигналов, ем Х = (х, х ), где сигнал х ается на вход 12„, сигнал х, — на д 12,;-S = S 1 US " Y, причем автомат находится в подмножестве гд лр цо

1вх же у„) к но ес риведенная матрица переходных вероятностей автомата имеет вид к

10 яние S E S выбирается в соответст! вии с матрицей ((Р, J(.

Автомату А сопоставляются подавтоматы Ak = (х, S, у;, П„ .)причем все автоматы А А ... Ак изоморфк!у 1с2э . э К ны т.е. отличаются лишь обозначением состояний. Тогда функция переходов автомата Ак, задается в виде таблицы переходов (см. таблицу), где под обо» значением M понимается выход из авто20 мата А„; и определение последующего состояния в соответствии с матрицей переходных вероятностей ((Р!1(1 .

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

25 к;

X ! !

S! Б2 S - -° -Sm-1 S÷

l 3

Ф 1 ! !

Х1 Sù Sm Sm - -° - Se SN !

1 !

Х2 W Б, S2 . ° ° Б!!!.2 Б,„!

На граф- схеме автомата (фиг. 9) с

"глубокими" состояниями каждая ветвь (S — S щ ) графа соответствует полуав4 томату А „.. Автомат назван автоматом и с "глубокими состояниями, так как при получении сигналов х (поощрения) он переходит в состояние S и при поЩ лучении сигнала х (наказание) он пе.,2

45 реходит в состоя е с и"д ом. На единицу меньшим, т.е. автомат способ запоминать действия, за которые,он п у. лучает поощрение. Число ш называется глубиной памяти. Данная величина выбз! -, рается для моделирования конкретного объекта.

Перед началом процесса моделирования на один из входов 7; группы подается импульс, определяюций, что выбра:но i-e начальное состояние автомата.

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

1608684 в

F (в, (t+t)7 - к,в „,(н).

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

S,,подавтоматов Ак., определяется

1

ГЫ=х 81, 50

Пусть, как показано на фиг. 10, в следующий такт времени t< по входу

12 постуш л сигнал Х1. Тогда в блоке

11 в соответствии с функцией yfSI(t+1)) будет сформирован сигнал переключения автомата в состояние Я . Действи» тельно, в блоке 11 имеется потенциал,"30 установит триггер 31< в единичное 1

;состояние. На единичном выходе триг" гера 312 установится потенциал, по переднему фронту которого через элементы ИЛИ 30, 30ц-30 к триггеры

31 „, 31ф -31к установятся в нулевые состояния. С выхода 16 первого блока

6 буферной памяти будет подан потенциал на выход 8 автомата (на выходе автомата установлен выходной сигнал у ), на вход 16 группы управляющих входов блока 3 задания законов распределений. Также по переднему фронту сигнала с выхода 16 блока 6 через элемент ИЛИ 9 во втором блоке 10 буферной памяти будет установлен в единичное состояние триггер 36 (сигнал подан от входа 33 через элемент ИЛИ

34, фиг. 7). По переднему фронту потенциала с единичного выхода триггера 36, через элементы ИЛИ 37 -37> будут установлены в нулевые состояния триггеры 36 -36„, второго блока 10 буферной памяти. Кроме того, на выходе 25

38 блока 10 будет установлен потенIJHGJI o

Блок 11 сигналов управления переключениями реализует функцию переходов П к в соответствии с таблицей.Ав- 30 томат функционирует в дискретные моменты времени t 0, t Логическая функция, определяющая нахождение автомата в состоянии S, определяется

)YI !

F(s (t+I)7=х,(и (t)+s (t)+...

+s (t)7, где S (t) — j-e состояние в предшествующий момент времени t, Логические функции, определяющие нахождение автомата в состоянии S .(j=1,m-1), определяются на выходе 38 1, который через элемент.

ИЛИ 39 будет подан на второй вход элемента И 40 +(. При подаче на первый вход элемента И 40 (потенциала от входа 12 „ на выходе 35 „„ блока 11 будет сформирован сигнал, подаваемый на вход 35 блока 10 памяти. Передним. фронтом потенциала триггер 36, блока

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

Пусть в такт времени t вновь пой ступит сигнал х . В блоке 11 будет сформирован сигйал управления перекнвненинни вновь цо функции. FPS (t+I)) и триггер 36,„ блока 10 памяти вновь останется в единичном состоянии.

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

11 будет сформирован сигнал управления переключе(нием в соответствии с функцией FPS . (t+1)(. Потенциал име3 ется на входе 38)1 олока 11 и подан сигнал на вход 12 . На выходе 35 )) будет сформирован сигнал, который будет подан на вход 35 „,второго блока 10 буферной памяти, по переднему фронту которого триггер Зб „,блока 10 будет установлен в единичное состояние. В такт t< поступит сигнал по входу 12 и автомат будет переведен в состояние S

Пусть, начйная с такта t, будет .у и следовать серия из ш сигналов х по входу 12 автомата. Тогда. в соответствии с функцией Р (Б (t+1)l, автомат

3 будет переведен в состояние S . При

1 поступлении очередного сигнала по входу 12 в блоке 11 будет сформирован сигнал управления переключением в соответствии с функцией РИ. Действительно, в блоке 11 будет открыт элемент И 401 и сигнал сформирован на выходе 21 блока 11.

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

В блоке 4 (фиг. 4) потенциалом по входу 21 открываются элементы И 22 22 и закрывается элемент И 23. Генератор 24 пуассоновского потока импульсов имеет частоту, превышающую частоту импульсов на входе 21. Таким образом, в момент опроса на любом из выходов регистра 25 потенциал фикси-. ся равновероятно. Кодер 26 кодиунитарный код в двоичный код чисравномерно распределенный в интер(0,1). На выходах 20 блока 4 бусформирован код случайного числа тот код подается на группу вторых рмационных входов 20 -20> блока 3 ния законов распределений. ак как на входе 162 имеется по- L ал, то в блоке 3 будут открыты енты И 15,-15 и на первые входы в 17,-17 „ сравйения будут поданы второй строки матрицы (Р; II с з

3 дов 142t -142Káëoêà 2.

Р2+Р 1 Р +Р + ° +12М г(t гг 2I г2. усть код числа А > Рг„Ау Р,+ Р, з +Ргг+Рг3 А6 Ъ +Ргг+Р23 24 ° а на выходах узлов 1724-17«сравнеия будет потенциал, но только на вы18 блока 3 будет потенциал, так потенциал с выхода узла 1724срав я закроет элементы И 19 -19 „, коммутаторе 5 (фиг. 5) сигнал 25 ода 18 4 через элемент ИЛИ 274 э емент И 284 пройдет на выход 29 ступит на вход 294 первого блока, ферной памяти. В блоке 6 через ент ИЛИ 30 триггер 314 по перед- 30 фронту сигнала будет установлен ничное состояние. Передним фрон-, импульса с выхода триггера 314 з элемент ИЛИ 322 триггер 31 буустановлен в нулевое состояние.

ыходе 84 автомата будет установпотенциал, что говорит о наличии

ro выходе сигнала у4. Через элеИЛИ 9 триггер 36 второго блока уферной памяти будет переведен в 40 чное состояние. Теперь будет ествлено моделирование при сигна выходе автомата у4. Длительь сигнала у определило во време2 ребывания автомата в "глубоком" оянии, определенном множеством руе руе ла, вал дет

А. инф зад тен эле узл код вых

А>

Тог ход как не с в и и б б эле нем н е том чер дет

На лен на мен

10 еди ос нал нос сос

8 2 ероятностный автомат позволяет делить время своего пребывания лубоком" состоянии на основе матпереходных вероятностей бинарных

50 ок выходных состояний, формируеобъектами внешней среды. опр

Риц оце мых

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

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

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

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

И подключены к входам элемента ИЛИ, выход которого подключен к информаци1608684

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

11К 11h 111

° °

° ° Ô ° Ф °

Ц11 13 12 ° °

° Ф ° ° ° °

Н11 1411 1411 1412 Й12 14

1 1411 1 1г ба

° ° Ô ° Ф °

ЦИ1 15Hz ° °

° ° ° ° ° ° 1 ° °

1 2 и 1, 14/Я

Йк1 Hg1 14к1 14gz14pg

Pual

n f 2

- Пс 1 Ыс 1 Яа.1 1 z 1Фс2 44с2

f4gp(1 ск 14 к

2 rr

2А

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

2 д 1 2 и

1П 111 111 112 112 112

° Q rr

141 f4> 141

111 ба

° Ф °

° Цю

/7

14, 14икикк

1608684

1В1н 18zg 1Вкм

21

Фиг. 0

1608684

1608684

Риа t0

СССР на, 101