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

 

Изобретение относится к области вычислительной техники и может быть использовано при моделировании цепей Маркова по заданному состоянию. Целью изобретения является расширение функциональных возможностей генератора. Генератор случайного процесса содержит группу датчиков пуассоновских потоков импульсов,группу элементов ЗАПРЕТ, блок вьфавнивания интенсивностей случайных потоков импульсов, группу управляемых верояткостных двоичных элементов, группу блоков памяти, регистр памяти, шифратор , генератор тактовых импульсов. Поставленная цель достигается за счет введения в генератор группы управляемых вероятностных двоичных элементов, включенных по ступенчатой .схеме и выполняющих функцию управляемого вероятностного (N+1)-no- люсника, в результате чего объект изобретения приобретает новое свойство - программируемой замкнутой системы связи со счетным числом N+1 состояний и дискретным временем. Случайный и независимый выбор очередного состояния происходит в моменты, определяемые тактовым генератором, по матрице строки квадратной матрицы вероятностей перехода, при этом номер матрицы строки определяется текущим состоянием п(+) выходного потока. Генератор работает следующим образом. Случайные потоки импульсов датчиков поступают на входы блока выравнивания. Блок выравнивания с помощью матрицы NxM выравнивателей производит преобразование 2N входных потоков импульсов в общем случае с различными интенсивностями в 2N независимых потоков импульсов,интенсивности которых одинаковы. С выходов блока выравнивания 2N пуассоновских потоков импульсов с одинаковой интенсивностью поступают на счетные и синхронизирующие входы N вероятностных двоичных элементов. Каждый вероятностный двоичный элемент выполняет роль вероятностного вентиля, который по заданной вероятности Р пропускает импульсы опроса на прямой выход и с вероятностью (1-Р) на инверсный выход. Настройка блоков памяти осуществляется по матрице условных вероятностей , элементы Р которой связаны с элементами Р. исходной матрицы вероятностей перехода. Установка начального состояния произведена подачей внешнего импульса на единичный вход регистра памяти. 1 з.п.ф-лы, 4 ил. (Л to со 4ii 00 ср Cio

СОЮЗ СОНЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (1I) Al (sn 4 G 06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3744173/24-24 (22) 22.05.84 (46) 30.05.86. Бюл. N - 20 (72) А.С.Анишин (53) 681 ° 333(088.8) (56) Авторское свидетельство СССР

Р 489098, кл. G 06 F 7/58, 1974.

Авторское свидетельство СССР

Р 744532, кл. С 06 F 7/58, 1978.

Авторское свидетельство СССР

Р 1138802, кл, G 06 F 7/58, 1983. (54) ГЕНЕРАТОР СЛУЧАЙНОГО ПРОЦЕССА (57) Изобретение относится к области вычислительной техники и может быть использовано при моделировании цепей Маркова по заданному состоянию.

Целью изобретения является расширение функциональных возможностей генератора. Генератор случайного процесса содержит группу датчиков пуассоновских потоков импульсов, группу элементов ЗАПРЕТ, блок выравнива- ния интенсивностей случайных потоков импульсов, группу управляемых вероятностных двоичных элементов, группу блоков памяти, регистр памяти, шифратор, генератор тактовых импульсов.

Поставленная цель достигается за счет введения в генератор группы управляемых вероятностных двоичных элементов, включенных по ступенчатой схеме и выполняющих функцию управляемого вероятностного (N+1)-полюсника, в результате чего объект изобретения приобретает новое свойство — программируемой замкнутой системы связи со счетным числом N+1 состояний и дискретным временем.

Случайный и независимый выбор очередного состояния происходит в моменты, определяемые тактовым генератором, по матрице строки квадратной матрицы вероятностей перехода, прн этом номер матрицы строки определяется текущим состоянием п(+) выходного потока. Генератор работает следующим образом. Случайные потоки импульсов датчиков поступают на входы блока выравнивания. Блок выравнивания с помощью матрицы ИиИ выравнивателей производит преобразование 2N входных потоков импульсов в общем случае с с различными интенсивностями в 2N независимых потоков импульсов,интенсивности которых одинаковы. С выходов блока выравнивания 2N пуассоновских потоков импульсов с одинаковой интен- с сивностью поступают на счетные и синхронизирующие входы N вероятностных двоичных элементов. Каждый вероятностный двоичный элемент выполняет роль вероятностного вентиля, который по ©Р заданной вероятности Р„ пропускает Да импульсы опроса на прямой выход и с вероятностью (1-Р„) на инверсный выход. Настройка блоков памяти осуществляется по матрице условных вероJ ятностей, элементы Р - которой свя"1 заны с элементами Р„исходной матри1 цы вероятностей перехода. Установка ф начального состояния произведена

Ъ подачей внешнего импульса на единичный вход регистра памяти. 1 з.п.ф-лы, 4 ил.

1 12

Изобретение относится к вычислительной технике и может быть использовано при моделировании цепей Napкова по заданному графу состояний или матрице вероятностей перехода, Цель изобретения — расширение функциональных возможностей генератора за счет моделирования цепей

Маркова по заданной матрице вероятностей перехода. На фиг. 1 изображена структурная схема генератора; на фиг. 2 — блок выравнивания случайных потоков импульсов, на фиг. 3 — вероятностный двоичный элемент; на фиг. 4 — регистр памяти.

Генератор случайного процесса содержит группу датчиков 1 пуассоновских потоков импульсов, группу 2 элементов ЗАПРЕТ, блок 3 выравнивания интенсивностей случайных потоков импульсов, группу управляемых вероятностных двоичных элементов 4,-4„, группу блоков 5» — 5 памяти, регистр

6 памяти, шифратор 7, генератор 8 тактовых импульсов.

Блок выравнивания содержит N X М (М = 1О8 N + 1) выравнивателей 9 двух потоков импульсов.

Каждый вероятностный двоичный элемент 4 содержит счетчик 10, стробированный дешифратор 11, группу 12 элементов И, группу 13 элементов

ЗАПРЕТ, первый 14 и второй 15 элементы ИЛИ.

Регистр 6 памяти содержит группу триггеров 16, — 16„„ и группу элементов ИЛИ 17, — 171,+1.

Генератор случайного процесса работает следующим образом.

Через открытые (в отсутствие импульсов генератора 8) элементы

ЗАПРЕТ группы 2 случайные потоки импульсов датчиков 1 группы поступают на соответствующие входы блока

3. Блок 3 с помощью матрицы из N x М выравнивателей 9 двух потоков импульсов производит преобразование

2N входных потоков импульсов в общем случае с различными интенсивностями в 2N независимых потоков импульсов., интенсивности которых одинаковы и, определяются как среднее арифметическое интенсивностей %, j=1 2N входных потоков

2й а;

3-"1

2 гг

34833 2

С Выходов блока 3 2N пуассоновских потоков импульсов с одинаковой интенсивностью Я поступают на счет- и ные и синхронизирующие входы N вероятностных двоичных элементов 4 группы.

Работа каждого вероятностного двоичного элемента 4 группы основана на использовании вероятностных свойств марковского процесса смены состояний счетчика 10, находящегося под воздействием (IIQ счетному входу и входу "Сброс" ) двух независимых пуассоновских потоков импульсов с равной интенсивностью. Суть этих свойств. состоит в том, что безуслов— ные вероятности пребывания счетчика

10 в состояниях 7 = 0,1,2,... определяются формулой геометрической прогрессии с начальным членом и коэффициентогл, равными 1/2

P = (1/2), 2 = О, 1)2.. ° (2) 10

50 заданной с помощью двоичного кода

0 Х 1 вероятности Р„ пропускает импульсы опроса на прямой выход и с вероятностью (1-Р„ ) — на инверсный выход„

Импульсы генератора 8 с частотой

F определяют длительность Т = 1/Р такта марковской цепи. Для надежной работы двоичных элементов группы 4

25 и не зависят от параметра 3 „

Импульсы опроса, поступающие на информационный вход элемента 4, проходят на вход стробирования дешифратора 11 и с вероятностями (2) появля30 ются на соответствующих выходах дешифратора 11.

Б соответствии с двоичным кодом

Х-= О., a1, а2. ".ащ, а,е 0.1, действующим на разрядном управляющем

ВХОде двоичного элемента Открыты те элементы И группы 12 (элементы

ЗАПРЕТ группы 13), которые соответст вуют разрядам управляющего кода Х, содержащим единицы (нули). Первый

14 (второй 15) элемент ИЛИ путем дизъюнктивного суммирования вероятМ (N Ф ностей - я-s eI, - Pe-1 ™e фор. Е1 Емгирует случайное событие, заключающееся в появлении импульса опроса на йрямогл (инверсном) выходе элемента 4.

Таким образом, каждый вероятностный двоичный элемент выполняет роль вероятностного вентиля, который по

12348 датчики 1 пуассоновских потоков импульсов с помощью группы 2 элемен:тов ЗАПРЕТ на время действия импульсов генератора 8 отключаются.

Будем полагать, что первый импульс генератора 8 появьщся на прямом выходе и-го двоичного элемента

Тогда соответствующий триггер 16 регистра 6 памяти переводится в состояние " 1", а все другие триггеры >0

16 регистра с с помощью группы элементов ИЛИ 17 — в состояние "О". Про-. странственно распределенное случайное событие, заключающееся в том, что триггер 16> регистра 6 находится 15 в состоянии "1", преобразуется с помощью шифратора 7 в цифровой двоич-. ный код A(e,) = n(t ). В соответствии с текущим кодом адреса А(й<), являющимся одновременно и выходным 20 сигналом генератора, на управляющие входы элементов 4 вызываются новые управляющие коды Х „, j = 1 N находящиеся в и-х строках N блоков

5 памяти. На следующем, втором так- 25 те, определяемом вторым импульсом генератора 8, работа генератора случайного процесса повторяется, но уже с учетом новых значений кодов, действующих на управляющих входах элементов 4 группы.

Рассмотрим методику настройки генератора при формировании цепи Марко ва по заданному графу ее состояний.

При этом воспроизводимый граф цепи т+

Маркова по числу N состояний (верг шин) не должен превышать воэможности генератора NÄ N+1, Предлагаемый генератор формирует цепь Маркова с (N + 1) дискретными состояниями по полному графу, содержащему максимально возможное число направлений перехода N(N+1). Для формирования цепи Маркова по заданному графу необходимо составить пол- 4 ную матрицу вероятностей перехода (! P„ }(; n, j = 1, N, в которой равны нулю все вероятности отсутствующих в графе Г(Х ) направлений перехода как в существующие, так и в не- 0 существующие вершины (состояния).

Группа вероятностных двоичных элементов 4 реализует функцию управляемого вероятностного 1, (N+1)-полюсника по методу условных вероятностей. В связи с этим настройка блоков 5 памяти группы должна осуществляться по матрице условных вероятФ

33 4

1 ностей, элементы Р„ которои связаны с элементами P исходной матрицы п1 вероятностей перехода соотношением р (3) — Рлк

x-i

При использовании формулой (3)

îo неопределенность типа — принимается равной нулю. Значения управляющих кодов Х представленных в виде npanit вильных двоичных дробей о, а,, а а численно равные условным вероятФ

1 лостям Р„, заносят в блоки 5 памяти, при этом индекс 1 соответствует номеру блока 5 памяти, а индекс n — адресу ячейки в j-м блоке памяти группы 5.

Установка начального п состояния моделируемой цепи Маркова производится подачей внешнего импульса на единичный вход и-го триггера 16 регистра 6 памяти, В предлагаемом генераторе интенсивность датчиков 1 является параметром, определяющим быстродействие элементов 4 группы при формировании независимых случайных событий.

Минимальный период опроса вероятностного двоичного элемента составляет

Т " (3-4) . (4) гМ

В предлагаемом генераторе вероятностные характеристики цепи Маркова определяются только значениями управляющих кодов Х„ и не зависят от интенсивностей датчиков 1. Благодаря этому предлагаемый генератор по точности работы не уступает генератору по прототипу.

Кроме того, изобретение характеризуется простым устройством, высоким быстродействием и надежностью в работе. Выход из строя даже нескольких датчиков 1 на нарушает работы генератора в целом. В этом случае с учетом (1) и (4) изменяется (снижается) лишь допустимая верхняя частота Р генератора 8.

Формула изобретения

1. Генератор случайного процесса, содержащий группу из 2N датчиков пуассоновского потока импульсов, блок выравнивания интенсивности потоков импульсов, группу из N блоков памяти, регистр памяти, выходы кото-ъ

1234833 рого соединены с соответствующими -. входами шифратора, выход которого является выходом генератора и соединен .с адресными входами блоков памяти группы, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет формирования цепей Маркова по заданному графу их состояний, в него 10 введены группа из N управляемых вероятностных двоичных элементов, группа из 2N элементов ЗАПРЕТ и генератор тактовых импульсов, выход которого соединен с информационным входом пер- 1 ваго управляемого вероятностного двоичного элемента группы и с объединенными инверсными входами 2N элементов ЗАПРЕТ группы, выходы датчиков пуассоновских потоков импульсов 2g соединены с прямыми входами одноименных элементов ЗАПРЕТ группы, выходы которых соединены с одноименными входами блока выравнивания интенсивностей потоков импульсов, х-е выходы 25 (х = 1,3,5,...) Е-й группы (к = — 1,2,..., 2N) блока выравнивания интенсивностей потоков импульсов соединены со счетными входами одноименных управляемых вероятностных двоичных элементов группы, j-e вы- ходы (j = 2,4,6) к-й группы блока выравнивания интенсивностей потоков импульсов соединены с синхронизирующими входами одноименных управляемых вероятностных двоичных элементов группы, прямые выходы которых соединены с одноименными входами регистра памяти, инверсный выход и-го (n = — 1 N — 1) управляемого вероятностУ ф) ного двоичного элемента соединен с информационным входом (и + 1)-го управляемого вероятностного двоичноro элемента, инверсный выход N-ro управляемого вероятностного двоичного элемента соединен с (N + 1)-м входом регистра памяти, m-разрядный управляющий вход и-го управляемого вероятностного двоичного элемента соединен с выходами и-го блока памяти.

2. Генератор по и. 1, о т л ич а ю шийся тем, что управляемый вероятностный двоичный элемент содержит счетчик, стробированный дешифратор, группу элементов И, группу элементов ЗАПРЕТ, первый и второй элементы ИЛИ, выходы которых являются соответственно прямым и инверсным выходами двоичного элемента, счетный и установочный в "О" входы счетчика являются соответственно счетным и синхронизирующим входами управляемого вероятностного двоичного элемента, информационные выходы счетчика соединены с информационными входами стробированного дешифратора, вход стробирования которого является информационным входом управляемого вероятностного двоичного элемента, выходы стробированного дешифратора соединены с первыми входами соответствующих элементов И группы, с прямыми входами соответствующих элементов ЗАПРЕТ группы, инверсные входы которых соединены с вторыми входами соответствующих элементов И группы и образуют разрядный управляющий вход управляемого вероятностного двоичного элемента, выходы элементов И и элементов ЗАПРЕТ групп соединены с соответствующими входами первого и второго элементов ИЛИ соответственно.

1? 34833

1234833

ИнЦ)

Прями

Йиод

Сиихр дк, Ин3срсНЫи чФ

Составитель И, Столяров

Редактор Е. Копча Техред М.Ходанич Корректор Л. Пилипенко

Заказ 2986/51 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие,г.ужгород,ул.Проектная, 4