Генератор случайного марковского процесса
ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО ПРОЦЕССА, содержащий блок управления , выходной регистр памяти, .датчик равномерно распределенных случайных чисел, выход которого соединен с информационным входом первого регистра адреса, выходы разрядов которого соединены с пэрвой группой адресных входов блока гамяти соответственно , отличающийся тем, что, с целью упрощения, он содержит второй регистр адреса, а блок управления содержит счетчик-делитель и генератор тактовых импульсов, выход которого соединен со счетным входом счетчика-делителя, выходы которрго соединены соответственно с входом Опрос датчика равномерно распределенных случайных чисел, с управляющим входом первого регистра адреса, с управляющим входом второго регистра адреса, с управляк«цим входом выходного регистра памяти и с входом Сброс счетчика-делителя, выходы разрядов второго регистра адреса соединены с второй группой адресных I входов блока памяти соответственно, группа выходов которого соединена с входами соответствующих разрядов выходного регистра памяти, выход которого является выходом генератора и соединен с информационным входом второго регистра адреса. сд 4 сх
СОЮЭ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
3(5D 06 F 7/58
1, -, ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЭОБРЕТЕНИЙ И OTHPbITHA (21) 3515469/18-24 (22) 24.11.82 (46) 30.01.84. Вюл. Р 4 (72) Л.И.Макаров, С.В.Макаров и Ю.В.Мерекин (71) Новосибирский государственный университет им.Ленинского Комсомола (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР
В 840896, кл. G.06 F 7/58, 1979.
2. Авторское свидетельство СССР
Р 451085, кл. G 06 F 7/58, 1973.
3. .Авторское свидетельство СССР
9 362291, кл. G 06 F 7/58, 1970 (про. тотип). (54)(57) ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО ПРОЦЕССА, содержащий блок управления, выходной регистр памяти,,датчик равномерно распределенных случайных чисел, выход которого соединен с информационным входом первого регистра адреса, выходы разрядов которого соединены с первой группой адресных входов блока памяти ссответ„„Su„„l 070548 А ственно, о тл и ч ающи и с я тем, что, с целью упрощения, он содержит второй регистр адреса, а блок управления содержит счетчик-делитель и генератор тактовых импульсов, выход которого соединен со счетным входом счетчика-делителя, выходы которого соединены соответственно с входом "Опрос" датчика равномерно распределенных случайных чисел, с управляющим входом первого регистра адреса, с управляющим входом второго регистра адреса, с управляющим входом выходного регистра памяти и с входом
"Сброс" счетчика-делителя, выходы разрядов второго регистра адреса соединены с второй группой адресных
С входов блока памяти соответственно, группа выходов которого соединена с входами соответствующих разрядов выходного регистра аамяти, выход которого является выходом генератора и соединен с информационным входом Я второго регистра адреса.
1070548 ных конечных цепей Маркова, содержащее блок управления, соединенный соответствующими выходами с блоком ввода, генератором равномерно распределенных случайных двоичных чисел и с выходным регистром, подключенным входом через шифратор к выходам схем
Изобретение относится к цифровой вычислительной технике и может быть использовано при построении моделирующих устройств, предназначенных для анализа и синтеза сложных систем
Известны устройства для моделирования однородных конечных цепей Маркова, например генератор случайного процесса, содержащий генератор равномерно распределенных случайных чисел, выходы которого соединены с 10 группой входов блока ассоциативной памяти, вход которого соединен с входом блока управления, а выходы блока памяти подключены к выходам первой группы злементон ИЛИ, который содержит группу функциональных преобразователей, выходы которых соеди нены с входами второй группы элементов ИЛИ, первая группа входов функциональных преобразователей соедине на с выходами блока управления, а вторая группа входов функциональных преобразователей соединена с выходами блока ассоциативной памяти соот ветственно (1).
Кроме того, известно устройство для моделирования однородных конечных цепей Маркова, которая содержит дешифратор и блок схем совпадения, перные входы которых соединены с соответствующими ячейками блока ассоциативной памяти, вторые входы подключены через дешифратор к выходному регистру, а выходы подключены к входам соответствующих схем сборки (23. 35
Оба устройства являются вариантами развития устройства для моделирования однородных конечных цепей Маркова, блок памяти в них выполнен в виде ассоциативного запоминающего 40 накопителя, содержащего регистр признака опроса, блок ассоциативных признаков и индикаторные элементы, ныходы которых соединены с входами каждой схемы сборки, а входы подключены к соответствующему выходу блока управления и к соответствующей группе выходов блока ассоциативных признаков, один из входов которого соединен с блоком ввода, а другой — с выходом генератора равномерно распределенных случайных .двоичных чисел че" рез регистр признака опроса, подключенный другими входами к соответствуницему выходу блока управления и выходному регистру.
Наиболее близким по технической сущности к предлагаемому является устройство для моделирования однородсборки, и блок памяти, который выполнен в виде ассоциативного запоминающего накопителя, содержащего регистр признака опроса, блок ассоциативных признаков и индикаторные элементы, выходы которых соединены с входами каждой схемы сборки, а входы подключены к соответствующему выходу блока управления и к соответствующей группе ныходов блока ассоциативных признаков, один из входон которого соединен с блоком ввода, а другой — с выходом генератора ранномерно распределенных случайных двоичных чисел через регистр признака опроса, подключенный другими входами к соответствующему выходу блока управления и к выходному регистру (3).
Недостатком прототипа является то, что все известные устройства при моделировании однородных конечных цепей Маркова, задаваемых разреженной стохастической матрицей состояний, требуют оборудование для хранения и обработки нулевых элементон матрицы состояний. Все усовершенствования, которым подвергался прототип, касались вариантов конструкции памяти, не затрагивая ее природы.
Наличие громоздкой матрицы переходов требует большого объема общей памяти, в том числе и для хранения нулевых элементов матрицы.
Цель изобретения — упрощение устройства для моделирования однородных конечных цепей Маркова.
Для достижения поставленной цели в генератор случайного марковского процесса, содержащий блок управления, выходной регистр памяти, датчик равномерно распределенных случайных чисел, выход которого соединен с информационным входом первого регистра адреса, выходы разрядов которого соединены с первой группой адресных входов блока памяти соответственно, введен второй регистр адреса, а блок управления содержит счетчик-делитель и генератор тактовых импульсов, выход которого соединен со счетным входом счетчика-делителя, пять выходов которого соединены соответственно с входом "Опрос" датчика равномерно распределенных случайных чисел, с управляющим входом первого регистра адреса, с управляющим входом второго регистра адреса, с управляющим входом выходного регистра памяти и с входом
"Сброс" счетчика-делителя, выходы разрядов второго регистра адреса соединены с второй группой адресных входов блока памяти соответственно, группа выходов которого соединена с входами соответствующих разрядов выходного регистра памяти, выход которого ян.ляется выходом генератора и соединен(1070548 с информационным входом второго регистра адреса.
На фиг.1 приведена блок-схема генератора; на фиг.2 — схема блока управления; на фиг.3 — диаграмма работы блока управления; на фиг.4 — числовая последовательность, записываемая в i-ю строку блока памяти.
Генератор содержит блок 1 управления, датчик 2 равномерно распределенных случайных чисел, узел 3 памяти, состоящий из блока 4 памяти и регистров 5 и б памяти, выходной регистр 7 памяти. Блок 1 управления содержит генератор 8 тактовых импульсон и счетчик-делитель 9. !5
Генератор работает следующим образом.
Пусть задана простая однородная цепь Маркова с конечным множеством состояний 9=15;),i= o,n-1 и стохас- 20 тической матрицей переходов Р=)(Р;К((, где Р;<, — вероятность переходон за один такт из состояния 5; в состояние 5>, Матрицу P преобразует .н матрицу 25 8=!!Ь(.!(, «=<,п-1, .<= 1,2", строка В; которой соответствует состоянию S; и представляет собой числовую последовательность, состоящую из и серий, причем к-я серия состоит иэ номерон К, повторенных а;„ раэ (фиг.2 ). и-1 n-< Так как + p .(, то) д 2<п т ° е к=о 1 к=о 35 матрица 1 содержит 2 столбцов. Матрица В построчно записывается (блок записи на фиг.1 не показан) в блок 4 памяти так, что строка б. записывается в < -ю строку матричной 40 <П памяти 4, имеющей и строк по 2 ячеек памяти в каждой, при этом ячейка памяти содержит ео 2 п двоичных разрядов, используемых для записи чисел К=0,1,..., и -1. 45 Регистр 5 предназначен для хранения номера (адреса ) строки памяти, соответствующей состоянию Марковской цепи с тем же номером. Регистр б предназначен для хРанения случайного числа, являющегося номером (адресом ) столбца матричной памяти. Выходной регистр 7 предназначен для хранения считанного из матричной памяти номера очередного состояния Марковской цепи. В начальный момент времени, до прихода первого тактирующего сигнала от блока 1 управления, регистры 5 и б и выходной регистр 7 устанавливаются н нулевое состояние. 60 Генератор 8 вырабатывает на своем выходе, соединенном с первым входом счетчика-делителя 9, непрерывную последовательность сигналов со скважностью 2 (фиг.3). Сигналы со скваж- 65 ностью 5, снимаемые с выходов 1-5 счетчика-делителя 9 показаны на фиг.3 Сигнал с выхода 5 подается на вход 2 счетчика-делителя 9 для установки счетчика-делителя в исходное состояние перед очередным циклом работы устройства, т.е. один такт работы устройства состоит из пяти тактон генератора тактирующих сигналов. Выходы 1-4 счетчика-делителя 9 являются соответственно выходами 1-4 блока 1 управления. Сигнал с выхода 1 блока 1 управления инициирует работу датчика 2 случайных чисел, сигнал с выхода 2 запись случайного числа в регистр б, сигнал с выхода 3 инициирует считывание из матричной памяти 4 номера очередного состояния Марковской цепи в соответствии с адресами, задаваемыми содержимым регистров 5 и б, сигнал 4 обеспечивает считывание этого номера из выходного регистра 7 на выход всего устройства и запись в регистр 5. Пусть в некоторый момент времени регистр 5 строк содержит номер т.е. моделируемый процесс находится в <состоянии S; . При приходе из блока 1 управления очередного i -го (t=1,2,... ) тактирующего сигнала датчик 2 случайных чисел с равномерным распределением вероятностей на отрезке (0,1) вырабатывает п -разрядное двоичное число пt=Ct 2 и величину Ct записывает в адресный регистр столбцов б в качестве номера столбца матричной памяти. Затем из ячейки памяти, находящейся в i-й строке в С+ „, столбце, считывается содержимое (номер К) в выходнсй регистр 7. Номер К записывается в адресный регистр 5 строк и является номером состояния S>, в которое переходит моделируемый процесс в момент t,,так как вероятность попадания случайного числа С в к-ю серию числовой последовательности 8; равна Р;1, . В следующий такт (t+1) процесс переходит с вероятностью Р1, иэ состояния 51, н неко) торое состояние 5, определяемое номером К и случайным числом r <+, и т.д . Таким образом происходит моделирование случайного Марковского процесса с конечным числом состояний, Объем матричной памяти, в которую записаны элементы матрицы В состав< П Г ляет Ч -2 n toy и бит. Объем памяти для хранения элементов стохастической матрицы переходов Р, в том числе и элементов Р;К-0, составляет Ч =mn25rn . Поэтому при и ъ2 объем матричной памяти Ч (Ч . Наибольший эффект от применения предлагаемого устройства достигается в системах моделирования случайных-Марковских процессов, задаваемых 1070548 ВиЮ Выхо ЮНА Ф Рыхл Eu/x Составитель A.Õàðàñîâ Редактор Е.Кривина Техред Т.Фанта Корректор В.Бутяга Заказ 11683/46 Тираж,699» Подписное. ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5 Филиал ППП "Патент", r.Ужгород, ул.Проектная, 4 разреженными стохастическими матрица1ми переходов, все строки которых со держат большое количество нулей, т.е. процессов с большим числом состояний и малым количеством переходов из одного состояния в другое. По сравнению с прототипом предлагаемый генератор отличается меньшим количеством оборудования и более простой конструкцией памяти. Использование предлагаемого устройства для построения, например, моделей состояния атмосферы, социологических и экономических моделей„ в условиях только одного вычислительного центра позволяет экономить 1-1,5 ч. машинного времени в сутки.
