Устройство для определения вероятностей состояний однородной дискретной цепи Маркова Советский патент 1990 года по МПК G06G7/122 

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

Цель изобретения - повышение быстродействия при вычислении вероятностей состояний однородной дискретной цепи Маркова,

В устройстве для определения вектора Р (т) || Pj(m) || , j - 1, п вероятностей состояний цепи используется изоморфизм матрицы R II г:; || , j, i e 1, п вероятностей переходов и размеченного графа состояний этой цепи. Определение вектора вероятностей состояний однородной дискретной цепи Маркова после m шагов при этом сводится к вычислению по формуле

Р(т) - РЫК -П P(k-l)P, (П

Кг«

где Р(о) - ||Р,|(о)Ц ,

j « 1 , n - вектор начальных вероятностей состояний ;

P(k-l) - || Pj (k-)||, j 1, n - вектор вероятностей состояний после k-1 шагов.

Промежуточные результаты вычислений (т.е. P(k) P(k-l) R , k I, n) xpaСП CO 4 4 J 1C

нятся в регистрах памяти, обеспечивающих их хранение без искажений.

На фиг. 1 изображена функциональная схема устройства; на фиг. 2 - блок-схема блока синхронизации; на фиг. 3 - блок-схема блока модели вершины.

Устройство содержит блок 1 синхронизации и группу блоков 2 моделей вершин графа состояний.

Блок 1 синхронизации имеет семь выходов 3-9.

Каждый блок 2 модели вершины имеет группу информационных входов 1Oj, j 1,n (n - количество блоков в группе), семь входов 11J-17J и два информационных выхода 18j и 19J Выходы 3-9 блока 1 синхронизации соединены соответственно с входами llj- 17j блоков 2 моделей вершин.

Блок 1 синхронизации предназначен для управления работой уствойст ва в процессе вычисления векторов (Состояний цепи Маркова. Он содержит триггер 20, ключ 21, генератор 22 тактовых импульсов, счетчик 23, ключи 24-26, счетчик 27 числа шагов, регистр 28 сдвига, разделительный диод 29. Каждый из блоков 2 моделей вершин предназначен для моделирования вершин цепи Маркова и вероятностей переходов г из j-й верши р i-ю за один шаг процесса, Он содержит сумматор 30, элемент 31 задержка регистры 32 и 33 памяти, элементы ИЛИ 34-36, ключи 37 и 38.

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

Перед началом работы триггер 20 устанавливается в нулевое состояние, счетчик 23 и регистр 28 сдвига обнуляются, в счетчик 27 числа шагов вводится число m шагов, коэффициенты усления соответствующих входов сумма- торов 30 устанавливают равными г:;, на входы начальных условий подаются напряжения, равные соответствующим компонентам Р:(о) вектора Р(о).

Работа устройства начинается с приходом сигнала Пуск. Бри этом на вход триггера 20 поступает сигнал, который переводит триггер 20 в состояние 1. Сигнал с прямого выхода триггера 20 поступает на управляющий вход ключа 21, контакты которого замыкаются, и запускается генератор 22 тактовых импульсов. С его выхода импульсы поступают на вход регистра

5 0

5

5

5

0

5

28 сдвига и через замкнутые контакты ключа 24 на счетный вход СЧРТЧИКЭ 23. Один цикл работы устройства соответствует одному тагу процесса и включает семь тактовых импульсов.

С приходом первого тактового импульса появляется сигнал логической 1 на первом выходе регистра 28 сдвига. Этот сигнал через замкнутые контакты ключа 25 поступает на первый выход

3блока 1 синхронизации и далее через входы llj блоков моделей вериглн на входы обнуления регистров 33 памяти.

С приходом второго тактового импульса сигнал логической появляется на втором выходе регнгтра 28 сдвига, с которого через з& ;: лутые контакты ключа 26 поступает на выход

4блока 1 синхронизации и далее через входы 12j блоков 2 моделей вер- шин на входы элементов ИЛИ 35 и управляющие входы ключей 38. Сигналы

с выхсдов элементов ИЛИ 35 поступают на входы записи регистров 33 памяти. Контакты ключей 38 замкыкаются и подключают входы задания начальных условий через элементы ИЛИ 36 к информационным входам регистров 33 памяти. При этом величины, равные -лементам Р-(о) ректора Р(о) ||Р;(оЯ1, j 1,п, по- тупают в регистру 33 памяти и запо- в них.

С приходом третьего тактового импульса сигнал 1 появляется на третьем выходе регистра 28 сдвига, с которого поступает на выход 5 блока 1 синхронизации и далее через входы 13j блоков 2 моделей вершин на входы об- нуленип регистров 32 памяти и обнуляет их.

С приходом четвертого тактового нм- пульса сигнал 1 появляется на четвертом выходе регистра 28 сдвига. Одновременно сигнал 1 появляется на выходе третьего разряда счетчика 23, этот сигнал поступает на управляющие входы ключей 24-26, контакты которых размыкаются до окончания -.работы устройства. Сигнал с четвертого выхода регистра 28 сдвига через выход 6, блока, 1 синхронизации и далее через входы 14j блоков 2 моделей вершин поступает на входы элементов 31 задержки и на входы считывания регистров 33 памяти, содержимое которых через первые информационные выходы 18j блоков 2 моделей вершин поступает на соответствующие информационные входы

10j -этих блоков. Эти величины умножаются на соответствующие коэффициенты г:; j, i l,n, равные вероятностям переходов из j-x вершин графа цепи в 1-е, суммируются в сумматорах 30 и поступают на информационные входы регистров 32 памяти. При поступлении сигналов с выходов элементов 31 чадержки на входы записи регистров 32 памяти сигналы с вьсхоцов сумматоров 30 запоминаются. Тем самым осуществляется операция умножения вектор-строки начальных вероятностей Р(о) || Р (о) II , j 1 ,п на матрицу вероятностей переходов R | г ; || j , i 1 , п. Сигналы, записанные в регистрах 32 памяти, ( ЭНОГ1ЯТСЯ р кными вероятностям Pj(k) нахождения точки цепи в .-ос- толниях j 1,п после k-1 шагов.

С п ;1ходом пятого тактового им- пульс, сигнал 1 появляется на пятом выходе регистра 28 сдви -а. Этот сигнал через выход 7 блока 1 синхронизации и далее через входы 15j блоков 2.моделей вершин поступает KI входа сбнуления регистров 33 памяти и обнуляет их.

С пр ходом шестого тактового им-- пульса появляется НА шестом выходе регистра 28 сдьнга сигнал Этот сигнал рь ход 8 блока 1 синхро- ничлщ, входы 16 j блоков 2 моделей верш,и поступает на вхгды элементов ИЛИ 34 и входы элементов ИЛИ 35. С выхода элементов ИЛИ 34 сигналы поступают на входы считывания регистро 32 памяти. При этом с их выходов величины, равные вероятностям P|(k), j 1,n , поступают через элементы ИЛИ 36 на информационные входы регистров 33 памяти и по сигналам с выходов -элементов ИЛИ 35 запоминаK TCj .

С п; н содом гсдьмого тактового им- появляется 1 на седьмом выходе регистра 28 сдвига. Этот сигнал поступав- т информационный вход этого регистр, и на счетный вход счетчик; 27 числа шагов, уменьшая его ccrje гтпс па единицу. На этом перрнй работы устройства заканчивается .

Второй и последующие до k тп-1 циклы идентичн порвому, та исключением т-о, что первый и второй тактовые импульсы не приводят к по- ячленитс сигп,пов на пчходах 3 и 4

блока 1 синхронизации, так как контакты ключей 25 и 26 разомкнуты.

Последний m -и цикл отличается от предыдущих тем, что при его завершении счетчик 27 числа шагов обнуляется и на его выходе переноса появляется сигнал 1, который через разделительный диод 29 поступает на

Q счетный триггс, К s ,-.Т°ВРДИТ его в состояние О. При этом сигнал на прямом выходе триггера 20 снимается, контакты ключа 2) размыкаются и отключают генератор 22 тактовых им5 пульсов. На инверсном выходе триггера 20 появляется сигнал J, который поступает на выход 9 блока 1 синхронизации и далее через входы 17j блоков 2 моделей вершин на управляющие ,вхоQ ды ключей 37, контакты которых подключают выходы регистров 32 памяти к информационным выходам устройства. Этот же сигнал, через элементы ИЛИ 34 поступает на входы считывания ре5 гистров 32 памяти. Таким образом, устройство выполняет операцию вычислений по формуле (1)

Формула изобретения

0

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

0 ИЛИ, причем выход сумматора соединен с информационным входом первого регистра памяти, выход которого соединен с информационным входом первого ключа и с первым входом первого эле5 мента ИЛИ, второй вход которого соединен с выходом второго ключа, информационный вход которого является входом задания начальных условий устройства, управляющий вход первого клюQ ча соединен с первым выходом блока синхронизации и с первым входом второго элемента ИЛИ, второй вход которого соединен с вторым выходом блока синхронизации и с первым входом TpeTbtg его элемента ИЛИ, второй вход которого соединен с третьим выходом блока синхронизации и с управляющим входом второго ключа, выход первого элемента ИЛИ соединен с информационным

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

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

5

5 0

0

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

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

фиг. 2