Генератор случайного марковского процесса
Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных-объектов. Целью изобретения является повышение точности формирования случайного марковского процесса. Для достижения поставленной цели в генератор введены регистр 7 сдвига, группа элементов И 8, элемент И 9, второй датчик 11 случайной двоичной цифры, мультиплексор 12, элемент ИЛИ-НЕ 13, элемент ИЛИ 14, накапливающий сумматор 15. Очередное состояние марковского процесса вырабатывается путем сравнения случайных чисел, ваемых датчиком 5, с элементами модифицированной матрицы переходных вероятностей и генерацией равномерно распределенных чисел, полученных путем случайного половинного деления с помощью регистра 7 сдвига и датчиков 10 и 11. 2 ил. (Л
СОЮЗ СОБЕТСНИХ
СОЦИО ЛИСТ ИЧЕСНИХ
РЕСПУБЛИН.(51)5 С 06 F 7/58
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н А BTOPCKOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОЗНРЫТИЯМ
ПРИ ГКНТ СССР (21) 4642374/24 (22) 24 ° 01,89 (46) 07,01.91 Бюл. И 1 (» ) Кишиневский политехнический институт им. С.Лазо (72) А.А.Гремальский и С.N.Àíäðîíèê (53) 681.3(088.8) (56) Авторское свидетельство СССР
У 1453403, кл . С 06 F 7/58, 1987.
Авторское свидетельство СССР
ltd 1531093, кл. С 06 F 7/58, 1988. (54) ГЕНЕРАТОР СЛУЧАЙНОГО ИАРКОВСКОГО
ПРОЦЕССА (57) Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов.
„„SU„„1619262 A 1
Целью изобретения является повышение точности формирования случайного марковского процесса. Для достижения поставленной цели в генератор введе" ны регистр 7 сдвига, группа элементов И 8, элемент И 9, второй датчик 11 случайной двоичной цифры, мультиплексор 12; элемент ИЛИ-НЕ 13, элемент ИЛИ 14, накапливающий сумматор 15. Очередное состояние марковского процесса вырабатывается путем сравнения случайных чисел, вырабатываемых датчиком 5, с элементами модифицированной матрицы переходных вероятностей и генерацией. равномерно распределенных чисел, полученных пуе тем случайного половинного деления с помощью регистра 7 сдвига и датчиков 10 и 11. 2 ил.
1619262
Изобретение относится к автоматике и вычислительной технике и может использоваться для генерации входных последовательностей при стохастическом контроле дискретных объектов.
Цель изобретения — повышение точности формирования случайного марковФ ского процесса.
На фкг.1 представлена структурная схема генератора; на фиг.2 — блоксхема алгоритма работы блока управления.
Генератор случайного марковского процесса содержит счетчик 1, блоки
2- 4 памяти, датчик 5 равномерно распределенных случайных чисел, схему 6 сравнения, регистр 7 сдвига с выходами 7.1 старших раз-.ядов и 7.2 младшего разряда, блок 8 элементов И, элемент И 9, датчики 10 и 11 случайной двоичной цифры, мультиплексор 12, элементы ИЛИ !3 и ll4, накапливающий сум" матор 15 и блок 16 управления.
Счетчик 1 предназначен для хранения и формирования адреса, по.которому осуществляется обращение к блокам 3 и 4 памяти. Блоки 2-4 памяти предназначены для хранения в сжатой
1 форме стохастической матрицы переходов. Считывание информации из блс— ков 2-4 происходит при поступлении соответствующих адресов на их адресные входы.
Регистр 7 сдвига предназначен для
35 хранения и сдвига в сторону младшего разряда информации, поступающей на его информационный вход.
Накапливающий сумматор 15 предназначен для формирования и хранения 40 текущего состояния цепи. Кроме того, код текущего состояния цепи является адресом, по которому происходит обращение к блоку 2 памяти.
Блок 16 управления предназначен 45 для реализации алгоритма работы генератора и полностью определяется блок-схемой алгоритма, представленнои на фиг.2. Блок 16 управления представляет собой упрагляющий автомат с состояниями а,,а,...,а, структур которого получается в соответствии с методами синтеза.
В состоянии а блок 16 управления выдает; сигналы "Запись " в счетчик и "Опрос" датчи «а 5.
В состоянии а блок 16 управпения вь;дает сигнал "Сброс" на накапливающий сумматор 15.
В состоянии а блок 16 управления выдает сигналы "Вход 1" на мультиплексор 12; "Сложить" на накапливающий сумматор 15 и "+1" в счетчик 1.
В состоянии а блок 16 управления выдает .сигналы: Запись" в регистр 7 и "Опрос" датчиков 10 и 11. !
3 состоянии а блок 16 управления выдает сигнал "Сложить" на накапливающий сумматор 15.
В состоянии а блок 16 управления выдает сигналы: "Сдвиг" на регистр 7 и "Опрос" датчиков 10 и Il.
Генератор работает слецующим образом.
Пусть задан марковский процесс описываемый конечным множеством состояний S = (sIII i = О, и-1 и стохастической матрицей переходов Р = //P I// и хп, где р, — вероятность перехода за один такт из состояния s. в состояние s, i,g = О, п-1, р, =ф11 2 ", ф, — целое, m — - параметр, определяющий точность представления элементов стохастической матрицы переходов °
Матрица P хранится в сжатом виде в виде векторов Q = //(j //, R =
//r //, Т = //t //.
Векторы Q, R и Т получаются следующим образом. устанавливают q> = 0 Сжимают строку Ро матрицы Р. Для этого в строке выделяют подстроки Р, P о .Р из последовательно расположенных о друг за другом одинаковых элементов.
Для каждой подстроки Р вычисляется
К к о чиспо 1(Р ) входящих в нее элементов, о
Просматривая строку Р слева направо, в координаты г„,г,г ...,., Го э Г19 С Ф, ° ° ° Векторов R и т последовательно выписывают: координату г<— длину подстроки P, уменьшенную на
К о к единицу, т.е. величину 1(P )-1; в координату t< — сумму всех элементов строки Р от Р до PoI, т.е. величиО 00 ну . P, где h — ичдекс столбца
К послеДнего элемента подстроки Р, Пусть, при сжатии строки ? s R ь и Т были выписаны. по Р значении, где
Ь, — число подстрок в строке Ро .
Устанавливают q< Щ . А!.алогично строке Р сжимают строку Р и в вектоО рах R и Т выписывают соответствующие значения, Пусть, — число подстрок строки PI.
Устанавливают q = q< +P,. Аналогичным образом сжимают строки Р, 1619262
P>,....,Pn,, определяя значение координат r р г ..., ., г
tp. В, t tp При этом qy qz +Pz3 qq q3 + Ðóю ° ° ° ° ° ° ° ° ° ° ° т ф 10 ь-(Ч n- + и- Вектор Q загружается в блок 2 памяти. Вектор R загружается в блок 3 памяти, Вектор Т загружается в блок 4 памяти, причем в память заносятся значения 0, где 0(в — числители дробей виде t 2 Разрядность и число слов блоков 2-4 памяти определяется из следующих рассуждений. 20 Число координат вектора Ч равно и. Числа координат вектора R и вектора Т зависят от средней длины (т.е. от числа элементов) 1 подстрок вида р матрицы P. Вектор R(T) содержит столько координат, сколько подстрок вида P, можно выделить в матрице P. Число подетрок определяется как и /1, где n — общее число элементов матрицы P. 30 Координаты q вектора Q принимают значения в диапазоне от 0 до n /1. Следовательно, разрядность блока 2 памяти, в котором хранится вектор Q определяется как j logan /1, где ) 1 обозначает ближайшее целое в сторону увеличения. Координаты т вектора R принимают значения от 0 до п-2. Следовательно, разрядность блока 3 памяти, в кото- 40 ром хранится вектор R определяется как (log ï-1L . Коордийаты t вектора Т имеют разрядность ш. Следовательно, суммарный объем памяти предлагаемого генера- 45 тора составляет Ч и ° j log тР/1 (+ 2n + (J log n-1 Г + m) бит. Начальное состояние sf цепи Маркова задается следующим образом. В накапливающий сумматор 15 загружается код f состояния sf. При этом на выходе блока 2 памяти появляется координата qf, т.е. указатель начала строки Р< в блоках 3 и 4 памяти. На этом процесс загрузки исходных данных завершен. Работа генератора сводится к реализации алгоритма управления, представленного на фиг.2. С приходом на управляющий вход генератора сигнала "Пуск" блок 16 управления переходит в состояние а и вырабатывает управляющие сигналы, Сигнал "Запись" поступает на синхронизирующий выход генератора, указывая, что на его информационном выходе установлено состояние sf. При этом в счетчик 1 записывается координата gf,ïoñòóïàþùàÿ.. с выхода блока 2 памяти. Изменение содержимого счетчика 1 запускает процесс чтения из блоков 3 и 4 памяти. На выходе блока 3 памяти появляется координата r вектора К, т.е. значение длины подстрок P, уменьшенное на единицу, а о на выходе блока 4 памяти — значение соответствующей координаты вектора Т, h т. е. сумма вида P где ho У )=о индекс столбца правого элемента подо строки Р . Датчик 5 вырабатывает на своем выходе некоторое случайное число х. После состояния а< блок 16 управления переходит в состояние а и содержимое накапливаюшего сумматора 15 равно нулю. В зависимости от признака сравнения блок 16 управления переходит в состояние а либо в состояние а+ Допустим, что схема 6 сравнения выработала признак " ) ", т.е. случайное число х с выхода датчика 5 равномерно распределенных случайных чиh сел больше, чем число Р с =о выхода блока 4 памяти. Тогда блок 16 управления переходит в состояние а и выдает управляющие сигналы Вход 1 и и ! 11 3I на мультиплексор 12. Сложить на накапливающий сумматор 15 и "+1 " в о счетчик 1, При этом число 1(Р )-1 с выхода блока 3 памяти передается на информационный вход накапливающего сумматора 15, сигнал "1" с выхода элемента ИЛИ 14 поступает на вход переноса накапливающего сумматора 15, в накапливающем сумматоре 15 выполняется операция сложения и его содержи мое становится равным (1(Р )-1) + ) о т !(1(Р ) h +1 = и где h — инО 1 Э 1 декс столбца левого, элемента подстроки,. следующей за подстрокой Р, т,е. 1619262 индекс столбца левого элемента подl строки P . Одновременно содержимое счетчика 1 увеличивается на единицу. Изменение содержимого счетчика 1 вновь запускает процесс чтения из бло5 ков 3 и 4 памяти. При этом на выходе блока 3 памяти появляется очередная координата r вектора R т.е. знаt чение длины подстроки Р, уменьшен- 1 нсэ на единицу, а на выходе блока 4 hi памяти — значение,0 Р, где h !)=o индекс столбца правого элемента под,1 строки Р„ . Схема 6 сравнения выраба 15 тывает признак "Й" либо ">", Если схема 6 сравнения вырабатыh1 вает признак " ) " т.е. х ),".Я Р 3=0 3 и для подстроки Р блок !6 управле- 20 ния вновь вырабатывает управляющие сигналы "Вход 1" на мультиплексор 12 "Сложить" на накапливающий сумматор 15 и "+1" на счетчик 1 (состояние а ). При этом в накапливающем сумматоре 15 записывается значение Ь + (1(P )- I )+ +1 = h (h< - индекс столбца левого элемента подстроки, следующей за подстрокой Р, т. е. индекс столбца левого элемента подстроки Р а содер- 0 э жимое счетчика 1 увеличивается на единицу. Изменение содержимого счетчика 1 вновь запускает процесс чтения из блсков 3 и 4 памяти и т.д. Если же схем.л 6 сравнения вырабаты-15 вает признак "«(", блок 16 управления переходит в состояние а!. Таким образом, к моменту, когда блок 16 управления переходит в состояние а, в накапливающем сумматоре !5 нахо- 40 1( дится индекс h столбца левого зле3 мента первой подстроки Р для котоФ h) рой х,>Р (Ь - индекс столбца 45 о у первого элемента подстроки Р ), а на выходе блока 3 памяти — зйачение длины 1(Р ) подстроки P,, умень1 шенной на единицу, т.е. значение (1(Р 6 )-1) 50 В состоянии а блок 16 управления выдает управляющие сигналы "Запись" в регистр 7 сдвига и "Опрос" датчи" ков !Ои 1 1 случайной двоичной цифры При этом в регистр 7 сдвига с выха55 да блока 3 памяти записывается значение у 1 (P )-1, а датчики 10 и 11, независима друг ат друга, вырабатывают на своих выходах равно(
f . Если Р, = О, указанный код нулевой, Если же Р0 = 1, на информационный вход накапливающего сумматора 15 через элементы И группы элементов И 8 и мультиплексор 12 подается код с выхода 7.1 старших разрядов регист- ра 7 сдвига, т,е. содержимое регистра 7, деленное на 2. Следовательно, на информационный вход накапливающего сумматора 15 поступает код Р ((у0/2)),где P ) обозначает ближайшее целое в сторону уменьшения. Одновременно на вход переноса накапливающего сумматора 15 через элемент ИЛИ 14 поступает значение с выхода элемента И 9. Если Р = О, на вход переноса, очевидно, поступает fi значение нуля, Если же P0 = 1, на вход переноса накапливающего сумматора 15 через элемент И 9 и элемент ИЛИ 14 с выхода 7.2 подается значение младшего разряда регистра 7 сдвига, т.е. остаток от деления содержимого и регистра 7 на 2. Другими словами, на вход переноса накапливающего сумматора 15 поступает код Р (y nod2} где mod †. знак операции вычисления остатка от целочисленного деления. Таким образом, в результате опера" ции сложения содержимое А накаплиC вающего сумматора 15 становится равным (о + PÎ Е ь/2 )+Ро(y шой2}, где А — предйдущее содержимое накапливающего сумматора 15, =.е. и А = h, Р - двоичная цифра на вйходе дат:ика !О случайной двоичной цифры; (у /2 ) - код, поступающий с выхода 7.1 регистра 7 сдвига, Р двоичн. я цифра на втором выходе дат" чика ll случайной двоичной цифры; (у©mod2} — значение младшего разряда с выхода 7.2 младшего разряда регистра 7 сдвига. 1619262 В зависимости от значения сигнала I на выходе элемента HJIH-НЕ 13 после состояния ао блок 16 управления переходит в состояние а либо в состоя5 ние а!. Допустим, что на выходе элемента ИЛИ 14 присутствует сигнал "0". Следовательно, хотя бы один из старших разрядов с выхода 7.1 регистр 7 сдвига отличен от нуля, т.е. (yg/2/ d й. Блок 16 управления пере- ходит в состояние а и выдает управляющие сигналы "Сдвиг" на регистр 7 сдвига и "Опрос" датчиков 10 и 11 рав-15 новероятной двоичной цифры. При этом в регистре 7 сдвига выполняется сдвиг и его содержимое становится равным 1 у/2 . На выходах датчиков 10 и ll появляются случайные двоичные 20 < !! цифры Р1 и Р> соответственно. После состояния а6 блок 17 управления вновь переходит в состояние а и выдает управляющий сигнал "Сложить" на накапливающий сумматор 15. При этом содер- 25 7 il 1 (Pg )-1 = А; Ao р ((уо/21)» А(= Aî + Po ((Уо 21 ) + î (yоmod2); ° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° (I y - /2J ); Aê= Aê + Pk,{(y„, 2J ) + Р,", (у, >mod2) у у вл I а ее ° ° у В состоянии ау блок 16 управления выдает управляющие сигналы "Запись" в счетчик 1 и "Опрос" датчика 5.При 35 этом сигнал на синхронизирующем выходе генератора указывает, что на его информационном выходе получено очередное состояние з цепи Маркова; в счетчике I запйсывается значение ко40 ординаты и, поступающее с выхода блока 2 памяти, и начинается новый цикл работы генератора. Таким образом, процесс порожде" 45 ния очередного состояния s цепи Маркова при текущем состоянии sf выполняется .в два этапа: первый — этап поиска в сжатой строке Ру подстроки Р такой, что 50 р1 оке р1 второй — этап равномерной генерации состояния s< из множества состояний }1 а й1 а 11 „. 55 и т.д. до тех пор, пока все старшие разряды с выхода 7.1 регистра 7 сдвига станут равными нулю. При этом на выходе элемента ИЛИ 13 установится сигнал "1" и блок 16 управления перейдет в состояние а<. К моменту перехода блока 16 управления в состояние а1 в накапливающем сумматоре 15 будет зафиксировано случайное число Ав = А +.Zs Ф где Ао = Ь, - Po ((уо 2g) + Pî (yc mod2) + + ° ° ° + Р к- (1ук-г Й3 ) + + Р"к-а(ук-а mod2) + Р к- ((ук-<П3)+ + Рк-1 (у„mod2) ° Из способа получения числа Z следует, что 0 < Z < yо и причем закон распределения случайного числа Z является равномерным. Очевидно, число A также является случайным и равномерным распределено в диапазоне hg,...,h II . Ц Случайное число Я, Я = А 1, является кодом следующего состояния цепи Маркова. жимое накапливающего сумматора 15 становится равным t р А А, + py ((yq/2) ) а у (у, mod2), где А I — предыдущее содержимое накапливающего сумматора 15; (jy,/2)) — код, поступаюиий с вюкоИ да 7.1 регистра 7 сдвига; P (Р ) — двоичная цифра на выхо1 1 де датчика 10 (11)(y Если на выходе элемента ИЛИ )3 присутствует сигнал "0", т е хотя бы один из разрядов выхода 7.1 регистра 7 сдвига отличен от нуля, блок 16 управления вновь переходит в состояHHQ а ° а и т д Таким образом, смена состояний а <- а блока 16 управления обеспечивает формирование в регистре 7 сдвига и в накапливающем сумматоре 15 следующих значений: (Выполнение первого этапа обеспечи- . вается сменой состояний а,а,а» а выполнение второго, этапа — сменой состояний а,а,а < блока 16 управления. 1619262 Формула изобретения Генератор случайного марковского процесса, содержащий блок управления, три блока памяти, счетчик, схему сравнения, датчик равномерно распределенных случайных чисел и датчик случайной двоичной цифры, причем вход „пуска генератора является входом пуска блока управления, первый выход которого является синхронизирующим выходом генератора и соединен с входом записи счетчика, выход которого соединен с адресными входами первого и второго блоков памяти, выход первого блока памяти со.единен с первым информационным входом схемы сравнения, выход которой соединен с первым входом задания логически..: условий блока управления, второй выход которого соединен с входом опроса датчика равномерно распределенного ) случайного числа, выход которого соеди-, нен с вторым информационным входом схемы сравнения, третий выход блока управления соединен со счетным входом счетчика, информационный вход которого соединен с выходом третьего блока памяти, четвертый выход блока управления соединен с входом опррса датчика случайной двоичной цифры, отличающийся тем, что, с целью повышения точности формирования случайного марковского процесса, в него введены второй датчик случайной двоичной цифры, регистр сдвига, два элемента ИЛИ, блок элементов И, мультиплексор, элемент И и накапливающий сумматор, причем выход второго блока памяти соединен с.первым инфюрмационным входом мультиплексора и с информационным входом регистра сдвига, вход записи которого соединен с пятым выходом блока управления, шестой выход которого соединен с входом сдвига регистра сдвига, выход старших разрядов которого соединен с информационным входом блока элементов И и с входами первого элемента ИЛИ, инверсный выход которого соединен с вторым входом задания логических условий блока управления, четвертый выход которого соединен с входом опроса второго датчика случайной двоичной цифры, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом младшего разряда регистра сдвига, выход первого датчика случайной двоич2О ной цифры соединен с управляющим входом блока элементов И, выход которого соединен с вторым информационным входом мультиплексора, выход которого соединен с первым информационным входом накапливающего сумматора, второй информационный вход которого соединен с выходом второго элемента ИЛИ, седьмой выход блока управления соединен с входом записи накапливающего сумматора, вход разрешения сложения. которого соединен с восьмым выходом блока управления, девятый выход которого соединен с управляющим входом мультиплексора и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом элемента И„ выход накапливающего сумматора является информационным выходом генератора и соединен с адресным входом третьего блока памяти, 1619262 Составитель Д.Феликсон Техред М.Дидик Корректор Н.Ревская Редактор А.Мотыль Заказ 48 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5! 1роиэводственно-иэдателы кий комбинат "Патент", г. Ужгород, ул, 1 агарияа, 101
