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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 4 б 06 1 7/5 ЕТ ИЯ ТВУ ческии инстит ндрони о ССС , 1974, СССР , 1984,ена структурная фиг. 2 - блок ераторВ-три г у фронт ЛИ 1115. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЬПИЯМПРИ ГКНТ СССР ПИСАНИЕ ИЗ ВТОРСКОМУ СВИДЕТЕ(56) Авторское свидетельств451085, кл. 6 06 Р 15/20Авторское свидетельство1070548, кл. б 06 Г 7/58 Изобретение относится к области автоматики и вычислительной техники и может использоваться для генерации вхОдных последовательностей п ри стохастическом контроле дискретных объектов.Цель изобретения - упрощение генератора.На фиг. 1 представлсхема генератора; науправления.Генератор случайного марковского процесса содержит блок 1 управления, генератор 2 случайнь 1 х чисел, блок 3 памяти указателей начала строк, счетчик 4, блок 5 памяти кодов состояний, блок 6 памяти элементов строк, блок 7 сравнения, выходной регистр 8 памяти. Блок 1 управления содержит ге тактовых. импульсов, динамическии гер 10, срабатывающий по заднем тактового импульса, элемент И инвертор 12 и три элемента И 13 -(54) ГЕНЕРАТОГ СЛ УЧА Й НОГО МА Г- КОВСКОГО ПРОЦЕССА(57) Изобретение относитсяавтоматике и вычислительной технике и может быть использовано для генерации входных последовательностей при стохастическом контролс дискретных объектов. Цель изобретения - упрощение генератора. Для этого в генератор введены функционально ориен 1 ированные блоки памяти. Генератор случайного марковского процесса сойержпт генератор случа 1" ных чисел, блок памятиказателей начала строк, блок памяти колов состояний. блок памяти элементов трок блоки управления, сравнения. счетчик ц регистр. 2 ил. 4 табл. Блоки 3, 5 и 6 памяти прейназначены для хранения в сжатой форме стохастической матрицы переходов. Считывание информации из блоков 3, 5 и 6 памяти происходит при поступлении соответств ющих адресов на их адресные входь 1.Счетчик 4 предназначен йля хранения и формирования адреса, по которому осуществляется обращение к блокам 5 и 6 памяти.Блок 7 сравнения выполняет сравнение чисел, поступающих от генератора 2 случайных чисел и от блока 6 памяти элементов строк, вырабатывая признак ( либо ).Выходной регистр 8 памяти прейназначен для хранения текущего состояния цепи.Генератор работает следующим образом.Пусть задан марковский процесс, описываемь 1 й конечным множеством состояний 5=(з, 1=0,п - 1 и стохастической матрнцей переходов Р= 1 Р; 1, гйе Р, - вероят ность перехода за один такт из состояния. Я=11 се 11, 1=О, и - з;К=11811;т=111,11, ь=О, с(п 2где д - степень разряженности матрицы Р.Координата Ч, вектора Я содержит суммарное число ненулевых элементов строкматрицы Р, предшествующих строке 1, т. е.Чо=ОЧ =Мо,Ч 2 - Ч +%Чл - = - Чл - 2+11 л - 2,где Мо, К,"., 1 Ч 2 - число ненулевых элементов строк 0,1 и - 2 матрицы Р.Перейдем от стохастической матрицы Рк матрице Р =11 Рй 11,О, если Р ,=0;где Р, = сУР, если РУФО. 0Векторы К и Т получаются следующимобразом./Из матрицы Р построчно выписывают ввектор К ненулевые элементы Р;,; в вектор Т - индексы к столбцов ненулевыхэлементов.Вектор Я загружается в блок 3 памяти указателей начала строк, содержащий и ячеек разрядностью 1 од 2 дп 2.Вектор К загружается в блок б памяти, элементов строк, содержащий дп ячеек разрядностью гп, причем в память записываются только числители аи дробей видаР;=а, 2Вектор Т загружается в блок 5 памятикодов состояний содержащий с(п 2 ячейки разрядностью 1 од 2 п. Например, для матрицы РФиз табл. 1 матрица Р имеет вид, представленный в табл. 2.Вектор Я представлен в табл. 3, а векторы К и Т - в табл. 4.Перед началом работы Я, К, Т вычисляются и загружаются в соответствующиеблоки 3, 5 и 6 памяти (на фиг. 1 устройство загрузки не показано),Начальное состояние з цепи задается следующим образом.В выходной регистр 8 памяти загру.жают код 1 состояния з. В счетчик 4 загружают координату Ч векторами (на фиг. 1устройства загрузки не показаны). При этомна выходах блока 6 памяти элементов строкпоявляется координата з, т. е. первыйненулевой элемент строкй 1 матрицы Р,который поступает на первую группу входов блока 7 сравнения. Одновременно навыходах блока 5 памяти кодов состоянийпоявляется код возможного будущего состояния зазл=1), а на выходах блока 3 памяти указателей начала строк - индекспервого ненулевого элемента строки а матрицы Р. в состояние Р= =а, 2, а, - целое.Стохастическая матрица Р хранится в сжатой форме в виде векторов 4На этом процесс загрузки исходнь 1 х данных завершен.В начальный момент времени, до приходапервого тактирующего сигнала от, генератора 9 тактовых импульсов, динамический Ртриггер 10 для определенности находится внулевом состоянии.Первый тактируюгций сигнал от генератора 9 тактовых импульсов через эле-мент И поступает на управляющий вход10 генератора 2 случайных чисел. По заднемуфронту тактового сигнала триггер 10 переключается в единичное состояние.После запуска по сигналу от блока 1управления датчик 2 равномерно распределенных на отрезке (0,1) случайных чисел вырабатывает гп-разрядное двоичное число7 =х2и величина х,; подается навторую группу входов блока 7 сравнения.Блок 7 сравнения может вырабатыватьпризнак ( (число от генератора 2 слу 20 чайных чисел меньше или равно, чемчисло, получаемое от блока б памяти элементов строк) либо признак ) (числоот генератора 2 случайных чисел больше,чем число, получаемое от блока 6 памятиэлементов строк).Если вырабатывается признак ).,очередной тактовый импульс генератора 9 через элемент И 13 поступает на счетный вход счетчика 4 и увеличивает егосодержимое на единицу,В результате изменения содержимогосчетчика 4 одновременно срабатывают блокипамяти 5 и б: на первую группу входовблока 7 сравнения поступает очередное значение ненулевого элемента строки а матрицы Р; на входы блока 3 памяти поступает код возможного будущего состояния з,.Вновь срабатывает блок 7 сравнения.Если блок 7 сравнения опять вырабатывает признак ), процесс увеличения счетчика 4 и чтения блоков 5 и 6 памятиповторяется, вновь срабатывает блок 7 и т. д.Если вырабатывается признак (, очередной тактовый импульс генератора 9через элемент И 15 поступает на входзаписи регистра 8 памяти и фиксирует внем код следующего состояния з Этот жетактовый импульс поступает на установочный вход счетчика 4 и фиксируетиндекс первого ненулевого элемента матрицы Р строки ю, который к этому времени появился на выходах блока 3 памятиуказателей начала строк.Одновременно по заднему фронту этогоже тактового импульса динамический 0-триггер 10 переключается в нулевое (исходноесостояние, поскольку на вход 0-триггера через инвертор 12 и элемент ИЛИ 11поступает инвертированное значение призу нака сравнения.Цикл выработки очередного состояния цепи завершен.С приходом очередного тактового импульса триггер 10 опять переключается в1481755 Формула изобретения Таблица 1 0 1 2 3 2 3 4 5 89310240 131 010241 0 0 0 0 651 010240 0 37310240 2 17 0 1024 3 175 0 512 4 0 0100710240 0 019 13 3375120 0 32 32 0 0 1632560 93256О 5 0 0 101310240 19 64 единичное состояние, выдается сигнал запуска генератора 2 случайных чисел и т. д.Таким образом, путем сравнения чисел, поступающих от генератора 2, с ненулевыми элементами матрицы Р происходит моделирование случайного марковского процесса. Генератор случайного марковского процесса, содержащий регистр, управляемый 10 генератор случайных чисел, блок управления, первый выход которого соединен с входом записи регистра памяти, а второй выход соединен с запускающим входом управляемого генератора случайных чисел, отличающийся тем, что, с целью упрощения, он содержит блок памяти указателей начала строк, блок памяти кодов состояний, блок памяти элементов строк, счетчик, блок сравнения двоичных чисел, выход которого соединен с запускающим 20 входом блока управЛения, третий выход 6 0 11 0 0 1024 7 .45 0 0 0 64которого соединен со счетным входом счетчика, установочный вход которого соединен с четвертым выходом блока управления, разрядные выходы счетчика подключены к соответствующим адресным входам блока памяти кодов состояний и адресным входам блока памяти элементов строк, информационные выходы которого соединены с первой группой соответствующих информационных входов блока сравнения, вторая группа информационных входов которого соединена с соответствующими информационными выходами управляемого генератора случайных чисел, информационные выходы блока памяти кодов состояний соединены с соответствующими информационными входами регистра и адресными входами блока памяти указателей начала строк, информационные выходы которого подк;.ю,ены к соответствующим информационн=.;. входам счетчика, информационные выходы регистра являются информационными выходами генератора случайного марковского процесса.1481755Фиг. 2Состав ител ь Ю. АндреевРедактор Л. Гратилло Техред И. Верес Корректор С. ЧерниЗаказ 2690/49 Тираж 669 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж - 35, Раушская наб., д. 4/5Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101