Вероятностный автомат Советский патент 1979 года по МПК G06F7/70 G06F17/18 G06F15/173 

(54) ВЕРОЯТНОСТНЫЙ АВТОМАТ

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

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

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

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

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

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

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

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

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

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

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

Соединенные последовательно генератор J, элемент «запрет 2 и регистр сдвига 3 образуют равновероятностный (1, k)-noлюсник, первый выход которого соединен с первыми входами элементов И первой строки матрицы 4, второй выход - с первыми входами элементов И второй строки матрицы 4 и т. д. Второй вход каждого элемента И матрицы 4 соединен с соответствующим выходом элемента ИЛИ. Выходы всех элементов И каждого столбца матрицы 4 объединены соответствующим элементом ИЛИ блока 5. Выход каждого элемента ИЛИ блока 5 соединен с первым входом соответствующего элемента И блока 7, второй же вход каждого из этих элементов И и второй вход элемента «запрет 2 соединен с выходом генератора 6. Выход каждого элемента И блока 7 соединен с единичным входом соответствующего триггера блока 8. Второй вход каждого триггера соединен с выходом соответствующего элемента ИЛИ.

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

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

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

О 1/3 2/3 2/3 О 1/3

Р 1/3 1/3 1/3

В этом случае соединение выходов триггеров будет такое, как показано на чертеже. Если, например, в некоторый момент опроса тактовым импульсом единица пройдет на триггер 92, то она пройдет через элементы ИЛИ 8i и ИЛИ 8п (в данном случае ИЛИ 5з) на вторые входы соседних триггеров и они окажутся в нулевом состоянии. Таким образом, автомат будет находиться во втором состоянии. Связь выхода тоиггепя .9г,