22114

Понятие устойчивости конечного автомата

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Дело в том что триггера в схеме имеет различные времена задержек сигналов обратной связи которые поступают с выходов триггеров на их входы через комбинационную схему II. По этим причинам если при переходе автомата из состояния ai в as должны измениться состояния нескольких триггеров то между выходными сигналами этих триггеров начинаются гонки. изменит свое состояние раньше других триггеров может через цепь обратной связи изменить может изменить сигналы возбуждения на входах других триггеров до того момента как они изменят свои состояния....

Русский

2013-08-04

48 KB

2 чел.

Лекция 17

 

Вторая техническая особенность конечного автомата связана с возможностью возникновения неустойчивых состояний и так называемых «гонок» в автомате. Понятие устойчивости заключается в следующем.

Пусть в графе автомата мы имеем такой участок. Здесь оба перехода (aias) и (as-af) выполняются под действием одного и того же входного сигнала xj. Если длительность синхронизирующего сигнала СИ2 больше времени перехода автомата из состояния ai в состояние as, то сразу после перехода автомата в as может начаться переход в следующие состояния af под действием того же входного сигнала xj. Если длительность синхронизирующего сигнала СИ2 больше времени перехода автомата из состояния ai  в состояние as, то сразу после перехода автомата в as может начаться переход в следующее состояние af под действием того же входного сигнала xj. Таким образом автомат может перескочить состояние as и к моменту времени t+1 оказаться в as, как это требуется по графу, а в af. Состояние as в данном случае будет неустойчивым.

Другой неприятный момент заключается в том, что при работе автомата могут возникать так называемые «гонки» (состязания). Дело в том, что триггера в схеме имеет различные времена задержек сигналов обратной связи, которые поступают с выходов триггеров на их входы через комбинационную схему II. По этим причинам, если при переходе автомата из состояния ai в as должны измениться состояния нескольких триггеров, то между выходными сигналами этих триггеров начинаются гонки. Тот триггер, который выиграет гонки, т.е. изменит свое состояние раньше других триггеров, может через цепь обратной связи изменить может изменить сигналы возбуждения на входах других триггеров до того момента, как они изменят свои состояния. Это, очевидно, может вызвать переход автомата совсем не в то состояние, которое нужно графу. Например. Пусть ai=101, а as=010. Тогда при переходе из ai в as под действием входного сигнала xj меняются состояния всех триггеров. Допустим, что первый триггер изменил свое состояние раньше других. В этом случае автомат окажется в некотором промежуточном состоянии ah=001, и если из этого состояния есть переход под действием сигнала xj в al=011, то автомат в момент времени t+1может оказаться в al, а не в as.

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


Здесь под действием синхронизирующего сигнала СИ1 формируются выходные сигналы Zl(t)  и переключаются триггера первого ряда. Под действием СИ2 состояния триггеров первого ряда переписываются в соответствующие триггера второго ряда. Поскольку СИ2 сдвинуты относительно СИ1, а сигнал обратной связи о состоянии автомата снимается с триггеров второго ряда, то в момент поступления входного сигнала, т.е. в  СИ1, состояние автомата не изменяется и продолжает оставаться прежним до СИ2. Поэтому в такой схеме полностью обеспечивается устойчивость состояний и устраняется влияние гонок. Действительно, гонки сигналов с выходов триггеров второго ряда возможны в момент СИ2, т.е. в момент переключения этих триггеров. Но в момент СИ2=1, СИ1=0 и следовательно эти гонки никак не могут повлиять на состояния триггеров первого ряда, которые переключаются в момент СИ1=1. Также не будет и неустойчивых состояний, поскольку автомат не может проскочить за один такт через одно состояние и перейти в следующее, ибо в момент перехода триггеров первого ряда в новое состояние, т.е. в СИ1, состояние триггеров второго ряда не меняется (СИ2=0) и, следовательно, не могут измениться и сигналы возбуждения триггеров первого ряда, которые зависят от состояния триггеров второго ряда. Поэтому автомат не может проскочить состояние.

С целью упрощения построения схем автоматов, имеющих двойную память, промышленность выпускает специальные двухступенчатые триггера. Рассмотрим работу такого триггера на примере двухступенчатого JK-триггера.

Особенностью двухступенчатого триггера является то, что он меняет свое состояние в момент окончания синхронизирующего сигнала С. В результате этого во время действия сигнала С выходные сигналы триггера не меняются, а происходит запись информации в триггер Т1. В момент С=0 состояние триггера Т1 переписывается в Т1’.

Q

 

_

Q

 

J

Q

C _

Q

K


Комбинационная схема
II

&

&

T1

TR

&

&

&

&

R

S

T

R

S

T

Комбинационная схема I

&

&

TT

J

C

K

S

R

T1

&

&

T1

J

K

&

&

1


 

А также другие работы, которые могут Вас заинтересовать

46269. Зависимость психического развития от содержания структуры деятельности ребенка. Понятие ведущей деятельности. (Эльконин, Леоньтев) 13.07 KB
  Зависимость психического развития от содержания структуры деятельности ребенка. Понятие ведущей деятельности. То что непосредственно определяет развитие психики ребенка это сама его жизнь развитие реальных процессов этой жизни иначе говоря развитие деятельности ребенка как внешней так и внутренней. Значит в изучении развития психики ребенка следует исходить из анализа развития его деятельности так как она складывается в данных конкретных условиях его жизни.
46270. Electricity Basics 13.06 KB
  Electricity is mde by converting some form of energy into flowing electrons t the power plnt. The type of power plnt depends on the source of energy used: therml power col oil gs nucle r underground stem solr power photovoltic kinetic power wter wind nd chemicl power fuel cell. This system enbles power plnts I nd end users to be connected together. Wtt W is unit mesure of electric power tht depends on mps nd volts.
46271. Языковая просодия, уровни изучения. Суперсегментные звуковые единства. Словесное ударение основные виды 13.05 KB
  Словесное ударение основные виды. Уровни изучения: словесное ударение и фразовая интонация Ударение в слове выделение фонетическими средствами одного слога в составе группы слогов. Виды ударений: экспираторное выдыхательное динамическое силовое ударение за счёт силы выдоха долготное тоновое ударение за счёт восходящего нисходящего комбинированного языкового тона на фоне нейтрального или др. prosodi припев ударение наслаиваются на цепочку сегментов слогов слов фраз предложений.
46272. Понятие субъекта в концепции Ж.Пиаже 13.02 KB
  Понятие субъекта в концепции Ж. Первоначально ребенок воспринимает мир как индивид который не знает себя в качестве субъекта не понимает своих собственных действий и поэтому приписывает реальности свои субъективные ощущения даже не подозревая об этом. По Пиаже ребенок на ранних стадиях развития воспринимает мир как солипсист он игнорирует себя в качестве субъекта и не понимает собственных действий. Конструкция представления об окружающем мире о реальности у ребенка в первые годы...
46273. Ж.Пиаже Как дети образуют математические понятия 13.01 KB
  Пиаже Как дети образуют математические понятия. Младшие дети думают что число изменилось. Но дети в возрасте около 7 лет уже понимают что перемещение не меняет число бусинок. Дети должны уловить принцип сохранения количества прежде чем они могут образовывать понятия числа.
46275. The category of mood 12.83 KB
  There re three moods in English the indictive mood the impertive mood nd the subjunctive mood.The indictive mood form shows tht wht is sid must be regrded s fct s something which hs occurred or is occurring t the moment of speking or will occur in the future. Therefore the indictive mood hs wide vriety of tense nd spect forms in the ctive nd pssive voice.
46276. Кризис семи лет 12.81 KB
  Основная симптоматика кризиса:Потеря непосредственности: между желанием и действием вклинивается переживание того какое значение это действие будет иметь для самого ребенка;Манерничание: ребенок чтото из себя стоит чтото скрывает уже душа закрыта;Симптом горькой конфеты: ребенку плохо но он старается этого не показывать;Трудности воспитания: ребенок начинает замыкаться и становится неуправляемым. Переживания приобретают смысл сердящийся ребенок понимает что он сердит благодаря этому у ребенка возникают такие новые отношения к...
46277. Эльконин Д.Б. «К проблеме периодизации психического развития в детском возрасте» 12.75 KB
  Некоторые считали что в этом возрасте важно развитие сенсомоторноманипулятивной деятельности. Однако решили что речь используется ребенком в данный период возраста для налаживания сотрудничества с взрослыми в предметной деятельности. В игровой деятельности ребенок моделирует отношения между людьми. Большие трудности представляло выделение ведущей деятельности у подростков.