Вероятностный автомат

Вероятностный автомат

Иллюстрации

Показать все

Реферат

 

(ii) 645l62

ОП ИСААКИЕ

ИЗОБРЕТЕН Ия

Сове Советских

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 22.02.77 (21) 2455327/18-24 с лрисоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 30.01.79. Бюллетень № 4 (45) Дата опубликования описания 22.03.79 (51) М К,п г 6 06 F 15(20

3осудерствеииый кемитет (53) УДК 681.3(088.8) по делам иэобретеиий и открытий (72) Авторы изо бретения

В. М. Глушаиь и Б. Я. Буянов (71) Заявитель

Таганрогский радиотехнический институт имени В. Д. Калмыкова (54) ВЕРОЯТНОСТНЫЙ АВТОМАТ

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

Известно устройство, предназначенное для формирования цепей Маркова. Однако оно оказывается черезмерно сложным в настройке на заданную матрицу переходных вероятностей (1).

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

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

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

Целью изобретения является упрощение устройства, путем упрощения настройки на заданную матрицу переходных вероятностей и обеспечение опроса состояний автомата в тактовые моменты времени, 2О Эта цель достигается тем, что автомат содержит элемент «запрет», вход которого соединен с выходом генератора пуассоновского потока импульсов, а выход — со входом регистра сдвига, матрицу логических 5 элементов, каждый столбец которой состоит из и и-входовых элементов ИЛИ и и 2входовых элементов И, первый вход каждого из которых соединен с выходом одного из и-входовых элементов ИЛИ, а второй зО вход — с соответствующим выходом реги645162

0 1/3 2/3

Р =- 2/3 0 1/3

1/3 1/3 1/3

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

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

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

Вероятности возбуждения выходов устройства являются линейной функцией числа объединяемых выходов равновероятностного (1, k)-полюсника. Поэтому набор заданной матрицы вероятностей переходов осуществляется очень просто без предварительных расчетов. При этом точность установки .вероятности возбуждения любого вы1 хода будет равна AP = —; —, где и — чис2и ло выходов вероятностного (1, k) -полюсника.

Структурная схема устройства приведена на чертеже. Устройство состоит из генератора 1 пуассоновского потока импульсов, элемента «запрет» 2, регистра 3 сдвига, матрицы 4 логических элементов, блока 5 элементов ИЛИ, генератора б тактовых импульсов, блока элементов И, блока 8 запоминающих логических элементов, каждая ячейка которого состоит из элементов ИЛИ

8 — 8„и триггеров 9 — 9„.

Соединенные последовательно генератор

1, элемент «запрет» 2 и регистр сдвига 3 образуют равновероятностный (1, k) -полюсник, первый выход которого соединен с первыми входами элементов И первой строки матрицы 4, второй выход — с первыми входами элементов И второй строки матрицы 4 и т. д. Второй вход каждого элемента И матрицы 4 соединен с соответствующим вы10

Зо

50 ходом элемента ИЛИ. Выходы всех элементов И каждого столбца матрицы 4 объединены соответствующим элементом ИЛИ блока 5. Выход каждого элемента ИЛИ блока 5 соединен с первым входом соответ.ствующего элемента И блока 7, второй же вход каждого из этих элементов И и второй вход элемента «запрет» 2 соединен с выходом генератора б. Выход каждого элемента И блока 7 соединен с единичным входом соответствующего триггера блока 8. Второй вход каждого триггера соединен с выходом соответствующего элемента ИЛИ.

Выход первого триггера 9, через контакты соединен с первыми входами всех элементов ИЛИ матрицы 4 и с первыми входами всех элементов ИЛИ 8, 8„, кроме

«своего» элемента ИЛИ 8ь Выход второго триггера 9 через контакты соединен со вторыми входами всех элементов ИЛИ матрицы 4 и со вторыми входами всех элементов ИЛИ 8ь 8З 8„, т. е. кроме своего элемента ИЛИ 8 . Выходы остальных триггеров соединены в такой же последовательности. Выходы триггеров одновременно являются выходами всего устройства.

Работает устройство следующим образом. Случайные импульсы с генератора 1 через элемент «запрет» 2 поступают на вход (циклического) регистра сдвига 2, в одном из разрядов которого записана единица, а в остальных — нули. Интенсивность случайных импульсов выбирается такой, чтобы записанная единица многократного «обегала» регистр между моментами опроса его состояний тактовыми импульсами. При таком условии единица будет находиться в момент опроса на любом из выходов регистра 3 с равной вероятностью. В зависимости от заданной матрицы переходных вероятностей организуются соответствующие связи триггеров 9> — 9 со входами матрицы

4 замыканием определенных контактов.

Элемент «запрет» 2 необходим для перекрытия выхода генератора 1 на время опроса состояний автомата.

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

В этом случае соединение выходов триггеров будет такое, как показано на чертеже.

Если, например, в некоторый момент опроса тактовым импульсом единица пройдет на триггер 9, то она пройдет через элементы

ИЛИ 8, и ИЛИ 8„(в данном случае ИЛИ

8З) на вторые входы соседних триггеро в и они окажутся в нулевом состоянии. Таким образом, автомат будет находиться во втором состоянии. Связь выхода тпиггепя 9.

645162

Змхп3ы со входами элементов ИЛИ матрицы 4 обеспечит появление в следующем такте единицы на выходе триггера 9> с вероятностью /з и с вероятностью /з на выходе триггера 9З. То есть будет формироваться вторая строка матрицы P. В следующем такте будет формироваться строка, равная номеру предыдущего состояния и т. д.

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

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

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

«запрет», вход которого соединен с выходом генератора пуассоновского потока импульсов, а выход — со входом регистра сдвига, матрицу логических элементов, каждый столбец которой состоит из и и-входовых элементов ИЛИ и и 2-входовых элементов И, первый вход каждого из ко5 торых соединен с выходом одного .из и-ахо- довых элементов ИЛИ, а второй вход— с соответствующим выходом регистра сдвига, блок элементов ИЛИ, входы которого подключены к выходам элементов И соот10 ветствующего столбца матрицы логических элементов, а выходы соединены с первыми входами блока элементов И, вторые входы которых соединены со вторым входом элемента «запрет» и с выходом генератора

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

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

25 входу соответствующего триггера данного блока.

Источники информации, принятые во внимание при экспертизе:

1. Авторское свидетельство СССР № 330459, кл. G 06 G 7/26, 1972.

2. Авторское свидетельство СССР, № 481901, кл. G 06 F 15/20, 1972.