CURS PDN

Automate Finite

Reducerea numarului de stari

In procesul de proiectare, etapa de eliminarea starilor redundante este referita prinreducerea starilor. Efectiv reducerea starilorinseamna identificarea starilor echivalente siapoi un numar de stari gasite ca echivalentesunt substituite, in functionarea automatului, cu o singura stare. Rezulta ca in tabelul de tranzitie al starilor/iesirilor toate liniile care corespund unor stari echivalente se vorsubstitui cu o singura linie rezultanta.

Definitie: Doua stari qi si qj sunt echivalentedaca pentru oricare configuratie de

intrare aplicata X se genereaza aceleasiiesiri, iar starile urmatoare

sunt identice sau echivalente.

ji qq

XqgqXqgq jjii ,,, 11

XqgXqgXqfXqf jiji ,,;,,

Stari echivalente

Proprietati ale starilor echivalente:1. Simetria: daca qi ~ qj atunci si qj ~ qi 2. Reflexivitatea: qj ~ qj pentru orice stare3. Tranzitivitatea: daca qi ~ qj si qj ~ qk

atunci qi ~ qk.

Metoda graficaSe considera un automat cu sase stari: A, B, C, D, E, F, a carui functionare este descrisaprin tabelul de tranzitie al starilor/iesirilor.O mapa a implicantilor care compara pentruechivalenta, fiecare stare cu fiecare stare esteo diagrama, ce are pe orizontala notate toatestarile mai putin ultima, in cazul nostru A, B, C, D, E, iar pe verticala toate starile mai putinprima, in cazul nostru B, C, D, E, F.

Fig. 1. Etapele reducerii numarului de stari prin metoda grafica a mapei implicantilor

a) Tabelul de tranzitie a starilor/iesirilor automatului;

In casuta de coordonate care corespundeintersectiei celor doua stari care se compara, una de pe orizontala si una pe verticala, se inscriu conditiile (starile) necesare pentruechivalenta celor doua stari. Aceste conditiinecesare pentru echivalenta se deduc din tabelul de tranzitie al starilor/iesirilor, comparand fiecare stare cu fiecare, pentrutoate configuratiile de valori ale cuvantului de intrare ce determina cele doua stari.

Verificarea conditiilor necesare pentru ca o pereche de stari sa fie echivalenta se realizeazaprin urmatorii pasi:1. Se elimina (se diagonalizeaza) din mapa implicantilor

acele casute ale caror perechi de stari coordonate au in tabelul de tranzitie al starilor/iesirilor iesiri diferitepentru aceeasi valoare a cuvantului de intrare.De exemplu: nu pot fi echivalente perechile A cu B, A cu D si A cu F, deoarece au iesiri diferite, decicasutele corespunzatoare intersectiei acestorperechi se diagonalizeaza.

2. Pentru perechile de stari prezente la care s-a verificat ca au iesiri identice, dupa inspectareatabelului, se inscrie in casutele corespunzatoare din mapa implicantilor care perechi de stari urmatoarear trebui sa fie echivalente pentru ca perechea de stari prezente comparate sa fie echivalenta.De exemplu, pentru prima coloana din mapa pentruca A~C necesita echivalenta intre B si D, iar A~E necesita C~E si D~F; pe coloana a doua B~D necesita B~D, B~F necesita B~F si C~D; pe coloanaa treia C~E necesita C~E si B~F; iar pe coloana a patra D~F necesita B~F si B~C.

3. Pentru fiecare casuta in care este inscrisa o conditiede echivalenta (perechi de stari), se analizeazadaca aceasta conditie de echivalenta esteindeplinita sau nu. Daca nu este indeplinita atunci sicasuta respectiva este diagonalizata. Se vaexemplifica aceasta analiza pentru prima coloanadin mapa implicantilor. Pentru ca A~C trebuie ca B~D. Dar, tot din mapa implicantilor se deduce ca B~D numai cand conditia din casuta de la intersectialiniei D cu colona B este adevarata, adica B~D. Deoarece echivalenta perechii (B, D) estedependenta de propria sa echivalenta (B, D), inseamna ca aceasta pereche este echivalenta(reflexivitatea).

Pentru ca A~E necesita C~E si D~F. Privind in mapa implicantilor pentru echivalenta perechii D, F este necesara B~F si B~C, iar pentru echivalentaC~E este necesara C~E si B~C. Pentru ca B~F estenecesar ca B~F si C~D, dar din casuta de coordonate C si D rezulta ca starile C si D nu suntechivalente. In concluzie, starile A si E nu suntechivalente si casuta de coordonate A si E de peprima coloana se diagonalizeaza.

Concluzie: Se aplica aceasta analiza si pentru celelaltecoloane/linii si se constata ca in afara de casuta de coordonate B, D, toate celelalte se diagonalizeaza, rezultand mapa implicantilor din fig.1.c). Rezulta ca sunt echivalente starile A cu C si starileB cu D.

Fig. 1. Etapele reducerii numarului de stari prin metoda grafica a mapei implicantilor

b) Mapa implicantilor dedusa din tabelul de tranzitie;c) Mapa implicantilor dupa validarea conditiilor de echivalenta;

4. Pentru fiecare pereche de stari echivalente se pastreaza doar una din stari, eventual se redenumesc starile (A=q0, B=q1, C~A=q0, D~B=q1, E=q2, F=q3) si se construieste tabelul simplificat al tranzitiei starilor/iesirilor, din fig.1.d). Deci automatul initial cu sase stari poate fi substituitin functionare cu un alt automat (echivalent) care are numai patru stari.

Fig. 1. Etapele reducerii numarului de stari prin metoda grafica a mapei implicantilor

d) tabelul de tranzitie al starilor/iesirilor pentru automatul echivalent(redus).

ExempluPentru automatul Mealy cu graful de tranzitie al starilor/iesirilor din fig. 2.a) sa se elimine starileredundante si apoi sa se redeseneze graful de tranzitie.

Fig. 2. a) Grafulde tranzitie al starilor/iesirilor;

SolutieDin graful de tranzitie al starilor/iesirilor se obtinetabelul de tranzitie al starilor/iesirilor din Fig.2.c), Iar din tabelul de tranzitie se deduce:1. Nu sunt echivalente urmatoarele perechi de

stari: A cu B, A cu C, B cu D, B cu E, C cu D si C cu E.

2. Starile: A~D numai daca sunt echivalente B cu C si D cu C si A cu B; A~E numai daca suntechivalente A cu E si B cu C; B~C numai dacasunt echivalente B cu C si A cu E; D~E numaidaca sunt echivalente C cu D si B cu E si A cu C.

Fig. 2. c) Tabelul de tranzitie a starilor/iesirilor automatului;

3. Se constata ca: AD deoarece AB si DC; DE deoarece AC, BE si CD; A~E numaidaca B~C, iar B~C numai daca A~E. Rezultaca A~E si B~C (simetrie daca qj~qi atunciqi~qj). Mapa implicantilor rezultata este cea din Fig. 2.f).

Fig. 2. e) Mapa implicantilor dedusa din tabelul de tranzitie;f) Mapa implicantilor dupa validarea conditiilor de echivalenta;

.

4. Se redenumesc starile in felul urmator: A=q0, B=q1, C~A=q0, D=q2, E~A=q0 pentrucare rezulta tabelul de tranzitie din Fig. 2.d).Functionarea automatului echivalent (redus) este descrisa prin graful de tranzitie al starilor/iesirilor din Fig. 2.b).

Fig. 2. d) tabelul de tranzitie al starilor/iesirilor pentru automatulechivalent (redus);

b) graful de tranzitie al starilor/iesirilor pentru automatul echivalent(redus).

Observatii In sinteza circuitelor combinationale se

intalnesc cazuri cand functia de transfer esteincomplet specificata, ceea ce in tabelul de adevar se indica prin semnul indiferent (dont care). Cazuri similare se intalnesc si la circuitele secventiale cand fie functia de transfer f, fie functia de tranzitie g, nu suntcomplet specificate ceea ce se reflecta prinindicarea semnului indiferent respectiv pentruanumite valori ale iesirii sau anumite stariurmatoare. Cand anumite stari nu suntspecificate automatul nu este predictibil.

Este indicat sa se evite asemenea cazuri fie prin alegerea numai acelor configuratii de intrare care conduc automatul numai prin starideja specificate sau, fie sa se specifice starilenespecificate daca prin aceasta nu se contravine rezultatului dorit. Odata specificatestarile, care initial erau nespecificate, automatul nu mai este incomplet specificat.

Pentru automatele incomplet specificate existaalgoritmi (grafici sau analitici) de reducere a numarului de stari.

In procesul de reducere al numarului de stari, specificarea iesirilor nespecificate poate fifacuta fara a se produce nici un impact asuprasecventei starilor automatului final. Esteindicat ca iesirile nespecificate sa fie lasatenespecificate in tabelul de tranzitie al starilor/iesirilor cat se poate de mult in procesul de reducere, deoarece prezentasemnului indiferent duce la o mai mare flexibilitate in compararea starilor din tabelulde tranzitie.

In validarea echivalentei a doua stari, trebuie ca iesirile sa fie identice pentru oricare configuratiede intrare. Cand se compara doua stari ale caroriesiri sunt incomplet specificate in locul notiuniide echivalenta se utilizeaza notiunea de staricompatibile.

Doua stari qi si qj sunt stari compatibile daca, pentru oricare secventa de configuratii aplicatepe intrare, se obtine o aceeasi secventa a iesiriicand iesirile nespecificate vor fi specificate, indiferent daca starile qi, qj sunt stari initiale saunu.

Asignarea starilor

Procesul de asignare al starilor(codificarea starilor) unui automat cu sstari consta in alocarea pentru fiecaresimbol de stare q0, q1, , qs-1 a cate unuicuvant de cod cu lungimea de minimum k biti. Valoarea lui k rezulta din relatia

2k-1s

Prin asignarea starilor, automatul definitsimbolic este transformat intr-un automat cu o structura specificata si functiile de transfer f si de tranzitie g sunt fixate.

Codificarea starilor este cea maiimportanta etapa in proiectarea unuiautomat.

Pentru un automat cu s stari din multimea 2kcuvinte, cu lungimea de k biti, se pot forma un numar de 2k!/(2k -s)!s! grupuri distincte, fiecaregrup contine s cuvinte. Apoi, prin mapareacelor s stari ale automatului pe un grup cu scuvinte rezulta un numar de s! asignari(codificari) diferite.

Deci numarul total de codificari, Nc, va fi:Nc= 2k!/(2k -s)!

Din numarul total de codificari Nc (de asignariposibile) unele sunt echivalente. Doua asignariale starilor sunt echivalente daca pentru celedoua implementari ale automatului functiile f sig au aceleasi marimi de dimensiune sicomplexitate.

Se obtin doua asignari echivalente in 2 cazuri:1. Cand codul unei asignari se obtine prin

complementarea codului celeilalte.2. Cand codul unei asignari se obtine din codul

altei asignari prin interschimbarea coloanelor z1si z0. (spre exemplu, cand k=[log24]=2 - stari)

Numarul total de asignari neechivalente, Ncne, pentru un automat cu s stari sicuvant de lungime de k biti se calculeazacu urmatoarea relatie

Ncne=(2k-1)!/(2k-s)!s!Valoarea lui Ncne creste dramatic in functie de numarul de stari s ale automatului, cateva din aceste valorisunt date in tabelul 1.

Tabelul 1. Valori pentru numarul asignarilor neechivalente, Ncne

Un procedeu simplu de asignare a starilor care are o probabilitate destul de ridicata pentru a duce la o solutie apropiata de cea optima se bazeaza pe conceptul de locusul starilor.

Locusul starilor este numarul de modificariale bitilor din cuvantul de stare cand pentru un automat se parcurg toate caile de tranzitie.

Se va alege acea codificare a starilor care sarealizeze o valoare cat mai mica pentrulocusul starilor.

Valoarea minima s-ar obtine cand codurileintre doua stari succesive pe oricare linie de tranzitie, in afara de buclele la aceeasi stare, ar diferi doar printr-un singur bit.

Aceasta modalitate de codificare, prin care codul unei stari difera doar printr-un singur bit fata de codurile starilor urmatoare, inspre care exista o cale de tranzitie, este referita ca o codificare cu variatie minima.

Codificarea cu variatie minima, pe langa faptulca pot duce la suprafete mai mari intr-odigrama VK, prin realizarea unei singurecomutatii in cuvantul de stare la trecerea de la o stare la alta, mareste siguranta in functionare a automatului, mai ale la celeasincrone.

Codificarea cu diferenta numai de un singurbit, intre doua stari succesive, nu estetotdeauna posibila.

Uneori, pentru realizarea unei codificari cu distanta de cod unu intre oricare doua starisuccesive este necesara introducerea unei starisuplimentare, dar aceasta suplimentare de staripe intreaga organigrama ar putea duce la cresterea numarului de biti in cuvantul de cod.

Aceasta rezolvare pentru codificarea cu variatieminima implica definirea si a unei iesiri in stareasuplimentara. Iesirea dependenta de stareasuplimentara poate fi repetarea iesirii y din starea anterioara sau nici o iesire NO-OPERATION daca functionarea automatuluipermite.

Pentru un automat valoarea locusului starilornu poate fi mai mica decat numarul s de stari. O valoare minima egala cu s pentru locusulstarilor se poate obtine doar la un automat la care exista s tranzitii neconditionate intrestarile succesive si codificarea starilor este cu variatie minima, de exemplu un numarator in cod Gray, uzual valoarea minima a locusuluistarilor este mai mare decat s.

Codificarea cu dependenta redusa

Presupune ca starile urmatoare ce se obtinprin tranzitia din aceeasi stare, in urma testariiunor variabile de intrare, sa difere intre eleprintr-un singur bit.

Aceasta inseamna ca expresia celor douastari, care se obtin in urma testarii unei singurevariabile x0, sa se exprime cat mai simplu in functie de aceasta variabila adica, sa fie de forma, de exemplu, z4z3x0z1z0. Cele doua stariurmatoare sunt z4z30z1z0 si z4z31z1z0.

Incercarea de a codifica cu dependentaredusa simultan dupa doua variabile, spreexemplu, x1, x0 nu este posibila, deoarececuvintele obtinute nu difera intre ele numaiprintr-un singur bit.

Deci codificarea cu dependenta redusa poatefi realizata doar in functie numai de o variabilatestata.

Codificarea de tip unic-activ (one-hot) La aceasta codificare cuvantul de cod nu mai

are lungimea de [log2s] ci are lungimea de s biti, adica atatia biti in cuvantul de cod cate stari are automatul, in plus, creste dimensiunearegistrului din calea de reactie.

Acest registru, pentru un automat cu s stari, vaavea s celule de memorare (bistabile) si nu[log2s] celule ca la asignarile prezentate panaacum. Datorita acestui avantaj, se consideracodificarea de tip unic-activ o codificarepreferata mai ales la implementarile integrate.

Proiectarea unui automat sincron

In proiectarea unui automat sincron se parcurg urmatoarele etape:1. Descrierea functionarii automatului.

Descrierea poate fi direct sub forma unei organigrame, a unui graf de tranzitie al starilor/iesirilor sau se transpune sub una din aceste formedintr-o descriere verbala.

2. Construirea tabelului de tranzitie al starilor/iesirilor si reducerea starilorredundante.

3. Codificarea starilor si construireatabelului de tranzitie asignat pentrustari si iesiri.

4. Sinteza functiilor de excitatie (stareaurmatoare) si a iesirilor.

5. Implementarea, intr-o anumitatehnologie, si apoi testarea.

6. Elaborarea documentatiei.