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

(51) 0 06 Г 15 36 ПИС БРЕТЕНИЯ ИДЕТЕПЬСТ ТОРОИОМ(прототип). ический адиот алмык тво ССС свидетел б Г 15/2 видетель б ." 15/2 1980 тво СС 1979оетосуддРстаенный номитет сссР О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(54)(57) 1. ВЕРОЯТНОСТНЫЙ АВТОМАТ,содержащий генератор пуассоновского потока импульсов, первый элементИ, первый вход которого соединен свыходом генератора пуассоновского потока импульсов, регистр сдви;га, первый вход которого Соединенс выходом первого элемента И, авыход регистра сдвига соединен сего вторым входом, блок задания закона распределения, блок элементов И, группа входов которого соединена с группой выходов блока задания закона распределения, блок памяти, группа входоз которого соединена с группой выходов блока элементов И, а группа выходов соединенас первой группой входов блока задания закона распределения, и генератор.тактозых импульсов, о т л ич а ю щ и й с я тем, что, с цельюрасширения функциональных возможностей путем моделирования полумарковских процессов, он дополнительно содержит генератор случайного напряжения, блок задания времени ожидания, группу элементов И, второйэлемент И и элемент ИЛИ, причемвыходы разрядов регистра сдвига сдинены с первыми входами соответсзующих элементов И группы, вторыевходы которых соединены с выходомэлемента ИЛИ и первым входом второго элемента И, а выходы соединеБО 1 О 45 ны со второй группой взводов, блока задания закона распределения, выход генератора тактовых импульсов соединен с тактовым входом блока задания времени ожидания и вторым входом второго элемента И, выход которого соединен с входом блока элементов И, управляющим входом блока задания времени ожидания и вторым входом первого элемента И, выход Генератора случайного напряжения сое динен с потенциальным входом блока задания времени ожидания, группа инфор:".ационных входов которого подключена к группе выходов блока памяти, а группа выходов соединена с входами элемента ИЛИ и является выходами автомата,2. Вероятностный автомат по п. 1, / о т л и ч а ю щ,и й с я тем, что генератор случайного напряжения С: содержит генератор пуассоновского по. тока импульсов, регистр сдвига, группу управляемых делителей напряжения,. элемент ИЛИ, выход которого является выходо:. генератора случайного напряжения, выход генератора пуассоновского потока импульсов соединен с входом регистра сдвига, выходы разрядов которого соединены с входами соответствующих справляемых делителей напряжения группы, выходы которых подключены к входам элемента ИЛИ. 3. Вероятностный автомат по п, о т л и ч а ю щ и й с я тем, что, блок задания времени ожидания содержит группу операционных усилителей, группу аналого-цифровых пре образователей, группу реверсивных счетчиков, группу дешифраторов, пе вую и вторую группы элементов И,. причем первые входы элементов И пе вой группы являются группой информационных входов блока вторые входы объединейы и являются управляющи,Решетник Коррек Подписное ака тент" П ил 7555/51 ВНИИПИ Государ по делам изо 113035, Москва, Тираж 70 бвенного комитета СССетений и открытий35, Раушская наб., д Ужгород, ул. Проектная,1045232 входом блока, третьи входы объединены и являются потенциальным входом блока, а выходы соединены с входами соответствующих операционныхусилителей группы, выходы операционных усилителей группы соединены свходами соответствующих аналого-цифровых преобразователей, группы, выходы которых соединены с первыми входами соответствующих реверсивныхсчетчиков группы, выходы разрядов Изобретение относится к вычислительной технике и может быть исполь-.зовано для моделирования сложныхстохастических систем, описываемыхмарковскими и полумарковскими процессами, а также для построения специализированных вычислительных и управляющих устройств.Известен автономный вероятностныйавтомат, содержащий генератор тактовых импульсов, первый генераторслучайных импульсов, выход которогосоединен с первым входом первогоэлемента И, второй вход которогосоединен с выходом генератора тактовых импульсов, первый и второй блоки элементов И, блок задания закона распределения, блок памяти, каждая ячейка которого состоит из триг-гера и элемента ИЛИ, регистр, выходы которого соединены соответственнос первой группой входов блока за 1,дания закона распределения, втораягруппа входов которого соединенасоответственно с выходами блока памяти, входы которого соединены с выходами первого блока элементов И,группа первых входов первого блокаэлементов И объединена и подключена к выходу генератора тактовых импульсов, вторая группа входов первого блока элементов И соединенасоответственно с выходами блоказадания закона распределения,второй и третий регистры, второйгенератор случайных импульсов ивторой элемент И, первый вход которого соединен с выходом второгогенератора случайных импульсов,а второй вход - со вторым входомпервого элемента И и с управляющимвходом третьего регистра, разрядныевходы которого соединены соответст- .венно с разрядными выходами второгорегистра, вход которого соединен свыходом первого элемента И, приэтом разрядные выходы третьего регистра соединены соответственно сгруппой информационных входов вто 9 реверсионных счетчиков группы соединены с входами соответствующихдешифраторов группы, выходы которыхсоединены с первыми входами элементов И второй группы и являются группой выходов блока, вторые входы элементов И второй группы объединены иявляются тактовым входом блока, авыходы соединены с вторыми входамисоответсгвующих реверсивных счетчиков группы. рого блока элементов И, группа управляющих входов которого объединена и подключена к выходу второго элемента И .1 .Однако данный вероятностный автомат моделирует однороцную цепь Маркова, что сужает его Функциональные возможности,Наиболее близок к предлагаемому"О.вероятностный автомат, содержащий генератор пуассоновского потока импульсов, генератор тактовых импульсов., элемент И, регистр, блок зада, ния закона распределения, блок эле ментов И и блок памяти, причем выход генератора пуассоновского потока импульсов соединен с первым входомэлемента И, выход которого соединенс первым входом регистра, первыйвыход которого соединен со вторымвходом регистра, а вторые выходыкоторого соединены с первыми входами блока задания закона распределения, выходы которого соединены спервыми входами блока элементов И,вторые вход которого соединеныс выходом генератора тактовых импульсов и вторым входом элемента И,а выходы - с входами блока памяти,выходы которого соединены соответственно со вторыми входами блоказадания закона распределения и выходными шинами вероятностного автомата 2.1 Однако известный вероятностныйавтомат моделирует простую цепь Маркова, т.е. цепь, в которой переход из состояния в состояние не зависит от времени пребывания в предыдущем состоянии, в то время как большинство стохастических процессов описывается моделью так называемых полумарковских цепей передача сообщений на сети связи, многие системы массового обслуживания, прокат ный стан и т,д. , Это ограничиваетЦель, изобретения - расширениефункциональных возможностей путеммоделирования полумарковских процессов.Поставленная цель достигаетсятем, что вероятностный автомат, содержащий генератор пуассоновскогопотока импульсов, первый элемент И,первый вход которого соединен свыходом генератора пуассоновскогопотока импульсов, регистр сдвига,первый вход которого соединен свыходомпервого элемента И, а выходрегистра сдвига соединен с его вторым входом, блок задания законараспределения, блок элементов И, 15группа входов которого соединенас группой выходов блока заданиязакона распределения, блок памяти,группа входов которого соединенас группой выходов блока элементов И,а группа выходов соединена с первой 20группой входов блока задания законараспределения, и генератор тактовыхимпульсов, дополнительно содержитгенератор случайного напряжения,блок задания времени ожидания, ,25группу элементов И, второй элементИ и элемент ИЛИ, причем выходыразрядов регистра сдвига соединеныс первыми входами соответствующихэлементов И группы, вторые входы З 0которых соединены с выходом элемента ИЛИ и первым входом второго элемента И, а выходы соединены со второй группой входов блока задания за-.кона распределения, выход генератора тактовых импульсов соединен с тактовым входом блока задания времениожидания и вторым входом второгоэлемента И, выход которого соединенс входом блока элементов И, управляющим входом блока задания времени ожидания и вторым входом первогоэлемента И, выход генератора случайного напряжения соединен с потенциальным входом блока заданиявремени ожидания, группа информацион ных входов которого подключена кгруппе выходов блока памяти, а группа выходов соединена с входами элемента ИЛИ и является выходами автома-.та,50Кроме того, в вероятностном автомате генератор случайного напряжения содержит генератор пуассоновского потока импульсов, регистр сдвига, группу управляемых делителейнапряжения и элемент ИЛИ, выходкоторого является выходом генератора случайного напряжения, выход генератора пуассоновского потока импульсов соединен с входом регистра б 0 сдвига, выходы разрядов которого соединены с входами управляемых делителей напряжения соответствующих групп выходы которых подключены к входам элемента ИЛИ.б 5 Блок задания времени ожидания со держит группу операционных усилителей, группу аналого-цифровых преобразователей, группу реверсивных счетчиков, группу дешифраторов, первую и вторую группы элементов И, причем первые входы элементов И первой группы являются группой информационных входов блока, вторые входы объединены и являются управляющим входом блока, третьи входы объединены и являются потенциальным входом блока, а выходы соединены с входами соответствующих операционных усилителей . группы, выходы операционных усилителей группы соединены с входами соответствующих аналого-цифровых преобразователей группы, выходя которых соединены с первыми входами соответствующих реверсивных счетчиков группы, выходы разрядов реверсивных счетчиков группы соединены с входами соответствующих дешифраторов груп пы, выходы которых соединены с первыми входами элементов И второй группы и являются группой выходов блока, вторые входы элементов И второй группы объединены и являют - ся тактовым входом блока, а выходы соединены со вторыми входами соответствующих реверсивных счетчиков группы.На фиг. 1 приведена блок-схема вероятностного автомата, на фиг, 2 функциональная схема блока задания закона распределения, на фиг. 3 функциональная схема блока элементов И на фиг. 4 - функциональная схема блока памяти, на фиг. 5 функциональная схема генератора случайного напряжения, на фиг. 6 - функ. циональная схема блока задания времени ожидания; на фиг. 7 - функциональная схема операционного усилителя блока задания времени ожидания, на фиг. 8 - вольт-амперная характеристика диода операционного усилителя, на фиг, 9 - временные диаграммы, отображающие работу вероятностного автомата. Вероятностный автомат фиг. 11 содержит генератор 1 пуассоновского потока импульсов, первый элемент И 2 регистр 3 сдвига, группу 4 элемен.тов И, блок 5 задания закона распределения, блок б элементов И, блок 7 памяти, блок 8 задания времени ожидания, генератор 9 случайного напряжения, генератор 10 тактовых импульсов, второй элемент И 11, элемент ИЛИ 12 и выходы 13 автомата. Выход генератора 1 пуассоновского потока импульсов соединен с первым входом первого элемента И 2, выход которого соединен с первым входом регистра 3 сдвига, Выход регистра 3 сдвига соединен с его вторым входом, а группа выходов соединенас первыми входами соответствующихэлементов И группы 4, входы которыхсоединены со второй группой входовблока 5. Группавыходов блока 5 соединена с группой входов блока 6элементов И, группа выходов которогосоединена с группой входов блока 7.Группа вйходов блока 7 соединена спервой группой входов блока 5 и групппой информационных входов блока 8задания времени ожидания, группаныходов которого соединена с входами элемента 12 ИЛИ и является выходами 13 автомата. Выход генератора10 тактовых импульсов соединен стактовым входом блока 8 задания времени ожидания и вторым входом вто-.рого элемента И 11, выход которогосоединен со вторым входом первогоэлемента И 2, входом блока 6 элементов И и управляющим входом блока 8задания времени ожидания. Выход генератора 9 случайного напряжениясоединен с потенциальным входом блока 8 задания времени ожидания. Выход элемента ИЛИ 12 соединен с первым входом второго элемента И 11и вторыми входами элементов И группы 4.Блок 5-7 аналогичны соответстнующим блокам прототипа.Блок 5,( фиг. ) имеют вторуюгруппу 14 входов, группу 15 элементов И, первую группу 16 элементов ИЛИ, первую группу 17 нходон,группу 18 выходов и вторую группу19 элементов ИЛИ. 35Блок 6 элементов И (фиг. 31 имеет группу 20 входов, группу 21 элементов И, вход 22 и группу 23 ныходов,Блок 7 (фиг. 4) имеет группу 24 4 Овходов, группу 25 триггеров, группу26 элементов ИЛИ и группу 27 выходов.Генератор 9 случайного напряжения ( фиг, .51 содержит генератор28 пуассоновского потока импульсов, регистр 29 сдвига, группу 30управляемых делителей напряжения,элемент ИЛИ 31 и имеет выход 32.Выход генератора 28 пуассоновскогопотока импульсов соединен с входомрегистра 29 сдвига, выходы разрядовкоторого соединены с первыми вынодами соответствующих переменных резисторов группы 30.Блок 8 задания времени ожидания( фиг. 61 имеет группу 33 информационных входон, первую группу 34элементов И, потенциальный вход 35,группу 36 операционных усилителей,группу 37 аналого-цифровых преобразонателей, группу 38 реверсивныхсчетчиков, группу 39 дешифратороэ,группу 40 выходов, вторую группу41 элементов И и тактовый выход 42,Выходы элементов И первой -группы , 65 34 соединены с входами соответствующих операционных усилителейгруппы 36, выходы которых соединеныс входами соответствующих аналогоцифровых преобразователей группы37, Выходы аналого-цифровых преобразователей группы 37 соединеныс первыми входами соответствующихреверсинных счетчиков группы 38, выходы разрядов которых соединены свходами соответствующих дешифраторов группы 39. Выходы дешифраторов группы 39 соединены с первымивходами элементов И второй группы41, вторые входы которых объединеныи являются тактовым входом 42 блока, а выходы соединены со вторымивходами соответствующих реверсиэныхсчетчиков группы 38.Пример возможной реализации операционного усилителя группы 36 вблоке 8 приведен на фиг, 7.Вероятностный автомат работаетследующим образом,Случайные импульсы от генератора 1 пуассоновского потока импульсов поступают через открытый (в интервалы времени, соответствующиенахождению автомата н 1 -х (1 = 1,И )состояниях) первый элемент И 2 напервый (синхронизирующий) вход ре -гистра 3 сдвига, который являетсяциклически замкнутым, в одном изразрядов которого записана единица, а в остальных нули. Интенсивность случайных. импульсов выбирается такой, чтобы записанная единица многократно обегала регистр3 сдвига между моментами опросаего состояний тактовыми импульсами генератора 10 тактовых импульсов,При таком условии единица будетнаходиться в момент опроса на любомиэ выходов регистра 3 сдвига с равной вероятностью.В зависимости от заданной матрицы .переходных вероятностей Р организуются соотнетстнующие связи триггерон группы 25 блока 7 с входамиэлементов ИЛИ группы 16 и блока 5матрицы логических элементов путемзамыкания определенных контактов( фиг, 2). Смена матриц переходовосуществляется организацией соответствующих обратных связей замыканием и размыканием контактов н блоке 5 матрицы логических элементов.С помощью блока 5 матрицы логических элементов выходы регистра 3 сдвига, который. совместно с генератором 1 представляет собой равно- вероятностный ( 1,( ) -полюсник, объединяются, обеспечивая заданную вероятность возбуждения выходных шин 13 вероятностного автомата.Вероятностивозбуждения выходов 13 автомата являются линейной функцией числа выходов регист 1045232ра 3 сдвига, Набор заданной матрицБГпереходов в блоке 5 очень прост,а точность установки вероятностивозбуждения любого выхода равнаЬР= -5 25 0 1/32/3 1/3 2/3 01/3 1/3 1/3 В этом случае соединение выходов триггеров группы 25 блока 7 запоми нающих логических элементом с элементами ИЛИ группы 16 блока 5 соответствует фиг. 2,Пусть система была в некотором состоянии и вышла из него. В этом 5 О случае на выходе элемента ИЛИ 12 присутствует нулевой потенциал, второй элемент 11 И открыт и импульсы генератора 1 не проходят через запертый первый элемент И 2 в регистр 3 сдвига, Кроме того, отсутствие потенциала с выхода элемента 12 ИЛИ открывает элементы И группы 4.Пусть поступающим тактовым импуль сом генератора 10 тактовых импульсов на вход 22 блока б элементов 6 О И единица с некоторого выхода 1 регистра 3 сдвига пройдет через соответствующие элементы И группы 4, вход .второй группы 14 блока 5 матрицы логических элементов (фиг. 21, от 65 где К - число выходов регистра 3сдвига.Кроме этого, в каждом -м состоянии автомат может находиться слу 1 Очайное время, определяемое для каждого собственной функцией распределения времени ожидания в состоянии 1; ЮДля полумарковских процессов, 15которые моделируются предлагаемымвероятностным автоматом,Г(1) определяется по формуле.КГ И) = Р Ь ) =.: 1" Я 1;,где 1 С - вероятность перехода автомата из 1 -го состояния в 1-е (элемент матрицы переходных вероятностей ),Г ,Ц)- переходная функция рас 1)пределения времени ожидания при переходе автомата из 1 -го состоянияв-е. 3 ОВ дальнейшем считают Г Н) известным,Для простоты дальнейшего рассмотрения работы вероятностного автоматасчитают, что автомат имеет три состоя 35ния и необходимо формировать матрицу переходных вероятностей вида крытый элемент И группы 15, элемент ИЛИ группы 19, выход группы 18 блока 5, вход 20 блока б элементов И ( фиг. 3), открытый по входу 22 элемент И группы 21, выход группы 23 блока б.и вход группы 24 блока 7 (фиг. 4) на единичный вход триггера группы 25 и перебросит его в единичное состояние. Потенциал с выхода этого триггера пройдет через элементы ИЛИ группы 26 на нулевые входы остальных триггеров группы 25 и перебросит их в нулевые состояния.Потенциалы с единичного выхода триггера группы 25 и выхода группы 27 блока 7 поступают на вход группы ЗЗ блока 8 задания времени ожиданияфиг. б ) и на первый вход соответствующего элемента И первой группы 34, причем на остальных входах этого элемента имеется разрешающий потенциал от элемента И 11 и от генератора 9 случайного напряжения.Генератор 9 случайного напряжения выдает на своем выходе импульс, амплитуда которого случайно распределена в интервале от нуля до единицы условного измерения.Генератор 28 пуассоновского потока импульсов выдает в циклически замкнутый регистр 29 сдвига синхронизирующую серию импульсов. В регистре 29 имеется одна единица, которая обегает его многократно, и в таком случае в момент опроса выхода 32 генератора 9 единица на выходах регистра 29 появляется равновероятно в любой момент времени. Переменные сопротивления группы 30 настроены таким образом, что амплитуда снимаемых с них напряжений дискретно увеличивается на величину 4,:1 К(К- число выходов регистра 29) по мере роста индекса сопротивления группы 30. Таким образом, учитывая, что частота работы генератора 28 значительно превышает частоту работы генератора 10, обеспечивается в момент опроса блока 8 генератором 10 появление на . выходе 32 гейератора 9, а следовательно, и на потенциальном входе 35 блока 8 импульса с напряжением О х, равномернораспределенным в интервале от нуля до единицы.С выхода элемента И группы 34 (фиг. б ) импульс с напряжением .поступает на вход 43 операционного усилителя группы 36. Диод 45 ( фиг.7) за счет вводимого масштабирования сопротивлением 44 имеет вольт-амперную характеристику ( фиг. 8), в достаточной степени точности апроксимирующую распределение Г (1) - функцию распределения времени ожидания системы (вероятностного автомата) во втором состоянии. Тогда с резистора 46 снимается напряжение , которое усиливается усилителем напряжения -резисторы 47 и 48 а также транзистор 49) и с выхода 50 снимается напряжение, определяющее время пребывания автомата во втором состоянии. Данное напряжение подается на аналого-цифровой преобразователь группы 37, который преобразует напряжение в цифровой код, количественно отобра-. жающий н двоичной системе счисления величину времени ожидания автомата во втором состоянии. 10Данный код эаписынается н соответствующий реверсивный счетчик группы 38. На выходе соответствующего де шифратора группы 39 .появляется единица, которая подается на выходную. шину группы 13 вероятностного автомата с выхода группы 40 блока 8. Этим потенциалом также открывается соответствующий элемент И группы 41 и запираются через элемент ИЛИ 12, элемент И 11 и элементы группы 4.Генератор 10 подает свои импульсы на вход 42 фиг. 6) блока 8 задания времени ожидания, Данные импульсы поступают через соответствующий элемент И группы 41 н соответствующий реверсивный счетчик группы 38, уменьшая считывая) его содержимое.Как только код соответствующего счетчика группы 38 будет считан до .ЗО нуля (истечет время пребывания автомата в состоянии два), на выходе соответствующего дешифратора группы 39 исчезнет потенциалбудет нулевой потенциал). Пропадет потенциал на соответствующем выходе группы 13 автомата, что свидетельствует о выхо.де его из второго состояния. На выходе элемента ИЛИ 12 будет нуль, что откроет элемент И 11 и элементы И группы 4 и запрет элемент И 2 на вре" мя выбора следующего состояния авто= матом.Связь выхода соответствующего триггера группы 25 блока 7 с группой входов 17 и элементов ИЛИ группы 45 16 блока 5 обеспечит появление . н следующем такте единицы на вЫходе ,предыдущего триггера группы 25 с вероятностью 2/3 и на выходе последующего триггера группы 25 с нероят ностью 1/3, т.е, очередным тактовым импульсом генератора 10 может быть выбрано первое состояние с нероятностью 2/3 и третье состояние с вероятностью 1/3, так как сформирована вторая строка матрицы Р. Причем функция распределения времени ожидания автомата в состоянии 1 равна Р(1), а в состоянии 3 - Рэ, (1) Далее работа будет происходить аналогично описанному выше.На фиг 9 временными диаграммами отображен процесс установки автомата во второе состояние, пребывание в нем и выход из него н первое состояние.Вероятностный автомат используется для моделирования сложных стохас тических систем или как управляющее устройство, прогнозирующее поведение системы.Прототип позволяет моделировать марковские процессы, в которых вре.- мя пребывания в определенном состоя - нии не зависит от предыдущего состояния. Предлагаемый автомат позволяет моделировать полумарковские процессы, в которых время пребывания в состоянии зависит от номера предыдущего состояния, т.е., например, выбор направления передачи сообщения на сети связи зависит от того, сколько времени будет передаваться сообщение по выбранному направлению. Таким образом, существенно расширена область применения вероятностного ав - автомата. При этом точность моделированиялибо управления) по сравнению с прототипом понышается н 1,5-2 раза за счет учета времени пребывания автомата в определенном состоянии. Дей - ствительно, если взять процесс упранления распределением потоков на сети, то время задержки сообщений при применении; известного устройства принимается постояннымНа самым де - ле время задержки - величина случайная, зависящая от многих факторов и определяемая функцией распределения. Предложенное устройство учитывает время задержки исходя из ее функции распределения, что повышает достоверность ( целенаправленность) управления, распределением сообщений, на сети.