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

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

Иллюстрации

Показать все

Реферат

 

О П И С А Н И Е 290281

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Соеетских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 14.VII.1969 (№ 1347288/18-24) с присоединением заявки ¹

Приоритет

МПК G 061 15/36 йоюитет по деласс иаобретеиий и открытий при Сосете Миииотрее

СССР

УДК 681.332.65(088.8}

Опубликовано 22.XII 1970. Бюллетень № 2 за 1971

Дата опубликования описания 10.II.1971

Авторы изобретения

P. Г. Бухараев и В, И. Геза

Заявитель Казанский государственный университет им. В. И. Ульянова-Ленина

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЦЕПЕЙ МАРКОВА

Данное изобретение относится к области счетно-решающей техники.

Известные устройства, сконструированные по принципу самоуправляемых вычислителей, не приспособлены к моделированию случайных процессов типа однородных цепей Маркова и поэтому обладают низким быстродействием.

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

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

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

Значение функции цепи Маркова поступает не только на выход, но и участвует в формировании нового адреса обращения к запоминающему устройству. Второй компонентой при составлении адреса является, равномерно распределенное в интервале (0,1) случайное число, Блок-схема описываемого устройства изображена на чертеже.

Блок управления 1 соединен с выходом блока 2 ввода начальных условий и со входом регистра адреса 8 и входом регистра зоны 4.

Выход регистра зоны подключен ко входу дешифратора зон 5. Выход регистра адреса 8 соединен со входом запоминающего устройства

6, выход запоминающего устройства подклю10 чен ко входу коммутатора зон 7. Выход блока управления 1 соединен параллельно с первыми входами схем совпадения 8, выходы которых подключены к одному из входов схем сборки 9, другие входы схем сборки соедине15 ны с выходами схем совпадения 10, первые входы которых подключены параллельно с первыми входами схем совпадения 8 к выходу блока управления 1. Вторые входы схем совпадения 8 подключены к выходу генератора 11

20 равномерно распределенных чисел, а вторые входы схем совпадения 10 соединены с выходами коммутатора зон 7. Выходная клемма 12 устройства подключена параллельно выходам коммутатора зон 7.

25 Работает данное устройство следующим образом.

В каждый такт работы устройства на входы

18, 14 параллельным кодом подается и-разрядное равномерно распределенное в интервале зо (0,1) случайное число <. В запоминающее уст290281

55 ройство б через блок ввода 2 запоминается таблица некоторого детерминированного автомата a>=y (а, Х), полученная при преобразовании стохастической матрицы цепи Маркова и начального распределения, где: а — состояние цепи Маркова в момент

tv+i; а — состояние цепи Маркова в момент

/д, Х вЂ” принимает все возможные значения случайного числа ; под 1л понимается дискретное время или Л-и такт работы устройства.

Таким образом, в ячейку запоминающего устройства по адресу. (а, <) записывается значение следующего состояния цепи а>, число ячеек равно числителю вероятности перехода цепи Маркова из состояния а в состояние а при условии, что элементы стохастической матрицы нормированы со знаменателем, равным

2", где и — число разрядов случайного числа .

Для кодирования состояний цепи Маркова порядка Q необходимо log> Q двойных разрядов; если число разрядов ячейки запоминающего устройства б намного больше, чем log> Q, то разряды ячеек разбиваются на зоны, поэтому формула детерминированного автомата принимает следующий вид: а = р(аь а, Х), где f(a, а ) =а; а = (а о а ); а — номер зоны в момент 3и; а,— номер зоны в момент iN+I.

Номер зоны по входам 15, записывается в регистр зоны 4, в каждый такт работы подается на дешифратор зон 5. Коммутатор зон 7 производит выборку из кодовых шин числа запоминающего устройства той зоны, номер которой записан в регистре зон.

Система схем совпадения 8, 10 и схем сборки 9 служит для разбиения регистра адреса 8 на две части — левую и правую; в правую часть регистра могут войти разряды, имеющие входы 14, в левую часть регистра могут входить разряды, имеющие входы как 13, так и

14. В правую часть регистра адреса в каждом такте записывается значение а . Левая часть ,регистра определяет величину точности апцроксиации цепи, а правая часть регистра совместно с регистром зон определяет порядок моделируемых цепей.

Блок управления управляет работой .всех блоков следующим образом: по входу 1б поступает информация о настройке на необходимый режим работы, по выходу 17 производится установка в нуль регистров Г, 4 перед началом моделирования и в каждый такт работы, по выходам 18, 19 производится опрос регистров

8, 4, по выходам 20 подаются сигналы на схемы совпадения 8, 10, чем производится разбиение регистра адреса на левую и правую части, так как на входы 14 поступают сигналы либо от коммутатора зон, либо разряды случайного числа от входа генератора 11. Результаты моделирования выдаются по выходу 12.

Перед началом моделирования по выходам

30 подаются сигналы на схемы совпадения 8, 5

15 го г5

10, которые делят регистр адреса 8 на левую и правую части. По выходу 17 производится установка нуля в регистрах 8 и 4.

Для моделирования начального распределения подается случайное число, которое заполняет левую часть регистра адреса. По выходам 18, 19 подаются сигналы опроса регистров 8, 4, содержимое регистров 8, 4 по выходам 21, 22 поступает на запоминающее устройство б и дешифратор зон 5. По выходу 17 регистры 8, 4 устанавливаются в «0». Поступивший на запоминающее устройство сигнал от регистра адреса производит выборку соответствующей ячейки, хранимая в ней информация по кодовым шинам числа подается на коммутатор зон 7, где и выбирается нужная зона.

С выходов коммутатора зон информация подается на выход 12 и, кроме того, на входы 15 регистра зон, а также на входы 14 регистра адреса для заполнения правой его части. В следующем такте происходит моделирование значения функции цепи Маркова, для этого с выхода генератора 11 снова подается случайное число g, по выходам 18, 19 подается сигнал опроса регистров 8, 4. По выходу 17 регистры 8, 4 устанавливаются в «О». С выходов коммутатора зон информация о состоянии цепи снова поступает на выход 12 и на регистры 3, 4, одновременно с этим с выхода генератора 11 подается новое случайное число, и все повторяется как и в предыдущем такте. Таким образом, выдача значения функции цепи Маркова осуществляется в каждый такт работы устройства моделирования, причем длительность такта равна времени обращения к запоминающему устройству при условии, что на выходе генератора 11 имеется случайное число требуемой разрядности.

В случае генерирования случайных чисел с заданным законом распределения правая часть регистра адреса 3 не заполняется. В регистр зон записывается номер закона распределения.

Числа с заданным законом распределения снимаются с выходов коммутатора зон, соединенных со входами схем совпадения 10, а номер закона распределения снимается с выходов коммутатора зон, соединенных со входами 15 регистра зон. Случайные числа и номера законов снимаются с выхода 12.

Предмет изобретения

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

Составитель Г. Полиевский

Техред T. П. Курилко Корректэр Т. А. Уманец

Редактос Б. С. Нанкина

Изд. 86 Заказ 158/16 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, SK-35, Раушская наб., д. 4/5

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