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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано для моделирования сложных сто хастических систем, описьшаемых марковскими процессами, а также для построения специализированных вычислительных и управляющих устройств. Цель изобретения - расширение функциональных возможностей путем задания функции вьпсодов как функции распределения от состояний вероятностного автомата. На фиг. 1 приведена схема вероятностного автомата; на фиг. 2 - функциональная схема блоков задания переходных вероятностей; на фиг. 3 функциональная схема блока задания законов распределений; на фиг. 4-функциональная схема блока определения состояний выхода. Вероятностный автомат содержит управляющие входы 1, блок 2 задания переходных вероятностей, установочные входы 3, блок 4 задания законов распределений, блок 5 генерации случайного кода, первый блок 6 памяти, блок 7 определения состояний выхода генератор 8 тактовых импульсов, KONT мутатор 9, второй блок 10 памяти, выходы 11. Блок 2 задания переходных вероятностей (фиг. 2) содержит коммутатор 12, выходы 13, узлы 14 памяти. Блок 4 задания законов распределений (фиг. 3) содержит регистры 15 памяти, первую группу элементов И 16, информационный вход 17, группу узлов 18 сравнения, информационные входы 19, выходы 20, вторую группу элементов И 21. Блок 7 определения состояний выхода (фиг. 4) содержит группу элементов ИЛИ 22 и группу узлов, каждый из которых включает вероятностный (1,К)полюсник 23, группу элементов ИЛИ 24 и группу элементов И 25. Вероятностный автомат работает следующим образом. На управляющие входы подаются входные сигналы, причем на управляющий вход Ц подается входной управляющий сигнал х . е X (1 ГТпГ). По установочным входам 3 блока 2 вводятся коды матрицы переходных вероятностей, которая имеет вид для каждого сигнала рч рЧрЧ .,pf 11 и 11 П 1п Р Р -(-Р р .Р . .Р П1 П1 П-1 П2 где Р ;- вероятность перехода вероятностного автомата из ITO состояния в j-e при подаче на вход 1Р управляющего сигнала х. Коды матриц переходных вероятностей заносятся , памяти. Управляющие сигналы х- подаются в блоке 2 на первые входы коммутатора 12 (фиг. 2). По приходу входного сигнала х , коды матрицы Р подаются на установочные входы блока 4 задания законов распределений. Синхронизация работы вероятностного автомата .осуществляется импуль сами генератора 8 тактовых импуль- сов, импульсы с выхода которого подаются на входы блока 5 генерации случайного кода, управляющие входы коммутатора 9 и блока 7 определения состояний. Алгоритм работы вероятностного автомата состоит в следующем. Б соответствии с поступивщим сигналом х в блок 4 задания законов распределеНИИ заносятся коды матрицы Р. , Предыдущее, состояние S(t-l) фиксируется в первом блоке памяти 6. В соответствии с состоянием S(t-l) и кодом числа, равновероятно распределенного в интервале от нуля до единицы, вырабатываемого блоком 5 генерации случайного кода,анализируется в блоке 4 строка матрицы р. , соответствующая номеру состояния S(t-l). Выбранное новое состояние S(t) в виде импульсов с соответствующего выхода блока 4 через коммутатор 9 фиксируется в первом блоке 6 памяти Блок 7 определения состояний выхода в соответствии с матрицей выходных вероятностей определяет выходной сигнал, который фиксируется во втором блоке О памяти и поступает на соответствующие выходы I1 вероятностного автомата. В блоке 7 определения состояний выхода реализуется матрица выходных вероятностей, которая имеет вид где Р. - вероятность появления вы ходиого сигнала на выходе вероятност ного автомата при условии, что он находился в i-м состоянии. В блоке 4 задания переходных вероятностей по установочным входам I в регистры 15 заносятся коды матри- ць Р. при условии, что подан в данный момент времени сигнал х. Предположим, что автомат находился в предьщущий момент времени в i-M состоянии, т.е. на втором установочном входе 17 блока 4 присутст- 1вует потенциал, подаваемый с выхода 17. первого блока 6 памяти. Тогд будут открыты соответствующие элементы И 16 и коды вероятностей pi.p; + 4.....p.V+p, ...Pi« записанные соответственно в регистрах 15. - 15,, будут поданы на первые входы узлов 18 сравнения, на вто рые входы которых от блока 5 подается код числа, равновероятно распределенного в интервале от нуля до еди ницы. Условия срабатывания узлов 18 йравнения: узел 18. срабатьшает при выполнении неравенства А Pj, где А - число равномерно распределенног ряда, представленное в двоичном коде; узел 18,1 - при А ( Рц и т.д., узел при A( 1). При срабатывании узлов 18 сравнения на ИХ выходах появляются потенциалы. Однако потенциал будет на выходе только элемента И 21 ;., так как потенциал с выхода узла 18 ij сравиени закрьшает остальные элементы И 21м - 21-j. Это говорит о том, что автомат перешел в j-е состояние и на выходе блока 4 будет потенциал. С выхода 20 Ij блока 4 потенциал посту пает на соответствующий информацион- ный вход коммутатора 9. С выхода комп мутатора 9 импульс изменения состояния подается на соответствующий вход первого блока 6 памяти. Новое состояние вероятностного автомата в виде имупльса, снимаемого с выхода 17; первого блока 6 памяти, одновременно подается и на вторые информационные входы блока 4 задания законов распределения и на информационные входы блока 7 определения состояний выхода. Последний в соответствии с матрицей выходных вероятностей определяет очередное состояние выхода. Происходит это следую- щим образом. На управляющий вход блока 7 подается импульс с выхода генератора 8, который разрешает срабатьгвание элементам И 25, на третьи входы которых .подан разрешающий потенциал от соответствующего информационного выхода 17j блока 6. Кроме того, с приходом импульса от блока 8 ера- батьшают равновероятностные (1 -f полюсники 23, в которых импульс с вероятностью 1/f может появиться на любом из f выходов. Выходы узлов 23/ соединены с входами элементов ИЛИ 24j в соответствии с распределением вероятностей -и строки матрицы W. Например, пусть j-я строка имеет вид 1/5; 2/5; 3/10; 1/10, тогда к элементу ИЛИ 24у будут подсоединены два выхода узла 23j, к элементу ИЛИ 24 четыре других выг хода узла 23-, к элементам ИЛИ 24jj и ИЛИ 24 J4 - соответственно три вы-хода и один выход вероятностного узла 23., который имеет десять выходов , Предположим, что в момент опроса появился импульс на третьем выходе зла 23j. Тогда через элемент ИЛИ срабатывает элемент И 25.2 и на ыходе элемента ИЛИ 22j будет потен циал, что свидетельствует о форми- ровании очередного выходного сигнала. Потенциал, характеризующий выходной сигнал вероятностного автомата, с выхода подается на соответствующий вход второго блока 10 памяти, фиксирует очередное состояние выхода вероятностного автомата и подает информацию об этом состоя- НИИ в виде импульса на соответствую

h 1г Jm 0

3/70-

/ J// &7 1ат

/zf- ПП

5

1 щий выход вероятностного автомата. При подаче очередного .ляющего сигнала цикл работы вероятностного автомата по установлению нового состояния и состояния выхода повторяется аналогичным образом, но состояние S; и сигнал выхода Z будут рассматриваться как соответственно S(t-l) и Z(t-l) состояния.

М Ч N

f f

i f f

n, //2 J

UK Фиъ. f От S.ff

фиг. Z От S/t. S tfffft fgfff,

Фиг.З (20it Zffiz 2ffiy ,

От S/t.8

Фиъ.