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

 

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

СОЮЗ СОВЕТСНИХ

СОЩУР ЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (11) Ai (51) 5.G 06 G 7/122

"- а3щ

ОПИСАНИЕ ИЗОБРЯ ЩНЩ)

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

К=1

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯ1к1

ПРИ ГКНТ СССР

1 (21) 4413245/24-24 (22) 10.03.88 (46) 07.01.90. Бюл. 9.1 (72) В.Г. Анисимов, E.Ã.Анисимов, В.А.Бутенко и В,М. Крикун (53) 681 ° 3(088.8) (56) Авторское свидетельство СССР

Ф 590769, кл. G 06 G 7/48, 1976, Авторское свидетельство СССР

Р 763911, кл. С 06 G 7/122, 1 980. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ ОДНОРОДНОЙ

ДИСКРЕТНОЙ ЦЕПИ MAPKOBA (57) Изобретение относится к вычислительной технике и предназначено для определения вероятностей состояний однородных "дискретных цепей

Маркова. Устройство также,:может применяться для выполнения операции

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

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

В устройстве для определения вектора P (m) = (Pj(m) f, j = 1, и вероятностей состояний цепи используется изоморфиэм матрицы R 11 r„;11

j, i 1, и вероятностей переходов и размеченного графа состояний этой цепи. Определение вектора вероятно2 перемножения матриц. Цель изобретения — повышение быстродействия при вычислении вероятностей состояний однородной дискретной цепи Маркова.

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

1 з.п.ф-лы, 3 ип. стей . состояний однородной дискретной цепи Маркова после m шагов при этом сводится к вычислению по формуле

fYl

P(m) = P(o)R = P P(k-1)В., (1) где Р(о) 11 Р, (о)п

1 1, и — вектор начальных вероятностей состояний;.

P(k-1) = !1Р;(- ) Ilp

) = 1, и — вектор вероятностей состояний после k-1 шагов.

Промежуточные результаты вычислений (т.е. P(k) = P(k-1) R, k = 1, и) хра1534472 нятся в регистрах памяти, обеспечиваю!цих их хранение без искажений.

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

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

Каждый блок 2 модели вершины имеет группу информационных входов 10j, l,n (n — количество блоков в группе), семь входов l lj- 17) и два информационных выхода !8j и 19j

Выходы 3-9 блока 1 синхронизации соединены соответственно с входами 11jl7j блоков 2 моделей вершин.

Блок ) синхронизации предназначен для управления работой устройства в процессе вычисления векторов состояний цепи Маркова. Он содержит 2 триггер 20, ключ 21, генератор 22 тактовых импульсов, счетчик 23, ключи 24-26,. счетчик 27 числа шагов, регистр 28 сдвига, разделительный диод 29. Каждый из блоков 2 моделей вершин предназначен для моделирования вершин цепи Маркова и вероятностей переходов r из j-й вершигы в

)1

i-ю за один шаг процесса. Он содержит сумматор 30, элемент 31 задержки, регистры 32 и 33 памяти, элементы

ИЛИ 34-36, ключи 37 и 38.

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

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

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

22 тактовых импульсов. С его выхода импульсы поступают на вход регистра

28 сдвига и через замкнутые контакты ключа 24 на счетный вход счетчика

23. Один цикл работы устройства соответствует одному шагу процесса и включает семь тактовых импульсов.

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

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

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

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

0 4 блока 1 синхронизации и далее через входы !2j блоков 2 моделей вер- шин на входы элементов ИЛИ 35 и управляющие входы ключей 38. Сигналы с выходов элементов ИЛИ 35 поступают на входы записи регистров 33 памяти. Контакты ключей 38 замкыкаются и под- ключают входы задания начальных условий через элементы ИЛИ 36 к информационным входам регистров 33 памяти. При этом величины равные .;лементам Р (о) век. у тора Р(о) = Р;(о) II, j = l,,п, поступают в регистры 33 памяти и запом;п аются в них, С приходом третьего тактового импульса сигнал "1" появляется на третьем выходе регистра 28 сдвига„ с которого поступает на выход 5 блока 1 синхронизации и далее через входы !3j блоков 2 моделей вершин на входы обЩ нуления регистров 32 памяти и обнуляет их.

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

2 моделей вершин поступает на соответствующие информационные входы

15344

l0j этих блоков. Эти величины умножаются на соответствующие коэффициенты r ", 3, 1 = 1,n, равные вероятностям переходов из j-х вершин

5 графа цепи в r-e, суммируются в сумматорах 30 и поступают на информационные входы регистров 32 памяти.

При поступлении сигналов с выходов элементов 31 задержки на входы записи регистров 32 памяти сигналы с выходов сумматоров 30 запоминаются.

Тем самым осуществляется операция умножения вектор-строки начальных вероятностей P(o) = tf P (о) II, j = 1,n на матрицу вероятностей переходов

К = ff r>, !!,j, i = 1, и. Сигналы, записанные в регистрах 32 памяти, становятся равными вероятностям

Р (k) нахождения точки цели в сос- 20 тояниях j = 1,п после k-1 щагов.

С пр-.тходом пятого тактового импульс сигнал "1" появляется ка пятом выходе регистра 28 сдвига. Этот

"игнал через выход 7 блока синхро- 25 низации и далее через входы 15j блоков 2.моделей вершин поступает ка входы обнуления регистров 33 памяти и обнуляет их.

С прпходом шестого тактового им- 30 пульса появляется ка шестом выходе регистра 28 сдвига сигнал"!". Этот сигнал через выход 8 блока 1 синхронизацк: и входы !6j блоков 2 моделей вершин поступает на входы элементов

ИЛИ 34 и входы элементов ИЛИ 35. С выхода элементов ИЛИ 34 сигналы поступают на входы считывания регистров

32 памяти. При этом с их выходов величины, равные вероятностям PI(k), 40 — и, поступают через эле енты

ИЛИ 36 на информационные входы регистров 33 памяти и по сигналам с выходов элементов ИЛИ 35 запоминаются i 45

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

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

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

Последний т -й цикл отличается от предыдущих тем, что при его завершении счетчик 27 числа шагов обнуляется и на его выходе перекоса появляется сигнал "!", который через pasделительный диод 29 поступает на счетный вх „, триго е..-;- 20 и и водит

ere в состояние "0". При этом сигнал

"1" на прямом выходе триггера 20 снимается, контакты ключа 21 размыкаются и отключают генератор 22 тактовых импульсов. На инверсном выходе триггера

20 появляется сигнал "1", который поступает на выход 9 блока 1 синхронизации и далее через входы )7j блоков

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

Этот же сигнал, через элементы ИЛИ

34 поступает ка входы считывания регистров 32 памяти. Таким образом, устройство выполняет операцию вычислений по формуле (!)

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

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

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

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

2. Устройство по и. l, о т л и— ч а ю щ е е с я тем, что блок синхронизации состоит из генератора так- 25 товых импульсов, .четырех ключей,триггера, разделительного диода, двух счетчиков, регистра сдвига, причем вход пуска блока соединен со счетным входом триггера и с катодом pGs $Q делительного диода, аноц которого соединен с выходом переполнения первого счетчика, счетный вход которого соединен с выходом старшего разряда регистра сдвига и с его информационным входом, прямой выход триггера соединен с управляющим входом первого ключа, информационный вход которого соединен с шиной единичного потенциала, выход первого ключа соединен с входом запуска генератора тактовых импульсов, выход которого соединен с входом регистра сдвига и с информационным входом второго ключа, выход которого соединен со счетным входом второго счетчика, старший разрядный выход которого соединен с управляющими входами второго, третьего и четвертого ключей, первый разрядный выход регистра сдвига соединен с информационным входом третьего ключа, выход которого является первым выходом блока, вторым выходом которого является выход четвертого ключа, информационный вход которого соединен с вторым разрядным выходом регистра сдвига, третий, четвертый, пятый и шестой разрядные выходы которого являются соответственно третьим, четвертым, пятым и шестным выходами блока, седьмой выход которого является инверсным выходом триггера.

1534472 Составитель Я, Феликсон

Редактор И. Тупица Техред М.Коданич Корректор Л.Вескид . (°

Заказ 43 Тираж 549 Подписное

ВНИИПИ Государственного .комитета по.изобретениям и открытиям при ГКНТ СССР

113035, Москва, Б-35, Раушская наб., д. 4!5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101