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

СОЮЗ СОВЕТСНИКСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК аоС 06 7/58 ОПИСАНИЕ ИЗОБРЕТЕНИ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ Н А ИТОРСНОМУ СВИДЕТЕЛЬСТ(71) Кишиневский политехнический институт им, С. Лазо(56) Авторское свидетельство СССРР 1051538, кл. С 06 Р 7/58, 1982.Авторское свидетельство СССРВ 1070548, кл, С 06 Р 7/58, 1982,(54) ГЕНЕРАТОР СЛУЧАЙНОГО 11 АРКОВСКОГО ПРОЦЕССА(57) Изобретение относится к областиавтоматики и вычислительной техникии может использоваться для генерациивходных последовательностей при стохастическом контроле дискретныхобъектов. Цель изобретения - упрощение генератора. Генератор содержитблок 1 управления, выходной регистр2 памяти, датчик 3 равномерно распределенных случайных чисел, группу бло.ЯО 278842 Аков преобразователей 5 код-вероят ность. Вместе с очередным тактовымсигналом блока 1 управления датчик3 вырабатывает 1 ш-разрядных случайных чисел, поступающих на вторыевходы преобразователей 5. Номер текущего состояния марковского процесса поступает с выхода регистрана группы адресных входов всех блоков 4 памяти, Из блока 4.1 считывается код вероятности первого битаномера нового состояния процесса ипоступает на первую группу входовпреобразователя 5,2, на выходе которого Формируется значение этого бита, которое поступает на адресныевходы блоков 4.24.1 с памяти, Кодвероятности второго бита поступаетс выхода блока 4,2 памяти на группувходов преобразователя 5,2 и т.дПроцесс продолжается асинхронно, последовательно, поразрядно и завершается после формирования 1-го битазаписью номера нового состояния врегистр 2. 1 з.п. ф-лы, 4 ил. 3 табл278842 НаГ Отд г,Ф Состаивтель А. КарасовТехред В.Кадар Корректор И. Муска Гратилло едакто аказ 68394 д. 4/5 наб. Производственно-полиграйическое предприятие, г. Ужгород, ул, Проектная, 4 Тираж 671 ВНИИИ Государственного коми по делам изобретений и отк 113035, Москва, Ж, РаушскаяИзобретение относится к области автоматики и вычислительной техники и может быть использовано Для моделирования однородных марковских процессов а такке в качестве се)еецасе)- зцровянного стохастического генератора тестовых последовательностей команд и операндов в составе систем стохастического ФункциоеадьеОго контроля диск 1)етпых обьектов, включая микропроцессорные,Цель изобретения - упрощение генератора,На фиг.изображена структурнаясхема генератора случайного маркозского процесса; на Аиг. 2 - структур-.НЯ 51 схРма пРРООРс 1:-) 023 атР ПЯ КО)Е еРОят)ость; еа Ее)НГ, 3 - э)естр)1 че "е;аясхема генератора случайс)го лЯре 13 ск 010 роцесса;, на 1)1 г, 4 - элс;трическая схема преобразозателя код-веРОЯТНОСТЬ,Генератор случайного марковскогопроцесса содержит блок 1 сцехроеизацци, регистр 2 памяти, датчик 3равнолеерпо распределенных случайньгхчисел группу блоков 4.1,4.1 спамяти, группу преобразозателей 5,1,Эо 1 о о о о 5 ЭоС КОД 1)вр 0511 НОС,Тьо1(ажды Преобразовате.ь э коп-вРОЯ )ЕЕОСТ 23 ГРУПЬЕ -) о 1о о о), 1 С (С 15" о 2)соеее 1" 11 сумматор Б ц эпе 1)ет 1 ц)11 7.ЕНСРс 1 ТОР СЛУ)ЯЕ)ОГО 1 ЯРКОВСКОГОпроцесса, меющего вос.емь состояний,может быгь изготовлен по схемам, при.ВЕДРННЫМ На фИГо 3 - 5.БЛОК 1 СИНХ 130 Е 1 ИЗсоЦИ)1 1)ЕЕГ о 3) СОдержит генератор 8 тактовггх импульсов, счетный триггер 9, элементы И10 и 11,/сТчце 3 равномерно распределенньгх случайных чисел сс)дер)кит регистр 12 сдвига с цегьес) обратноц св)язи, сформированной путем е)е Ес 1 леееИ 51 логической операции ИСК;11 Е 1 Я.Щ 151", ).111 над его 13-м и 31-и разрядами прц помощи элемента 13 11 СИПОЧЛ 1(21 ЦЕГ 111 г 1, выход которого соединен с ие 11)ормационным входом первого разряда регистра 12 сдвига.Генератор работает с,едуеощ"м образом.Пусть заДае ма 131 сопсквй процесс р описываемый конечным мно)кеством состояний Б = 1 Б;, 3. = О, и - 1 и стохастической матрипей переходон РР (, 1 де Р;р - вероятность перр)ЬХОДЯ Зс 1 ОДИН ТЯКТ ИЗ СОСТОЯ)Е 151 Б) О-)и сос.тояпце Б 1 1 =.О иц 2 Р, =г- 11 ссаждолеу еостсянию Б" .:6 е Марковас)яв)гся в соогт;егс ПИР 1(-)с)зр 5 деоедвоичное ИсгО 1 ное) сОстояния (Ь оо Ьо) 2. ЬЯ )О 1 Ь - СТЯР -15 и разряд числа 1 из чисповой последовательности 0,1,2п. 1 созп- честно разрядов (бит), необходимоедгя представления каждого из номеровсостояний Б .Бцепи Маркова,)оя и,Вьходеой рег:.:стр 2 памятц имео 15 1)1 е 11 раз)5)дОВ пе)ецнязееяс)е 1 дг)5)хр яп е и ия и Оме 1) а т е куще Г О с О ст О я 11 ияцепи Маркова, 5 голл)оЕегос)1 однов;)емеппо адресом 511 РЕкц с)лока 4,1 памяти истаршей частью адреса ячеек бло сов2 О 42, о о о,4 о 1 С ПЯМ 52 ГИ, 1 ЕОбХОДИМ 010 ДЛЯ11)оер 15 оваеп 5 Номера случайного состояния цепи Маркова. 1 оличество преобразователей 5 код-вероятность, негобходимое для псс гроения генератора,25 ,)я 3 о 1 с,Марковский процесс следует рассмаьривять как поспело)ательност. ресаЛИЗЯЕГй) С)УЧайНЫХ ЗЯВИСНМЫХ СЛОКНЫХсобытйй переходо:3 в одЕО из состоя 3)" )1)пий Б 1 -.:О 13-1 цз с стояния Бс:1"0 е с)1) Окой ), РР1 Ят)ццы2 евеходс 23 1: о ФОР)Г Оо)Я 1 Пе номеРЯ слсе)ующего состояния может осуществляться георазряд 10 и тогда упомянутое 35сложное собьггце может быть ирецставлОБО кяк совокупность элРм)ентяе)ньхс)отбытий: )2)ориро)ание значения каждо 10 рсзряда Ь).) )омсрс (1) Ьо ро оЬ ) следующего события Б в зависимости как от номера текущего события,ЬЕ оЬ 5 5 оо оЬо 1 Я 1 1 От РЕЯЛИЗЯЦИИслучайного процесса фор)серо)яни 51 значс)ицй всех рязряцов (Ь Ь; ),предше туесше)сх (2+1) -му разряду. 11 ЯПравлене: еоразрядного с)ормиро)данияот старшего разряда Ь, к Спадшему Ь,Хак как старший разряд Ь, не имеет11)едшест 3 ую)его разряда ,2 я пегодвойная зависимость выражается в одиночную (только ог номера 3. текущегосо с 1 ОЯни 5 Б 1 )При перехода к упомянутьгм элементарпем событиям необходеЬЕО с гохстц ческую матрицу переходов Р прсобразо 2)ать 13 стохастиЕесесую лестрецу Лзеячений условных вероятностей цо 5113 лени 51 3101 ис)ессои 1 в )сзг)яттеЬ , еОмера СОстояееея Бо в зявиси 1278842держит 3 допол/ттет 3:/ьтх а(гресных Входов, подк)О/ен/ьгх и выходам ере образователей 5.1. 5 код-вероЯТТ 100: Ь и 7 Т ПОМОКГ /(ОТРЬСХ (тИТу аО 1 С 5 ТРКУНИР ЗгсаЧРНПЯ аз 75 ДОВ )7,1)(с 01)/ируРмого ггмера состояния 8(7,у/1 ЛЯ обеспе т"е/и 5 вЯгбоРл Ячеек бло(ОБ 424( плмяти, сорт/етству)сщих номеру столбц матритт/ы А, групт 3 Ы СТ 17/ц( лт 7 СС//СХ УЗХО(03 ссгосг 5 Н)7- ТЫХ бт от)ГТ Иамстн СОЕтГИПЕсЬ с.ТНО 1 ьгенц 1 с 1 мтг )азт)ядами мс)кд",у собоЙ и пОДКЛ 1051 Е 1 ЕЯ ( СООТВЕ 1 СВсОЩГ )с ЗРЯдсэ(Г тьЕксОдс .Ы 7(С;. ПО ГО Т) Сс Г С 1 Т Л 2 П амя 1 И 158 срттРТгстс 5(РЕНТСсТ сЭ, ( мл трт:цыс/77 - 0 . (.,773 УОтуз тс Ол 3)Я,7 ОБ 7(77((517 а;3 7751 71 л (" гт(Рлс 13 Р 7(151771с.сттг цотт317101 СЯ ЬТЯ зстпСИ 3/а "ТЕ 1175 Ос, с с 77 стз"(СрЯ 71 Ы т(отрс1 О (.,7(БТ(/уТЫ Б;(ТОВО Са ОСТИН,).)г(.Сра зря т (//(Оэ та (у 3 ил ./етгия -,-- умножаОТ П и с,у )55 аНТЕ Э.ГОИ Ч,ТСТИ кода поступает на первую группу вхо- ДОВ Тй-РаЗР 5 ЦГОГО ДтОИЧЦОГО СУММатО- ра 6 преобразователя 5 код-вероятность, 15 я кодирс)ания значения вероЯТНОСТЕй С 7, ЯЧЕйкн бЛОКОБ 1.1(Т,тс(гспамяти дтол)(нь содержать тг+1 разрядов. В табл. 3 представлены значения чепрех разря)пых кодов пероятностей с(7 полученных в результате кодирова- (77иия содержимого табл. 2.ЕСЛГ,цЛ 5 тТОСтр 7 Етня бЛОКОВ А,14,1( памяти используются интегр альИе с)(еьь Г/па 1(1551".(2 тО приведецные в таб,1, 3 зцачеция ко- дОВ ЕОбХОДИМО ПрртиВЕртнрОВать ПЕРЕД ЗаПИСЬЮ Б т/сЕ Ц(И, Так КаК БЫХОт, - Ной Каска/Т Э 1 ИХ И ТРТ" 7)аЛЬ)НЫХ СХЕМ 51 Б- ляется иггтзертттру(Оццг 1 ладя(еьу праБОГ 7 1723 сс:с/.ТУ КО 7:(7. БЕ;70 Г 1 ИОСТ СООТ- ветствует С 1 ука,3. нс.й итттегт)атьгой схемы,3) Нагсс.ГЬ Ный М(7 с Р Нт Б Т) ЕМЕ Т 5 ЦСприхода иррного трактующего сигналаот бло;л 1) тригт"р с для о(7, ецслен/10 С/1 1 с) )ДТС Я В 1 сстЕЦОМ СОСОЯТ 1",1 и регистр 1 дат гика 3 равномерно рас- ТРЕДЕЛЕНЬХ С;Уса йЦ ГХ стЦСЕЛ - Г п 1)от 31 оп)ном сОс.7 ряепи) БыходнОи т)е 15 стт) 2 ттасгятп для (предетРнностн Ц Ц 75/РУЗОМ (". 0",70,Н:ЦИ,ЕЕ)сну)а 107 8 БЬ 1)сба ТЫВаЕТ Па Свс)- ем выхсве непрерь Бную последс)ватель 710 СТЬ СИГЦБ)ГОП Со СКЗа)КНССТГЫО ДВат(ртс)рьгн ттпербт)а РуО с я . (тва ств.(ян ссз ьп(ПоЛЗС Сстссс)та СР С(1 а)(Т(ОСТЬ 7 ЧЕ 77( Г (с 577. Рсс сс с 57 7 ( Гос, ттгГ 17 1(тс/Гу; Э-.Ь;С с тса Ьс 0 тг1 . 1 Т)Ебт)Г)эдаса(СТТЕ Р(. у 77(: (337 тяп тОС Р Г 1 И .0 ОГ Г ЧР ТНОГО тцИГЕ)а ) Обвсгеттс)7(сГ;ЕГО КОМГУУтс 77/ссО т(ажгГСстР С с" с: РЕ Ц/ЕС) О ссГЦаЛа генератора 8 на Один пз выходов б:10- ка 1,.,Ига,у с первого выхода блокаГ 7357 уЕТ рабртс) Да ЧИТ:,а 3 раВНОМРрн раст гс)Р 57,(ГТ(5/тнь)7( стцесе ч, 1 т)31 этс,т; ретпст) 12 ге 1/ератора 11 с,Осл(довагР Бис С Сс:;"т Г)суТСЕСТ 5 Л(СЕ 7 КОЛЬИСБОй,Гсцн (гсс(с)ОрМ.1/с(у 1 7 Тут)с с(71 И с нсп. ССС.Жу 3 атРГ/17 ТГС 1 13 ГО и с10 раэ- )цов указаИого регистра выполняется логтст( с(а Я Опетация СК 11(Ч/1011,Е 1 И при огсэт;,и элемента 13 резульа 1 3 ПИ 7 БЕЕ.,5. В ПЕ) БЬИ Ь) а э ПЯД регистра 12Сигнал с второго выхода блока управления осуществляет запись номера следуОщего состояния 87, сд)ормировацного поразряно на выходах пре 1278842образователей 5 код-вероятность в выходной регистр 2 памяти. Один такт работы устройства состоит из двух тактов генератора 8 тактирующих сигНалов, 5Пусть в некоторый момент времени выходной регистр 2 памяти содержит номер (Ь Ь Ь ), т.е, моделируемый.процесс находится в состоянии Б;. 11 ри выходе из блока 1 управления 1 О очередного тактирующего сигнала датчик 3 равномерно распределенных случайных чисел вырабатывает на группах 1.21 с выходовш-разрядных чисел (в примере - три трехразрядных числа) . Значение вероятности каждого числа равно 2 , Каждое из указанных случайных чисел поступает через соответствующие вторые группы входов преобразователей 5.1. 5.1 с на вторые 20 группы входов ш-разрядных сумматоров б.Номер (ЬЬгЬ) состояния Б; поступает на соответствующие адресные входы всех блоков 4.14,1 с25 памяти, обеспечивая конкретизацию условия выборки номера столбца матрицы 1 . При этом из блока 4.1 памяти происходит считывание ячейки, определяемой номером состояния Б;, со держимое которой является кодом вероятности 2 Ю+ ,; появления логической "1" в разряде Ь, номера следующего состояния Б,Если элемент , указанного кода вероятности равен логической "1", то на выходе преобразователя 5,1 код-вероятность произойдет установка логической "1" с вероятностью достоверного события д, =1, обеспечиваемое40 логическим элементом ИЛИ 7, независимо от состояния выхода переноса сумматора 6. В противном случае, когдаО, сумматор 6 осуществляет ариф 45 метическое сложение значения с тп-.разрядным двоичном числом и на выходе переноса сумматора 6 появляется значение разряда Ь, с вероятностью появления логической "1" "-, которое2 50 через логический элемент ИЛИ .7 поступаетна выход преобразователя 5.1 код-вероятность, Таким образом, обеспечивается Формирование значения разряда Ь номера состояния Б с вероят ностью появления логической "1", лежащей в диапазоне 01 включительно. Использование известного преобразователя код-вероятность, состоящего только из сумматора, не позволяет перекрыть указанный диапазон значений вероятности логической "1", так как при этом максимальная величинавероятности ограничена значением Щс - 1--с 1,2По окончании формирования полученное значение разряда Ь поступает на соответствующие адресные входы всех следующих блоков 4.24,1 с памяти, что обеспечивает конкретизацию дополнительного условия выборки адресов ячеек этих блоков в зависимости от конкретного значения разряда Ь . Эти условия становятся полностью определенными только для блока 4.2 памяти, у которого имеется всего один дополнительный адресный вход условия реализации значения т предшествующего разряда Ь . Из блока 4.2 памяти происходит считывание ячейки, определенной номером состояния Б; и сформированным стохастическим значением разряда Ь, содержимое которой является кодом условной вероятности 2 + г, появления логической "1" в разряде Ь номера состогяния Б. Код вероятности поступает на первую группу входов преобразо-вателя 5,2 код-вероятность, который осуществляет стохастическое Формирование значения разряда Ь номера сосгтояния Б. Процесс формирования значения разряда Ь аналогичен изложенгному процессу формирования значения разряда Ь.Таким образом, процесс,формирования номера состояния развивается последовательно по направлению от старшего разряда Ь к младшему Ь асинхронно, так как время установки значения каждого разряда Ьц зависит только от времени чтения блоков 4,1 4.14.) памяти и задержки преобразователей 5.15,1 с код-вероятность соответствующих предшествующих разрядов ЬЬ, При этом на первую группу входов преобразователя 5,1 с код-вероятность поступает код вероятности появления логической "1" в разряде Ь, считываемой иэ ячейки блока 4.1 с памяти, адрес которого определен номером состояния Б; и сформированными значениями всех предшествующих разрядов ЬЬ, номера состояния Б. На выходе преобразователя 51 с код-вероятность ус 1278842танавлиттяется стохасттгческое зцачецие разряда ЬСформиронаццое значеццс Номера (Ь, т,Ь,) гт состояпия 8 ц записьгнается тга т,гтхотттгой т)е Гист") 2 пагъггтттг Яг)и ПОМОЩИ ТГ)ЯЕ(Т)ЕРУ 01 ЕГО СИГЦЯЛЯ т ПОСТУ- па 10 ще 10 с тт 01)ОГО блог(я 1 . 1 поступает на выход генератора, заперпая тц)ОЦЕСС ПЕРЯХОЦЯ МОЦЕЛИР Я;ОГО МЯР- к ОпскОГО гтр Оцес с) иЗ со стОЯИЯ 8Б 10 СОСТР 5 ТГЕЕт. 8 О С задавОй т)ЕГ)05 ТПОСТЬЮ Р . 11 о 5 утеггОе Зцачеция Номера (Ь т т т т т ) . ) П СОСТОгг 1 Гт;7 ПОС 7 утаР 7,ии Я Ягг,) ес пье нхо гтьг т) сеУ. блт) ко)3 4.1,4.1( памяти, обеспечивая под ГОТОНК)т ПярЕХСЬта ПрогтЕССЯ Б СЛЕдувщем такте из состояция 8, г, пекотороеА)состЯ)цге 8 т с БеРоятцос )ью Р/) ОПРЕДЕтпггя)ЕОтЯ ЦОБЬГ ЗтаЧЕЦИЕМ СЛУЧайпьх чисел, Егоступ;ющих с групп Бы 20ходов датчика 8 1)111 поперцо распреде.1(ЕП 1 ЫХ СЛУЧЯИНЫХ ЧттСЕГГ 1 т КО)10 тн 13(т 1)013г . 11тгостеге 1057 БГеп 15 т лог.яскт).нка)дом разрягте (Ь ,Ь счптываеГтХ И.з СООТБЕт.тСТБуО 1 т 1 Х;Етьт.етх 6 ЛОткон 254, 1, т 1( ПЯМЯТ 11 пв соотиествующиеУХОЕЕ) ПРСОбг)азова тт,)ЕИ Ь1 тэ т т Ь т(код Ве 1)05 ткость т 1 тц,1 ЯКЕг Обт)азомт Птт)оттскод)т Модятгиронаце случайпого марковского про- З 0цесся с коцеч 1 ьгг ислОм состояций Б,Суммарный объем памят группы блоКОБ 41 т э р ь ф 1( памя 1 И 1) кОтот)ые Записаны коды вероятностей соответсБУЮЩИЕ ),.1 тЕМЕПТЯМ Ма Т)И 51 тг тт - Зи (и) (и)-ь ) бит, )гбъ:ж матрг Но 1ЯМЯТГ В КОТОр 10 3 Пса 11)1 3)СМ(т 1 ТЫмат)ипы 1) прет,лтагае)т)ГО ,тст)01 сп)ЯптСОСТЯ)-:Л 5 СГ=. 2 П 10 т П. ПОЗ;ОМу6т ттП 1)и . - :; --суггьгарьеьггтг объем10 тт, и и+1блоков Йь,14.1( памяти т с тгНаба)ГтИЕ Зф 1)ЕКТ От ПрГЕПЕия ПРЕД 1 таГЯЕМОГО ГЕЦЕРатОРЯ СЛУЧайОГО ттЯРКОБСКС 1 О ПРОьтЕС Са тоо",т 1;.:-.1 Стт В СцтетЕтЯХ Стадаттза ЕГГ.) СТО)(;т С 1 цттпе; ттЬЕттафГРЕГЦВ ПЕ 1)СХОДОВ Зцатт ттцГЯ 1:Ет)оятностее пе 1)еходов т(07 орт.гх 1 еап Б птп- РтОКО г ЦЯПЯЗ СНЕ ЧИС Ет 1 а С 17 РСЗ КЯ (О 1) Т, Е, При СГКттътяОМ От;СОВЕНИ РЯСПР".т.а)ЕтЯ ВЕРОЛТПОСТЕй - .:, Ст ОкаХМатРЕГЦЫ ) О Г РЯВЦОЕЕРЦОГОт ТЯК, ЯП- рИЫРр Б т ттттттая КОГтта П = 10 И гп = 8, что соответствует процессу моделиронация потока случайпых микро- команд микропроцессора, относительное сокращецие объема памяти составляет тц, 2 10 Р.П7 Е (и - 1) (и+1)4 Г), так как гзависит от и показательно, а 11 - липейцо.Формула и 3 о б р е т е ц и я1, Генератор сгтучайцого марковского процесса, содерКащцй блок сицхроцизации, регистр памяти, датчик равцомерцо распределенцых случайцьх чисел, вход "Опрос" которого подключенк пе",)Бому Выходу блока синхт)онизяции второй вьг;од которого соедицепс синхропизируюг 11 и Бхоцом регистрапамяти, гыход которого является Выходом генератора, о т л и ч а ю -П и й с я темчто, с тгелью упрое-.ци)1 т Оц сот)якит ГРУппУ блоков па.мяти и группу преобразователей кодБероятпость, цьходы которых соедице 1 пп с Вьгходами соответстБующих ряз)51 ДОН РСГИС 1 тРОБ ИЯМ 517 И тВЬХОД КОТОРОго соедицец с пераыми адресцьМи Входами блокоц гтамяти группы, Быхоцыкоторыхосдинент с входами заданиявероятцостц соотн тстну апгих преобра-зователей код-вероятность группы,ипОргЯцггоцпые нхоцы которых подключецы к Выходам датчика ранцомерпора(.пределенпых случайных чисел соответстнец 10Быхзд )- го .преобразователя код Вероятностт: (1=1 т(=) 1(число блоков памяти в группе) соецицец с +1) - ым Яд песцым входом всехначиная с (1+1) -Го, блоков памяти.группы.2. Гецетрятор по и, 1,ч а и щ и й с я тем) что какдый греОораЗОвагтель коц .3 ерояОсть содсрж)т злемецт 11 Л и "ут матор нтход переноса которого с)ед тптец с первымБХО,ГОМ ЗЛЕМЕПТЯ )ЕДЕБТС)РОЙ ВХОД КОтОРОГО СОВ.ЕСГПО г. ПЕРВЫМ НХОЦОМ СУМ,МЯТ 01)с ЯБЛ 5 ЕТСЯ 11,)тБ 5 ЯЕПЦЕтМ ВХОДОМпреобразователя, ицфорггатт)Оцным входом которого является второй входсумматораньход .)Лемепта ИЛИ является Входом преобразователя.