Bazelearii automatelor finite

admisibila este o evolutie cu proprietatea:

Uneori se impune pentru evolutiile admisibile ale automatului ca starea initiala sa apartina unei submultimi S1 inclusa in S.

Daca si card atunci automatul se numeste slab initial.In cazurile extreme card S =1,S =S automatul se numeste initial respectiv neinitial,iar pentru ,card S >1 automatul se numeste strict slab initial.Automatul A'=(I',S',O',f',g') este un subautomat al automatului A=(I,S,O,f,g) daca .Un automat nu ajunge in starile initiale printr-o anumita evolutie.In mod curent automatul este adus intr-o stare initiala in urma unei comenzi din exterior(care poate fi diferita de semnalele aplicate la intrari).

O stare a unui automat initial este inaccesibila daca orice evolutie in spatiul starilor,care porneste din stari initiale,nu contine starea respectiva.Asadar nu putem vorbi despre stari inaccesibile numai in cazul automatelor initiale.

Doua stari sa,sb apartine lui S sunt echivalente daca evolutia automatului ,pornind din aceste stari,genereaza la iesire siruri de configuratii binare identice.

Un semiautomat este un triplet S=(I,S,f),

Semiautomatul atasat automatului A=(I,S,O,f,g) este semiautomatul A=(I,S,f).

Un semiautomat este finit si/sau determinist in sensul in care aceste proprietati au fost definite pentru automate.Conceptul de semiautomat separa acea parte interna a unui automat care este responsabila de evolutia interna ,de autonomia propriu-zisa.In general,optimizarea unui automat se reduce la componentele necesare pentru implementarea functiilor de iesire,obtinem semiautomatul asociat.

Un automat este imediat daca:

Adica,starea curenta(si eventual intrarea curenta) determina iesirea la acelasi moment t.

Un automat este cu intarziere daca:

Adica,iesirea curenta depinde de starea(si eventual intrarea) din ciclul anterior de ceas.

Structurile celor patru tipuri de automate in figura 1.3 de mai jos.Acestea contin un sistem combinational si elemente de memorie(registre) comandate pe frontul semnalului de ceas.Rezulta inca o data modul in care aceste automate reactioneaza la variatiile semnalelor de intrare.Toate cele patru tipuri de automate sunt semnificative deoarece,in functie de aplicatie ,ele se integreaza in mod diferit,ca modalitate de a reactiona,intr-o structura concreta.Prin SLC am notat structurile logice de tip combinational din componenta automatelor,iar prin R am notat elementele de memorie de tip registru(paralel-paralel)

Figura 1.3.Structura automatelor Mealy si Moore

Figura 1.4.Structura unui semiautomat

Structura unui semiautomat este prezentata in figura 1.4 si este destul de clar ca ea nu corespunde nici unei realizari concrete.Un sistem fara iesire este lipsit de sens.Totusi.din punct de vedere teoretic si in practica proiectarii acest concept se va dovedi util.

In schemele bloc de mai sus am notat SLC sistemele logice asociate automatelor iar prin R am desemnat elementele de memorie de tip registru.Aceste elemente de memorie pot fi reprezentate de bistabile de tip D,de tip J-K,de tip T sau de tip S-R,toate acestea comutand pe frontul(crescator sau descrescator) al semnalului de ceas.Etapele care trebuie parcurse pentru proiectarea unui automat sunt prezentate in figura 1.5:

Reprezentarea automatelor finite

A reprezenta un automat inseamna a reprezenta cele 3 functii de tranzitie f, g si .Exista mai multe moduri de reprezentare a acestor functii, in functie de etapa de proiectare sau de analiza functionarii automatului respectiv.

Grafuri de stare. Reprezentarea prin grafuri se face asociind fiecarei stari cate un nod al grafului in timp ce tranzitiilor dintre stari li se asociaza arce.Arcele vor fi orientate si marcate cu conditia care determina tranzitia (atunci cand aceasta tranzitie este conditionata). Iesirea este marcata distinct la automatele Mealy si la cele Moore.Astfel ,pentru automatul Mealy, iesirea este reprezentata pe arc, iar pentru Moore iesirea este asociata nodului care reprezinta starea.

Exemplu

Voi folosi ca exemple in acest paragraf doua automate, unul Mealy si unul Moore.In Figura 1.a) este reprezentat un automat Mealy cu trei stari s0,s1,s2 .Combinatiile binare acceptate la intrare sunt i1,i2 ,iar multimea O are patru elemente o0,o1,o2,o3.S=,I=,O=.

Daca starea curenta este s1,exista o singura tranzitie, neconditionata, in starea urmatoare s0.In acest caz, la iesire se genereaza vectorul o1.Din starea curenta s0, daca la intrare se aplica i1,atunci se genereaza la iesire o2,iar starea urmatoare este sTot din s0,daca la intrare se aplica i2 se obtine la iesire o1,iar starea urmatoare este s1 .Din starea s2,automatul va trece in s1 generand la iesire o3 daca la intrare se aplica i1.Daca in starea curenta s2 se aplica la intrare i2,se genereaza la iesire o0 iar starea nu se schimba

Figura 1.: a)Graful de stare al automatului Moore

b)Graful de stare al automatului Mealy

Descrierea formala a automatelor finite

In Figura 1.b) este reprezentat un automat Moore.Conform definitiei fiecare stare are asociata o configuratie binara de iesire.In acest caz, multimea starilor este S=,multimea configuratiilor de intrare si cea a configuratiilor de iesire sunt aceleasi ca si la automatul Mealy O= .In starea s4 iesirea este o1,in starea s5 iesirea este tot o1,in starea s6 iesirea este o2,in starea s2 iesirea este o3 iar in starea s8 iesirea este o0 .Tranzitia starilor depinde de intrarile aplicate.Astfel din starea curenta s4 automatul evolueaza in starea s5 sau s6, dupa cum la intrare se aplica sau nu se aplica i2(se aplica i1).Celelalte tranzitii pot fi interpretate in mod similar.

Diagramele de timp pot oferi uneori o reprezentare sugestiva a comportamentului unui automat.

Sa presupunem ca dorim sa obtinem un automat care sa furnizeze la iesire un semnal cu frecventa .In diagramele de timp din Figura s-a reprezentat semnalul de ceas al sistemului, CLK, impreuna cu semnalul de iesire .

In cele ce urmeaza ne vom referi la masina sincrona care este reprezentata in diagramele de timp din Figura ca fiind masina M1.Pentru ca evenimentele temporale apar la tranzitia semnalului de ceas din 0 in 1, pentru implementarea acestui automat se vor folosi circuite basculante bistabile care comuta pe frontal semnalului de ceas.Pentru a simplifica modul in care se utilizeaza diagramele de timp,intarzierile de propagare pentru obtinerea semnalului de iesire Z la momentele 1, 3, 5, etc.nu sunt reprezentate.Atunci cand timpul este o variabila critica sau atunci cand un automat nu functioneaza dupa cum ne asteptam (acest lucru se poate intampla la frecvente ridicate,ale semnalului de ceas ,daca se utilizeaza dispozitive lente si/sau circuite cu niveluri logice multiple), trebuie sa se deseneze diagrame de timp separate, pentru a verifica intervalele critice pentru diferite trasee ale semnalelor; este cazul sistemelor de dimensiuni mari.

Figura : Diagramele de timp pentru masina M1

Din diagramele de timp pentru masina sincrona M1, putem obtine graful de stare Moore din Figura 3..Este o modalitate obisnuita sa se deseneze o diagrama de stari pentru o masina sincrona cu un semnal de ceas presupus implicit.Pentru ca la implementarea acestui automat vor fi utilizate bistabile activate pe frontului semnalului de ceas, tranzitiile dintr-o stare in alta apar atunci cand semnalul de ceas isi schimba valoarea din 0 in 1.In diagrama de stari Moore sunt mentionate valorile iesirii Z pentru fiecare dintre cele patru stari ale masinii a,b, c si d.Valorile iesirii Z sunt plasate in nodurile care reprezinta starile, pentru ca la o masina Moore iesirea depinde univoc de starea curenta.

Figura 3.: Graful de stare pentru masina M1

Tabelele de tranzitie reprezinta tot o forma primara de descriere a functionarii unui automat.In Figura 4 sunt reprezentate sub forma unor tabele de tranzitie functiile de tranzitie ale automatelor Mealy si Moore care au fost introduce in Figura 1.In figurile 4.a si 4.b sunt tabelele care reprezinta functiile de tranzitie a starilor ,f, pentru automatele Mealy si respective Moore.In figurile 4.c si 4.d sunt tabelele care reprezinta functiile de tranzitie a iesirilor, g si , pentru automatele Mealy si respective Moore.

a)

b)

c)

d)

Figura 4.:a)Tranzitia starilor pentru automatul Mealy descris in figura 1.

b)Tranzitia starilor pentru automatul Moore descris in figura 1.

c)Tranzitia iesirilor pentru automatul Mealy descris in figura 1.

d) Tranzitia iesirilor pentru automatul Moore descris in figura 1.

Pentru tabelul de tranzitie a starilor, pe coloane se reprezinta starea curenta iar pe linii se reprezinta combinatiile de intrare.In interiorul tabelului se trece starea urmatoare in care ajunge automatul pornind de la o stare curenta si aplicand o anumita combinatie de intrare (Mealy si Moore)

Pentru tabelul de tranzitie a iesirilor, pe coloane se reprezinta starea curenta iar pe linii se reprezinta combinatiile de intrare (Mealy) sau iesirile.In interiorul tabelului se trece iesirea automatului in functie de starea curenta combinatia de intrare (Mealy) sau in functie de starea curenta (Moore).

Astfel, pentru automatul reprezentat prin tabelul de tranzitie a starilor din Figura 4.a, din starea s2, daca la intrare se aplica i1,starea urmatoare va fi s1;daca starea curenta este s1 iar la intrare se aplica i2,starea urmatoare devine s0.La fel pot fi interpretate si celelalte tabele.Observam in tabelul din figura 4.d ca fiecarei stari i se asociaza o configuratie binara de iesire (Moore).

Organigrame

Organigramele pot fi reprezentate in doua forme :

-organigrame simbolice, in care starile, combinatiile de intrare si de iesire apar cu numele lor s0,s1,i1,i2 s.a.m.d;

-organigrame binare, in care in locul numelor apar codurile binare ale starilor, vectorilor de intrare si ai celor de iesire.

Pentru ambele tipuri de organigrame se folosesc simbolurile:

-cercuri pentru a reprezenta starile;

-dreptunghiuri pentru a reprezenta iesirile;

-romburi pentru a reprezenta configuratiile binare de intrare.

Pentru automatele de tip Moore nu se utilizeaza un simbol separate pentru stare, dar vom nota alaturi de dreptunghiul asociat iesirii numele starii respective.

Organigramele simbolice asociate automatelor prezentate in Figurile 4.a si 4.b sunt prezentate in Figura 5.a si respectiv Figura 5.b.

Pentru a trece de la organigrame simbolice, in care se folosesc numele starilor si ale combinatiilor de intrare si de iesire, la organigrame binare, este necesar sa se stabileasca codurile binare asociate elementelor celor trei multimi care definesc automatul I, S, O.

Figura 5.:a)Organigrama simbolica pentru automatul Mealy introdus in figura 1a)

b) Organigrama simbolica pentru automatul Moore introdus in figura 1..b)

Intr-o problema concreta de proiectare multimile I si O sunt codificate indirect prin enuntul problemei.Multimea S poate fi definite de proiectant deoarece ea depinde de structura interna a automatului care nu este transparenta la borne.Vom alege pentru vectorii de intrare o codificare pe un bit (A), pentru stari o codificare pe doi biti (Q1 si Q0,respectiv Q2,Q1,Q0 pentru automatul Moore), iar pentru iesiri o codificare pe trei biti ( O2,O1,O0).Tabelele din figura 6. prezinta codificarile alese pentru automatele introduce in Figurile 1.a si 1.b.Se obtin astfel organigramele din figurile 7a si 7b.

Tabelele de adevar

Tabelele de adevar sunt reprezentari secundare care se obtin dintr-o reprezentare primara, de exemplu dintr-o organigrama binara.Aceste tabele reprezinta tabelele de adevar asociate structurilor logice combinationale care intra in structura automatului.In exemplele care urmeaza variabilele care reprezinta starea urmatoare vor fi notate prin .Ele sunt obtinute la iesirea SLC asociat automatului si se aplica la intrarile registrului de stare R.

Automatul Mealy al carui tabel de tranzitie este prezentat in Figura 4., poate fi prezentat prin tabelul de adevar din Figura 8.a.Pentru functia de tranzitie nu a fost definita pentru ca acest cod nu este folosit, automatul avand numai trei stari.

a)

b)

Figura 6.:a)Codificarile binare pentru elementele celor 3 multimi care definesc automatul Mealy introdus in figura 1.a

b)Codificarile binare pentru elementele celor 3 multimi care definesc automatul Moore introdus in figura 1.b

a)

b)

Figura 7:a)Organigrama binara pentru automatul Mealy introdus in figura 1.a

b)Organigrama binara pentru automatul Moore introdus in figura 1.b

a)

b)

Figura 8.:a)Tabele de adevar pentru automatul Mealy introdus in figura 1.a

b)Tabele de adevar cu variabile incluse pentru acelasi automat

Figura 9.:Tabelul de adevar cu variabile incluse pentru automatul Moore introdus in figura 1. b

O varianta posibila pentru tabelul de adevar este aceea in care variabilele care descriu intrarea automatului sunt incluse in celulele tabelului ca in Figura 8.b.Am notat prin "-"variabilele don't care.

Tabelul de adevar cu variabilele de intrare incluse pentru automatul Moore este prezentat in Figura 9.Starea 000 este urmata de starea 111 daca A=1 sau 011 daca A=1, asadar succesorul poate fi reprezentat prin in tabelul de tranzitie.Celelalte linii care definesc tranzitia starii au fost completate in mod similar.

Diagrama de tranzitie

Diagramele de tranzitie se obtin direct din tabelele de adevar si ofera reprezentare mai compacta a automatelor,cu posibilitate de minimizare a functiilor ce caracterizeaza CLC-ul asociat.

In Figura 10. sunt prezentate diagramele Karnaugh asociate automatului Mealy introdus in figura 1.a.In Figura 10.a sunt obtinute functiile f si g pornind de la o diagrama de referinta.Aceste diagrame sunt detaliate in Figura 10.b, astfel incat sa se obtina expresiile minimizate pentru functiile de transfer:

Figura 10:a)Diagramele karnaugh pentru automatul Mealy introdus in figura 1.a

b)Diagramele karnaugh detaliate pentru variabilele de stare si pentru cele de iesire

Diagramele de tranzitie asociate automatului Moore introdus in figura 1.b sunt prezentate in figura 11.Din aceste diagrame se obtin expresiile simplificate pentru functiile f si :

Figura 11:a)Diagramele karnaugh pentru automatul Moore introdus in figura 1.a

b)Diagramele karnaugh detaliate pentru variabilele de stare si pentru cele de iesire

3.Codificarea starilor

O etapa importanta in realizarea automatelor finite este codificarea starilor.Problema fundamentala care se pune in realizarea concreta a automatelor finite este aceea a optimizarii semi-automatului SA=f(I,S,f) care intra in structura automatului finit.

Inginerul proiectant are maxima libertate in obtinerea functie de tranzitie a starii.Efecte importante de minimizare globala sau de realizabilitate in conditii concrete se pot obtine intr-o convenabila codificare a starilor automatului.Codificarea elementelor multimilor I si O este strict determinata prin definirea initiala a automatului.Aceste coduri sunt impuse de contextual in care va functiona automatul.Codificarea elementelor multimii S intr-un nod sau altul nu afecteaza functionarea automatului la nivelul definitiei abstracte ,ci este afectata numai marimea (complexitatea)structurii care implementeaza automatul finit.Codurile elementelor din S nu sunt niciodata accesibile la borne.

Secventa sau ordinea de asignare a codurilor pentru toate starile automatului este arbitrara in proiectarea automatelor,dar alegerea unei anumite codificari afecteaza atat complexitatea ecuatiilor de excitatie pentru elementele bistabile ,a ecuatiilor care determina starea urmatoare precum si a ecuatiilor iesire.Au existat multe incercari de obtinere a unei proceduri generale care sa conduca la o implementare cu numar minim de componente.Aceasta problema este destul de complexa si,in general,necesita folosirea unui altgoritm de cautare dificil de implementat.Totusi,putem incerca recomandari pentru codificarea starilor astfel incat sa obtinem rezultate practice utile.

Codificarea starilor conform principiului dependentei reduse in functie de o variabila,presupune ca starile care urmeaza unei stari date trebuie sa fie codificate astfel incat un singur bit al codului sa depinda de aceasta variabila.

Fragmentul de organigrama din Figura 3.1.a are starile codificate cu dependenta redusa fata de variabila de intrare B.In adevar,codurile starilor care sunt separate prin variabila B sunt s2 si s3,adica 010 si 011 sau 01B adica,numai bitul cel mai putin semnificativ depinde de variabila B.

In fragmentul din Figura 3.1.b codificarea este realizata cu dependenta redusa fata de variabila A astfel:pentru b = 0 codurile care sunt separate prin variabila A sunt 101 si respective 111, 1A1,iar daca b = 1 starile separate prin A sunt 101,respective 100,adica 10A.

Codificarea starilor cu variatie minima presupune ca starile succesive sa fie codificate astfel incat codurile sa difere printr-un numar minim de biti(daca este posibil numai printr-un singur bit).

In Figura 3.2 se exemplifica o codificare cu variatie minima.Starea s1 (010) poate fi urmata de una din starile s2 (000), s3 (110) sau s4 (011).Toate aceste stari s2, s3 si s4,difera printr-un singur bit de starea s1,adica s-a realizat o codificare cu variatie minima.

Codurile starilor separate prin B sunt 110 si 011,adica 1B,adica nu s-a realizat o codificare cu dependenta redusa fata de variabila B.

a)

b)

Figura 3.1. : Doua exemple de codificare a starilor conform principiului dependentei reduse

(a)     fata de variabila de intrare B,

(b)            fata de variabila de intrare A.

Figura 3.2:Exemplu de codificare a starilor conform principiului variatiei minime

Nu in orice situatie e posibila o codificare cu variatie minima.Sa consideram de exemplu fragmentul de organigrama din Figura 3.3.In acest caz nu poate fi realizata o codificare cu variatie minima pentru toate starile.

Daca s1 difera de s0 printr-un singur bit,iar fata de s2 (s1 ≠ s2) tot printr-un singur bit,atunci s2 si s0 vor trebui sa difere prin cel putin 2 biti.Asadar,pe o bucla cu trei stari nu poate fi realizata codificarea cu variatie minima in cazul cel mai favorabil,adica al diferentei de un singur bit.

Figura 3.3:Imposibilitatea codificarii starilor cu variatie minima pe o bucla cu 3 stari

Cele doua modalitati de codificare sunt incompatibile.Ele pot fi folosite impreuna la codificarea starilor unui automat,dar numai pe portiuni distincte ale organigramei.

Automatele cu intrari asincrone vor fi proiectate astfel incat codificarea starilor sa respecte principiul dependentei reduse fata de variabilele de intrare care nu comuta sincron cu ceasul automatului.

4.Reducerea numarului de stari pentru automatele finite

Uneori,in procesul de proiectare a unui automat sincron,specificatiile de proiectare conduc la un tabel de stari si la o realizare hardware care contine mai multe stari si,implicit,mai multe dispozitive bistabile,decat sunt necesare.

Astfel,pentru s stari,numarul n de dispozitive bistabile care se poate utileza pentru a reprezenta toate starile automatului se poate determina din .

Pentru a investiga daca o masina particulara a fost propusa spre implementarea cu un numar de stari mai mare decat era necesar,se poate face apel la un tabel de implicatii.Acesta sta la baza unei metode care permite proiectorului sa determine starile redundante.Daca numarul de stari ale automatului poate fi redus(mentinand acelasi comportament intrare-iesire),atunci s-ar putea reduce numarul de elemente bistabile,totusi,chiar daca numarul starilor se poate reduce,pot exista cazuri in care numarul de dispozitive bistabile sa nu se reduca.

Definitie:Doua stari care genereaza iesiri identice si care evolueaza in aceeasi stare urmatoare(ca rezultant al aparitiei frontului activ al unui semnal de ceas sau al aparitiei unor intrari externe) se numesc stari identice.

Starile identice sunt redundante.Se poate elimina una din cele doua stari,obtinand astfel un numar mai mic de stari pentru automatul considerat.Adesea,starile identice pot fi identificate fie in graful caracteristic automatului fie in diagramele de tranzitie,prin simpla inspectie a acestora.

Definitie: Doua stari ale unui automat,m-n,sunt implicit echivalente atunci cand genereaza iesiri identice,dar starile urmatoare depind de echivalenta implicita a doua alte stari,r-s.Daca se demonstreaza ca starile r-s sunt echivalente,atunci si m-n sunt echivalente.

In mod indirect,se pot determina grupuri de stari echivalente prin identificarea tuturor perechilor de stari care nu sunt echivalente(iesirile lor nu sunt identice).

In tabelul de tranzitii pentru masina M1,prezentat in Figura 4.1,comparam pe rand starea a cu starile b,c si d,apoi starea b cu starile c si d,apoi starea c cu starea d,pentru a determina caracteristicile fiecarei perechi de stari.Starile unei perechi pot fi identice,implicit echivalente sau neechivalente.

Tabelul de implicatii din figura 4.a permite listarea rezultatelor comparatiilor de mai sus intr-o maniera ordonata.Pentru proiecte mari,sunt necesare treceri succesive prin tabel,pentru a determina toate starile neechivalente

Tabelul de implicatii este construit in modul urmator:in directia orizontala se listeaza in ordine, de la stanga la dreapta,toate starile cu exceptia ultimei stari.In directia verticala se listeaza in ordine,de sus in jos,toate starile cu exceptia primei stari.Aceasta organizare ofera cate o celul elementara pentru a caracteriza fiecare pereche de stari a automatului.

Pentru a completa tabelul de implicatii,vom compara,pe rand ,cate doua coloane din tabelul de tranzitii.In acest mod,comparam fiecare stare cu lista in directia X in tabelul de implicatii cu starea corespunzatoare listata in directia Y.Daca doua stari sunt identice,atunci starile lor urmatoare sunt identice si iesirile sunt identice;aceasta se marcheaza in celula corespunzatoare a tabelului printr-un semn x.Daca doua stari nu sunt echivalente,atunci iesirile generate nu sunt identice.Aceasta se marcheaza in celula corespunzatoare cu x.Daca doua stari sunt implicit echivalente, atunci iesirile sunt identice dar nu sunt identice starile urmatoare; starile care vor trebui comparate pentru a stabili echivalenta se mentioneaza in celula corespunzatoare sub forma m = n.

Figura :Tabelul de tranzitie pentru masina M1 din capitolul 2

a)

b)

c)

Figura 4.:a)Tabelul de implicatii pentru automatul M1

b)Prima trecere prin tabelul de implicatii

c)A doua trecere pentru reducerea numarului de stari

Modul in care se completeaza tabelul de implicatii pentru masina M1,la o prima trecere,este ilustrat in Figura 4.b.Celula de la intersectia starilor a si b caracterizeaza doua stari implicit echivalente care depind de echivalenta starilor b si c;in consecinta,se noteaza b = c in celula respective.Celula de la intersectia starilor c si d caracterizeaza alte doua stari implicit echivalente,care depind de echivalenta starilor a si d;se noteaza a = d in aceasta celula.Toate celelalte stari nu sunt echivalente.

La a doua trecere se verifica echivalenta starilor b si c,a si d,pentru a vedea daca acestea sunt dependente sau nu.Atat b-c cat si a-d sunt dependente de stari neechivalente(celulele de la intersectia starilor b-c si a-d contin fiecare cate un x);in consecinta,celulele care contin b = c si a = d sunt marcate cu x,dupa cum se arata in Figura 4.c.Pentru ca nu mai exista stari implicit echivalente care sa fie verificate dupa a doua trecere,putem spune ca nu exista stari identice sau echivalente in masina M1.Asadar pentru proiectare se poate lua in considerare un numar minim de patru stari.Atunci cand sunt identificate stari identice sau echivalente,de exemplu starea m si starea n,putem inlocui cele doua stari,n si m,peste tot cu aceeasi stare.

Aceeasi metoda de reducere se aplica si in cazul masinilor Mealy.