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

1

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

Цель изобретения повышение точ ности вероятностного автомата.

На фиг. 1 приведенй структурная схема вероятностного автомата; на фиг. 2 - структурная схема первого блока- формирования управляющих сигналов; на фиг. 3 - структурная схема второго блока формирования управляющих сигналов; на фиг. 4 - функциональная схема первого матричного коммутатора; на фиг. 5 - функциональная схема второго матричного коммутатора; на фиг. 6 - функциональная схема регистра сдвига; на фиг.7 функциональная схема первой группы элементов И; на фиг. 8 - фукнциональная схема дополнительной группы элементов И; на фцг. 9 - функциональная схема первого блока элементов ИЛИ; на фиг. 10 - функциональная схема дополнительного блока элементов ИЛИ; на фиг. 11 - функциональная схема первого запоминающего устройства; на фиг. 12 - функциональная схема дополнительного зап:оминающего устройства; на фиг. 13 - функциональная схема блока задержки.

Блок-схема вероятностного автомата (фиг. 1) содержит первые управ- . ляющие входы Ц-1,, первьй блок 2 формирования управляющих сигналов; дополнительный второй блок 3 формирования управляющих сигналов; первую группу установочных входов автомата; вторую, группу установочных входов 5 автомата; первый матричный коммутатор 6, второй матричный коммутатор 7; регистр 8 сдвига; генератор 9 тактовых импульсов; первую группу элементов И 10;: вторую дополнительную группу элементов И 11; первый блок 12 элементов ИДИ; второй дополнительньй блок 1 3 элементов ИЛИ;первое запоминающее устройство 14; - второе дополнительное запоминающее устройство блок 15 задержки; выходы 16j - 16fj, вероятностного автомата..

002962

Блок-схема первого блока формирования управляющих сигналов (фиг.2) содержит первую группу входов 1 п вторую группу входов 4;j тт ° 5 мутатор 17, регистры IB - 18, выходы 19; - 19.

Блок-схема второго блока 3 формирования управляющих сигналов (фиг.3 ) содержит первую группу вхо- 10 дов 1-1 - In, вторую группу входов 5Й, коммутатор 20, регистры 2Ц - 21,, вьпсоды -22;- 22.

Функциональная схема первого матричного коммутатора 6 (фиг. 4 ) содержит управляющие входы 19 - 19 , -ii

сумматоры 23,1 элементы И 24 - 24| , первую группу информационных входов 25 - 25 , узлы сравнения 26, 26|, вторую группу 20 информационных входов 27 - 27, разрядные выходы 28,- ,вторые элементы И 29„ -29„., Функциональная схема второго 25 дополнительного матричного коммутатора 7 (фиг. 5) содержит управляющие входы 22 - 22/ , первую группу информационных входов 25 - 25., сумматоры 30 - ЗС|,,,,-, первые эле30 «™ - 31. УЗЛЫ 32, - 32 сравнения, вторые информационные входы 33 - 33, разрядные выходы 34i-, - 34,вторые элементы И 35

35 Функциональная схема регистра 8 сдвига (фиг. 6) содержит разрядные вьгходы 25 - 25, управляющий вход 36; первые и второй элементы И 37, 38, генератор 39

лп ь

пуассоновского потока импульсов,

регистр 40, кодер 41.

Функциональная схема первой группы элементов И 10 (фиг. 7) содержит управляющий вход 36; элементы И

45 42 - 42, информационные входы , выходы 44 J, - 44.

Функциональная схема второй дополнительной группы элементов И 11 (фиг. 8) содержит управляющий

50 вход 36, элементы И 45 - 45 , информационные входы 46 - 46 , выхо-

дан 47.

Функциональная схема первого блока элементов ИЛИ 12 (фиг. 9) содер- 55 жит входы 28,, - 28„,выходы 43 - f элементы ИЛИ 48 ,, - 48.

Функциональная схема второго блока элементов ИЛИ 13 (фиг. 10) содер жит входы 34 , выходы 46 - , элементы ИЛИ 49 49. Функциональная схема первого запоминающего устройства 14;, (фиг. II) содержит выходы 27-, -27, входы 44 4 , триггеры 50 т элементы ИЖ 51, - 51. Функциональная схема второго до- полнительного запоминающего устрой-ства 14, (фиг. 12) содержит выходы 16 - 16, входы 47 т триг геры 52„, элементы ИЛИ 53, Функциональная схема блока 15 за держки (фиг. 13) содержит входы 27 27д, выходы 33-, - 33„, триггеры 54 54р,, элементы 55 - 55 задержки. Элементы вероятностного автомата взаимосвязаны следующим образом. Группа управляющих входов Ц- соединена с первыми группами.входов первого 2 и второго 3 блоков формир вания управляющих сигналов, первая mm вторая 5 - 5 „ группы управляющих входов соединены соответственно с вторыми группами входов первого 2 и второго 3 блоков .формирования управляющих сигналов, выходы которых соединены соответственно с управляющими входами первого 6 и второго 7 матричных коммутат ров, первые информационные входы коj торьпс объединены и соединены с вы-ходами регистра сдвига, вход которого соединен с выходом генератора такто вых импульсов и с первыми управляющими входами первой 10 и второй .11 групп элементов И соответственно, разрядные выходы первого 6 и второго 7 матричных коммутаторов соединены с входами соответственно первого 12 и второго 13 элементов ИЛИ, выходы которых соединены соответственно с вторыми информационными входами первой 10 и второй 1 групп элементов И, выходы которых соединены соответственно с входами первого 14,. и второго 14л запоминаю щих устройств, выходы первого запоминающего устройства I4 соединены с вторыми информационными входами . первого 6 матричного коммутатора и входами блока 13 задержки, выходы которого соединены с вторыми информационными входами второго 7 матричного коммутатора выходы второго за поминающего устройства 1 соединены с выходами 6л - 16; вероятностного автомата. 96 В первом блоке формирования управляняцих сигналов 2 первая группа входов 1у - 1 соединена с первьг ми входами коммутатора 17, вторые входы которого соединены с соответствующими входами регистров 18 - 18, а выходы 1935j,являются выходами блока 2, вторые входы которого 4 - 4|J, соединены с входами регистров 18 - 18„ соответственно. Во втором дополнительном блоке 3 формирования управляющих сигналов первая группа входов 1 - 1 соединена с первыми входами коммутатора 20, вторые входы которого соединены с соответствующими выходами ре- : гистров 2Ц 2lf,, а выходы 22j - являются выходами блока 3, вторая группа входов которого 5, - 5 {},п, соединена с входами .регистров 21,) - 21(, соответственно. В первом матричном коммутаторе 6 управляющие входы 1У j - 19(1 соединены соответственно с первыми входами сумматоров 23(1 1 ,т) и первыми входами первых элементов И 24 - 24j(i l,m),a управляющие входы 19J.- I9|j- (i l,m, j 2,m) соединены с .вторыми входами соответ- ствующих сумматоров 23,j;|i 1 ,m, j 2,m),первые входы сумматоров 23.J- (i l,m, j 2,m-1 ) соединены с выходами сумматоров 23 ,, и пер- выми входами первых элементов И аШ, J 2,т-1), первые информационные входы 25 -25, матричного коммутатора6 соединены с первыми входами узлов сравнения 26 .j mm вторые входы которых соединены с выходами соответствующих первых элементов И 24 - 24,, вторые входы которых соединены с соответст- взт)щими вторыми информационными входами 27 - 27 коммутатора 6, разрядные выходы 2Ъ (1 1,т-) которого соединены с выходакш соответст- вующих узлов 26 (1 1,т) сравнения и первыми входами втюрых элементов И 29j - 29,;,,, (i T,m), разрядные выходы 28,-:- коммутатора 6 соединены с выходами вторых элемен- (1 j ), выходы тов и 29; узлов 26ij (i l,m,. j 2,m) сравнения соединены с соответствующими j-ми входами соответствующих вторых элементов И (i l,m,J « 27m). Во втором дополнительном матричном коммутаторе 7 управляющие входы 22|у - 22l(i l,m) соединены соответственно с первыми входами 30H(i сумматоров 30- (i 1,m) и первыми И 311 - З входами первых элементов входами первых, элементиь п л| - , (1 1,т), а ;|Аправлякщие входы 22 22,-- (i l,m, j 2,m) соединены свторыми входами соответствующих сумматоров 30 (i l,m, J 2,m) первые входы сумматоров 30,-;(i 1 ,m J 2,m) соединены с выходами сумгматор , и первыми входами пер- вых элементов И 3iJ - 31. (i 1 ,m. J 2,:m-hl), первые информационные входы 25j, - 25 коммутатора .7 со. единены с первыми входами узлов 32.- 32| сравнения, .вторые входы которых соединены с выходами соот- ветствующих первых элементов И 313l, вторые входы которых соединены с соответствующими вторыми информационными входами 33 - 33| коммута- тора 7, разрядные выходы 34- (1 1, которого соединены с выходами соответствующих узлов 32. (i l,m) сра нения и первым входами вторых эле35i(i l,m), выхоментов И 35 -- im-i ды 34.J коммутатора 7 соединены с выходами вторых элементов И 35{.-1 (1 1,т, j 2,m), выходы узлов 32, (i 1,m, J 2,m) сравнения соедин ны с соответствующими -ми входами соответствующих вторых элементов И 35 ,1 1,т, j Tim). В регистре 8 сдвига вход 36 соединен с первыми входами первых эле ментов И 37. - 37 и первыми входом второго элемента И 38, второй вход которого соединен с выходом генератора 39 пуассоновского потока имnyjrtTcoB, а выход соединен с тактовь входом регистра 40, вход переполнения которого соединен с,соответствующими входом регистра .40 и входом кодера 41, остальные входы которого соединены с выходами регистра 40, а выходы - с вторыми входами первых элементов И 37 - 37, выходы которьБс соединены с выходами 25 - 25 регистра 8 сдвига. В первой группе элементов И 10 управляющий вход 36 соединен с первыми входами элементов И 42jj-42., вторые входы которых соединены с И1 формационными входами первой группы элементов И 10, а выходы - с выхода ми первой группы элементов И 10. Во второй дополнительной группе элементов И 11 управляющий вход 36 соединен с первыми входами элементов И 45| -А5, вторые входы которых соединены с информационными вхо дами второй группы элементов И 11, а выходы - с выходами 47. 7 группы элементов И 11, ИЛИ 12 В первом блоке элементов входы 28 - 28 . соединены с входами соответствующих элементов ИЛИ А8( (i l,m), выходы которых соединены с выходами 43)(i 1,m) первого блока элементов ИЛИ 12. Во втором блоке элементов ИЛИ 13 входы 34 - 34р, (i l,in) соединены с входами соответствующих элементов ШШ 49 (i l,m), выходы кото- рых соединены с выходами. 46;; (i l,m) второго блока элементов ИЛИ 13 В первом запоминающем устройстве 14 входы 44.,-44j соединены с единичными входами триггеров 50 50, нулевые входы которых соединены с выходами элементов ИЛИ 5 Ц - 51, а единичные вьгходы соединены с выхо- 14 и входами 27 блока дами 27, соответствующих элементов ИЛИ 5 Ц 51 , причем выход триггера 50- соединен с выходом запоминающего устройства 14 и входами элементов ИЛИ ЗЦ-З :., 51 2-5т . Во втором дополнительном запоминающем устройстве 14 входы соединены с единичными входами триггеров , нулевые входы которых соединены с выходами элементов ИЛИ 53 -53, а единичные выходы соединены с выходами запоми-. нающего устройства lAj и входами со-, ответствующих элементов ИЛИ , причем выход триггера 52. соединен с выходом 16. запоминающего устройства 14j и входами элементов ИЛИ , 53.-53. В блоке 1.5 задержки входы соединены с единичными входами соответствующих триггеров , нулевые входы которых соединены с выходами соответствующих элементов 55. - г 55 задержки, входы которых соединены с нулевыми выходами триггеров , единичные выхЬды кото рьк соединены с выходами 33.-33: блока 15 задержки. Работает вероятностный автомат следующим образом. На управляющие входы I подаются .управляющие сигналы х-бХ, причем сигнал X; подается на вход (Дому входному сигналу х . соответств ет. -матрица Р. и А переходных вероя ностей, причем коды вероятностей ма ;рицы переходных вероятностей Р , оп ределяющие состояние системн, заносятся по второй группе входов 4 в регистры 18 первого блока 2 формиро вания управляющих сигналов. Коды ве роятностей матрицы переходных .вероятностей А., определяющие состояние выходов системы в зависимости о состояний самого автомата, заносят ся по второй группе входов 5 в регистры 21 второго блока 3 формирова ния управляющих сигналов. Предлагаемое устройство является вероятностным автоматом типа Мшш, причем для него выполняется условие |М(а ,у/а, х) и(а/а, x)k(y/a, х), где (х(а/а, х) вероятность того, что при подаче вхо ного сигнала х авт мат из состояния а перейдет в состоя- ние а , причем (а/а, х) задается матрицей Р. ; jU.(a ,у/а,х)- вероятность того, что вероятностный автомат, будучи в состоянии а, при подаче на вход сигнала х, вьщает на выходе сигнал у, переходя одновременно в состояние а ; а,а еи множество состояний автомата; У BY множество выходных сигналов; |;л(у/а,х) вероятность того, что автомат при no даче входного сигнала X, будучи в состоянии а, выдает выходной сигнал у, причем (у/а.,х) задается матрицей А,. В соответствии с вероятностной мерой (I ) рассмотрим функционирование вероятностного автомата. Такты изменений состояний автомата и его выходных сигналов задают 96 генератором 9 тактовых импульсясов. В исходном состоянии автомат находится в 1-ом состоянии, т.е. на выходе 27, первого блока памяти 14 имеется потенциал, а на выходах 16 автомата имеется сигнал у;. Пусть потенциал на выходах I6j имеется потенциал на выходах loj второго запоминающего устройства 14 Входной сигнал х поступает на вход 1. Рассмотрим как произойдет процесс выбора нового состояния автомата и выходного сигнала. Так как на первом входе 1, имеет ся потенциал, то соответственно в первом и втором 2 и 3 блоках формирования управляющих сигналов в коьгмутаторах 17 и 20 (фиг. 2 и 3) коды вероятностей матрицы Р имеют вид на выходах коммутатора 17 блока 2. Данные коды поступят на первые установочные входы 19.,.,- -19| первого матричного коммутатора 6 (фиг.4). Код iTv- хранится в регистре 18j. блока 2. Коды вероятностей матрицы А, из регистров 2J через коммутатор 20 (фиг.З) блока 3 поступят на управляющие входы второго матричного коммутатора 7 (фиг. 5). Появление импульса генератора тактовых импульсов 9 приведет к тому, что по управляющему входу 36 (фиг. 7) открыты элементы И 42 первой группы 10 (фиг. 8), открыты также элементы И 45 второй группы 11, а также сработает регистр 8 сдвига. Причем в регистре 8 сдвига при отсутствии импульса на входе 36 элемент И 38 открыт (фиг. 6) и записан ная в одном из разрядов регистра 40 единица под действием тактовых импульсов, формируемых генератором 39 пуассоновского потока импульсов, многократно обегает регистр 40 между опросами регистра 8 сдвига по входу 36. При появлении .сигнала на вхо- де 36 элемент И 38 закрывается, а элементы И 37 открываются. На одном из выходов регистра 40 случайным образом равновероятно фиксируется 9 потенциал на время действия импульс по входу 36. Данный равновероятный сигнал кодируется кодером 41 в код, йеличинд которого равновероятно рас пределена в интервале от нуля до единицы. Данный код К снимается с выходов 25 блока 8. Код равномерно распределенного числа с разрядных выходов регистра 8 сдвига подается на первые ин- формационные входы первого 6 и вто рого 7 матричных коммутаторов. Рассмотрим работу первого матричного коммутатора 6. На втором информационном входе 27 имеется разрешангщий потенциал с выхода 27 первого запоминающего устройства 1 следовательно, . открыты элементы И 24.-. 24, . На первых входах 19.19 и выходах сумматоров формируется следующий ряд кодов соот- ветственно ; я.Ч +1Г. : 11 11 11 11 ii 13 - Kt +...4F 11 11 .. Ш причем сумма h V-. + F V. f1 12 im Данный ряд кодов подается через элементы И 24 24 на первые вхо ды узлов 26 26 сравнения, на вторые входы которых подается с пер вых информационных входов коммутат ра 6 код К числа равномерно распределенного ряда. Узел сравнения 26. сработает,если код числа к меньше либо равен сумме кодов 7Г , Trt I,-.-, + . 11 il u 11 im подаваемых на первые его входы. Считается при этом, что автомат перешел в состояние из .состояния i . Так как на выходах узлов 26 26-в,сравнения нулевой потенциал, а на выходах узлов 26 сравнени единичньй потенциал, то соответстве 2%.2 ,r но элементы И ; закрыты, a открыт только элемент И 29jj.. Таким образом, потенциал будет на разрядном выходе 28 первого матричного коммутатора 6. Данный потенциал поступает на ин формационный вход 28 { первого блок элементов ИЛИ 12 (фиг. 9), проходи через элемент ИЛИ 48 { на выход 43j 96 . 10блока 12. Затем поступает на информационный вход 43f (фиг. 7) первой группы элементов И 10, проходит через открытый элемент И 42, поступает на выход 44 группы элементов И 10. Затем поступает на вход 44в первого запоминающего устройства 14, (фиг. 11.) и перебрасывает триггер 50 в единичное состояние. ПоТендиал с единичного выхода 27j триггера 50 через элемент ИЛИ 5 li, сбрасьшает триггер 50у в нулевое состояние .Считаем, что автомат перешел в состояние 2. Потенциал с выхода 27 бло- ка 14 поступает на второй информационный вход коммутатора 6 и на вход 27 блока 15 задержки, в котором устанавливается триггер 54j в единичное состояние (фиг. 13). . Б настоящий момент времени имеется потенциал на выходе 33 блока 15, так как элемент 55- задержки времени задерживает сигнал на такт генератора 9, а триггеры 54 сбрасываются по заднему фронту сигнала. I Рассмотрим как происходит определение выходного сигнала. Для этого рассмотрим работу второго матричного коммутатора 7 (фиг. 5). На первые управляющие входы 22 поступают коды вероятностей а. На первые ин формационные. входы 25 подается код /fc числа равномернораспределенного ряда с разрядных выходов регистра 8 сдвига. На втором информационном входе 33. имеется разрешающий потенциал от блока 5 задержки. СледовательнЬ, открыты элементы И 31,- - 31.. На k первых входах 22 ,- 22 1 и выходах сумматоров 30. - 30,-, 11 -,,„, формируется следующий ряд кодов соответственно ot . „t . ot . „t J. ot j, „t j« л + аТм; г ; k причем сумма а Данная последовательность кодов подается через элементы И 31. на первые входы узлов 32 ,- 32 сравнения, на вторые входы которых подается от первых информационных входов 25.коммутатора 7 код t числа равномерно распределенного ряда. Узлы 32 сравнения срабатывают аналогично узлам 26 сравнения коммутатора 6. Пусть код V. меньше либо равен сумме кодов а ;, + а , +. .. +а.,..., г fi ii я-L тогда сработают узлы ,- 32 сравнения и на их вькодах будут единичные потенциалы а на выходах узлов сравнения 32, З2 потенциалов не будет. Открыт будет лишь элемент И 35 j и на ра рядном выходе 34,Y коммутатора 7 будет потенциал. Данный потенциал поступит на вход 34,Y второго блока элементов ИЛИ 13 (фиг. 10), проходит через элемент ИЛИ 48 у, на вьрсод 46 ( блока 13, Затем поступает на информационный вход 46 у второй группы элементов И II (фиг. 7), проходит через открытый элемент И 45 и по :ступает на выход 47, второго запоминающего устройства 142. (Фиг. 12) и перебрасывает триггер 52 в еди.ничное состояние. Потенциал с едини ного выхода 16f. триггера 52 через элемент ИЛИ 53j сбрасьтает в нулевое состояние триггер 52| . На выходе автомата установлено новое состояние выхода У , т.е. вместо выходного сигнала у установ лен на выходах 16 автомата вводной сигнал у.;. Выполнено условие ( }, т.е. авто мат перешел в новое состояние из состояния i, ив соответствии с 96 прежним состоянием i и сигналом входа Хх определен новый выходной сигнал у на очередном такте функционирования вероятностного автомата. При моделировании стохастических систем применяется формальная модель, в которой случайный выходной сигнал стохастически определяется от состояния системы. Известный вероятностный автомат не выполняет данной функции, так как в его формальном описании функция выхода детер- минированно определяется состоянием Если известно, что число выходов tn, то на базе известного устройства можно реализовать предлагаемое, если взять m известных устройств. Если стоимость известного уст- ройства С, а предлагаемого Cj, то экономическая эффективность от применения предлагаемого устройства как управляющего в системе с m выходными сигналами определится форулой г, Сг Из формулы следует, что в зависиости от роста m существенно возрасает величина экономической эффекивности использования предлагаемого ероятностного автомата.. Фиг,г /; h In. Ф Фиг-З

Фиг,5 Jbf Я е й пт

ф ф NJ/

43,

492

i

i

2 iJJ./ffV

46,

.

rffl П-г

Rl

Ш

57,

LOI

1200296

49,

т

27,

«

I

tl

3d

y±h:

ВЕРОЯТНОСТНЫЙ АВТОМАТ по авт..св. № 1108455, о т л и ч а ю щ и и с я тем, что, с целью повышения точности, он содержит блок задержки, дополнительные запоминающее устройство, группу элементов И, блок элементов ИЛИ, матричный коммутатор и блок формирования управлянлцих сигналов, первая группа входов которого является группой установочных входов автомата, а вторая входов является группой управлякицих входов автомата, выходы дополнительного блока формирования управляющих сигналов подключены к группе входов дополнительного матричного коммутатора, первая группа информационных входов которого подключена . соответственно к разрядным выходам регистра, а вторая группа соединена соответственно с группой вьпсодов блока задержки, группа входов которого подключена соответственно к выходам запоминающего устройства, разрядные выходы матричного коммутатора через дополнительный блок элементов ШШ подключены к первой группе входов дополнительной группы элементов И, вторые входы которых объединены и (П подключены к выходу генератора тактовых импульсов, а выходы дополнительного блока элементов И соединены соответственно с входами запоминающего устройства, выходы которого являются группой выходов автомата.

«

Wj 47,

L

,27

5,

332

И,

я«