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

IfИ

У0 - 1 (Pi )-1 А ; АО - hy ;

У, (Уо/2); А, А0 + Р (Уо/21 ) + Р0 (yemod2);

у|Г: Ьм/2з :т; А

Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных-объектов. Целью изобретения является повышение точности формирования случайного марковского процесса. Для достижения поставленной цели в генератор введены регистр 7 сдвига, группа элементов И 8, элемент И 9, второй датчик 11 случайной двоичной цифры, мультиплексор 12, элемент ИЛИ-НЕ 13, элемент ИЛИ 14, накапливающий сумматор 15. Очередное состояние марковского процесса вырабатывается путем сравнения случайных чисел, ваемых датчиком 5, с элементами модифицированной матрицы переходных вероятностей и генерацией равномерно распределенных чисел, полученных путем случайного половинного деления с помощью регистра 7 сдвига и датчиков 10 и 11. 2 ил. (Л

и т.д. до тех пор, пока все старшие разряды с выхода 7.1 регистра 7 сдвига станут равными нулю. При этом на выходе элемента ИЛИ 13 установится сигнал 1 и блок 16 управления перейдет в состояние a..

К моменту перехода блока 16 управления в состояние а

в накапливающем сумматоре 15 будет зафиксировано случайное число

Ак А0 + Z,

где А0 h« ;

Z - ) + (y0mod2) +

+ .;.+ Ри(СУк-2/2 ) +

+ Рк-г(Ук-г m°d2) + Р ки ()

+ PK-I (yK tmod2).

Из способа получения числа Z следует, что и причем зако распределения случайного числа Z является равномерным.

Очевидно, число А также является случайным и равномерным распределено в диапазоне hy ,...,h у.

Случайное число СО, СО А является кодом следующего состояния цепи Маркова.

В состоянии af блок 16 управления выдает управляющие сигналы Запись в счетчик 1 и Опрос датчика 5.При

этом сигнал на синхронизирующем выходе генератора указывает, что на его информационном выходе получено очередное состояние 8щ цепи Маркова; в счетчике 1 записывается значение координаты ц™, поступающее с выхода блока 2 памяти, и начинается новый цикл работы генератора.

Таким образом, процесс порожде- ния очередного состояния цепи Маркова при текущем состоянии sf выполняется в два этапа:

первый - этап поиска в сжатой строке Pi подстроки Pf такой, что pj-i /х Ј р| ;

второй - этап равномерной генерации состояния SQ из множества состояний

AW Г ) и S lsay, hy ЈGOЈhji .

i

Выполнение первого этапа обеспечивается сменой состояний а,аг,аэ, а выполнение второго, этапа - сменой состояний а,ae,ag блока 16 управления.

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

Генератор случайного марковского процесса, содержащий блок управления, три блока памяти, счетчик, схему сравнения, датчик равномерно распределенных случайных чисел и датчик случайной двоичной цифры, причем вход „пуска генератора является входом пуска блока управления , первый выход которого является синхронизирующим выходом генератора и соединен с входом записи счетчика, выход которого соединен с адресными входами первого и второго блоков памяти, выход первого блока памяти соединен с первым информационным входом схемы сравнения, выход которой соединен с первым входом задания логических условий блока управления, второй выход которого соединен с входом опроса датчика равномерно распределенного случайного числа, выход которого соеди- , нен с вторым информационным входом схемы сравнения, третий выход блока управления соединен со счетным входом счетчика, информационный вход которого соединен с выходом третьего блока памяти, четвертый выход блока управления соединен с входом опррса датчика случайной двоичной цифры, отличающийся тем, что, с целью повышения точности формирования случайного марковского процесса, в него введены второй датчик случайной двоичной цифры, регистр сдвига, два элемента ИЛИ, блок элементов И, мультиплексор, элемент И и накапливающий сумматор, причем выход второго блока памяти соединен с первым информационным входом мультиплексора и

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

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

г двоичной цифры, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом младшего разряда регистра сдвига, выход первого датчика случайной двоич0 ной цифры соединен с управляющим входом блока элементов И, выход которого соединен с вторым информационным входом мультиплексора, выход которого соединен с первым информационным вхо5 дом накапливающего сумматора, второй информационный вход которого соединен с выходом второго элемента ИЛИ, седьмой выход блока управления соединен с входом записи накапливающего

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

ч Вход 1 на мультиплексор 12 сложить на на - кагмидающии сумматор 15 „м насцетмх 1

Редактор А.Мотыль

Составитель Д.Феликсон

Техред М;Дидык Корректор Н.Ревская

fft

Пуск -

„ Прием б счетчик 1 „Опрос датчика 5

„ Сорос накапливающего сумматора

„Прием & регистр h опрос датчикоб

, wpoc юЬ11

и

Сложить на

накапливающий сумматор 15

Вшад ч / элемента или-мГ 13

ак

„СдВц2 на регистр 7 „Опрос датцихоб 10 и 11

Фиг. 2