Устройство для моделирования цепей маркова

О П И С А Н И Е 290281ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Соеетских Социалистических РеспубликЗависимое от авт. свидетельстваЗаявлено 14 Л 11.1969 ( 1347288/18-24)с присоединением заявкиПриоритет МПК б 06 15/36 Комитет по делам иаобретеиий и открытий при Сосете Миииотрее СССРУДК 681.332.65(088.8) Опубликовано 22.Х 11,1970, Бюллетень2за 1971 Дата опубликования описания 10.11.1971 Авторыизобретения Р, Г, Бухараев и В, И, Геза Заявитель Казанский государственный университет им. В. И. Ульянова-Ленина УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЦЕПЕЙ МАРКОВА Данное изобретение относится к области счетно-решающей техники.Известные устройства, сконструированные по принципу самоуправляемых вычислителей, не приспособлены к моделированию случайных процессов типа однородных цепей Маркова и поэтому обладают низким быстродействием. Предложенное устройство отличается от известных тем, что обеспечивает моделирование значения функции однородных конечных цепей Маркова за один рабочий такт, равный по длительности времени обращения к запоминающему устройству. Это достигается путем преобразования стохастической матрицы цепи Маркова и начального распределения цепи в таблицу состояний детерминированного автомата и записью полученной таблицы в запоминающее устройство. Алгоритм работы предложенного устройства состоит в том, что случайным образом формируется адрес обращения к запоминающему устройству, по которому и выбирается значение функции цепи Маркова.Значение функции цепи Маркова поступает не только на выход, но и участвует в формировании нового адреса обращения к запоминающему устройству. Второй компонентой при составлении адреса является, равномерно распределенное в интервале (0,1) случайное число,Блок-схема описываемого устройства изображена на чертеже.Блок управления 1 соединен с выходом блока 2 ввода начальных условий и со входом регистра адреса 3 и входом регистра зоны 4.Выход регистра зоны подключен ко входу дешифратора зон 5. Выход регистра адреса 3 соединен со входом запоминающего устройства 6, выход запоминающего устройства подклю чен ко входу коммутатора зон 7. Выход блокауправления 1 соединен параллельно с первыми входами схем совпадения 8, выходы которых подключены к одному из входов схем сборки 9, другие входы схем сборки соедине ны с выходами схем совпадения 10, первыевходы которых подключены параллельно с первыми входами схем совпадения 8 к выходу блока управления 1. Вторые входы схем совпадения 8 подключены к выходу генератора 11 20 равномерно распределенных чисел, а вторыевходы схем совпадения 10 соединены с выходами коммутатора зон 7. Выходная клемма 12 устройства подключена параллельно выходам коммутатора зон 7.25 Работает данное устройство следующим образом.В каждый такт работы устройства на входы13, 14 параллельным кодом подается и-разрядное равномерно распределенное в интервале зо (0,1) случайное число . В запоминающее уст.55 50 55 ройство б через блок ввода 2 запоминаетсятаблица некоторого детерминированного автомата а 1=р (а, Х), полученная при преобразовании стохастической матрицы цепи Марковаи начального распределения, где:а - состояние цепи Маркова в моментя+; а - состояние цепи Маркова в момент8 я , Х - принимает все возможные значенияслучайного числа ; под 1 л понимается дискретное время или Л-и такт работы устройства.Таким образом, в ячейку запоминающегоустройства по адресу (а, ) записывается значение следующего состояния цепи а 1, числоячеек равно числителю вероятности переходацепи Маркова из состояния а в состояние апри условии, что элементы стохастической матрицы нормированы со знаменателем, равным2", где и в чис разрядов случайного числа ,Для кодирования состояний цепи Маркова порядка Я необходимо 1 од 2 Я двойных разрядов;если число разрядов ячейки запоминающегоустройства б намного больше, чем 1 од Я, торазряды ячеек разбиваются на зоны, поэтомуформула детерминированного автомата принимает следующий вид:а 1=р(а а 2, Х),где (аь а ) =а; а=(ао а 1,); а 2 - номер зоны в момент 1 д; а, - номер зоны в момент 1 у+.Номер зоны по входам 1 б, записывается врегистр зоны 4, в каждый такт работы подается на дешифратор зон 5. Коммутатор зон 7производит выборку из кодовых шин числа запоминающего устройства той зоны, номер которой записан в регистре зон.Система схем совпадения 8, 10 и схем сборки 9 служит для разбиения регистра адреса 3на две части - левую и правую; в правую частьрегистра могут войти разряды, имеющиевходы 14, в левую часть регистра могут входить разряды, имеющие входы как 13, так и14, В правую часть регистра адреса в каждомтакте записывается значение а,. Левая часть,регистра определяет величину точности апцроксиации цепи, а правая часть регистра совместно с регистром зон определяет порядокмоделируемых цепей.Блок управления управляет работой всехблоков следующим образом: по входу 1 б поступает информация о настройке на необходимый режим работы, по выходу 17 производитсяустановка в нуль регистров Г, 4 перед началоммоделирования и в каждый такт работы, повыходам 18, 19 производится опрос регистров3, 4, по выходам 20 подаются сигналы на схемы совпадения 8, 10, чем производится разбиение регистра адреса на левую и правую части, так как на входы 14 поступают сигналылибо от коммутатора зон, либо разряды случайного числаот входа генератора 11. Ре.зультаты моделирования выдаются по выходу 12,Перед началом моделирования по выходам40 подаются сигналы на схемы совпадения 8,5 10 15 го г 5 30 35 40 45 50 10, которые делят регистр адреса 3 на левую и правую части. По выходу 17 производится установка нуля в регистрах 3 и 4,Для моделирования начального распределения подается случайное число , которое заполняет левую часть регистра адреса. По выходам 18, 19 подаются сигналы опроса регистров 3, 4, содержимое регистров 3, 4 по выходам 21, 22 поступает на запоминающее устройство б и дешифратор зон б. По выходу 17 регистры 3, 4 устанавливаются в 0. Поступивший на запоминающее устройство сигнал от регистра адреса производит выборку соответствующей ячейки, хранимая в ней информация по кодовым шинам числа подается на коммутатор зон 7, где и выбирается нужная зона. С выходов коммутатора зон информация подается на выход 12 и, кроме того, на входы 15 регистра зон, а также на входы 14 регистра адреса для заполнения правой его части. В следующем такте происходит моделирование значения функции цепи Маркова, для этого с выхода генератора 11 снова подается случайное число , по выходам 18, 19 подается сигнал опроса регистров 3, 4. По выходу 17 регистры 3, 4 устанавливаются в 0. С выходов коммутатора зон информация о состоянии цепи снова поступает на выход 12 и на регистры 3,4, одновременно с этим с выхода генератора 11 подается новое случайное число, и все повторяется как и в предыдущем такте. Таким образом, выдача значения функции цепи Маркова осуществляется в каждый такт работы устройства моделирования, причем длительность такта равна времени обращения к запоминающему устройству при условии, что на выходе генератора 11 имеется случайное число требуемой разрядности.В случае генерирования случайных чисел с заданным законом распределения правая часть регистра адреса 3 не заполняется. В регистр зон записывается номер закона распределения, Числа с заданным законом распределения снимаются с выходов коммутатора зон, соединенных со входами схем совпадения 10, а номер закона распределения снимается с выходов коммутатора зон, соединенных со входами 15 регистра зон. Случайные числа и номера законов снимаются с выхода 12. Предмет изобретения Устройство для моделирования цепей Маркова, содержащее блок управления, блок ввода начальных условий, генератор равномерно распределенных чисел, запоминающее устройство, схемы совпадения и сборки, коммутатор зон, регистр адреса и регистр зоны, дешифратор зон, отличающееся тем, что, с целью повышения быстродействия процесса моделирования, одни выходы коммутатора зон соединены со входами регистра зон, другие выходы коммутатора зон соединены через схемы совпадения и сборки со входами регистра адреса, выход регистра адреса соединен со входом за290281 Составитель Г. Полиевскийдактор Б. С. Нанкина Техред Т. П. Курилко Корректэр Т. А. Уманец Изд. 86 Заказ 158/16 Тираж 480 ПодписиЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров ССС Москва, Ж, Раушская наб., д. 45 ипография, пр. Сапунова,поминающего устройства, выход регистра зон соединен со входом дешифратора зон, выход дешифратора зон и выход запоминающего устройства подключены ко входам коммутатора зон, выходы коммутатора зон соединены с выходной клеммой устройства.