Генератор цепи маркова

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

3 у G.06 F 7/58

ГОСУДАРСТВЕННЬФ НОМИТЕ 1; СССР

ПО ДЕ11АМ ИЗОБРЕТЕНИЙ И ОТНРЬ1ТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ. (21) 3404981/24-24 (22) 02.03.82 (46) 30.11.84.. Бюл. № 44 (72) А.Е. Богатых (53) 681.325(988.8) (56) 1. Авторское свидетельство СССР

¹ 290281, кл. G 06 F 7/58, 1969.

2. Авторское свидетельство СССР № 336671, кл. G 06 F 7/58, 1970.

3. Авторское свидетельство СССР № 481901, кл. G 06 F 7/58, 1972 (прототип). (54) (57) ГЕHEPATOP ЦЕПИ, содержащий блок управления, состоящий из переключателя, триггера и ключа, шифратор, группа выходов которого соединена с группой входов вероятностного (1,k) — полюсника соответственно, вход "ОПРОС" которого объединен с счетным входом триггера и первым управляющим входом ключа и подключен к выходу первичного источника случайных сигналов, а группа выходов вероятностного (1, %) — полюсника является группой выходов генератора и соединена с группой информационных входов блока памяти

„„ЯЦ„„1126951 А соответственно> первый и второй считывающие входы которого подключены соответственно к единичному и нулевому выходам триггера, единичный вход которого подключен к первому выходу переключателя, вход которого объединен с информационным входом ключа и подключен к шине "+, а второй выход переключателя соединен с вторым управляющим входом ключа, выход которого подключен к стробирующему входу шифратора, о т л и ч а юшийся тем, что, с целью повышения быстродействия, он содержит коммутатор и счетчик, счетный вход . которого объединен с счетным входом

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

1 1126

Изобретение относится к вычислительной технике и может быть исиользовапо при решении р,.:.ли)ных вероятностных задач, ocoGeHHQ задач статического моделирования.

Известно устройство для моделирования цепей Маркова, содержащее первичный источник случайных сигналов, схему формирования случайных сигналов с произвольным законом pacIIpepe!-. ния, запоминающее устройство и -:стройство управления. Исходные данные определенным образом отобража)отся в таблице состояний детерминированного автомата. которая записывается в запомина)ощее устройство. Каждое последующее состояние цепи Маркова получается .путем случайной выборки его из запоминаюшего устройства IIo

Ъ адресу, определяемому предыдущим состоянием цепи и случайным сигналом, поступающим от г1ервичиого ис-точника (1 g, Недостаток устроиства закл)очается в том, что для обеспечения

25 его работы необходимо сложное устроиство управления и запоминающее устройство с большим объемом памяти.

Это приводит к значительному усложнению устройства моделирования цепей Маркова (особенно неоднородных) и к снижению его быстродействия.

Известно также устройство для получения случайных процессов марковского типа, содержащее первичный источник случайных сигналов, веро-ятностный распределитель и функциональный преобразователь. -Каждое по1:-ледующее состояние цепи формируется вероятностным распределителем соглас" l Г но команде, получаемой от функционального преобразователя, который преобразует предыдущий сиг1)ал в соответствии с исходными данными цепи Маркова.

Несмотря на некоторое уменьшение объема необходимой памяти, применение функционального преобразователя усложняет устройство (особенно при моделировании неоднородной цепи

MGpKoBB) и уменьшает е.го бь)стродей-. ствие, что является существенным недостатком известного устройства-., Наиболее близким к предпагаемому является генератор цепи Маркова, содержащий шифра- îð,,группа выходов

КОТОРОГО СОЕДИНЕНа С ГРУППОЙ ВХОДОВ

)зероятностного (1, k) — пол)осника. ooTBeTcTBeHH0, Вхор ОПРОС" кото".

951 2 рого объединен с входом блока управления и подк)поч. н к выходу ГерВичнОГО истОчника случайнь)х сиГналОв

> а группа выходов вероятностного (1, %) — полюсиика соединена с гругпой инфор)ационньгх входов блока паМЯТИ СООТВЕТСТВЕННО ПЕP))b)H И ВТОРОИ считывающие входы которого подключены соответственно к первому и второму выхода) блока у.1равле )ия, третий вьгход которого подключен к стробиру)оцему входу шифратора, группа входов которого соединена с группой выходов блока памяти cooòâåòcòвенно 1.3 3, Данно ус-1 ойстго, ор.: пу -шее однородную цепь Маркова, принципиально может быть использовано для формирования одного ша)а (такта) неодНОРОДной Цепи IQPI(OBB, Ec!II.

Маркова состоит из нескольких шагов, то необходимс синхронизироват;, работу стольких же устройств, )то технически сложно и снижает быстродействие. При )=спользсвании одного устройства необходимо после каждого шага цепи производить замену ши 1)ратора с тем. чтобы в конечном "-Гете мен- .a матрицы вероя "Hocòåé переходов,. что потребует больших затрат вpемe Iи,>

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

Для дос)"ижения поставленной цели в генератор цепи Марков-. содержащий блок унравления, co(тоящий из переключателя, триггер=- ii )Iëiîae, шифратор„ группа выходо-) которого соединена с групг.ой входов )зероятностнОГО (1 1:)-пол)осп1-;1,;. сООтв =; ст— венно, вход "ОПР00" которого объединен с счетн;„:.. входoь триггера I )Iepвым угравля)ощим 1)ходо).: кгюча и подкл)очен к вь)ходу перв)ьчного ис:-о пинка случайны;. сигналсн,. =-- гр,ппа выходов вероятностного (1,1с)-по ))осника является группой выходов генерато ie и сое;:.:,H;Ie а с Гр, пой и)фсрмацио);Них входов блока памяти

CO0TBe1 СТВЕНИО, ПЕРВЬ)и И BTOPой тываюшие;:,ходы котор:ro подключены соотaf тстве11но к един:.:1ноь)у и пуле))о. )у . )ых)ода" 1 Тр! II Гера едини . . )ь;и вход которог0 иодклю;е . . перв );,)у Bf.)>",oäó .;,.- ре к!11 чате))я )- х )ц ко- 01)G1 i o5úeäHHcH с ии(110дмя1)ио .Нь у и и вхОдом ключа и лодклю.-Iен к шин = + а B -opoé выход пе-ек.-о )а -е:я cое„-.:HeH с;:, т01)ым упгавляtñ!!11- .и 1)ходо- 1 к. . о-)а

1126

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

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

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

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

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

12 и 13.

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

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

В исходном положении переключателя

11 с шины "+" 10 подается сигнал 35 на включающий вход ключа 8, ключ срабатывает и через него с шины 10 подается сигнал на вход шифратора .4.

Иа выходах шифратора 4 появляется определенная комбинация сигналов, 40 которые поступают на входы вероятностного (1,%) — палюсника 2, в резуль-. тате чего последний переключается на формирование позиционных случайных сигналов цепи Маркова с заданны- 45 ми начальньп1и вероятностями. Ы моменты поступления случайных сигналов от первичного источника 1 на выходах устройства формируются сигналы с заданными начальными вероятностя- 50 ми. Работа вероятностного (1,%)-полюсника подробно описана в прототи-. пе.

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

951 4 ключа 8 имеется постоянный управ."1яю-. щий сигнал от переключателя 11, питапие на триггср 9 не подано, а на управляющем входе шагсисгс счетчика нет сигнала. Триггеры блока 5 срабатывают, так как на пх управляющих входах пет сигналов.

Таким образом, в исходном положении генератор является датч!I!;см позиционных случайных сигналов с заданными вероятностями.

При включении переключателя .11 управляющий сигнал с. включающего входа кл!о-Ià 8 снимается, падается ьп1тание на триггер 9 и сигнал на управляющий вход счетчика 6. Очеред1нпм сигналом от первичного истачн1п;а формируется после,:и1ий случайньй позиционный сигнал с 1. ачальньпьп вероятностями, являющийся первым сигналом цепи Мар;:сва, ключ 8 прп этом выключается, ч за приводит к снятию сигнала с входа шифратора 4.

При подаче питания н; триггер 9, на одном из ега выхадсв появляется сигнал, который подается на управляющие входы одной из лннеек блока 5 памяти. Очередной сигнал от пер1зичного источника 1 зафиксируется также в счетч11ке 6 и на его выходе псявзг1 ся сигнал, который произведет переключение цепей коммутатора 7 так, что выходы б:гока 5 памят11 будут соединены с слредез:ен1111ми входами ш11фратора. В момент прохождения перззого сигнала цепи Маркова сработает -триггер 12. С вы: ода тр1.ггера 12 через коммутатор 7 пс Tóïàåò сиг11ал на определе1 ньп1 вход шифратора 4, на выходах которого появляется ксмбпнация сигHалсв, IIBpE!кляча1о1цал всроя гностный (1,11)-11слюсник 2 на 1, срмированпе второго сигнала цс 1и Маркс1за . с версятнсст1111и, заданными матр1ьцей вероятностей переходов на зтсм шаге.

Далее устройство работает ан",— логично, Предлагаемое устройство повышает быстродействие при фсрмпрова IIIII неоднородной цепи Маркова, что существенна уменьшает машинное в; емя при статическом моделировании, ускоряет исследование сложных автоматизированных систем управления. Павьппение быстродействия достигается за счет введения в устройство шагового счетчика и коммутатора (первьпй из них подсчитывает количество сфорИ»((М»((.ХЮ. » ФИ (Г

» Р" (//Г

t I

1 1 з1 с1 1. И 11 ка

Зяюа "6(1 /

„„.„,н, „,,—,...-...„,, . / Сг iI) ., IOC (Ва, " 5., -::..(1(. C . . (.é (аб. „д, Ч(/ В

"., II IIC IIr: Е ф((В(1Ь1а-,1 !Ц1, 1(;. 1 Е,:,— г у-,"; 1 (;,В t JI „1(1рОЕ(К"! вал, мированных шагов цепи Иарков . и .-а основе э тои и118)0 pi(t =- I vTIT)(tH J1>+t т работой коммутатора „который o-,I. ñпечивает коммутацию входов ш.:.фратора управления, в котором закодиро- 1Е JQKTО1 . ((1 „1 pT> 17, ((, Е r В ц

Dp.íû все матрицы вероятностей переходов), :. аким образом, предлагаемое

,:тройство формирует не только однород... 1с, но и неоднородные цепи ркова.