Генератор случайного процесса Советский патент 1986 года по МПК G06F7/58 

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

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

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

Генератор случайного процесса содержит группу датчиков 1 пуассоновс- ких потоков импульсов, группу 2 элементов SAIIPJET, блок 3 выравнивания интенсивностей случайных потоков импульсов, группу управляемых вероятностных двоичных элементов 4,-4ц, группу блоков 5,- 5f( памяти, регистр 6 памяти, шифратор 7, генератор 8 такто-вых импульсов.

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

Каждьй вероятностный двоичный элемент 4 содержит счетчик 1Q, стро- бированный дешифратор П, группу 12 элементов И, группу. 13 элементов ЗАПРЕТ, первый 14 и второй 15 элементы ИЛИ,

Регистр 6 памяти содержит группу триггеров 16,- , и группу элементов ИЛИ 17, - 17(4..

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

Через открытые (в отсутствие импульсов генератора 8) элементы ЗАПРЕТ группы 2 случайные потоки импульсов датчиков 1 группы поступают на соответствующие входы блока 3. Блок 3 с помощью матрицы из N х М выравнивателей 9 двух потоков импульсов производит преобразование 2N входных потоков импульсов в общем случае с различными интенсивностямй в 2N независимых потоков импульсов., интенсивности которых одинаковы и ,определяются как среднее арифметичес кое интенсивн.остей )(. , j 1,2N входньос потоков

2N

(1)

гм

2N

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

Работа каждого вероятностного двоичного элем.ента 4 группы основана на использовании вероятностных

свойств марковского процесса смены состояний счетчика 10, находящегося под воздействием, (по счетному входу и входу Сброс) двух независимых пуассоновских потоков импульсов с

равной интенсивностью. Суть этих

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

Р 41

Р (1/2) , г 0,1,2,., (2)

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

IV

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

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

О,

I Z

в и « а

В1

а, 6

0,1, дей

0

5

ствующим на разрядном управлякнцем входе двоичного элемента, открыты те элементы И группы 12 (элементы ЗАПРЕТ группы 13), которые соответствуют разрядам управляющего кода X, содержащим единицы (нули). Первый 14 (второй 15) элемент ИЛИ путем

дизъюнктивного суммирования вероят п /т

ностей

SIP

ЕМ

е-)

а„

форПБ

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

на прямом (инверсном) выходе элемента 4, .

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

0 заданной с помощью двоичного кода О : X 6 1 вероятности Р пропускает импульсы опроса на прямой выход и с вероятностью (I-P) - на инверсный выход,,

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

3

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

тояние

11 ч II

, а все другие триггеры

10 кодов , представленных в виде правильных двоичных дробей о, а,, а,..,

16 регистра с с помощью группы элементов ИЛИ 17 - в состояние О. Пространственно распределенное случайное событие, заключающееся в том, при этом индекс j соответствует номеру что триггер регистра 6 находится 15 блока 5 памяти, а индекс п - адресу

а, численно равные условным вероятностям „;, заносят в блоки 5 памяти.

Ч, преобразуется с по- ячейки в j-M блоке памяти группы 5.

20

25

30

35

в состоянии

мощью шифратора 7 в цифровой двоичг ный код A(t,) n(tp. В соответствии с текущим кодом адреса A(t, ), являющимся одновременно и выходным сигналом генератора, на управляющие входы элементов А вызываются новые управляющие коды X „: , j 1, N, находящиеся в п-х строках N блоков 5 памяти. На следукндем, втором такте, определяемом вторым импульсом генератора 8, работа генератора случайного процесса повторяется, но уже с учетом новых значений кодов, действующих на управляющих входах элементов 4 группы.

Рассмотрим методику настройки генератора при формировании цепи Марко ва по заданному графу ее состояний. При этом воспроизводимый граф цепи Маркова по числу N состояний (вершин) не должен превышать возможности генератора Np i N+1.

Предлагаемый генератор формирует цепь Маркова с (N + 1) дискретными состояниями по полному графу, содержащему максимально возможное число направлений перехода N(N+1). Для формирования цепи Маркова по задан- ному графу необходимо составить пол- ную матрицу вероятностей перехода Р „; II ; п, j 1, N, в которой равны нулю все вероятности отсутствующих в графе r(N) направлений перехода как в существующие, так и в не- 50 существующие вершины (состояния).

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

Установка начального Пр состоя- .ния моделируемой цепи Маркова производится подачей внешнего импульса на единичньй вход п-го триггера 16 регистра 6 памяти.

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

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

T.min(3-4)

(4)

40

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

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

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

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

J

костей, элементы „ которой связаны с элементами исходной матрицы вероятностей перехода соотношением

(3)

Г

К.1

при использовании формулой (3) неопределенность типа g принимается равной нулю. Значения управляющих

10 кодов , представленных в виде правильных двоичных дробей о, а,, а,..,

при этом индекс j соответствует номеру 15 блока 5 памяти, а индекс п - адресу

при этом индекс j соответствует номер блока 5 памяти, а индекс п - адресу

а, численно равные условным вероятностям „;, заносят в блоки 5 памяти.

Установка начального Пр состоя- .ния моделируемой цепи Маркова производится подачей внешнего импульса на единичньй вход п-го триггера 16 регистра 6 памяти.

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

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

T.min(3-4)

(4)

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

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

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

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

рого соединены с соответствующими -. входами пшфратора, выход которого является выходом генератора и соединён с адресными входами блоков памя- ти группы, отличающийся тем, что, с целью расширения функцио- нальньк возможностей генератора за счет формирования цепей Маркова по заданному графу их состояний, в него введены группа из N управляемых вероятностных двоичных элементов, группа из 2N элементов ЗАПРЕТ и генератор тактовых импульсов, выход которого соединен с информационным входом пер- вого управляемого вероятностного двоичного элемента группы и с объединенными инверснь1ми входами 2N элементов ЗАПРЕТ группы, выходы датчиков пуассоновских потоков импульсов соединены с прямыми входами одноименных элементов ЗАПРЕТ группы, выходы которых соединены с одноименными входами блока выравнивания интенсив- ностей потоков импульсов, i-e выходы (i 1,3,5,..,} k-й группы (k

1,2 2N) блока выравнивания

интенсивностей потоков импульсов соединены со счетными входами одноименных управляемых вероятностных двоичных элементов группы, j-e выходы (J 2,4,6) k-й группы блока выравнивания интенсивностей потоков импульсов соединены с синхронизирующими входами одноименных управляемых вероятностных двоичных элементов группы, прямые выходы которых соединены с одноименными входами регистра памяти, инверсньй выход п-го (п

1, N - 1) управляемого вероятност ного двоичного элемента соединен с информационным входом (п + 1)-го управляемого вероятностного двоичноj10 15 0 5

о

5

0

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

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

Вш.

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

jjfc-j

(риг. 2