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

(191 (И 5 С 06 Р 7/5 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ПЮТ СССРс"(56) Авторское свидетельство ССГР В 1070548, кл. Г Об Р 7/58, 1983.Авторское свидетельство ССГР В 1481755, кл. Г Об Р 7/58, 1988, (54) ГЕНЕРАТОР СЛУЧАЙНОГО гЗРКОВСКОГО пРОПессз(57) Иэобретение относится к автоматике и вычи жет испольэ входных но итель аться технике и моля генерацииьностей при стохаискретных объедоват ическом к тов. 1 ель ол обретения являетс вышение бы я достижен тродеисгвия генераторая поставленной цели вдены регисгр 4 сдвига,сумматор-вычитатель 51 О, причем повышение генератор вв накапливают и элемент ИЛИ быстродейств ется эа счет ба элементов вероятностей я генератора днаправлепногоматриды перохо2 ил стигаерегиых ПИСАНИЕ ИЗОБРЕТЕН46 6ся в состоянии л. Сигнал Опрос поступает на вход датчика 2. Сигнал"Сложитьпоступает на суммирунщийвход накапливающего сумматора-вычитателя 5, Датчик 2 вырабатывает ш-разрядное двоичное число т = х 2и величина х подается на вторуюгруппу информационных входо схемы9 сравнения двоичных чисел. Одновременно в накапливающем сумматоревычитагеле 5 формируется текущий адрес Айг, по которому выполняется обращение к блоку 6 памяти кодов состояний и к блоку 7 памяти элементов строк. На выходе блоков 7 и 6 памяти появляются координаты г и Г соответственно. Эти координаты соответствуют элементу строки Г матрицы Р , находяегося по адресу Ад((Ч + и/21+ с, где с - значение младшего разряда регис тра 4 сдвига, Координата г поступает нл первую группу информационных входов схемы 9 сравнения двоичных чисел, Схема 9 сравнения может вырабатывать признак ( (число от датчика 2 случайных чисел меньше илц равно, чем число, получаемое от блока 7 памяти элементов строк), либо Ь (число от датчика 2 случайных чисел больше,а чем число, получаемое от блока 7 памяти элементов строк). О, если Р, = О,К КР если Р.О. у=оР1 К 25 40 1624(4Перейдем от стохлсгической матрицы Р к матрице Р = /( Р,К(/ Векторы К и Т получаются следующим образом, 10Иэ матрицы Р построчно выписы -вают в вектор К нуль и ненулевыеэлементы Р,Кв вектор Т нуль и ицКдексы столбцов к ненулевых элементов.Векторы 11 и О загружают в блок 3памяти указателей начала строк, содержащий и ячеек. При этом координаты цр 1 щ О, 1, 2, ,изаписываются в поле старших разрядов (имсоответствует выход 3.1), л координаты Ч - в поле младших разрядов(им соответствует выход 3.2) блока 3памяти указателей начала строк. Чис ло старших и младших разрядов ячеекблока 3 памяти указателей началастрок определяется максимальным значением координат векторов У и О цсоставляет 1 ог. иц 11 од (д + и)(соответственно,Вектор К загружается в блок 7 памяти элементов строк, содержащийд +и ячеек разрядностью ш, причемв памяти записываются только числители 411, уменьшенные ца единицу, дробей вида г = й. 2и 35Вектор Т загружается в блок 6 памяти кодов состояний, содержлщй(г411 + и ячеек разрядностью 1 оби,Перед началом работы векторы УК и Т вычисляются и загружаютсяв соответствующие блоки 3, 6 и 7 памяти (на фиг,1 устройства загрузкине показано).Начальное состояние з цепи залается следующим образом. 45В регистр 8 загружают код Г состояния в. И регистр 4 сдвига загружают число ненулевых элементов строкиГ стохастической матрици Р (значениекоординаты ц вектора У) л в цакапливающий сумматор-выцитатель 5 указателя начала строки Г - матрицы Р(значение коордицлгы Ч вектора О).На этом процесс загрузки исходныхданных завершен,Работа генератора гводится к реализации алгоритма управленц(фнг.2). После загрузки цлчлльцогосостояния блок 1 управления цлходитВ зависимости от значений сигналов, поступающих от схемы 9 сравнения двоичных чисел ц с выхода элемента ИЛИ 1 О, блок 1 управления становится в одно цз следующих состояний: при сигнал "1 олы(е" на выходе схемы 9 сравнения и сигнала "О" на выходе элемента ИЛИ 1 О (число, хранящееся в старших разрядах регистра 4 сдвига це равно нулю) - в состоянии а(, при сигнале "Меньше цли равно" на выходе схемь( 9 сравнения и сигнале "О на выходе элемента ИЛИ 1 О - в состоянии л ; при сигнале "Больше" на выходе схемы 9 срлвцецця и сигнале "1" на выходе элемента ИЛИ 1 О - в состоянии л, прц сигцале "Меньше или равно" цл выходе схемы 9 сравнения и сцгцлле "1" нл виходе элемента ИЛИ 10 - в сстоянии л.Пусть фиксируется г стояние л(При этом подается упрлвляюий сигнал "Сдвиг" нл регистр 4 сдвигл и сигнал Сложить нл цлклп:ц(влюий сумматор-вычитлтель 5. В результате50 этого в накапливающем сумматоре-вычитателе 5 Формируется новый адресАйг. На выходе блоков Ь и 7 памятипоявляются новые координаты с и г,5которые соответствуют элементу строки Г матрицы Р, находящегося по ад -ресу Ас 1 г = Адг + ц/4 + 1. Координата г поступает на первую группуинформационных входов схемы 9 сравнения двоичных чисел .Вновь срабатывает схема 9 сравнения, в зависимости от значения сигналов с выхода схемы 9 сравнения и свыхода элемента ИЛИ 10, вновь устанавливается одно из состояний а а,а и а 4 и т.д. Пусть Фиксируется а.В состоянии а подается сигнал"Сдвиг" на регистр 4 сдвига и сигнал "Вычесть" на. накапливающий сумматор-вычитатель 5. При этом в накапливающем сумматоре-вычитателе 5фиксируется цовьц адрес Ас 1 г. На выходе блоков 6 и 7 памяти появляютсякоординаты с и г, которые соотнетствуют элементу строки с матрицыР , находячегося по адресу Ас 1 гАдг - 11/8 1 - с . Координата гпоступает на первую группу информационных входов схемы 9 сравнения.В зависимости от значения сигналов на выходе схемы 9 сравнения ц навыходе элемента ИЛИ 10 вновь Фиксируется одно из состояний а, а, аз,а 4,и т.д.35В состоянии а з выдается сигнал"Сложить" на накапливающий сумматор-вычитатель 5. В результате этого в накапливающем сумматоре-нычитателе 5 Формируется адрес Аг, по которому происходит обращение к блокам 6 и 7 памяти. На выходе блоков6 и 7 памяти появляются координатыи г, которые соответствуют первому ненулевому элементу строки гматрицы Р, т.е. находящегося по адресу Ас 1 г = Ас 1 г + с (на выходе 4.1регистра 4 сдвига поступает ноль).Блок 1 управления переходит нсостояние а,с,1Подается сигнал Записьц на регистр 8. Этот же сигнал подается навход "Запись" регистра 4 сдвига инакапливающего сумматора-вычитателя5При этом в регистр 8 Фиксируетсяочередное состояние змарковскогопроцесса, в регистр 4 сдвига Фиксируется координатавектора 11 (числоненулевых элементов строки 1 матрицы Р), а в яакалинающем сумматоренычитателе 5 записывается координата с 1 у вектора Г) (указатель началастроки матрицы Р),Вновь выдается сигнал "Сложить"на накапливающий ".умматор-нычитатель5 и "Опрос" - ца датчик 2, Вновь внакапливающем сумматоре-вычитателе5 формируется адрес, по которому происходит считывание 6 и 7 памяти,вновь срабатывает схема 9 сравнения.По признаку сравнения и значению сигнала на выходе элемента ИЛИ 10 блок 1 управления вновь переходит н одно из состояний а, а, а, аи т.д.Таким образом, смена состояний а, - аобеспечивает логарифмический поиск (мегод половинного деления) очередного состояния марковского процесса, а состояние а 4 - Фиксацию найденного состояния. формула изобретения Генератор случайного марковского процесса, содержащий блок управления, первый, второй ц третий блоки памяти, датчик равномерно распределенных случайных чисел, регистр и схему сравнения, причем группа выходов схемы сравнения соединена с группой входов задании логических условий блока управления, первый выход которого соединен с входом опроса датчика равномерно распределенных случайных чисел, выход которого соединен с первым информационным входом схемы сравнения, второй информационный вход которой соединен с выходом первого блока памяти, выход второго блока памяти соединен с адресным входом третьего блока памяти и с информационным входом регисгра, вход записи которого соединен с вторым выходом блока управления, выход регистра является информационным выходом генератора, о тл и ч а ю щ и й с я тем, что, с целью повышения быстродействия, в него введены регистр сдвига, накапливающий суммато 1 -вьчтатель и элемент ИЛИ,причем третий ныход блока управления соединен с входом записи регистра сдвига и с входом разрешения записи накапливающего сумматора-нычитателя, первый инФормационный вход которого соединен с выходом младптих разрядов третьего блока памяти, выход старших разрядов которого соединен с ицформа 1 и1 О ционным Входом 1 сГНГТч сиглвьхокоторого соединен с вторым инАОрмлПИОННЫМ ВХОДОМ НЛКапПНЛсЕГО СУММЛтора-вычитателя, вьг(О кторго сеДИНЕН С аДРЕСНЬИ ВХсДЛМИ ПСРВОГО Ивторого блоков памяти, выхды старших разрядов регистра сдвига соединены с входами эпемента 1 ПИ, инверсНЫй ВЫХОД КОтОРсГО СОЕДИНЕН С;П;в НИ"НЫМ В О тМ ЭЛЛ(1 ИЯ 11",с;С СКИ, уГГ,овиЙ блока управ.ения, сс.Твертыи ВЫХ; КОТРОГО ГОсИПЕН Г ВХОДОМ сдвига регистра с;(пигл, пятый выходблока управления с едине с входомрЛЗРЕШЕНИЯ С;О;ЕНИЯ НЛКЛПДИВЛНсЕГОсумматор-вычитлт.я, вхо;с. разрешения вычитания к торгг соединен сШЕСТЫМ ВЫХО; М ДсКЛ УПРЛВПЕНИЯ,