Вероятностный автомат Советский патент 1983 года по МПК G06F15/173 G06F7/70 G06F17/18 

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

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

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

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

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

Однако данный вероятностный автомат моделирует однородную цепь Марква, что сужает его функциональные возможности.

. «

Наиболее близок к предлагаемому вероятностный автомат, содержащий генератор пуассоновского потока импульсов, генератор тактовых импульсов., элемент И, регистр, блок задания закона распределения, блок элементов И и блок памяти, причем выход генератора пуассоновского потока .импульсов соединен с первым вход элемента И, выход которого соединен с первым входом регистра, первый выход которого соединен со вторым входом регистра, а вторые выходы которого соединены с первыми входами блока задания закона распределения, выходы которого соединены с первыми входами блока элементов И, вторые входы которого соединены с выходом генератора тактовых импульсов и вторым входом элемента И, а выходы - с,входами блока памяти, выходы которого соединены соот:Ветственно со вторыми входами блока задания закона распределения и вы.ходными шинами вероятностного автомата t 2 . i

Однако известный вероятностный автомат .моделирует простую цепь Маркова, т.е. цепь, в которой переход из состояния в состояние не зависит от времени пребывания в предыдущем состоянии, в то время ка большинство стохастических процессо описывается моделью так называемых полумарковских цепей передача сообщений на сети связи, многие системы массового обслуживания, прокатный стан и т.д. . Это ограничивает функциональные возможности автома|Та. Цель, изобретения - расширение функциональных возможностей путем моделирования полумарковских проце сов . Поставленная цель достигается тем, что вероятностный автомат, со держащий генератор пуассоновского потока импульсов, первый элемент И первый вход которого Соединен с выходом генератора пуассоновского потока импульсов, регистр сдвига, первый вход которого соединен с выходомпервого элемента И, а выхо регистра сдвига соединен с его вто рым входом, блок задания закона распределения, блок элементов И, группа входов которого соединена с группой выходов блока задания закона распределения, блок памяти, группа входов которого соединена с группой выходов блока элементов а группа выходов соединеь а с перво группой входов блока задания закон распределения, и генератор тактовы импульсов, дополнительно содержит генератор случайного напряжени-я, блок задания времени ожидания, группу элементов И, второй элемент И и-элемент ИЛИ, причем выходы разрядов регистра сдвига соединены с первыми входами соответствующих элементов И группы, вторые входы которых соединены с выходом элемента ИЛИ и первым входом второго элемента И, а выходы соединены со второй группой входов блока задания за кона распределения, выход генератора тактовых импульсов соединен с та товым входом блока задания времени ожидания и вторым входом второго элемента И, выход которого соединен с входом блока элементов И, управляющим входом блока задания времени ожидания и вторым входом первого элемента И, выход генератора случайного напряжения соединен с потенциальным входом блока задания времени ожидания, группа информацио ных входов которого подключена к группе выходов блока памяти, а груп па выходов соединена с входами элемента ИЛИ и является выходами автом та. Крометого, в вероятностном автомате генератор случайного напряжения содержит генератор пуассоновс кого потока импульсов, регистр сдви га, группу управляемых делителей напряжения и элемент ИЛИ, выход которого является выходом генератора случайного напряжения, выход генератора пуассоновского потока импульсов соединен с входом регистра сдвига, выходы разрядов которого со динены с входами управляемых делите лей напряжения соответствующих rpyn выходы которых подключены к входам элемента ИЛИ. Блок задания времени ожидания со держит группу операционных усилителей, группу аналого-цифровых преобразователей, группу реверсивных счет чиков, группу дешифраторов, первую и вторую группы элементов И, причем первые входы элементов И первой группы являются группой информационных входов блока, вторые входы объединены и являются управляющим входом блока, третьи входы объединены и являются потенциальным входом блока, а выходы соединены с входами соответствующих операционных усилителей . группы, выходы операционных усилителей группы соединены с входами .соответствующих аналого-цифровых преобразователей группы, выходы которых соединены с первыми входами соответствующих реверсивных счетчиков группы, выходы разрядов реверсивных счетчиков группы соединены с входами соответствующих дешифраторов груп пы, выходы которых соединены с первыми входами элементов И второй группы и являются группой выходов блока, вторые входы элементов И второй группы объединены и являются тактовым входом блока, а выходы соединены со вторыми входами соответствующих реверсивных счетчиков группы. На фиг. 1 приведена блок-схема вероятностного автоматаJ на фиг. 2 функциональная схема блока задания закона распределения; на фиг. 3 функциональная схема блока элементов И} на фиг. 4 - функциональная схема блока памяти, на фиг. 5 функциональная схема генератора слу-чайного напряжения; на фиг. б - функциональная схема -блока задания времени ожидания; на фиг. 7 - функциональная схема операционного усилителя блока задания времени ожидания; на фиг. 8 - вольт-амперная характеристика диода операционного усилителя/ на фиг. 9 - временные диаграммы, отображающие работу вероятностного автомата. Вероятностный автомат (фиг. 1) содержит генератор 1 пуассоновского потока импульсов, первый элемент И 2 регистр 3 сдвига, группу 4 элементов И, блок 5 задания закона распределения, блок 6 элементов И, блок 7 памяти, блок 8 задания времени ожидания, генератор 9 случайного на-«пряжения, генератор 10 тактовых импульсов, второй элемент И 11, элемент ИЛИ 12 и выходы 13 автомата. Выход генератора 1 пуассоновского потока импульсов соединен с первым входом первого элемента И 2, выход которого соединен с первым вхоом регистра 3 сдвига. Выход региста, 3 сдвига соединен с его вторым ходом, а группа выходов соединена с первыми входами соответствующих элементов И группы 4, входы которы соединены со второй группой входов блока 5. Группавыходов блока 5 со динена с группой входов блока б элементов И, группа выходов которо соединена с группой входов блока 7 Группа выходов блока 7 соединена с первой группой входов блока 5 и гр пой информационных входов блока 8 задания времени ожидания, группа , выходов которого соединена с входа ми элемента 12 ИЛИ и является выхо дами 13 автомата. Въаход генератора 10 тактовых импульсов соединен с тактовым входом блока 8 задания вр мени ожидания и вторым входом sto рого элемента И 11, выход которого соединен со вторым входом .первого элемента И 2, входом блока 6 элеме тов И и управляющим входом блока 8 задания времени ожидания. Выход ге нератора 9 случайного напряжения соединен с потенциальным входом бл ка 8 задания времени ожидания. Выход элемента ИЛИ 12 соединен с пер вым входом второго элемента И 11 и вторыми входами элементов И груп пы 4 . Блок 5-7 аналогичны соответству щим блокам прототипа. Блок 5.(фиг. 2) имеют вторую группу 14 входов, группу 15 элементов И, первую группу 16 элементов ИЛИ, первую группу 17 входов, группу 18 выходов и вторую группу 19 элементов ИЛИ. Блок6 элементов И (фиг. 3) имеет .группу 20 входов, группу 21 элементов И, вход 22 и группу 23 выходов. Блок 7 (фиг. 4) имеет группу 24 входов, группу 25 триггеров, группу 26 элементрв ИЛИ и группу 27 выходо в. Генератор 9 случайного напряжения (фиг..5).содержит генератор 28 пуассоновского потока импульсов, р.егистр 29 сдвига, группу 30 управляемых делителей напряжения, элемент ИЛИ 31 и имеет выход 32. Выход генератора 28 пуассоновского потока импульсов соединен с входом регистра 29 сдвига, выходы разрядов которого соединены с первыми вывода ми соответствующих переменных резисторов группы 30.J Блок 8 задания времени ожидания (,фиг. 6) имеет группу 33 информационных входов, первую группу 34 элементов И, потенциальный вход 35 группу 36 операционных усилителей, группу 37 аналого-цифровых преобразователей, группу 38 реверсивных счетчиков, группу 39 дешифраторов, группу 40 выходов, вторую группу 41 элементов И и тактовый выход 42, Выходы элементов И первой-группы 34 соединены с входами соответствующих операционных усилителей группы 36, выходы которых соединены с входами соответствующих аналогоцифровых преобразова.телей группы 37.- Выходы аналого-цифровых преобразователей группы 37 соединены с первыми входами соответствующих реверсивных счетчиков группы 38, выходы разрядов которых соединены с входами соответствующих дешифраторов группы 39. Выходы дешифраторов группы 39 соединены с первыми входами элементов И второй группы 41, вторые входы которых объединены и являются тактовым входом 42 блока, а выходы соединены со вторыми входами соответствующих реверсивных счетчиков группы 38. Пример возможной реализации операционного усил.ителя группы36 в блоке 8 приведен на фиг. 7. Вероятностный автомат работает следующим образом. Случайные импульсы от генератора 1 пуассоновского потока импульсов поступают через открытый (в ийтервалы времени, соответствующие нахождению автомата в l-x(,)i) состояниях) первый элемент И 2 на первый (синхронизирующий) вход регистра 3 сдвига, который является циклически замкнутым, в одном из разрядов которого записана единица, а в остальных нули. Интенсивность случайных, импульсов выбир.ается такой, чтобы записанная единица многократно обегала регистр 3 сдвига меходу моментами опроса его .состояний тактовыми импульсами генератора 10 тактовых импульсов. При таком условии единица будет находиться в момент опроса на любом из выходов регистра 3 сдвига с равной вероятностью. В зависимости от заданной матрицы -переходных вероятностей Р организуются соответствуквдие связи тркг геров группы 25 блока 7 с входами элементов ИЛИ группы 16 и блока 5 матрицы логиче.ских элементов путем замыкания определенных контактов (фиг. 2). Смена матриц переходов осуществляется организацией соответствующих обратных связей замыканием и размыканием контактов в блоке 5 матрицы логических элементов. С помощью блока 5 матрицы логических элементов выходы регистра 3 сдвига, который совместно с генератором 1 представляет собой равновероятностный (1,К) -полюсник, объединяются, обеспечивая заданную вероятность возбуждения выходных ин 13 вероятностного автомата. Вероятности- возбуждения выходов 13 автомата являются линейой функцией числа выходов регистpa 3 сдвига. Набор заданной матриЦЕ переходов в блоке 5 очень прост, а точность установки вероятности возбуждения любого выхода равна ДР--гг К - число выходов регистра 3 сдвига. Кроме этого, в каждом -i-м состоянии автомат может находиться слу чайное время, определяемое для каждого собственной функцией распределения времени ожидания в состоянии F( ((:/ Для полумарковских процессов, которые моделируются предлагаемым вероятностным автоматом, Р(t) определяется по формуле )Ptt,t)|F,j(i)l4, где тс - вероятность перехода ав томата из -го состоя ния в у-е (элемент ма трицы переходных вероят ностей Р), -Ц) переходная функция рас пределения времени ожидания при переходе авто мата из 1 -го состояни в j -е. В дальнейшем считают F Ct) извест ным. Для простоты дальнейшего рассмо рения работы вероятностного автомат считают, что автомат имеет три состо ния и необходимо формировать матрицу переходных вероятностей .вида В этом случае соединение выходов триггеров группы 25 блока 7 запоми- нающих логических элементом с элеме тами ИЛИ группы 16 блока 5 соответ вует фиг. 2. Пусть система была в некотором состоянии и вышла из него. В этом случае на выходе элемента ИЛИ 1.2 присутствует нулевой потенциал, второй элемент 11 И открыт и импульсы генератора 1 не проходят через запертый первый элемент И 2 в регистр 3 сдвига. Кроме того, отсутствие потенциала с выхода элемента 12 ИЛИ от крывает элементы И группы 4. Пусть поступающим тактовым импуль сом генератора 10 тактовых импульсов на вход 22 блока б элементов И единица с некоторого выхода i регистра 3 сдвига пройдет через соответствующие элементы И группы 4, вхо .второй группы 14 блока 5 матрицы логических элементов (фиг., 2)), открытый элемент И группы 15, элемент ИЛИ группы 19, выход группы 18 блока 5, вход 20 блока б элементов И (фиг. 3) , открытый по входу 22 элемент И группы 21, выход группы 23 блока б. и вход группы 24 блока 7 (фи. 4 на единичный вход триггера группы 25 и перебросит его .в единичное состояние. Потенциал с выхода этого триггера пройдет череэ элементы ИЛИ группы 26 на нулевые входы остальных триггеров группы 25 и перебросит их в нулевые состояния. Потенциалы с единичного выхода триггера группы 25 и выхода группы 27 блока 7 поступают на вход группы 33 блока 8 задания времени ожидания фиг. 6 ) и на первый вход соответст - вугацего элемента И первой группы 34, причем на остальных входах этого элемента имеется разрешающий потенциал от элемента И 11.и от генератора 9 случайного напряжения. Генератор 9 случайного напряжения выдает на своем выходе импульс, амплитуда которого случайно распределена в ин-тервале от нуля до единицы условного измерения. Генератор 28 пуассоновского потока импульсов выдает в циклически замкнутый регистр 29 сдвига синхронизирующую серию импульсов. В регистре 29 имеется одна единица, которая обегает его многократно, и в таком случае в момент опроса выхода 32 генератора 9 единица на выходах регистра 29 появляется равновероятно в любой момент времени. Переменные сопротивления группы 30 настроены таким образом, что амплитуда снимаемых с них напряжений дискретно увеличивается на величину (К- число выходов регистра 29) по мере роста индекса сопротивления группы 30. Таким образом, учитывая, что частота работы генератора 28 значительно Превышает частоту работы генератора 10, обеспечивается в момент опроса блока 8 генератором 10 появление на . выходе 32 генератора 9, а следовательно, и на потенциальном входе 35 блока 8 импульса с напряжением (j , равномернораспределенным в интервале . нуля до единицы. С выхода элемента И группы 34 (фиг. 6 импульс с напряжением (Jy поступает на вход 43 операционного усилителя группы 36. Диод 45 (фиг.7/ за счет вводимого масштабирования сопротивлением 44 имеет вольт-амперную характеристику (фиг. 8), в доста-точной степени точности апроксимирующую распределение F (t/ - функию распределения времени ожидания системы (вероятностного автомата) во тором состоянии. Тогда с резистора 46 снимается напряжение (j.,, которое силивается усилителем напряжения (регисторы 47 и 48, а также транзистор 49) и с выхода 50 снимается напряжение, определяющее время пребывания автомата во втором состоянии. Данное напряжение подается- на аналого-цифровой преобразователь группы 31f который преобразует напряжение в цифровой код, количественно отобра жающий в двоичной системе счисления величину времени ожидания автомата во втором состоянии. . Данный код записывается в соответствующий реверсивный счетчик груп пы 38. На выходе соответствующего де шифратора группы 39 появляется единица, которая подается на выходную. шину группы 13 вероятностного автомата с выхода группы 40 блока 8. Этим потенциалом также открывается соответствующий элемент И группы 41 и запираются через элемент ИЛИ 12, элемент И 11 и элементы группы 4 Генератор Ю подает свои импульсы ка вход 42 (фиг, б) блока 8 задания времени ожидания. Данные импуль поступают через соответствующий элемент И группы 41 в соответст,вующий реверсивный счетчик группы 38, уменьшая (считывая) его содержимое . Как только код соответствующего счетчика группы 38 будет считан до нуля (истечет время пребывания авто мата в состоянии два), на выходе . соответствующего дешифратора группы 39 исчезнет потенциал (будет нуле,вой потенциал). Пропадет потенциал на соответствующем выходе группы 13 автомата, что свидетельствует о вых .де его из второго состояния. На выходе элемента ИЛИ 12 будет нуль, чт откроет элемент И 11 и элементы И ; группы 4 и запрет элемент И 2 на вр мя выбора следующего состояния авто матом., . Связь выхода соответствующего триггера группы 25 блока 7 с группой входов 17 и элементов ИЛИ групп 16 блока 5 обеспечит появление в следующем такте единицы на выходе iпредыдущего триггера группы 25 с ве |роятностью 2/3 и на выходе -последую щего триггера группы 25 с вероят;; ностью 1/3, т.е. очередным тактовым импульсом генератора 10 может быть выбрано первое состояние с вес оятностью 2/3и третье состояние с вероятностью 1/3, так как сформирована вторая строка матрицы Р. Причем функция распределения времени ожидания автомата в состоянии 1 равна Р (i) , а в состоянии 3 - Р, (4;)Далее работа будет происходить аналогично описанному выше. На фиг,- 9 временными диаграммами отображен процесс установки автомата во второе состояние, пребывание в нем и выход из него в первое состояние. Вероятностный автомат используется для моделирования сложных стохас-тических систем или как управляющее устройство, прогнозирующее поведение системы. Прототип позволяет моделировать марковские процессы, в которых время, пребывания в определенном состоянии не зависит от предыдущего состояния. Предлагаемый автомат позволяет моделировать полумарковские процессы, в которых время пребывания в состоянии зависит от номера предыдущего состояния, т.е., например, выбор на.правления передачи сообщения на сети связи зависит от того, сколько времени будет передаваться сообщение по выбранному направлению. Таким образом,существенно расширена область лримр-нения вероятностного ававтомата. При этом точность моделиро-- вания ( либо управления } по сравнению с прототипом повышается в 1,5-2 раза за счет учета времени пребывания автомата в определенном состоянии. Действительно, если взять процесс управления распределением потоков на сети, то время задержки сообщений при применении; известного устройства принимается постоянным. .На самым деле время задержки - величина случайная, зависящая от многих факторов и определяемая функцией распределения. Предложенное устройство учитывает время задержки исходя из ее функции распределения, что повышает достоверность ( целенаправленность управления;: распределением сообщений; на сети.

фiJ8.i rfi Пг ff /7л

t 1

/5/

УК

Т

-iH

фае. 8