Proiectarea Automatului Finit (Semafor) în Verilog

Scopul lucrării: să se proiecteze un automat de dirijare cu luminile unui semafor.

Noţiuni teoretice

AUTOMATE FINITE

Definiţia formală a automatelor finite spune simplu că un automat este finit dacă mulţimea stărilor este finită. Inginerul, o fiinţă pragmatică, face imediat observaţia că orice automat fizic realizabil trebuie să posede un număr finit de stări. Definiţia au-tomatelor finite va deveni semnificativă pentru un practician numai cu o interpretare suplimentară, limpezitoare.Un prim comentariu posibil este acela că funcţia de tranziţie a stării unui au-tomat finit este specificată pentru o mulţime de stări ce nu poate deveni oricât de mare, aşa cum a fost cazul, spre exemplu, pentru numărătoare. Definiţia dată automatului numărător "funcţionează" pentru un numărător de n biţi, pentru un n oricât de mare, teoretic chiar infinit. În cazul unui automat finit, funcţia de tranziţie va presupune specificarea explicită a tuturor stărilor interne ale automatului şi a modului cum acestea comută. O astfel de definiţie nu va putea fi dată pentru un număr oricât de mare de stări, ci numai pentru stările specificate într-o manieră finită. Pentru automatele finite nu vom avea o regulă de specificare a regulii de comutare, aşa cum am reuşit pentru numărătoare. Absenţa unei forme regulate de definire a regulii va face ca automatele finite să fie nişte circuite complexe.Necesitatea de a specifica explicit modul în care se comută din fiecare stare a automatului finit, va impune definiţii cu o dimensiune proporţională cu dimensiunea spaţiului stărilor. Deci, dimensiunea definiţiilor automatelor finite fiind proporţională cu dimensiunea structurii automatelor finite, vom putea considera aceste tipuri de circuite ca fiind circuite complexe. Iar un circuit complex nu poate deveni oricât de mare (infinit!?), el este condamnat la finitudine.Un al doilea comentariu posibil referitor la finitudine este dat de modul de utilizare al automatelor finite. Una din aplicaţiile cele mai interesante ale automatelor finte o constituie recunoaşterea şi generarea şirurilor regulate de simboluri (şiruri generate cu un set finit de reguli simple, conform cărora şirul nu poate creşte decât la un capăt într-un mod independent de şirul deja format). Un automat care poate genera sau recunoaşte buna formare a unor şiruri regulate oricât de lungi, teoretic chiar infinite, va fi denumit, prin contrast, finit.Un al treilea comentariu posibil se referă la faptul că nu se pot da descrieri extensibile pentru conceperea automatelor finite. Nu vom putea niciodată folosi un au-tomat finit pentru a proiecta un alt automat finit care să-1 includă. Dacă dorim să extin-dem funcţionalitaea unui automat finit va trebui să-1 definim din nou şi să reluăm de la început procesul de proiectare. Automatele numărătoare, care nu sunt automate finite, dacă sunt proiectate pentru o anumită dimensiune, pot fi folosite ca atare în proiectul unui numărător extins. Acest lucru nu este posibil pentru automatele finite, ce nu pot fi privite ca structuri extensibile. Finitudinea lor le "împiedică" să devină oricât de mari, aşa cum pot să o "facă", spre exeemplu, numărătoarele sau automatele acumulatoare.

Structura automatelor finite

Automatele finite în varianta sincronă sunt caracterizate prin faptul că în struc-tura lor este realizată o perfectă segregare între:

• circuitul care stochează starea automatului: registrul de stare

• circuitele care calculează funcţiile de tranziţie ale stării şi ieşirii: circuite combinalinale complexe, realizate cu porţi, PLA-uri sau ROM-uri

• circuitul care realizează, când este cazul, întîrzierea ieşirii: registrul de ieşire.

Registrele reprezintă structuri simple, singurul efort pe care-l vom face pentru proiectarea lor este acela de a le specifica dimensiunea. Spre deosebire de registre, cir-cuitele combinaţionale folosite în proiectarea automatelor finite sunt circuite complexe. Complexitatea unui automat finit va fi dată, în consecinţă, de complexitatea circuitelor combinaţionale de calcul al celor două funcţii de tranziţie. Tehnologia curentă de re-alizare a acestor circuite va fi cea a PLA-urilor. Pentru circuite foarte simple, vom folosi porţi logice, iar pentru funcţii foarte complexe vom prefera să folosim ROM-uri, cel puţin pentru primele variante, cele de prototip.Semiautomatul, reprezentat în Figura 9.18a, este un concept cu o reprezentare simbolică (Figura 9.18b), util pentru dezvoltarea discursului legat de automate. Semi-automatul ca atare nu poate fi implementat fizic, dar este un nume bun pentru o parte a unui automat. Când realizăm fizic structura din Figura 9,18a, atunci realizăm de fapt un automat la care Q = Y iar g(qi) = qi. Dar când ne gândim exclusiv la bucla unui automat pentru a o optimiza sau a o adapta la un regim special de lucru putem folosi cu succes conceptul de semiautomat. Orice automat are un semiautomat asociat. Unui semiautomat i se pot asocia mai multe automate. Dar şi unui automat i se pot asocia mai multe semiautomate. Acest fapt va permite ca majoritatea tehnicilor de optimizare a structurii şi fucţionării automatelor să se aplice, de fapt, semiautomatului asociat.Structura unui semiautomat finit sincron conţine:

• registrul de stare, RSn, pentru semiautomatele cu cel mult 2n stări, recomandabil cu mai mult de 2n~l

« PLA-ul de pe buclă, LOOP PLA, la care se poate reduce orice circuit, pornind de la cea mai simplă reţea de porţi şi ajungând până la un ROM; PLA-ul are n + p intrări şi n ieşiri, dacă mulţimea X este codificată cu p biţi.

Mulţimea X este definită, de regulă, de cel care "comandă" proiectarea automat-ului. Mulţimea Q este definită de proiectantul automatului. Domeniul semiautomatului va fi cel în care proiectantul îşi va putea manifesta la maximum abilitatea, optimizând structura automatului ce i-a fost comandat spre realizare.Automatul Mealy imediat, reprezentat în Figura 9.18c, se obţine adăugând unui semiautomat un circuit ce calculează funcţia de tranziţie a ieşirii, OUTPUT PLA. Pentru acest tip de automat, funcţia de tranziţie a ieşirii este definită în produsul cartezian Q x X. OUTPUT PLA este un circuit combinaţional care va primi pe intrări valoarea variabilei de intrare, X, şi pe cea a variabilei de stare, Q. Va genera la ieşire o valoare din Y. între intrarea şi ieşirea acestui tip de automat este o cale combinaţională, în sensul că ieşirea poate "urmări", cu o întârziere dată de adâncimea OUTPUT PLA, orice variaţie a intrării. Intrarea este cuplată asincron la ieşire, cu toate avantajele şi dezavantajele ce vor decurge de aici. Automatul Mealy imediat este automatul cu reacţia cea mai rapidă a ieşirii la variaţiile intrării. Vom opta pentru această variantă de automat finit când vom avea nevoie de reacţii foarte prompte la un eveniment aplicat intrării.Automatul Moore imediat, reprezentat în Figura 9.18d, şe caracterizează prin faptul că funcţia sa de tranziţie a ieşirii depinde numai de stare. Circuitul combinaţional OUTPUT PLA adăugat semiautomatului va avea intrările conectate numai la registrul de stare, adică numai la "ieşirea" semiautomatului. Ieşirea acestui tip de automat suportă efectele variaţiei intrărilor numai prin intermediul tranziţiilor prealabile realizate în spaţiul stărilor. Efectul variaţiei intrării afectează ieşirea cu o întârziere de o perioadă a ceasului. Registrul de stare funcţionează în acest caz şi ca un registru de întârziere, facilitate pe care o are deoarece este realizat cu bistabili de tip D (delay), pentru care funcţia de întârziere este implicită. "Izolarea" ieşirii de intrare poate fi fructificată pentru obţinerea unor comporta-mente altfel imposibile. Dezavantajul izolării ieşirii de intrări va fi convertit în avantaj atunci când intrările vor pune "probleme" (spre exemplu, atunci când nu vor avea o variaţie sincronă cu ceasul sistemului). Din punct de vedere abstract, întotdeauna un comportament descris cu un automat de tip Mealy va putea fi descris şi cu un automat de tip Moore, dar realizarea concretă va pune probleme suplimentare, de regulă atunci când semnalele nu se vor com-porta "suficient de ideal". Lumea semnalelor reale cere din partea inginerilor nuanţări pe care spaţiul teoretic şi le poate apropia numai cu un efort suplimentar.