CID Seminar 6

În acest seminar vi se va prezenta noțiunea de automat finit și modul de descriere al acestuia în Verilog.

Cuvinte cheie: automat finit, FSM (Finite State Machine), Mealy, Moore, stare, tranziție Sintaxa Verilog: localparam

Automatul finit, numit și FSM (Finite State Machine), este un model matematic de computație, definit de următoarele elemente:

• O mulțime finită de simboluri de intrare, numită alfabet de intrare;
• O mulțime finită și nevidă de simboluri de ieșire, numită alfabet de ieșire;
• O mulțime finită și nevidă de stări, din care doar una, numită starea curentă, este activă la un moment dat;
• O stare inițială, care face parte din mulțimea stărilor;
• O funcție de tranziție a stărilor, care calculează starea următoare a automatului în funcție de starea curentă și de simbolul de intrare;
• O funcție de calcul a ieșirii, care determină simbolul de ieșire în funcție de starea curentă (în cazul automatelor de tip Moore) sau în funcție de starea curentă și de simbolul de intrare (în cazul automatelor de tip Mealy).

În sistemele digitale, un automat finit este utilizat pentru a programa o secvență de operații și se poate implementa ca un circuit secvențial. Astfel, simbolurile de intrare și de ieșire vor fi reprezentate de toate combinațiile posibile de intrare, respectiv de ieșire, ale circuitului. Funcția de tranziție a stărilor și funcția de calcul a ieșirii vor fi implementate ca circuite logice combinaționale (CLC-uri), iar starea curentă a automatului va fi memorată într-un registru intern.

La fiecare front al ceasului, valoarea stării următoare, calculată de către CLC, va fi încărcată în registru. Dacă registrul are n biți, numărul maxim de stări care pot fi reprezentate este 2ⁿ. Acest număr poate fi mai mic, în funcție de schema de codare a stărilor. De exemplu, pentru n = 4, folosind codarea binară se pot reprezenta cel mult 16 stări (0000, 0001, 0010, ..., 1111), în timp ce pentru codarea one-hot, în care doar un singur bit poate lua valoarea 1, se pot reprezenta 4 stări (1000, 0100, 0010, 0001).

Întrebare: Care este cel mai simplu automat cu care v-ați întâlnit până acum?

Stările și tranzițiile dintre acestea se pot reprezenta în diferite moduri. Cel mai folosit dintre acestea este diagrama de stări, în care stările și tranzițiile sunt reprezentate sub forma unui graf orientat. Alt mod posibil de reprezentare este tabelul de tranziție al stărilor, similar unui tabel de adevăr.