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

 

ВЕРОЯТНОСТНЬЙ АВТОМАТ, содержащий блок генерации случайного кода, генератор тактовых импульсов, блок задания переходных вероятностей , содержащий группу узлов памяти и коммутатор, группа управляющих входов которого является группой управляющих входов автомата, группа информационных входов коммутатора подключена к выходам узлов памяти группы, входы которых являются установочными входами автомата, KOI мутатор , выходы которого соединены с информационными входами первого блока памяти, блок задания законов, распределений, состоящий из п идентичных узлов, каждый из которых содержит группу регистров, группу схем сравнения, первую и вторую группы элементов И, в каждом идентичном узле выходы регистров группы подклкгчены к первым входам соответствукт щих элементов И первой группы, вторые входы которых объединены и подключены к соответствующему выходу первого блока памяти, выходы элементов И первой группы соединены с входами первой группы соответствую « .ааг «.ггг; щих схем сравнения группы, входы второй группы подключены соответственно к выходам блока генерации слу чайного кода, выход первой схемы, сравнения группы и выходы элементов И второй группы каждого идентичного узла подключены к соответствую щим информационным входам коммутатора , выход первой схемы сравнения . соединен с первыми инверсными входами элементов И второй группы, выход k-й схемы сравнения, группы (k 2,п) подключен к прямому входу (k-1)-го элемента И второй группы и k-м инверсным входам элементов И .второй группы с номерами, большими (k-l), разрядные входы регистров W всех узлов блока задания законов распределений подключены соответственно к выходам коммутатора блока задания переходных вероятностей, о т л и - чающийся тем, что, с целью расширения функциональных возможносю тей путем задания функции выходов как функции распределения от состояний вероятностного автомата, он 1C дополнительно содержит второй блок со памяти, выходы которого являются выходами автомата, и блок определе ния состояний выхода, состоящий из группы элементов ИЛИ и h одинаковых узлов, каждый из которых содержит вероятностный (I,k)-полюсник, группу элементов И, в каждом уэле выходы вероятностного

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

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

РЕСПУБЛИН

А. ц114 G 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ.(21) 3732037/24-24 (22) 21.04.84 (46) 23.12.85. Бюл. N - 47 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.И. Финаев, В.Е. Ланкин и Г.В. Кононова (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1108455> кл. G 06 F 15/20, 1982.

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

l» 1112367, кл. G 06 G 15/20, 1983, (54)(57) ВЕРОЯТНОСТНЫЙ АВТОМАТ, содержащий блок генерации случайного кода, генератор тактовых импульсов, блок задания переходных вероятностей, содержащий группу узлов памяти и коммутатор, группа управляющих входов которого является группой управляющих входов автомата, группа информационных входов коммутатора подключена к выходам узлов памя ти группы, входы которых являются установочными входами автомата, ком мутатор, выходы которого соединены с информационными. входами первого блока памяти, блок задания законов, распределений, состоящий as n идентичных узлов, каждый из которых содержит группу регистров, группу схем сравнения, первую и вторую группы элементов И, в каждом идентичном узле выходы регистров группы подклю чены к первым входам соответствую щвх элементов И первой группы, вторые входы которых объединены и подключены к соответствующему выходу первого блока памяти, выходы элементов И первой группы соединены с входами первой группы соответствую„„Я0„„1200297 щнх схем сравнения группы, входы второй группы подключены соответственно к выходам блока генерации случайного кода, выход первой схемы сравнения группы и выходы элементов И второй группы каждого идентич" ного узла подключены к соответствую щим информационным входам коммутатора, выход первой схемы сравнения . соединен с первыми инверсными входа" ми элементов И второй группы, выход k-й схемы сравнения группы (k= 2,n) подключен к прямому входу (k-1)-го элемента И второй группы и k-м инверсным входам элементов И ,второй группы с номерами, большими щ . (k-!), разрядные входы регистров всех узлов блока задания законов рас пределений подключены соответственно ( к выходам коммутатора блока задания переходных вероятностей, о т л ич а ю шийся тем, что, с целью расширения функциональных возможностей путем задания функции выходов как функции распределения .от состо- { „ » яний вероятностного автомата, он (» дополнительно содержит второй блок фф памяти, выходы которого являются Щ выходами автомата, и блок определения состояний выхода, состоящий из группы элементов ИЛИ и h одинаковых узлов, каждый из которых содержит вероятностный (l,k)-полюсник, группу элементов И, в каждом узле выходы :Ь вероятностного (l,k)-полюсника подключены к входам элементов ИЛИ груп" пы, выходы которых соединены с пер» выми входами элементов И группы. соответственно, вторые входы элемен" та И группы i-ro узла (i l k) объединены и подключены к i вы1200297

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

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

На фиг. 1 приведена схема вероят° ностного автомата; на фиг. 2 — функциональная.схема блоков задания переходных вероятностей; на фиг. 3— а функциональная схема блока задания законов распределений; на фиг. 4.— функциональная схема блока определеHHH O TO HHH BbIXOPR

Вероятностный автомат содержит управляющие входы 1, блок 2 задания переходных вероятностей, установочные входы 3, блок 4 задания законов распределений, блок 5 генерации случайного кода, первый блок 6 памяти, блок 7 определения состояний выхода, генератор 8 тактовых импульсов, коммутатор 9, второй блок 10 памяти, выходы 11.

Блок 2 задания переходных вероятностей (фиг. 2 ) содержит коммутатор 12, выходы 13, узлы 14 памяти.

Блок 4 задания законов распределений .(фиг. 3) содержит регист ры 15 памяти, первую группу элементов И 16, информационный вход 17, группу узлов 18 сравнения, информационные входы 19, выходы 20, вторую группу элементов И 21.

Блок 7 определения состояний выхода (фиг. 4} содержит группу элементов ИЛИ 22 и группу узлов, каждый из которых включает верояттатора, выходы i-х элементов И всех узлов соединены с соответствующим входом i-го элемента ИЛИ группы блока определения состояния выхода, а выходы элементов ИЛИ группы подключены к входам второго блока памяти.

-ностный (l,k)-полюсник 23, группу элементов ИЛИ 24 и группу элементов И 25.

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

На управляющие входы подаются входные сигналы, причем на управляющий вход 1; подается входной управляющий сигнал х ь. Х (i= Г,ш).

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

11 и 12 11 12 1п где P " " — -вероятность перехода вероЮ

11 ятностного автомата из 1-го состояния в j-е при подаче на вход 1 управляющего сигнала х . Коды матриц переходных вероятностей заносятся

25 в узлы 14 памяти.

Управляющие сигналы х. подаются

1 в блоке 2 на первые входы коммутатора 12 (фиг. 2 ). По приходу входного сигнала х, коды матрицы Р,.

1 подаются на установочные входы блока 4 задания законов распределений.

Синхронизация работы вероятностного автомата осуществляется импуль35 сами генератора 8 тактовых импульсов, импульсы с выхода которого по даются на входы блока 5 генерации случайного кода, управляющие входы коммутатора 9 и блока 7 онределе40 ния состояний.

Алгоритм работы вероятностного автомата состоит в следующем. В соответствии с поступившим сигналом х; в блок 4 задания законов распределе1200297

15

Р.. 1 Р> 1 ° ° ° -1 1К

2 22

° ° ° ° ° ° ° ° ° ° ° ° 01 П21 ° ° ° 1 ПК з ний заносятся коды матрицы Р . Пре1 дьщущее. состояние S(t-1) фиксируется в первом блоке памяти 6. В соответствии с состоянием S(t-1) и кодом числа, -равновероятно распределенного в интервале от нуля до единицы, вырабатываемого блоком 5 генерации случайного кода, анализируется в блоке 4 строка матрицы .Р,, соответствующая номеру состояния S(t,-I).

Выбранное новое состояние S(t,) в виде импульсов с соответствующего выхода блока 4 через коммутатор 9 фиксируется в первом блоке 6 памяти.

Блок 7 определения состояний выхода в соответствии с матрицей вы.ходных вероятностей определяет выходной сигнал, который фиксируется во втором блоке !О памяти и поступает на соответствующие выходы 11 вероятностного автомата.

В блоке 7 определения состояний выхода реализуется матрица выходных вероятностей, которая имеет вид где P. - вероятность появления вы1! ходного сигнала на выходе вероятностЗо ного автомата при условии, что он находился в i-м состоянии.

В блоке 4 задания переходных вероятностей по установочным входам 13 в регистры 15 заносятся коды матрицы Р при условии, что подан в данный момент времени сигнал х 1, Предположим, что автомат находил." ся в. предыдущий момент времени в х-м состоянии, т.е. на втором установочном входе 17- блока 4 присутст-!

;вует потенциал, подаваемый с выхо-! да 17, первого блока 6 памяти. Тогда будут открыты соответствующие элементы И 16 и коды вероятностей записанйые соответственно в регистрах 15,.„ — 15;„, будут поданы на первые входы узлов 18 сравнения, иа вторые входы которых от блока 5 подается код числа, равновероятно распределенного в интервале от нуля до единицы. Условия срабатывания узлов 18

Сравнения: узел 18. срабатывает при

i1 выполнении неравенства А P где

И1

А - число равномерно распределенного ряда, представленное в двоичном коде; узел IS„< - при А 4 (Р;„+ Р; ) и т.д., узел 18;„- при А (ХР; = }.

При срабатывании узлов 18 сравнения на их выходах появляются потенциалы.

Однако потенциал будет на выходе только элемента И 21!!.<, так как потенциал с выхода узла 18 >1 сравнениУ закрывает остальные элементы И 21 " - .

1!

21Ä„ „. Это говорит о том, что автомат перешел в 1-е состояние и на выходе 20; блока 4. будет потенциал.

С выхода 20; блока 4 потенциал посту пает на соответствующий информацион, ный вход коммутатора 9. С выхода коьг" мутатора 9 импульс изменения состояния подается на соответствующий вход первого блока 6 памяти.

Новое состояние вероятностного ав томата в виде имупльса, снимаемого с выхода 17 первого блока 6 памяти, одновременно подается и на вторые информационные входы блока 4 задания законов распределения и на информационные входы блока 7 определения состояний выхода. Последний в соответствии с матрицей выходных вероятностей определяет очередное состояние выхода. Происходит это следующим образом. На управляющий вход блока 7 подается импульс с выхода генератора 8, который разрешает срабатьгвание элементам И 25, на третьи входы которых .подан разрешающий потенциал от соответствующего информационного выхода 17 блока 6. Кроме того

t с приходом импульса от блока 8 срабатывают равновероятностные (1- )полюсники 23, в которых импульс с вероятностью I/f может появиться на любом из f выходов. Выходы узлов 23 соединены с входами элементов ИЛИ

24 „ — 24 в соответствии с распределением вероятностей 1-й строки матрицы ф.. Например, пусть -я строка имеет вид

1/5; 2/5; 3/10; 1/10, тогда к элементу ИЛИ 24 будут под11 соединены два выхода узла 23 к

J 1 элементу ИЛИ 241 — четыре других вы хода узла 23, к элементам ИЛИ 24 . у 1 !5 и ИЛИ 24 1 - соответственно три выхода и один выход вероятностного узла 23, который имеет десять вью" ходов.

Предположим, что в момент опроса появился импульс на третьем выходе узла 23 . Тогда через элемент ИЛИ

24 < сра атывает элемент И 25 и на ,12 выходе элемента ИЛИ 22 будет потен1200297 циал, что свидетельствует о формировании очередного выходного сигнала. Потенциал, характеризующий выходной сигнал вероятностного автомата, с выхода подается на соответствующий вход второго блока 10 памяти, фиксирует очередное состоя-. ние выхода вероятностного автомата и подает информацию об этом состоянии в виде импульса на соответствую щий выход вероятностного автомата.

При подаче очередного управляюще.

5 го сигнала цикл работы вероятностного автомата по установлению нового состояния и состояния выхода повторяется аналогичным обраэом, но состо« яние S и сигнал выхода Z будут рас3

1О сматриваться как соответственно

S(t-1) и Z(t-1) состояния.

1200297

t/ nï

/г

Jïn

l n// (и/ пп

0n/ 3rt. 5

Ю»

1 оп

2 п

А/й

1200297

0m &.8 фиг. 4

Составитель В. Фукалов

Редактор В. Петраш Техред Ж.Кастелевич Корректор Г. Решетник

Заказ 7869/55 Тираж 709 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4