Mașini finite

Un automat finit este un tip de circuit secvential ce este proiectat cu ajutorul unor metode specifice ale starilor finite intr-un mod secvential predeterminat. Sunt doua tipuri de automate finite, Mealy si Moore. Iesireile automatului de tip Moore depind doar de starile in care se poate afla automatul. In schimb, iesirile automatului de tip Mealy depind atat de starile in care se poate afla automatul cat si de datele de la intrarile acestuia.

Un FSM (automat finit) este format din trei parti:

1. Registru secvential de stare curenta : acest registru reprezinta un set de circuite basculante bistabile (flip-flops) de n-biti sincronizat de un singur semnal de tact si este folosit pentru a retine (mentine) starile vectorului FSM-ului. Un vector de stare cu dimensiunea de n-biti are 2n valori cunoscute si ca stari de codare. De obicei nu toate 2n valori sunt necesare, prin urmare cele nefolosite trebuiesc proiectate astfel incat sa nu apara in timpul functionarii automatului. Un FSM cu m-stari necesita mai putin de log2(m) circuite basculante bistabile intr-un registru de stari.

2. Logica combinationala pentru starea urmatoare. Un FSM poate fi la un moment dat doar intr-o singura stare si fiecare tranzitie activata de semnalului de tact determina schimbarea FSM-ului din starea curenta in starea urmatoare. Aceasta este descrisa de logica pentru starea urmatoare. Starea urmatoare este o functie data de intrarile si starea curenta a FSM-ului.

3. Logica combinationala pentru iesiri: Iesirile, in cazul automatelor de tip Mealy sunt date de catre starea curenta in care se afla automatul si intrarile acestuia. Daca la un automat de tip Moore se vrea derivarea iesirilor de la starea urmatoare si nu de la starea curenta, atunci datele de iesire se inregistreaza pentru timpi "clock-to-out" mai rapizi.

Automatele de tip Moore si Mealy au urmatoarele structuri:

fig.1.Structura de baza a unui automat de tip Moore

fig.2. Structura de baza a unui automat de tip Mealy

Utilizand un semnal de reset se asigura un comportament robust si fara intreruperi a automatului. Astfel se asigura ca acesta intotdeauna va fi initializat cu o stare cunoscuta, valida, inaintea primului semnal de tact. In lipsa unui semnal de reset, nu exista nici o metoda de a prezice valoarea initiala a registrelor de stari cat timp circuitul este alimentat la tensiune. Automatul se poate bloca, ramanand intr-o stare necodificata, necunoscuta. Semnalul de reset ar trebui implementat in prima parte a automatului , in procesul secvential al strarii curente.

Semnalul de reset asincron este preferat in locul unui semnal sincron deoarece nu necesita decodarea starilor nefolosite, minimizand logica pentru starea urmatoare.

Deoarece tehnologiile FPGA detin mai multe resurse, codarea starilor in modul "one hot" (intr-o data de codare apare doar un singur de 1 si restul bitilor sunt 0) generata de intrumentul de sinteza poate utiliza o arie optima de porti logice si poate avea performante sporite.

Automatul de tip Mealy

Urmatorul exemplu reprezinta un model de automat de tip Mealy a carei diagrama de stare este prezentata mai jos:

fig.3. Diagrama de stare a unui automat de tip Mealy

Din diagrama de mai sus se poate descrie functionarea automatului. Cand acesta se afla in starea 0, daca intrarile sunt in 00 atunci iesirea va fi in 0 si automatul va ramane in starea 0; daca intrarile sunt in 10, atunci iesirea va fi in 1 iar automatul va trece in starea 1; daca intrarile sunt 01, atunci iesirea va fi in 1, iar automatul va trece in starea 4; daca intrarile sunt in 11, iesirea va fi in 1 si automatul va trece in starea 2.

Cand automatul se afla in starea 1, daca intrarile sunt in 00, atunci iesirea va fi in 0, iar automatul va trece in starea 1; daca intrarile sunt in 01 sau 11, atunci iesirea va fi in 0, iar automatul va ramane in starea 1; daca intrarile sunt in 10, atunci iesirea va fi in 0, iar automatul va trece in starea 2.