CURS PDN

Automate Finite

Definitie: Structura CLS sincron care contine in bucla de reactie un circuit de memorare/registru (care la randul sauconstituie un CLS), este referinta printermenul de automat (finit) sau cu abreviatia FMS (Finite State Machine).

Fig. 1. Circuitul secvential sincron: a) Structura de principiu; b) Structura de principiu pentru CLS sincron cu iesire intarziata.

a) b)

Definitii si clasificari ale automatelor

Definitia unui automat finit este similaracu cea a unui CLS asincron, cu deosebirea ca timpul nu mai este o variabila continua ci discreta, multiplu de perioada semnalului de ceas, iT, adicavariabilele circuitului sunt esantionate, dar pe fronturile active:

A=(X,Y,Q,f,g) (3.1)

Definitie: Daca pentru oricare configuratiede intrare si de stare prezenta functiilede transfer, f si de tranzitie, g, au cardinalul unitate (contine un singurelement), atunci automatul estedeterminist, altfel este nedeterminist.

1,,1,,, xqgxqfXxQq

Definitie: Un automat A este finit dacacele trei multimi X, Y si Q sunt finite.

Definitie: Un automat A autonom, sauorologiu, este un automat la care multimea finita a intrarilor este cardinalulunitate |X|=1. Automatul genereaza variatii la iesirefara sa se modifice configuratia de intrare.

Definitie: O evolutie/traiectorie a automatului A este un sir de stariinlantuite q0 ->q1-> ->qi->qi+1->, iarstarea q0 este starea initiala a evolutiei. O evolutie cu proprietatea:

este o evolutie admisibila. iiiii XqgqXXQq ,,, 1

Definitie: Totalitatea starilor din care poateporni automatul este multimea starilorinitiale .In functie de cardinalul multimii Q0automatele pot fi:

- automat cu o singura stare initiala- automat cu mai multe stari initiale- automat neinitial (toate starile pot fi

initiale), .

QQQ 00 ,

1, 00 QQQ

1, 00 QQQ

QQ 0

Obs: Intr-o stare initiala nu se ajunge printr-o evolutie generata de configuratii din multimea semnalelor de intrare X ciprintr-o alta comanda exterioara, de exemplu printr-o comanda de initializaresau prin conectarea la tensiune se genereaza starea initiala.

Definitie: O stare a automatului esteconsiderata inaccesibila daca oricaretraiectorie in spatiul starilor ce pornestedin stari initiale nu o contine.

Obs: De exemplu, daca pentru un automat cu trei biti de stare z2z1z0 pot exista opt stari q0,q1,q2,q3,q4,q5,q6,q7, dar suntdefinite numai cinci stari, q0q4, in functionarea automatului atunci cele treistari, q5, q6 si q7 sunt inaccesibile

Definitie: Doua stari qi si qj suntechivalente daca pentru oricareconfiguratie de intrare aplicata X se genereaza aceleasi iesiri, iar starileurmatoaresunt identice sau echivalente.

ji qq

XqgqXqgq jjii ,,, 11

XqgXqgXqfXqf jiji ,,;,,

Obs: Daca un grup de stari se demonstreaza ca sunt echivalente, toatestarile acelui grup sunt substituite printr-osingura stare, astfel reducandu-se numarul total de stari ale automatului.

Definitie: Un semiautomat, SA, estedefinit prin tripletul:

SA = (X, Q, g)Obs: Structural, semiautomatul se obtine

prin eliminarea din structura automatuluia partii care calculeaza functia de transfer, f.

Automat Mealy si Moore

Definitie: Un automat Mealy este definitprin cvintuplu A=(X, Y, Q, f, g) cu:

Definitie: Un automat Moore este definitprin cvintuplu A=(X, Y, Q, f, g) cu:

QQXgYQXf

::

QQXgYQf

::

Obs: La automatul Mealy parteacombinationala calculeaza atat functia de transfer f cat si cea de tranzitie g pe bazaprodusului cartezian XxQ.

La automatul Moore functia de tranzitie g se calculeaza la fel ca la automatul Mealy, pe baza produsuluicartezian XxQ, pe cand functia de transfer f este calculata doar pe bazastarii prezente Q.

Obs: Iesirea automatului Moore estedependenta de intrare doar prinintermediul tranzitiilor realizate in spatiulstarilor.

Fiecare din aceste doua tipuri de automate poate fi realizat cu functionareimediata sau intarziata, vezi figuraurmatoare.

Fig. 2. Variante de automate Mealy structuratepe baza unui semiautomat, SA:

a) Structura fundamentala pentru automatul Mealy imediat; b) Structura fundamentala pentru automatul Mealy cu intarziere.

a) b)

Fig. 2. Variante de automate Moore structuratepe baza unui semiautomat, SA:

a) Structura fundamentala pentru automatul Moore imediat; b) Structura fundamentala pentru automatul Moore cu intarziere.

a)

b)

Descrierea automatelor cu intarziere/imediat Automatul Mealy imediatStructura acestui automat se obtine prin completareasemiautoamtului SA cu CLC2 care calculeaza iesireaY(iT) pe baza produsului cartezian dintre starea prezentasi intrarea prezenta.

Y(iT)=f(X(iT), q(iT))Iesirea Y(iT) citita inainte de consumarea perioadei de regim tranzitoriu va fi afectata de hazard. Daca intrareanu este sincronizata, ci se modifica asincron oricand in intervalul iT si (i+1)T, aceste modificari se simt in iesire.

Automat Mealy cu intarziereCompletarea SA se face atat cu circuitul CLC2 pentrucalculul functiei de transfer, f, cat si cu un registru, Reg2, pentru memorarea iesirii Y(iT). Introducea unui registruva face ca modificarile provocate de iesirea Y(iT) peintervalul iT-(i+1)T, datorate regimului tranzitoriu, de la o intrare sincronizata, sau datorate variatiilor intrarii, de la o intrare asincrona, sa nu mai poata ajunge la iesire. Valoarea iesirii este asignata, doar in momentele de aplicare a frontului activ de ceas la Reg2, cu valoareacalculata pe baza intrarii si starii anterioare.

Y((i+1)T):=f(X(iT), q(iT)),deci iesirea reflecta intrarea cu o intarziere de un tact.

Automatul Moore imediatDeoarece la acest automat iesirea se calculeazaca functie numai de stare prezenta, la SA se adaugacircuitul CLC2 care are ca intrari doar starea prezenta. Deoarece in starea prezenta se reflecta intrareaanterioara si nu cea prezenta, iesirea este intarziata cu un tact fata de intrare (la fel ca la automatul Mealy cu intarziere). Deci pentru intrarea prezenta se obtineiesirea numai peste un tact.

Y((i+1)T):=f(q((i+1)T))=f(g(X(iT), q(iT)))

Desi se obtine o izolare a iesirii fata de intrare, nu exista doarCLC2 intre intrare si iesire, totusi automatul Moore imediatpoate genera hazard la iesire. Hazardul este generat de faptulca circuitul CLC2 poate avea de la intrarea (iesire Reg1) panala iesirea sa un numar diferit de niveluri logice pentru fiecaretraseu de transfer. Foarte frecvent, la acest tip de automat se elimina circuitul CLC2, iesirea fiind identica cu starea YQ, ceea ce elimina hazardul combinational din iesire.Comportamental, un automat Moore imediat poate fi echivalentcu un automat Mealy cu intarziere deoarece la ambele iesireacalculata pe baza starii prezente si a intrarii prezente va fiasignata la iesire, doar pe urmatorul front activ de ceas.

Automatul Moore cu intarzierePentru a se elimina posibilitatea de hazard pe iesire de la automatul Moore imediat se adauga pe iesire un registru, Reg2, obtinandu-se automatul Moore cu intarziere. La intarzierea iesirii fata de intrare cu un tact de la Moore imediat, de data aceasta se mai introduce inca o intarziere de un tact, deci automatul Moore cu intarzieresimte o intrare transferata la iesire cu o intarziere de doua tacte.

Y((i+2)T):=f(q((i+1)T))=f(g(X(iT), q(iT)))

Reprezentarea automatelor

Modalitatile de reprezentarea a automatelorsunt prin:

Graficul de tranzitie a starilor Tabelul de tranzitie a starilor Diagrama de variatie in timp a semnalelor Organigrama.

In general se va alege ca modalitate de reprezentare varianta care duce la o masura a complexitatii cat mai simpla.

Graful de tranzitie al starilor

Definitie:Pentru un CLS sincron graful de tranzitie al starilor (diagrama de tranzitie a starilor) este o reprezentaregrafica a functiei de tranzitie a starilor, g, si a functiei de transfer intrare-iesire, f, pentru toate configuratiile de intrare X.

In acest graf fiecarui nod (cerculet) ii esteasignata o stare, iar fiecare arc orientatintre cele doua noduri reprezinta tranzitiaintre cele doua stari.

Pentru un automat Mealy pe un arc de tranzitie se noteaza expresia logica a variabilelor de intrare (expresia logica a tranzitiei) sau configuratia valorilorvariabilelor de intrare pentru care aceastaexpresie este adevarata, care va provocatranzitia respectiva, precum si valoareaconfiguratiei de iesire Y generata de aceasta tranzitie.

Pentru un automat Moore, deoarece iesirilesunt functii doar de starea prezenta, f:Q->Y, pearce nu sunt trecute configuratiile de iesire Ygenerate de tranzitiile respective, configuratiade iesire este inscrisa in cerculetul stariiprezente din care se genereaza iesirearespectiva, iar pe arce se inscrie doar expresialogica a tranzitiei sau configuratia valorilorvariabilelor de intrare pentru care expresialogica a tranzitiei este adevarata.

ExempluAutomat cu doua intrari x1x0 si o iesire y, tranzitia din starea q0 in una din urmatoarelepatru stari posibile q1, q2, q3, q4, graful de tranzitie este reprezentat in figurile urmatoare, unde ina) avem graful pentru o functionare de tip Mealy,

iar in b) avem graful pentru o functionare de tip Moore.

Fig. 3. Graful de tranzitie a starilor: a) Segment de graf pentru automat de tip Mealy;b) Segment de graf pentru automat de tip Moore.

La graful de tip Mealy in noduri suntinscrise numai starile, iar pe fiecare arc este trecuta expresia logica a tranzitiei/valoarea configuratiei de iesire; la graful de tip Moore in noduri pe langa stare este inscrisa si configuratia de iesire, iar pefiecare arc este trecuta doar expresia logicaa tranzitiei.

Daca la ceas iT automatul ajunge in q0 la cel de tip Moore se genereaza iesirea y=1, iar la cel de tip Mealy in aceasta stare q0 se genereaza iesirea y=1 numai dacaconfiguratia de intrare este 01 (x1x0=1), pentru celelalte trei configuratii (00, 10, 11) se genereaza y=0.

La urmatorul impuls de ceas (i+1)T se trecein starea urmatoare pentru care expresialogica a variabilelor de intrare esteadevarata, de exemplu pentru 10 (x1x0=1) se trece in starea q3 (unde y=0 pentruautomatul Moore, valoarea pentru y la automatul Mealy nu este precizatadeoarece din aceasta stare, in acest caz, nu mai este figurat nici un arc de tranzitie la o alta stare).

Constructia unui graf de tranzitii al starilortrebuie sa fie fara ambiguitati, ceea ceimpune pentru expresiile de tranzitieinscrise pe arcele care pornesc dintr-ostare sa fie mutuale exclusive sau toateincluse.

Tranzitii mutual exclusive Tranzitiile sunt mutual exclusive, daca dintr-o

stare, pentru aceeasi configuratie a valorilor de intrare nu exista simultan transferuri la doua saumai multe stari (exista transfer pe un arc numaiatunci cand expresia respectiva de transfer are valoarea 1).

Se poate verifica daca dintr-o stare nu existatransferuri simultane, efectuand produsul logic intre expresiile de transfer de pe doua arce de transfer care pornesc din starea respectiva, acesteproduse trebuie sa aiba totdeauna valoarea zero pentru oricare configuratie a valorilor variabilelorde intrare.

Pentru n arce care pornesc dintr-o stare numarul total de perechi pentru care se face produsul expresiilor de transfer esteegal cu n(n-1)/2.

Configuratiile valorilor de intrare testate, pentru care produsul logic al expresiilorde transfer de pe doua arce are valoarea1, sunt referite ca fiind dublu acoperite(de doua transferuri).

Tranzitii toate incluse

Tranzitiile sunt toate incluse, daca sumalogica a expresiilor de pe arcele care pornesc dintr-o stare este totdeaunaegala cu 1 pentru oricare configuratie a valorilor variabilelor de intrare testate; configuratiile de valori ale variabilelor de intrare testate pentru care aceasta sumalogica este egala cu zero sunt referiteprin configuratii neacoperite.

Concluzie

Cu ajutorul unei diagrame VK, de toatevariabilele care se testeaza in starearespectiva, se pot determinaconfiguratiile neacoperite precum siconfiguratiile dublu acoperite.

Pentru aceeasi functionare o implementare sub forma de automat Moore necesita mai multe stari decatimplementarea sub forma de automat Mealy.

In general, modelul Mealy este uzualpentru circuitele secventiale sincrone, iarmodelul Moore pentru circuiteleasincrone.

Graful de tranzitie al starilor/iesirilor esteun instrument potrivit pentru verificareafunctionarii automatului.

Exemplu:

Un automat cu doua intrari x1, x0 si o singuraiesire y, genereaza iesirea egala cu 1 numaicand din sirul de succesiuni aplicate peintrare se identifica secventa 00, 01, 11, 10. Pentru acest automat sa se deseneze grafulde tranzitie al starilor atat pentru o functionarede tip Mealy, cat si pentru o functionare de tip Moore.

Fig. 4. Grafuri de tranzitie pentru automatul care identificasuccesiunea 00 01 11 10:

a) Pentru un model Mealy cu marcarea pe arce a configuratiilor de intrare si iesire;

Fig. 4. Grafuri de tranzitie pentru automatul care identificasuccesiunea 00 01 11 10:

b) Pentru un model Mealy, dar cu inscrierea pe arce a expresieilogice a functiei de tranzitie;

Fig. 4. Grafuri de tranzitie pentru automatul care identificasuccesiunea 00 01 11 10:

c) Pentru un model Moore.

Tabelul de tranzitie al starilor

Informatia continuta in graful de tranzitieal starilor/iesirilor poate fi transpusa intr-o forma mult mai practica pentru sintezaautomatului tabelul de tranzitie al starilor (al iesirilor).

In tabelul de tranzitie al starilor existaatatea linii cate stari distincte prezintaautomatul si atatea coloane cate cuvintediferite se pot aplica la intrare.

Un element al tabelului tranzitiilor, aflat la intersectia unei linii cu o coloana, vareprezenta starea urmatoare/iesirea a automatului obtinuta la tranzitia din starea prezenta corespunzatoare aceleilinii prin aplicarea la intrare a cuvantuluide pe acea coloana.

Uneori, elementele tabelului cuprindnumai starea urmatoare, pentru iesiri se intocmeste un tabel de aceeasi forma ale carui elemente sunt iesirilecorespunzatoare - denumit tabeluliesirilor. Tabelul iesirilor pentru automatulMoore se reduce doar la o singuracoloana, avand atatea elemente catestari distincte exista (iesirile sunt functiinumai de starea prezenta).

Concluzie

Tabelul de tranzitie al starilor, este o reprezentare abstracta a automatului, sipermite o comparare sistematica a starilor pentru identificarea perechilor de stari echivalente.

Exemplu:

Sa se construiasca tabelele de tranzitieale starilor/iesirilor pentru automatulreprezentat in cele doua modele Mealy siMoore, din Fig. 4.

Fig. 5. Tabel de tranzitie/iesire

pentru modelul Mealy

Fig. 5. Tabel de tranzitie/iesire

pentru modelul Moore

Diagrama de variatie in timp ale semnalelor Functionarea automatului poate fi descrisa prin

variatia in timp a semnalelor de intrare, de stare si de iesire.

Diagrama de semnale este potrivita in general la automatele generatoare care depind minimal de intrare sau chiar de loc (functionareautomata).

Pornind de la diagrama de semnale, in care se identifica starile automatului, se poate deduce tabelul de tranzitie al starilor/iesirilor si apoi se poate construi graful de tranzitie.

Exemplu

Pentru automatul a carui functionare esteprezentata prin variatia in timp a semnalelor din Fig. 6, sa se deducagraful de tranzitie al starilor/iesirilor.

Fig. 6. a) Descrierea functionarii automatului prin diagramede variatie in timp ale semnalelor

a)

Fig. 6. b) Tabelul de tranzitie dedus din diagramele de semnalc) Graful de tranzitie al starilor/iesirilor.

b) c)

Organigrama

Descrierea fara ambiguitati a functionariiunui automat printr-un graf de tranzitie al starilor/iesirilor poate deveni destul de greoaie si cu dificultati.

Pentru a evita aceste dificultati s-a preluatmodalitatea de descriere a algoritmilorutilizata in dezvoltarea de soft, adicaorganigrama (flow chart).

Simbolurile grafice utilizate in constructia uneiorganigrame sunt urmatoarele trei:

- Cerculet sau dreptunghi: reprezinta o stare a automatului;

- Rombul: reprezinta elementul de decizie binar;- Dreptunghi sau dreptunghi rotunjit: simbol pentru

iesire conditionata, corespunde unei iesiri de tip Mealy intr-un graf de tranzitii.

Simbolurile grafice pot ficombinate impreuna pentrua forma celula de baza a unei organigrame numitablocul de stare.

Concluzie

Diferenta principala intre un bloc de stare si o organigrama pentru un program estemodul cum se interpreteaza timpul; la o organigrama operatiile sunt realizatesuccesiv in timp, una dupa alta, pe candintr-un bloc de stare, care este o unitatedintr-o diagrama, toate operatiile se realizeaza in acelasi timp, concurent.