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

(11) 645162 ОП ИСААКИЕ ИЗОБРЕТЕН ИЯ Сове Советских Социалистических Республик(23) Приоритет - (43) Опубликован СССР по делам иэобретеиий и открытий(72) Авторы изобретени В, М, Глушань и Б, Я. Буянов аганрогский радиотехнический институт имени В. Д, Калмыкова) ВЕРОЯТНОСТНЪй АВТ Изобретение относится к области вычислительной техники и может быть использовано для моделирования сложных стохастических процессов и систем, для построения специализированных вычислительных устройств.Известно устройство, предназначенное для формирования цепей Маркова. Однако оно оказывается чрезмерно сложным в настройке на заданную матрицу переходных вероятностей 11.Наиболее близким техническим решением к данному изобретению является вероятностный автомат 2, содержащий генератор пуассоновского потока импульсов, регистр сдвига, генератор тактовых импульсов, блок элементов И, выходы которого подключены к первым входам блока запоминающих логических элементов, состоящего из элементов ИЛИ и триггеров.Недостатком известного вероятностного автомата является сложность настройки на заданную матрицу переходных вероятностей. Эта сложность обусловлена тем, что заданная вероятность появления импульса на соответствующем выходе обеспечивается изменением времени стробирования ключа, соединенного с этим выходом, и заполнением этого временного промежутка случайными импульсами. При таком способе вероятности возбуждения выходов автомата являются нелинейными функциямидлительностей стробирующих временныхинтервалов. Поэтому при каждой смене5 матрицы переходных вероятностей необходим трудоемкий предварительный расчет.Кроме того, состояния вероятностногоавтомата являются нетактируемыми, т. е,сигнал на выходных шинах появляется в10 случайный момент времени и имеется аппаратурная избыточность за счет использования счетчика, регистра сдвига, а также двухлинеек запоминающих логических элементов.Целью изобретения является упрощениеустройства, путем упрощения настройки назаданную матрицу переходных вероятностей и обеспечение опроса состояний автомата в тактовые моменты времени,20 Эта цель достигается тем, что автоматсодержит элемент запрет, вход которогосоединен с выходом генератора пуассоновского потока импульсов, а выход - со входом регистра сдвига, матрицу логических25 элементов, каждый столбец которой состоит из и а-входовых элементов ИЛИ и п 2 входовых элементов И, первый вход каждого из которых соединен с выходом одногоиз а-входовых элементов ИЛИ, а второй30 вход - с соответствующим выходом реги5560 65 стра сдвига, блок элементов ИЛИ, входы которого подключены к выходам элементов И соответствующего столбца матрицы логических элементов, а выходы соединены с первыми входами блока элементов И, вторые входы которых соединены со вторым входом элемента запрет и выходом генератора тактовых импульсов, выходы блока элементов И соединены с первым входом соответствующего триггера блока запоминающих логических элементов, выходы триггеров являются выходами блока и подключены к входам и-входовых элементов ИЛИ матрицы логических элементов и к входам элементов ИЛИ данного блока, выход каждого элемента ИЛИ блока запоминающих логических элементов подключен к второму входу соответствующего триггера данного блока.Сущность изобретения состоит в следующем. С помощью матрицы логических элементов выходы равновероятностного (1,й) -полюсника объединяются, обеспечивая заданную вероятность возбуждения выходных шин устройства. Цепи обратной связи, соединяющие выходы устройства со входами и-входовых элементов ИЛИ посредством контактов, обеспечивают формирование всех строк матрицы переходов заданого вероятностного автомата.Смена матриц переходов осуществляется организацией соответствующих обратных связей замыканием и размыканием контактов в матрице логических элементов.Вероятности возбуждения выходов устройства являются линейной функцией числа объединяемых выходов равновероятностного (1, й)-полюсника. Поэтому набор заданной матрицы вероятностей переходов осуществляется очень просто без предварительных расчетов. При этом точность установки вероятности возбуждения любого вы 1хода будет равна КР = - ; - , где и - чис 2 ило выходов вероятностного (1, Й) -полюс- ника.Структурная схема устройства приведена на чертеже. Устройство состоит из генератора 1 пуассоновского потока импульсов, элемента запрет 2, регистра 3 сдвига, матрицы 4 логических элементов, блока 5 элементов ИЛИ, генератора б тактовых импульсов, блока элементов И, блока 8 запоминающих логических элементов, каждая ячейка которого состоит из элементов ИЛИ 8 - 8 и триггеров 9, - 9.Соединенные последовательно генератор 1, элемент запрет 2 и регистр сдвига 3 образуют равновероятностный (1, й) -полюсник, первый выход которого соединен с первыми входами элементов И первой строки матрицы 4, второй выход - с первыми входами элементов И второй строки матрицы 4 и т. д. Второй вход каждого элемента И матрицы 4 соединен с соответствующим вы 10 15 20 25 зо 35 40 45 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 на время опроса состояний автомата.Для простоты положим, что вероятностный автомат имеет три состояния и необходимо формировать матрицу переходных вероятностей видаО 1/3 2/3 Р =- 2/3 О 1/3 1/3 1/3 1/3В этом случае соединение выходов триггеров будет такое, как показано на чертеже. Если, например, в некоторый момент опроса тактовым импульсом единица пройдет на триггер 9 то она пройдет через элементы ИЛИ 8, и ИЛИ 8(в данном случае ИЛИ 8 з) на вторые входы соседних триггеров и они окажутся в нулевом состоянии. Таким образом, автомат будет находиться во втором состоянии. Связь выхода тпиггепя 9.со входами элементов ИЛИ матрицы 4 обеспечит появление в следующем такте единицы на выходе триггера 9, с вероятностью 9, и с вероятностью /, на выходе триггера 9 з. То есть будет формироваться вторая строка матрицы Р. В следующем такте будет формироваться строка, равная номеру предыдущего состояния и т. д.Предлагаемое устройство по сравнению с прототипом сокращает в 3 - 4 раза время настройки на заданную матрицу переходных вероятностей, так как исключаются предварительные расчеты, а сама настройка производится очень оперативно. Устройство является более простым, так как из него исключены счетчик и одна линейка запоминающих логических элементов.Формула изобретенияВероятностный автомат, содержащий тенератор пуассоновского потока импульсов, регистр сдвига, генератор тактовых импульсов, блок элементов И, выходы которого подключены к первым входам блока запоминающих логических элементов, состоящего из элементов ИЛИ и триггеров, о тлич а ющий ся тем, что, с целью упрощения автомата за счет упрощения процесса настройки на заданную матрицу переходных вероятностей, он содержит элемент запрет, вход которого соединен с выходом генератора пуассоновского потока импульсов, а выход - со входом регистра сдвига, матрицу логических элементов, каждый столбец которой состоит из и и-входовых элементов ИЛИ и а 2-входовых элементов И, первый вход каждого из ко торых соединен с выходом одного из и-вхо- довых элементов ИЛИ, а второй вход -с соответствующим выходом регистра сдвига, блок элементов ИЛИ, входы которого подключены к выходам элементов И соот ветствующего столбца матрицы логическихэлементов, а выходы соединены с первыми входами блока элементов И, вторые входы которых соединены со вторым входом элемента запрет и с выходом генератора 15 тактовых импульсов, выходы блока элементов И соединены с первым входом соответствующего триггера блока запоминающих логических элементов, выходы триггеров являются выходами блока и подключены к 20 входам и-входовых элементов ИЛИ матрицы логических элементов и к входам элементов ИЛИ данного блока, выход каждого элемента ИЛИ блока запоминающих логических элементов подключен ко второму 25 входу соответствующего триггера данногоблока. Источники информации, принятые во внимание при экспертизе:301, Авторское свидетельство СССР330459, кл. 6 06 6 7/26, 1972. 2. Авторское свидетельство СССР,481901, кл. б 06 Р 15/20, 1972.