Генератор случайного процесса

(51) 4 С 06 Р 7/58 ОПИСАНИЕ ИЗОБРЕТЕНИЯ Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССРВ 489098, кл. С 06 Р 7/58, 1974.Авторское свидетельство СССР)1 744532, кл. С 06 Р 7/58, 1978. Авторское свидетельство СССР Р 1138802, кл, 0 06 Г 7/58, 1983.(54) ГЕНЕРАТОР СЛУЧАЙНОГО ПРОЦЕССА(57) Изобретение относится к областивычислительной техники и может бытьиспользовано при моделировании цепей Маркова по заданному состоянию.Целью изобретения является расширение функциональных возможностейгенератора, Генератор случайногопроцесса содержит группу датчиковпуассоновских потоков импульсов, группу элементов ЗАПРЕТ, блок выравнива-ния интенсивностей случайных потоковимпульсов, группу управляемых вероятностных двоичных элементов, группублоков памяти, регистр памяти, шифратор, генератор тактовых импульсов.Поставленная цель достигается засчет введения в генератор группыуправляемых вероятностных двоичныхэлементов, включенных по ступенчатой схеме и выполняющих функцию управляемого вероятностного (И+1)-полюсника, в результате чего объектизобретения приобретает новое свойство - программируемой замкнутой системы связи со счетным числом И+1 состояний и дискретным временем. Случайный и независимый выбор очередного состояния происходит в моменты, определяемые тактовым генератором, по матрице строки квадратной матрицы вероятностей перехода, прп этом номер матрицы строки определяется текущим состоянием п(+) выходного потока, Генератор работает следующим образом. Случайные потоки импульсов датчиков поступают на входы блока выравнивания. Блок выравнивания с помощью матрицы ИиМ выравнивателей производит преобразование 2 М входных потоков импульсов в общем случае сс различными интенсивностями в 2 И независимых потоков импульсов,интенсивности которых одинаковы. С выходов блока выравнивания 2 М пуассоновских потоков импульсов с одинаковой интен- с сивностью поступают на счетные и синхронизирующие входы И вероятностных двоичных элементов. Каждый вероятно- аале стный двоичный элемент выполняет роль вероятностного вентиля, который по М заданной вероятности Р пропускает 4 ь импульсы опроса на прямой выход и с вероятностью (1-Р) на инверсный выход, Настройка блоков памяти осуществляется по матрице условных вероятностей, элементы Р которой связаны с элементами Р исходной матри 1 Ц цы вероятностей перехода, Установка ф начального состояния произведенааааЪ подачей внешнего импульса на единичный вход регистра памяти, 1 з.п.ф-лы, 4 ил.1 О 15 20 5 О 2Еа;2 1 12Изобретение относится к вычислительной технике и может быть использовано при моделировании цепей Маркова по заданному графу состоянийили матрице вероятностей перехода,Цель изобретения - расширениефункциональных возможностей генератора за счет моделирования цепейМаркова по заданной матрице вероятностей перехода.На фиг. 1 изображена структурнаясхема генератора; на фиг, 2 - блоквыравнивания случайных потоков импульсов, на фиг. 3 - вероятностныйдвоичный элемент; на фиг. 4 - регистрпамяти.Генератор случайного процесса содержит группу датчиков 1 пуассоновских потоков импульсов, группу 2 элементов ЗАПРЕТ, блок 3 выравниванияинтенсивностей случайных потоков импульсов, группу управляемых вероятностных двоичных элементов 4,-4,группу блоков 5- 5 г памяти, регистр6 памяти, шифратор 7, генератор 8тактовых импульсов.Блок выравнивания содержит М Х М(М = 1 о 8 М + 1) выравнивателей 9двух потоков импульсов.Каждый вероятностный двоичныйэлемент 4 содержит счетчик 10, стробированный дешифратор 11, группу 12элементов И, группу 13 элементовЗАПРЕТ, первый 14 и второй 15 элементы ИЛИ,Регистр 6 памяти содержит группутриггеров 16, - 16 и группу элементов ИЛИ 17 - "7+Генератор случайного процессаработает следующим образом.Через открытые (в отсутствие импульсов генератора 8) элементыЗЛПРЕТ группы 2 случайные потокиимпульсов датчиков 1 группы поступают на соответствующие входы блока3. Блок 3 с помощью матрицы из И х Мвыравнивателей 9 двух потоков импульсов производит преобразование2 И входных потоков импульсов в общемслучае с различными интенсивностямив 2 М независимых потоков импульсов.,интенсивности которых одинаковы и, определяются как среднее арифметическое интенсивностей %, =1,2 И входных потоков 34833 1 С выходов блока 3 2 Б пуассоновских потоков импульсов с одинаковой интенсивностью Я поступают на счет-7 иные и синхрснизирующие входы И вероятностных двоичных элементов 4 группы.Работа каждого вероятностного двоичного элемента 4 группы основана на использовании вероятностных свойств марковского процесса смены состояний счетчика 10, находящегося под воздействием (по счетному входу и входу "Сброс" ) двух независимых пуассоновских потоков импульсов с равной интенсивностью. Суть этих свойств состоит в том, что безуслов - ные вероятности пребывания счетчика 10 в состояниях У = 0,1,2, определяются формулой геометрической прогрессии с начальным членом и коэффициентогл, равными 1/2Р = (1/2) , 2 = О, 1,2 (2) 25 и не зависят от параметра 3,Импульсы опроса, поступающие наинформационный вход элемента 4, проходят на вход стробирования дешифратора 11 и с вероятностями (2) появля 30 ются на соответствующих выходах дегшлфратора 11.Б соответствии с двоичным кодомХ. = О., а а . ,а, а, б О, 1, действующим на разрядном управляющемвходе двоичного элемента, открыты теэлементы И группы 12 (элементыЗАПРЕТ группы 13), которые соответствуют разрядам управляющего кода Х,содержащим единицы (нули). Первый14 (второй 15) элемент ИЛИ путемдизъюнктивного суммирования вероятМ тчностей . - 18-се- Ре- сВ,фор. Е Емгирует случайное событие, заключающееся в появлении импульса опросана йрямогл (инверсном) выходе элемента 4,Таким образом, каждый вероятностный двоичный элемент выполняет рольвероятностного вентиля, который по заданной с помощью двоичного кода ОХ б 1 вероятности Р пропускает импульсы опроса на прямой выход и с вероятностью (1-Р ) - на инверсный выход Импульсы генератора 8 с частотой Р определяют длительность Т = 1/Р такта марковской цепи. Для надежной работы двоичных элементов группы 412348 датчики 1 пуассоновских потоков импульсов с помощью группы 2 элементов ЗАПРЕТ на время действия импульсов генератора 8 отключаются.Будем полагать, что первый импульс генератора 8 появюзся на прямом выходе и-го двоичного элементаТогда соответствующий триггер 16регистра 6 памяти переводится в состояние " 1", а все другие триггеры 016 регистра с с помощью группы элементов ИЛИ 17 - в состояние "О". Пространственно распределенное случайное событие, заключающееся в том,что триггер 16 регистра 6 находится 15в состоянии "1", преобразуется с помощью шифратора 7 в цифровой двоич-.ный код А(й,) = п(1). В соответствии с текущим кодом адреса А(С,),являющимся одновременно и выходным 20сигналом генератора, на управляющиевходы элементов 4 вызываются новыеуправляющие коды Х, 3 = 1, И,находящиеся в и-х строках Б блоков5 памяти. На следующем, втором такте, определяемом вторым импульсомгенератора 8, работа генератора случайного процесса повторяется, ноуже с учетом новых значений кодов,действующих на управляющих входахэлементов 4 группы.Рассмотрим методику настройки генератора при формировании цепи Маркова по заданному графу ее состояний.При этом воспроизводимый граф цепитфМаркова по числу И состояний (вергшин) не должен превышать воэможностигенератора ИИ+1,Предлагаемый генератор формирует цепь Маркова с (Н + 1) дискретными состояниями по полному графу, содержащему максимально возможное число направлений перехода И(И+1). Для Формирования цепи Маркова по заданному графу необходимо составить пол ную матрицу вероятностей переходаРа 1и, 3 = 1, И, в которой равны нулю все вероятности отсутствующих в графе Г(Х ) направлений перехода как в существующие, так и в не существующие вершины (состояния).Группа вероятностных двоичных элементов 4 реализует функцию управляемого вероятностного 1, (И+1)-полюсника по методу условных вероят" ностей. В связи с этим настройка блоков 5 памяти группы должна осуществляться по матрице условных вероятФ 33 4ч ностей, элементы Р которои связаны с элементами Рисходной матрицып 1вероятностей перехода соотношениемР(3)- Рпкк.1При использовании формулой (3)онеопределенность типа - принимается равной нулю. Значения управляющих кодов Х представленных в виде прачфвильных двоичных дробей оэ а 19 а 21у а численно равные условным вероятФ 1лостям Р, заносят в блоки 5 памяти, при этом индекс 3 соответствует номеру блока 5 памяти, а индекс и - адресу ячейки в 3-м блоке памяти группы 5,Установка начального п состояния моделируемой цепиМаркова производится подачей внешнего импульса на единичный вход и-го триггера 16 регистра 6 памяти,В предлагаемом генераторе интенсивность датчиков 1 является параметром, определяющим быстродействиеэлементов 4 группы при формировании независимых случайных событий.Минимальный период опроса вероятностного двоичного элемента состав- ляет Т "(3-4) . (4)гИ В предлагаемом генераторе вероятностные характеристики цепи Маркова определяются только значениями управляющих кодов Х и не зависят от интенсивностей датчиков 1. Благодаря этому предлагаемый генератор по точности работы не уступает генератору по прототипу.Кроме того, изобретение характеризуется простым устройством, высоким быстродействием и надежностью в работе. Выход из строя даже нескольких датчиков 1 на нарушает работы генератора в целом. В этом случае с учетом (1) и (4) изменяется (снижается) лишь допустимая верхняя частота Р генератора 8. формула изобретения 1, Генератор случайного процесса, содержащий группу из 2 И датчиков пуассоновского потока импульсов, блок выравнивания интенсивности потоков импульсов, группу из Н блоков памяти, регистр памяти, выходы кото ърого соединены с соответствующими -. входами шифратора, выход которого является выходом генератора и соединен .с адресными входами блоков памяти группы, о т л и ч а ю щ и й с я тем, что, с целью расширения Функциональных возможностей генератора за счет формирования цепей Маркова по заданному графу их состояний, в него 10 введены группа из Ю управляемых вероятностных двоичных элементов, группа из 2 М элементов ЗАПРЕТ и генератор тактовых импульсов, выход которого соединен с информационным входом пер ваго управляемого вероятностного двоичного элемента группы и с объединенными инверсными входами 2 Н элементов ЗАПРЕТ группы, выходы датчиков пуассоновских потоков импульсов 20 соединены с прямыми входами одноименных элементов ЗАПРЕТ группы, выходы которых соединены с одноименными входами блока выравнивания интенсивностей потоков импульсов, -е выходы 25 (х = 1,3,5,) 1 с-й группы (1 с = - 1,2 2 И) блока выравниванияинтенсивностей потоков импульсов соединены со счетными входами одноименных управляемых вероятностных двоичных элементов группы, 3-е вы- ходы (3 = 2,4,6) к-й группы блока выравнивания интенсивностей потоков импульсов соединены с синхронизирующими входами одноименных управляемых вероятностных двоичных элементов группы, прямые выходы которых соеди" нены с одноименными входами регистра памяти, инверсный выход и-го (и = - 1 И - 1) управляемого вероятност"Уф) ного двоичного элемента соединен с информационным входом (и + 1)-го управляемого вероятностного двоичного элемента, инверсный выход И-гоуправляемого вероятностного двоичного элемента соединен с (И + 1)-мвходом регистра памяти, ш-разрядныйуправляющий вход и-го управляемоговероятностного двоичного элементасоединен с выходами и-го блока памяти,2. Генератор по и. 1, о т л ич а ю щ и й с я тем, что управляемый вероятностный двоичный элемент содержит счетчик, стробированный дешифратор, группу элементов И, группу элементов ЗАПРЕТ, первый и второй элементы ИЛИ, выходы которых являются соответственно прямым и инверсным выходами двоичного элемента, счетный и установочный в "О" входы счетчика являются соответственно счетным исинхронизирующим входами управляемого вероятностного двоичного элемента, информационные выходы счетчика соединены с информационными входами стробированного дешифратора, вход стробирования которого является инФормационным входом управляемого вероятностного двоичного элемента, выходы стробированного дешифратора соединены с первыми входами соответствующих элементов И группы, с прямыми входами соответствующих элементов ЗАПРЕТ группы, инверсные входы которых соединены с вторыми входами соответствующих элементов И группы и образуют разрядный управляющий вход управляемого вероятностного двоичного элемента, выходы элементов И и элементов ЗАПРЕТ групп соединены с соответствующими входами первого и второго элементов ИЛИ соответственно.липенко кт одписн ака комитета СС открытииская наб. 4/ ие,г.ужгород,ул.Проектная, 4 86/51 Тираж 671 ВНИИПИ Государственног по делам изобретений 3035, Москва, Ж, Рароизводственно-полиграфическое пре Прямои Йиод Фарсь(июд