Генератор случайного Марковского процесса Советский патент 1984 года по МПК G06F7/58 

Изобретение относится к цифровой вычислительной технике и может быть использовано при построении моделирующих устройств, предназначенных для анализа и синтеза сложных систем

Известны устройства для моделирования однородных конечных цепей Маркова, например генератор случайного процесса, содержащий генератор равномерно распределенных случайных чисел, выходы которого соединены с группой входов блока ассоциативной памяти, вход которого соединен с входом блока управления, а выходы блока памяти подключены к выходам первой группы элементов ИЛИ, который содержит группу функциональных преобразователей, выходы которых соединены с входами второй группы элементов ИЛИ, первая группа входов функциональных преобразователей соедине« на с выходами блока управления, а вторая группа входов функциональных преобразователей соединена с выходами блока ассоциативной памяти соответственно С1 .

Кроме того, известно устройство для моделирования однородных конечных цепей Маркова, которая содержит дешифратор и блок схем совпадения, первые входы которых соединены с соответствующими ячейками блока ассоциативной памяти, вторые входы подключены через дешифратор к выходному регистру, а выходы подключены к входам соответствующих схем сборки 2.

Оба устройства являются вариантами развития устройства для моделирования однородных конечных цепей Маркова, блок памяти в. них выполнен в виде ассоциативного запоминающего накопителя, содержгицего регистр признака опроса, блок ассоциативных признаков и индикаторные элементы, выходы которых соединены с входами каждой схемы сборки, а входы подключены к соответствующему выходу блока управления и к соответствующей группе выходов блока ассоциативных признаков, один из входов которого соединен с блоком ввода, а другой - с выходом генератора равномерно распределенных случайных двоичных чисел через регистр признака опроса, подключенный другими входами к соответствунадему выходу блока управления и выxoднo лy регистру.

Наиболее близким по технической сущности к предлагаемому является устройство для моделирования однородных конечных цепей Маркова, содержащее блок управления, соединенный соответствующими выходами с блоком вво да, генератором равномерно распределенных случайных двоичных чисел и с выходным регистром, подключенным входом через шифратор к выходам схем

сборки, и блок памяти, который выполнен в виде ассоциативного запоминающего накопителя, содержащего регистр признака опроса, блок ассоциативных признаков, и индикаторные элементы, выходы которых соединены с входами каждой схемы сборки, а входы подключены к соответствующему выходу блока управления и к соответствующей группе выходов блока ассоциа0 тивных признаков, один из входов которого соединен с блоком ввода, а другой - с выходом генератора равномерно распределенных случайных двоичных чисел через регистр призна5 ка опроса, подключенный другими входами к соответствующему выходу блока управления и к выходному регистру 3.

Недостатком прототипа является то, что все известные устройства при

Q моделировании однородных конечных цепей Маркова, задаваемых разреженной стохастической матрицей состояний, требуют оборудование для хранения и обработки нулевых элементов матрицы состояний. Все усовершенствования, которым подвергался прототип, касались вариантов конструкции памяти, не затрагивая ее природы. Наличие громоздкой матрицы переходов требует большого объема общей памяти, в том числе и для хранения нулевых элементов матрицы.

Цель изобретения - упрощение устройства для моделирования однородных конечных цепей Маркова.

Для достижения поставленной цели в генератор случайного марковского процесса, содержащий блок управления, выходной регистр памяти, датчик равномерно распределенных случайных чисел, выход которого соединен с информационным входом первого регистра адреса, выходы разрядов которого соединены с первой группой

адресных входов блока памйти соответственно, введен второй регистр адреса, а блок управления содержит счетчик-делитель и генератор тактовых импульсов, выход которого соединен со счетным входом счетчика-делителя, пять выходов которого соединены соответственно с входом Опрос датчика равномерно распределенных случайных чисел, с управляющим входом первого регистра адреса, с управляющим входом второго регистра адреса, с управляющим входом выходного регистра памяти и с входом Сброс счетчика-делителя, выходы разрядов второго регистра адреса соединены с второй группой адресных входов блока памяти соответственно, группа выходов которого соединена с входами соответствукндих разрядов выходного регистра памяти,выход которого является выходом генератора и соединен с информационным входом второго регистра адреса. На фиг.1 приведена блок-схема ге нератора; на фиг.2 - схема блока уп равления; на фиг.З - диаграмма рабо ты блока управления; на фиг.4 - чис ловая последовательность, записываемая в i-ю строку блока памяти. Генератор содержит блок 1 управления, датчик 2 равномерно распреде ленных случайных чисел, узел 3 памя ти, состоящий из блока 4 памяти и регистров 5 и 6 памяти, выходной регистр 7 памяти. Блок 1 управления содержит генератор 8 тактовых импул сов и счетчик-делитель 9. Генератор работает следующим образом. Пусть задана простая однородная цепь Маркова с конечным множеством состояний S-{5i , i40, П--1 и стохастической матрицей переходов (, где P;i вероятность переходов за один такт из состояния 5 в состояние i,KrO,n-i , Piij-a- Z,.-целое . Матрицу Р преобразует в матрицу 6-llfaf,jll, 1 0,п-1 , --i, , строка Bj кото рой .соответствует состоянию S и представляет собой числовую последо вательность, состоящую из п серий, причем к-я серия состоит из номеров К, повторенных а,- раз (фиг.2). П--1и-Так как ) р. - , то „ -2. матрица 1 содержит 2 столбцов. Матрица В построчно записывается (блок записи на фиг.1 не показан в блок 4 памяти так, что строка В- за писывается в i-ю строку матричной памяти 4, имеьзщей п строк по 2 яч .ек памяти в каждой, при этом ячейка памяти содержит Eog-2 двоичных разрядов, используемых для записи чисел ,1,..., п -1. Регистр 5 предназначен для хране ния номера (адреса) строки памяти, соответствующей состоянию Марковско цепи с тем же номером. Регистр б предназначен для хранения случайного числа, являющегося номером (адресом I столбца матричной памяти. Выходной регистр 7 предназна ген для хранения считанного из матрично памяти номера очередного состояния Марковской цепи. В начальный момент времени, до прихода первого тактирующего сигнал от блока 1 управления, регистры 5 и 6 и выходной регистр 7 устанавливаются в нулевое состояние. Генератор 6 вырабатывает на своем выходе, соединенном с первым вхо дом счетчика-делителя 9, непрерывну последовательность сигналов со сква ностью 2 (фиг.31. Сигналы со скважностью 5, снимаемые с выходов 1-5 счетчика-делителя 9 показаны на фиг.З. Сигнал с выхода 5 подается на вход 2 счетчика-делителя 9 для установки счетчика-делителя в исходное состояние перед очередным циклом работы устройства, т.е. один такт работы устройства состоит из пяти тактов генератора тактирующих сигналов.Выходы 1-4 счетчика-делителя 9 являются сответственно выходами 1-4 блока 1 управления. Сигнал с выхода 1 блока 1 управления инициирует работу датчика 2 случайных чисел, сигнал с выхода 2 запись случайного числа в регистр б, сигнал с выхода 3 инициирует считывание из матричной памяти 4 номеру очередного состояния Марковской цепи в соответствии с адресами, задаваемыми содержимым регистров 5 и б, сигнал 4 обеспечивает считывание этого номера из выходного регистра 7 на выход всего устройства и запись в регистр 5. Пусть в некоторый момент времени регистр 5 строк содержит номер { , т.е. моделируемый процесс находится в «состоянии Sj . При приходе из блока 1 управления очередного i-го (t l, 2 ,.. .) тактирующего сигнала датчик 2 случайных чисел с равномерным распределением вероятностей на отрезке о,I вырабатывает m -разрядное двоичное число , 2 и величину С записывает в гицресный регистр столбцов б в качестве номера столбца матричной памяти. Затем из ячейки памяти, находящейся в i-й строке в С -п-, столбце, считывается содержимое (номер К) в выходной регистр 7. Номер К записывается в адресный регистр 5 строк и является номером состояния 5). , в которое переходит моделируемый процесс в момент t , так как вероятность попаДания случайного числа С в к-ю серию числовой последовательности В равна Р . В следующий такт (t+1) процесс переходит с вероятР ; ИЗ СОСТОЯНИЯ Si в неконостьюторое состояние Sy , определяемое номером К и случайным числом г +, и т.д. Таким образом происходит моделирование случайного Марковского процесса с конечным числом состояний. Объем матричной памяти, в которую записаны элементы матрицы В, составляет Vgrl pCo n бит. Объем памяти для хранения элементов стохастической матрицы переходов Р, в том числе и элементов Р,-(:0 , составляет Vp mn2sni . Поэтому при п 2 объем матричной памяти Vg Vp . Наибольший эффект от применения предлагаемого устройства достигается в системах моделирования случайных Марковских процессо.в, задаваег 1Х

разреженнЕлми стохастическими матрица ми переходов, все строки которых содержат большое количество нулей, т.е. процессов с большим числом состояний и малым количеством переходов из одного состояния в другое.

По сравнению с прото1ипом предлагаемый генератор отличается меньшим

количеством оборудования и более простой конструкцией памяти. Использование предлагаемого устройства для построения, например, моделей состояния атмосферы, социологических и экономических моделей в условиях только одного вычислительного центра позволяет экономить 1-1,5 ч. машинного времени в сутки.

ГЕНЕРАТОР СЛУЧАЙНОГО МАРКОВСКОГО ПРОЦЕССА, содержащий блок управления, выходной регистр памяти, .датчик равномерно распределенных случайных чисел, выход которого соединен с информационным входом первого регистра адреса, выходы разрядов которого соединены с пэрвой группой адресных входов блока гамяти соответственно, отличающийся тем, что, с целью упрощения, он содержит второй регистр адреса, а блок управления содержит счетчик-делитель и генератор тактовых импульсов, выход которого соединен со счетным входом счетчика-делителя, выходы которрго соединены соответственно с входом Опрос датчика равномерно распределенных случайных чисел, с управляющим входом первого регистра адреса, с управляющим входом второго регистра адреса, с управляк«цим входом выходного регистра памяти и с входом Сброс счетчика-делителя, выходы разрядов второго регистра адреса соединены с второй группой адресных I входов блока памяти соответственно, группа выходов которого соединена с входами соответствующих разрядов выходного регистра памяти, выход которого является выходом генератора и соединен с информационным входом второго регистра адреса. сд 4 сх

Выхода

Выхода

Выходз

Bbixodti

Выхода