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

СОЮЗ СОБЕТСНИХСОЦИА ЛИСТ ИЧЕСНИХРЕСПУБЛИН 51)5 0 0 ОСУДАРСТВЕННЫЙ НОМИТЕО ИЗОБРЕТЕНИЯМ И ОЗНРЫТРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ(54) ПРОЦ ЧАИНОГО 11 АР 108 С ГЕНЕРАТОР СЛУССАИзобретениеи вычислител относится к автомаьной технике и может тике ис ьзоватьс дователь нерации входных ей при стохасти ком нтроле дискретных кто ВТОРСКОМУ СВИДЕТЕЛЬСТВ,8111619262 А 1 2Целью изобретения является повьпдение точности формирования случайного марковского процесса. Для достижения поставленной цели в генератор введе" ны регистр 7 сдвига, группа элементов И 8, элемент И 9, второй датчик 11 случайной двоичной цифры, мул типлексор 12; элемент ИЛИЕ 13, эле мент ИЛИ 14, накапливающий сумматор 15, Очередное состояние марковского процесса вырабатывается путем сравнения случайных чисел, вырабатываемых датчиком 5, с элементами моди фицированной матрицы переходных веро ятностей и генерацией. равномерно распределенных чисел, полученных путем случайного половинного деления с помощью регистра 7 сдвига и датчиков 10 и 11. 2 ил.Изобретение относится к автоматикеи вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов.Цель изобретения - повышение точности формирования случайного марковФского процесса.На фкг.1 представлена структурная схема генератора; на фиг.2 - блоксхема алгоритма работы блока управления.Генератор случайного марковского процесса содержит счетчик 1, блоки 2-4 памяти, датчик 5 равномерно распределенных случайных чисел, схему 6 сравнения, регистр 7 сдвига с выходами 7.1 старших разядов и 7.2 младшего разряда, блок 8 элементов И, элемент И 9, датчики 1 О и 11 случайной двоичной цифры, мультиплексор 2, элементы ИЛИ 13 и 14, накапливающий сум" матор 15 и блок 16 управленияСчетчик 1 предназначен для хранения и формирования адреса, по.которому осуществляется обращение к блокам 3 и 4 памяти. Блоки 2-4 памяти предназначены для хранения в сжатой1форме стохастической матрицы переходов. Считывание информации из блоков 2-4 происходит при поступлении соответствующих адресов на их адресные входы.Регистр 7 сдвига предназначен для35 хранения и сдвига в сторону младшего разряда информации, поступающей на его информационный вход.Накапливающий сумматор 15 предназначен для формирования и хранения 4 О текущего состояния цепи, Кроме того, код текущего состояния цепи является адресом, по которому происходит обращение к блоку 2 памяти. Блок 16 управления предназначен 45для реализации алгоритма работы генератора и полностью определяетсяблок-схемой алгоритма, представленноина фиг,2. Блок 16 управления представляет собой упрагляющий автомат ссостояниями ааа, структуркоторого получается в соответствиис методами синтеза,В состоянии аблок 16 управлениявыдает; сигналы "Запись" в счетчики "Опрос" датчика 5.В состоянии а блок 16 управпениявя;дает сигнал "Сброс" на накапливающий сумматор 15,В состоянии аблок 16 управлениявыдает сигналы "Вход 1" на мультиплексор 12; "Сложить" на накапливающий сумматор 15 и "+1" в счетчик 1.В состоянии а блок 16 управления выдает .сигналы: Запись в регистр 7 и "Опрос" датчиков 1 О и 11.3 состоянии а блок 16 управлениявыдает сигнал "Сложить" на накапливающий сумматор 15.В состоянии а блок 16 управлениявыдает сигналы: "Сдвиг" на регистр 7и "Опрос" датчиков 1 О и 11.Генератор работает слецующим образом.Пусть задан марковский процессописываемый конечным множеством состояний Б = з; , д = О, ии стохастической матрицей переходов Р = //Р //и хп, где р, - вероятность переходаза один такт иэ состояния з, в состояние з, 1, = О, п, р, =ф 2 ",ф, - целое, ш - параметр, ойределяющий точность представления элементовстохастической матрицы переходовМатрица Р хранится в сжатом видев виде векторов Я = // //, К =//г //, Т = /Й //.Векторы Ц, К и Т получаются следующим образом.Устанавливают ц = О Сжимаютстроку Ро матрицы Р. Для этого в строке выделяют подстроки Р, Р0Р.Р из последовательно расположенныходруг за другом одинаковых элементов.Для каждой подстроки Р вычисляетсяКкочиспо 1(Р ) входящих в нее элементов,оПросматривая строку Р слева направо, в координаты г,г,1,г,.,,го,г ,1- , векторов К иТ последовательно выписывают: координату г -длину подстроки Р , уменьшенную накофкединицу, т.е. величину 1(Р )-1; вкоординату 1 к - сумму всех элементовстроки Р от Р до Ро 1 т.е. величинуР , где Ь - ичдекс столбцаКпослеДнего элемента подстроки Р,Пусть, при сжатии строки Р в Кьи Т были выписаны. позначении, гдеЬ, - число подстрок в строке Ро .Устанавливают пЩ . Аналогичностроке Р сжимают строку Р и в вектоОрах К и Т выписывают соответствующие значения, Пусть , - число подстрок строки РУстанавливают о= п +,. Аналогичным образом сжимают строки Р, 1619262Начальное состояние аЕ цепи Маркова задается следующим образом. В накапливающий сумматор 15 загружается код Г состояния вй. При этом на выходе блока 2 памяти появляется координата ЧГ, т.е. указатель начала строки Р в блоках 3 и 4 памяти. На этом процесс загрузки исходных данныхзавершен. 55 РРп определяя значение координат г ,, гг ".ф 5 ф фф" р.+р,+р ф ,р,п-При этомЧ Ча +3Ч" Ч 3+ РюЭ ф 10Ч П- Ч п- +РИ-аВектор Ц загружается в блок 2 памяти. Вектор К загружается в блок 3 памяти, Вектор Т загружается в блок 4 памяти, причем в память заносятся значения 0, где 06 - числители дробей виде бМ 2Разрядность и число слов блоков 2-4 памяти определяется из следующих рассуждений. 20Число координат вектора Ч равно и. Числа координат вектора К и вектора Т зависят от средней длины (т.е. от числа элементов) 1 подстрок вида Р матРицы Р. ВектоР К(Т) содеР жит столько координат, сколько подстрок вида Р , можно выделить в матрице Р. Число подетрок определяется как п /1, где и - общее число элементов матрицы Р. 30Координаты и вектора Я принимают значения в диапазоне от О до п/1, Следовательно, разрядность блока 2 памяти, в котором хранится вектор Я, определяется как 1 1 оп/1 , гдеобозначает ближайшее целое в сторону увеличения.Координаты т вектора К принимают значения от О до п. Следовательно, разрядность блока 3 памяти, в кото ром хранится вектор К, определяетсякак1 о п Коордийаты 1 вектора Т имеют разрядность ш. Следовательно, суммарный объем памяти предлагаемого генера тора составляет Чи1 оя п,11 +2 п+ (103 п + ш) бит. Работа генератора сводится к реализации алгоритма управления, представленного на фиг.2. С приходом науправляющий вход генератора сигнала"Пуск" блок 16 управления переходитв состояние а и вырабатывает управляющие сигналы,Сигнал "Запись" поступает на синхронизирующий выход генератора, указывая, что на его информационном выходе установлено состояние зЕ. Приэтом в счетчик 1 записывается координата дй,поступающая с выхода блока 2 памяти. Изменение содержимогосчетчика 1 запускает процесс чтенияиз блоков 3 и 4 памяти, На выходе блока 3 памяти появляется координата гвектора К, т.е. значение длины подстрок Р , уменьшенное на единицу, аона выходе блока 4 памяти - значениесоответствующей координаты вектора Т,т.е. сумма видаР , где Ьо=оиндекс столбца правого элемента подостроки Р, Датчик 5 вырабатывает насвоем выходе некоторое случайное число х.После состояния а блок 16 управления переходит в состояние а и содержимое накапливаюшего сумматора 15 равно нулю.В зависимости от признака сравнения блок 16 управления переходит в состояние а 1 либо в состояние а+Допустим, что схема 6 сравнения выработала признак " ) ", т.е. случайное число х с выхода датчика 5 равномерно распределенных случайных чиИ сел больше, чем числоР сД:о выхода блока 4 памяти. Тогда блок 16 управления переходит в состояние а и выдает управляющие сигналы Вход 1и и11 3 на мультиплексор 12. Сложить на накапливающий сумматор 15 и "+1" вО счетчик 1, При этом число 1(Р )-1 с выхода блока 3 памяти передается на информационный вход накапливающего сумматора 15, сигнал "1" с выхода элемента ИЛИ 14 поступает на вход переноса накапливающего сумматора 15, в накапливающем сумматоре 15 выполняется операция сложения и его содержи мое становится равным (1(Р )-1) + 1о (Ф1(Р ) Ь +1 =и где Ь- инОф1 декс столбца левого, элемента подстроки,. следующей за подстрокой Р , т.е.индекс столбца левого элемента подстроки Р . Одновременно содержимоесчетчика 1 увеличивается на единицу.Изменение содержимого счетчика 1вновь запускает процесс чтения из бло 5ков 3 и 4 памяти, При этом на выходе блока Д памяти появляется очередная координата г вектора К, т.е. значение длины подстроки Р ,уменьшен Онс на единицу, а на выходе блока 4Ьпамяти - значение, Р, где Ь - :оиндекс столбца правого элемента подстроки Р. Схема 6 сравнения вырабатывает признак " Й " либоЕсли схема б сравнения вырабатыЬвает признак " ) " т.е. х );,К.Р0=о 3 и для подстроки Р, блок 6 управления вновь вырабатывает управляющиесигналы "Вход 1" на мультиплексор 12"Сложить" на накапливающий сумматор 15и "+1" на счетчик 1 (состояние а ).3При этом в накапливающем сумматоре 15записывается значение Ь + (1(Р )-1)+ +1 = Ь(Ь - индекс столбца левогоэлемента подстроки, следующей за подстрокой Р , т.е. индекс столбца левого элемента подстроки Р а содерзжимое счетчика 1 увеличивается на единицу. Изменение содержимого счетчика 1 вновь запускает процесс чтенияиз блсков 3 и 4 памяти и т.д.Если же схем.л 6 сравнения вырабаты вает признак "( ", блок 16 управления переходит в состояние а. Таким образом, к моменту, когда блок 16 управления переходит в состояние а,в накапливающем сумматоре 15 нахо1дится индекс Ь столбца левого зле 3мента первой подстроки Р для котоФ рой х .,У Р (Ь - индекс столбца:опервого элемента подстроки Р ), а на выходе блока 3 памяти - зйачение длины 1(Р" ) подстроки Р", , уменьшенной на единицу, т,е. значение (1(Р 6 )-1) 50В состоянии а блок 16 управления выдает управляющие сигналы "Запись" в регистр 7 сдвига и "Опрос" датчи"ков Ои 1 1 случайной двоичнойцифРыПри этом в регистр 7 сдвига с выхо 55 да блока 3 памяти записывается значение у1 (Р )-1, а датчики 10 и 11, независима друг от друга, вырабатывают на своих выходах равноявероятные двоичные цифры Р и Рр совответственно. Блок 6 управления пе-.реходит в состояние а.В состоянии аблок 16 управлениявыдает сигнал "Сложить" на накапливающий сумматор 15. К этому моментуна информационный вход накапливающего сумматора 15 через мультиплексор 12 (на управляющем входе мультиплексора 12 - сигнал "О") поступает код с выхода группы элементов И 8.. Если Р = О, указанный код нулевой,Если же Р = 1, на информационныйвход накапливающего сумматора 15 через элементы И группы элементов И 8и мультиплексор 12 подается код свыхода 7,1 старших разрядов регист-ра 7 сдвига, т,е. содержимое регистра 7, деленное на 2. Следовательно,на информационный вход накапливающего сумматора 15 поступает кодР (Уо /2 ),где) обозначает ближайшее целое в сторону уменьшения,Одновременно на вход переноса накапливающего сумматора 15 через элемент ИЛИ 14 поступает значение с выхода элемента И 9, Если Р = О, навход переноса, очевидно, поступаетзначение нуля, Если же Р = 1,на вход переноса накапливающего сумматора 15 через элемент И 9 и элемент ИЛИ 14 с выхода 7.2 подается значение младшего разряда регистра 7сдвига, т.е, остаток от делениясодержимого и регистра 7 на 2, Другими словами, на вход переноса накапливающего сумматора 15 поступает кодРо (у,шо 2),где шой в . знак операции вычисленияостатка от целочисленного деления. Таким образом, в результате опера" ции сложения содержимое А накапливающего сумматора 15 становится равнымо + О Е о 2)+Ро (Ъшой 2) э где А - предйдущее содержимое накапливающего сумматора 15, т.е.ицвоичная цифра на вйходе датчика О случайной двоичной цифры (у /2 ) - код, поступающий с выхода 7.1 регистра 7 сдвига; Р двоичн,я цифра на втором выходе дат" чика 11 случайной двоичной цифры; (ушоп 2) - значение младшего разряда с выхода 7.2 младшего разряда регистра 7 сдвига,1619262 1 О В зависимости от значения сигнала на выходе элемента ИЛИ-НЕ 3 после состояния а блок 16 управления переходит в состояние а либо в состоя 5 ние а(.Допустим, что на выходе элемента ИЛИ 14 присутствует сигнал "0". Спедовательно, хотя бы один из старших разрядов с выхода 7.1 регистр 7 сдвига отличен от нуля, т.е, Ус/22 Ф О. Блок )6 управления пере- ходит в состояние а и выдает управляющие сигналы "Сдвиг" на регистр 7 сдвига и "Опрос" датчиков 1 О и 11 равновероятной двоичной цифры. При этом в регистре 7 сдвига выполняется сдвиг и его содержимое становится равныму 1/2. На выходах датчиков 10 и 11 появляются случайные двоичные 20Вцифры Р( и Р соответственно. После состояния а 6 блок 17 управления вновь переходит в состояние ао и выдает управляющий сигнал "Сложить" на накапливающий сумматор 15. При этом содер И1 (Р ) -1 щ А; Ао 11 у ра ееВ состоянии а блок 16 управлениявыдает управляющие сигналы "Запись"в счетчик 1 и "Опрос" датчика 5.При 35 этом сигнал на синхронизирующем выходе генератора указывает, что на егоинформационном выходе получено очередное состояние з це и Маркова; всчетчике 1 запйсывается значение ко ординаты ( , поступающее с выхода блока 2 памяти, и начинается новый циклработы генератора. Таким образом, процесс порожде"45ния очередного состояния зрА цепи Маркова при текущем состоянии зЕ выполняется .в два этапа:первый - этап поиска в сжатой строке Р подстроки Р такой, что50 Ряке Рвторой - этап равномерной генерациисостояния зиз множества состоянийЯ ввз , ЬА) с 155 и т.д. до тех пор, пока все старшие разряды с выхода 7.1 регистра 7 сдвига станут равными нулю. При этом на выходе элемента ИЛИ 13 установится сигнал "1" и блок 16 управления перейдет в состояние а.К моменту перехода блока 16 управления в состояние а в накапливающем сумматоре 15 будет зафиксировано случайное число о+.22где Ао = Ьо ( 5 о П 3) + о (уо шок(а 2) ++ Рк 1(У, ш 12)Из способа получения числа 2 следует, что 0 62 уо и причем закон распределения случайного числа 2 является равномерным.Очевидно, число Атакже является случайным и равномерным распределено в диапазоне Ь(Ь у .ЦСлучайное число Я, Я = А 1, является кодом следующего состояния цепи Маркова. жимое накапливающего сумматора 15 становится равным1АЕ . А, + Р, (у,/2 ) а Р (у, юоо 2), где А - предыдущее содержимоенакапливающего сумматора 15;(у,/2) - код, поступаюиий с вюкоИда 7,1 регистра 7 сдвига;Р (Р ) - двоичная цифра на выходе датчика 10 (11);(ушо(12) - значение младшего разряда регистра 7 сдвига.Если на выходе элемента ИЛИ 13 присутствует сигнал "0", т.е, хотя бы один из разрядов выхода 7. регистра 7 сдвига отличен от нуля, блок 16 управления вновь переходит в состояние а(аТаким образом, смена состояний а - а блока 16 управления обеспечивает формирование в регистре 7 сдвига и в накапливающем сумматоре 15 следующих значений;(Выполнение первого этапа обеспечи- .вается сменой состояний аралуазуа выполнение второго, этапа - сменойсостояний а 4,аз,аблока 16 управления.Формула изобретения1Генератор случайного марковского процесса, содержащий блок управления, три блока памяти, счетчик, схему сравнения, датчик равномерно распределенных случайных чисел и датчик случайной двоичной цифры, причем вход пуска генератора является входом пуска блока управления, первый выход которого является синхронизирующим выходом генератора и соединен с входом записи счетчика, выход которого соединен с адресными входами первого и второго блоков памяти, выход первого блока памяти соединен с первым информационным входом схемы сравнения, выход которой соединен с первым входом задания логически: условий блока управления, второй выход которого соединен с входом опроса датчика равномерно распределенного ) случайного числа, выходкоторого соеди-, нен с вторым информационным входом схемы сравнения, третий выход блока управления соединен со счетным входом счетчика, информационный вход которого соединен с выходом третьего блока памяти, четвертый выход блока управления соединен с входом опррса датчика случайной двоичной цифры, о т л и ч а ю щ и й с я тем, что, с целью повышения точности формирования случайного марковского процесса, в него введены второй датчик случайной двоичной цифры, регистр сдвига, два элемента ИЛИ, блок элементов И, мультиплексор, элемент И и накапливающий сумматор, причем выход второго блока памяти соединен с.первым инфюрмационным входом мультиплексора и с информационным входом регистрасдвига, вход записи которого соединен с пятым выходом блока управления, шестой выход которого соединенс входом сдвига регистра сдвига, выход старших разрядов которого соединен с информационным входом блокаэлементов И и с входами первого элемента ИЛИ, инверсный выход которогосоединен с вторым входом задания логических условий блока управления, четвертый выход которого соединен с входом опроса второго датчика случайнойдвоичной цифры, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходоммладшего разряда регистра сдвига, выход первого датчика случайной двоич 2 О ной цифры соединен с управляющим входом блока элементов И, выход которогосоединен с вторым информационнымвходом мультиплексора, выход которогосоединен с первым информационным вхо 25 дом накапливающего сумматора, второйинформационный вход которого соединенс выходом второго элемента ИЛИ,седьмой выход блока управления соединен с входом записи накапливающегосумматора, вход разрешения сложения.которого соединен с восьмым выходомблока управления, девятый выход кото.рого соединен с управляющим входоммультиплексора и первым входом второгоэлемента ИЛИ, второй вход которого соединен с выходом элемента И выходнакапливающего сумматора является информационным выходом генератора и соединен с адресным входом третьего блока памяти,69262 ксон ставитель Д.фхред М.Дидик Редак Мотыль Корректор Н Ревска одственно-издательский комбинат "Патент", г. Ужгород, ул, 1 агарина, 1 О Заказ 48ВНИИПИ Госуда Тиражвенного комитета по113035, Москва, Жбретени аушская Подписноеи открытиям при ГКНТ СССРб., д. 4/5