УСТРОЙСТВО для МОДЕЛИРОВАНИЯ ЦЕПЕЙ МАРКОВА Советский патент 1971 года по МПК G06F15/173 G06F17/18 

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

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

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

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

Блок-схема описываемого устройства изображена на чертеже.

Блок управления 1 соединен с выходом блока 2 ввода начальных условий и со входом регистра адреса 3 и входом регистра зоны 4. Выход регистра зоны подключен ко входу дешифратора зон 5. Выход регистра адреса 3 соединен со входом запоминающего устройства 6, выход запоминающего устройства подключен ко входу коммутатора зон 7. Выход блока управления / соединен параллельно с первыми входами схем совпадения 8, выходы которых подключены к одному из входов схем сборки 9, другие входы схем сборки соединены с выходами схем совпадения 10, первые входы которых подключены параллельно с первым;; входами схем совпадения 8 к выходу блока управления /. Вторые входы схем совпадения 8 подключены к выходу генератора II

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

Работает данное устройство следующим образом. ройСтво 6 через 1блок ввода 2 запоминается таблица некоторого детерминированного автомата а1 ф (а, X), полученная при преобразовании стохастической матрицы цепи Маркова и начального распределения, где: а - -состояние депи Маркова в момент N+1 ; а - состояние цепи Маркова в момент IN X - принимает все возможные значения случайного числа t,; лод л-понимается дискретное время или Л-й такт работы устройства. Таким образом, в ячейку запоминающего устройства по адресу (а, С) записывается значение следующего состояния цепи ai, число ячеек равно числителю вероятности перехода цепи Маркова из состояния а в состояние ai при условии, что элементы стохастической матрицы нормированы со знаменателем, равным 2, где п-число разрядов случайного числа . Для кодирования состояний цепи Маркова по.рядка Q необходимо Iog2 Q двойных разрядов; если число разрядов ячейки запоминающего устройства 6 намного больше, чем logg Q, то разряды ячеек разбиваются на зоны, поэтому формула детерминированного автомата принимает следующий вид: а1 ф(аь «2, X), где f(ai, 02) а; а 1(а, Os - номер зоны в момент а ,- номер зоны в момент IN+IНомер зоны по входам 15, записывается в регистр зоны 4, в каждый такт работы подается на дещифратор зон 5. Коммутатор зон 7 производит выборку из кодовых шин числа запоминающего устройства той зоны, номер которой записан в регистре зон. Система схем совпадения 8, 10 и схем сборки 9 служит для разбиения регистра адреса 3 на две части-левую и правую; в правую часть регистра могут войти |разряды, имеющие входы 14, в левую часть регистра могут входить разряды, имеющие входы как 13, так и 14. В правую часть регистра адреса в каждом такте записывается значение а. Левая часть регистра определяет величину точности апцроксиации цепи, а правая часть регистра совместно с регистром зон определяет порядок моделируемых цепей. Блок управления управляет работой всех блоков следующим образом: по входу 16 поступает информация о настройке на необходимый режим работы, по выходу 17 производится установка в нуль регистров 3, 4 перед началом моделирования и в каждый такт работы, по выходам 18, 19 производится опрос регистров 3, 4, по выходам 20 подаются сигналы на схемы совпадения 8, 10, чем производится разбиение регистра адреса на левую и правую части, так как на входы 14 поступают сигналы либо от коммутатора зон, либо разряды случайного числа от входа генератора 11. Результаты моделирования выдаются по выходу/2. 10, которые делят регистр адреса 3 на левую и правую части. По выходу 17 производится установка пуля в регистрах 3 ъ 4. Для моделирования начального распределения подается случайное число С,, которое заполняет левую часть регистра адреса. По выходам 18, 19 подаются сигналы опроса регистров 3, 4, содержимое регистров 3, 4 по выходам 21, 22 поступает на запоминающее устройство 6 и дешифратор зон 5. По выходу 17 регистры 3, 4 устанавливаются в «О. Поступивший на запоминающее устройство сигнал от регистра адреса производит выборку соответствующей ячейки, хранимая в ней информация по кодовым щинам числа подается на коммутатор зон 7, где и выбирается нужная зона. С выходов коммутатора зон инфор,мация подается на выход 12 и, кроме того, на входы 15 регистра зон, а также на входы 14 регистра адреса для заполнения правой его части. В следующем такте происходит моделирование значения функции цепи Маркова, для этого с выхода генератора // снова подается случайное число t. по выходам 18, 19 подается сигнал опроса регистров 5, 4. По выходу 17 регистры 3, 4 устанавливаются в «О. С выходов коммутатора зон информация о состоянии цепи снова поступает на выход 12 и на регистры 3,4, одновременно с этим с выхода генератора // подается новое случайное число, и все повторяется как и в предыдущем такте. Таким образом, выдача значения функции цепи Маркова осуществляется в каждый такт работы устройства моделирования, причем длительность такта равна времени обращения к запоминающему устройству при условии, что на выходе генератора 11 имеется случайное число требуемой разрядности. В случае генерирования случайных чисел с заданным законом распределения правая часть регистра адреса 3 не заполняется. В регистр зон записывается номер закона распределения. Числа с заданным законом распределения снимаются с выходов коммутатора зон, соединенных со входами схем совпадения 10, а номер закона распределения снимается с выходов коммутатора зон, соединенных со входами 15 регистра зон. Случайные числа и номера законов снимаются с выхода 12. Предмет изо-бретения Устройство для моделирования цепей Маркова, содержащее блок управления, блок ввода начальных условий, генератор равномерно распределенных чисел, запоминающее устройство, схемы совпадения и сборки, коммутатор зон, регистр адреса и регистр зоны, дешифратор зон, отличающееся тем, что, с целью повышения быстродействия процесса моделирования, одни выходы коммутатора зон соединены со входами регистра зон, другие выходы коммутатора зон соединены через схемы совпадения и сборки со входами регистра адреса, 5 поминающего устройства, выход регистра зон соединен со входом дешифратора зон, выход дешифратора зон и выход запоминающего уст6ройства подключены ко входам коммутатора зон. выходы коммутатора зон соединены с выходной клеммой устройства.