Генератор цепи Маркова Советский патент 1984 года по МПК G06F7/58 

I Изобретение относится к вычислительной технике к может быть испол зовано при решении рзь гичных вероя ностных задач ,особенно задач статического моделирования. Известно устройство для моделирования -цепей Маркова, содержащее первичный источник случайных сигнал схему формирования слут1айных сигнал с произвольным законом распределения, заиоиинающее устройство н устройство управления. Исходные данные определенным образом отображаются в таблице состояний детерминированного автомата, которая записывается в запоминающее устройство. Каяодое последующее состояние цепи Маркова получается .путем случайной выборки его из запоминающего устройства по адресу, определяемому предыдущим состоянием цепи и случайным сигналом, поступающим от первичного источника С 3 Недостаток устройства зактиочается в том, что для обеспечения его 1эаботы гшобходимо сложное устро ство управления и запоминающее устройство с большим объемом памяти, Это приводит к значительному усложнению устройства моделирования цепей Маркова (особенно неоднородных) и к снижен1-по его быстродействия„ Известно также устройство для получения случайных процессов марковского типа, содержащее первичный источник случайных сигналов, веро™ ятностный распределитель и функциональный преобразователь. Каждое пос ледующее состояние цепи- формируется вероятностным распределителем согла но команде J получаемой от фуикционапьного преобразователяS который преобразует предьщущш сигнал з соо ветствии с исходными данными цепи М кова „ Несмотря на некоторое :|,/- 1еньшенис объема необход1- мой памяти, применение фуикционального преобразова еля усложняет устройство (особенно при моделировании неоднородной цепи Маркова) и уменьшает его быстродей-стБие, что является существенньм недостатком известного устройст)за. Наиболее близким к предлагае1---10 му является генератор цепи Маркова содержащий шифратор группа выходов которого соединена с группой входов нероятностнсго (1 .) - пол осника, соответственно, вход ОПРОС кото-12роге объединен с входом блока управления и подключен к вькоду первичного источника случайных сигналов, а группа выходов вероятностного С1 51) - полюсника соединена с группой информационных входов блока памяти соответственно, первый и второй считывающие входы которого подключены соответственно к первому и второму выходам блока управления, третий вькод которого подключен к стробирующему входу шифратора, группа входов KOTopctPO соедипена с группой выходов блока памяти соответственно Гз 1, Данное устройство, формирующее однородную цепь Маркова, принципиаль.но может быть использовано для формирования одного шага (так7а) неоднородной цепи Маркова. Если цепь Маркова состоит из нескольких шагов, то необходимо синхронизировать работу стольких же устройств, что технически сложно и снижает быстродействие При использозан1- и одного устройства необходимо после каждого шага цепи производить замену шифратора с тем, чтобы в конечном счете матрицы вероятностей переходов, что потребует больших затрат зремеии Цел1; изобретения - повьпиение быстродействия генератора Для достршения поставленной -цели в генератор цепи Маркова, содержащий блок управления, состоящий из переключателя, триггера и ключа, шифратор,, группа выходов которого соединена с группой ззходов вероятностного ( 1,10-полюсникЕ соответственно, вход ОПРОС которого объединен с счетнш входом тзиггера п первым управляющим входом ключа и подключен к выходу первичного источника случаЙ -;ь1Х -сигналов, а группа выходов вероятностного (1 1)-по:шснгп а является группой выходов генератора и соединена с группой инфсрг-1йЦ1 онных входов блоха памяти соответственно, первыр; и второй считываташие вхо.цы которого подключены cooTBercTBei-iHo к едггничному и нулевому ): Ь х:ода,-1 триггера, едини-:пый вход которого подключе:-: к первому выходу п-ареключателя, нхоц к-з- торсгС объединен с ипформациог ты входом ключа и подключен к шине ,, а вгор-ой выход переключателя соединен с Бторьы упран.г;Я|0 1 им входом ключа.

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

На чертеже приведена блок-с-хема генератора.

Генератор содержит первичный йсточник 1 случайных сигналов, вероятностный (1, 1)-полюсн, 2, блок 3 управления, шифратор 4, блок 5 памяти, счетчик 6 и коммутатор 7.

Блок 3 управления содержит ключ 8 триггер 9, шину V 10, переключатель 11.

Блок 5 памяти содержит триггеры 12 и 13.

Вероятностный (1 ,1)-полюсник 2 содержит генератор 14 импульсов, счетчик 15, коммутатор 16, регистр сдвига, ключи 18, элемент ИЛИ 19.

Работает генератор следующим образом.

В исходном положении переключател 11 с шины -ь 10 подается сигнал на включающий вход ключа 8, ключ срабатывает и через него с щины 10 подается сигнал на вход шифратора .4. Иа выходах шифратора Д появляется определенная комбинация сигналов, которые поступают на входы вероятносного (1 ,1)-пол10сника 2, в резуль тате чего последний переключается на формирование позиционных случайных сигналов цепи Маркова с заданными начальными вероятностями. В моменты поступления случайных сигналов от первичного источника 1 на выходах устройства формируются сигпалы с заданными начальными вероятностями. Работа вероятностного (1,1)-полюсника подробно описана в прототи-не.

Сигналы от первичного источника 1 поступают на выключающий вход ключа счетный вход триггера 9 и счетный вход счетчика 6. Но они не срабатывают, так как на включающем входе

ключа 8 имеется постоянный упрагз:1Я1ощий от переключателя 1 1 , питание на триггер 9 не подано, а на управляющем входе шагового счетчика нет сигнала. Триггеры блока 5 срабатывают, так как на их управляющих входах нет сигналов. Таким образом, в исходном положении генератор является датчиком позиционных случайных сигналов с .заданными вероятностями.

При- включении переключателя -11 управляющий сигнал с. включающего входа клю-ia 8 снимается,подается питание на триггер 9 и .сигнал на управ ляющий вход счетчика 6, Очередти м сигналом от первичного источника 1 фop иpyeтcя последними случайныГ позиционный сигнал с шгчальньми вероятностями, являющийся первым cигнaлo цепи Маркова, ключ 8 при этом выключается, что приводит к снятию сигнала с входа шифратора 4. При подаче питания на триггер 9, на одном из его выходов появляется сигнал, который подается на управляющие входы одной из лннсек блока 5 памяти. Очеред ой сигнал от первичНого источника 1 заф1Н :с11руется также в счетчике 6 и на его выxo; e появит.ся сигнал, который произведет пере. ключение цепей .татора 7 так, что выходы блока 5 памухтн будут соединеиы с опреде::сн :1мм входами шифратора. Б момент прохождения первого сигнала цепу Маркова сработает -триггер 12„ С выхода триггера 12 через коммутатор 7 поступает на определеиньм вход шифратора 4, на В1: ходах которого появляется комбинация сигналов, перек.П10чаюи,ая вероятностный (1,1()-11олюс1 ик - 2 на формирование второго С1 гнала цепи Маркова с вереятностя И, заданными матрицей вероятностей переходов на этом шаге.

Далее устройство работает aia- логично.

Предлагаемое устройство повьш1ает быстродействие при фop ipoвaнин неоднородной цепи. Маркова, что существенно уменьи ает машинное время при статическом моделировании, ускоряет исследование сложных автоматизированных систем управления.. Повьш1ение быстродействия достигается за счет введения в устройство шагозого счетчика и коммутатора (первый из них подсчитыва:;т количество сфор

ГЕНЕРАТОР ЦЕПИ, содержащий блок управления,состоящий из переключателя, триггера и ключа, шифратор, группа выходов которого соединена с группой входов в,ероятностного