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.

Exemplul 1

Definiți stările și tranzițiile necesare pentru un automat finit care să recunoască secvența de intrare 0ⁿ1^m, cu n, m ≥ 0. Desenați diagrama de stări. Descrieți comportamental circuitul în Verilog. Realizați un modul de test pentru acest circuit.

Ce tip de automat ați implementat?

Explicații suplimentare:

Pașii pentru descrierea comportamentală a unui automat finit sunt următorii:

1. Analizați cerința și desenați diagrama de stări;
2. Numărați stările și stabiliți numărul de biți de care aveți nevoie pentru registrul de stare;
3. Definiți modulul în Verilog, adăugând intrările, ieșirile și registrul de stare intern;
4. Folosind un bloc always secvențial și un bloc condițional case, descrieți toate tranzițiile posibile către alte stări, pentru fiecare stare posibilă;
5. Definiți și descrieți ieșirile combinaționale în funcție de starea curentă și de intrări.

Observați că, odată ajuns într-una din stările finale, automatul se blochează. Pentru a putea trece înapoi în starea inițială, este necesar un semnal de reset. Prin urmare:

Regulă: Un automat finit are în mod obligatoriu un port de reset. Când reset-ul este activ, automatul trece într-una din stări, care este astfel desemnată ca fiind starea inițială.

Observați că avem o stare nefolosită. În general, ca regulă de bună practică, pentru toate stările nefolosite, care sunt reprezentate de cazul default din blocul case, tranziția următoare va fi întotdeauna către starea inițială (de reset).

Observați că stările sunt definite ca valori. Pentru un număr mare de stări, codurile vor deveni greu de înțeles. Prin urmare, introducem următoarele notații în modul:

localparam STATE_READ_0 = 2'b00;
localparam STATE_READ_1 = 2'b01;
localparam STATE_ERROR  = 2'b10;

Aceste notațiile le putem folosi apoi în locul valorilor.

Exemplul 2

Descrieți structural modulul de la exemplul anterior, astfel:

• Cele două CLC-uri vor fi definite ca module separate;
• Automatul va fi un modul „de top”, în care instanțiați cele două CLC-uri și registrul de stare.

Testați automatul cu modulul de test de la exercițiul anterior.

Exemplul 3

Realizați un automat finit pentru o mașină care vinde ciocolată CMOS, care costă 2,5 lei. Automatul acceptă monede de 50 de bani și bancnote de 1 leu. Denumiți starea curentă în funcție de suma acumulată în prezent, exprimată în multipli întregi de 50 de bani (de exemplu STATE_0_BANI, STATE_50_BANI, STATE_100_BANI etc.). Când se ajunge la suma de 2,5 lei sau mai mult, automatul va livra o ciocolată și va relua procesul, scăzând 2,5 lei din suma curentă. Automatul nu restituie restul.

Ce tip de automat ați implementat?

Explicații suplimentare:

Circuitul trebuie să aibă următoarele porturi:

• input load50bani – activ când este introdusă o monedă de 50 de bani
• input load1leu – activ când este introdusă o bancnotă de 1 leu
• output ack50bani – activ când automatul detectează inserția unei monede de 50 de bani
• output ack1leu – activ când automatul detectează inserția unei bancnote de 1 leu
• output productDelivered – activ când este livrată o ciocolată

De ce este nevoie de porturile „ack”?