Macchine a stati finiti in Verilog: il pattern FSM standard

Cos'è una FSM

Una macchina a stati finiti è un controller che:

• In ogni momento si trova in uno di un insieme fisso di stati con un nome.
• Passa da uno stato all'altro in base agli ingressi (e magari allo stato corrente).
• Produce uscite che dipendono dallo stato corrente (e forse dagli ingressi correnti).

Questo copre una quantità sorprendente di progettazione digitale: controller di semafori, trasmettitori UART, controller di memoria, gestori di protocolli di rete, decodificatori di istruzioni, tutto ciò che ha modalità di funzionamento discrete.

Ciò che rende le FSM diverse dalla logica di datapath è che lavorano con stati, non con valori. Un contatore scorre 1, 2, 3, 4. Una FSM scorre IDLE, FETCHING, BUSY, DONE: stessa forma, ma gli stati hanno un nome e le transizioni hanno un significato.

Il pattern a due processi

La FSM standard in Verilog usa due blocchi always:

1. Un blocco sincronizzato dal clock che cattura il registro di stato a ogni fronte. Usa l'assegnazione non-blocking. È minuscolo: di solito tre righe.
2. Un blocco combinatorio che usa un case sullo stato corrente per calcolare lo stato successivo e le uscite. Usa l'assegnazione blocking. Il codice "interessante" sta qui.

Questa separazione ha tre vantaggi: ti obbliga a ragionare esplicitamente sullo stato, produce hardware che corrisponde in modo pulito a "un registro più un blocco combinatorio" ed è lo standard: chiunque legga il tuo Verilog lo riconoscerà all'istante.

Un esempio completo: rilevatore di sequenza

Una FSM classica nei corsi: rilevare la sequenza di bit 1011 su un ingresso seriale ed emettere un impulso di un solo ciclo quando la sequenza è completa.

module seq_detect_1011(
    input  wire clk,
    input  wire reset,
    input  wire in,
    output reg  detected
);
    // State encoding - localparam because it's an implementation detail.
    localparam S0 = 3'd0;   // no progress
    localparam S1 = 3'd1;   // saw "1"
    localparam S2 = 3'd2;   // saw "10"
    localparam S3 = 3'd3;   // saw "101"

    reg [2:0] state, next_state;

    // ---------------------------------------------------------------------
    // Block 1: clocked state register
    // ---------------------------------------------------------------------
    always @(posedge clk) begin
        if (reset) state <= S0;
        else       state <= next_state;
    end

    // ---------------------------------------------------------------------
    // Block 2: combinational next-state + output logic
    // ---------------------------------------------------------------------
    always @(*) begin
        // Defaults - so we never accidentally infer a latch.
        next_state = state;
        detected   = 1'b0;

        case (state)
            S0: if (in)  next_state = S1;
            S1: if (~in) next_state = S2;
                else     next_state = S1;
            S2: if (in)  next_state = S3;
                else     next_state = S0;
            S3: if (in) begin
                    next_state = S1;
                    detected   = 1'b1;     // emit pulse, keep looking
                end else begin
                    next_state = S2;
                    detected   = 1'b1;     // same - pulse, then look from S2
                end
            default: next_state = S0;
        endcase
    end
endmodule

module test;
    reg clk = 0;
    reg reset = 1;
    reg in = 0;
    wire detected;

    seq_detect_1011 dut(.clk(clk), .reset(reset), .in(in), .detected(detected));

    always #5 clk = ~clk;

    initial begin
        #12 reset = 0;
        // Drive the input sequence: 1 0 1 1 (should detect at the second-to-last)
        in = 1; #10;
        in = 0; #10;
        in = 1; #10;
        in = 1; #10;    // <-- detected should pulse here
        in = 0; #10;
        // Try again with an overlapping sequence: 1 0 1 1 0 1 1
        in = 1; #10;
        in = 1; #10;    // another detection
        #20 $finish;
    end

    always @(posedge clk)
        $display("t=%0t in=%b state=%0d detected=%b", $time, in, dut.state, detected);
endmodule

La struttura a due blocchi è quella descritta nell'elenco precedente. Vale la pena sottolineare alcuni dettagli di pulizia:

• Valori predefiniti in cima al blocco combinatorio. next_state = state (resta dove sei) e detected = 1'b0 (nessun impulso) sono le assegnazioni "non fare nulla". Ogni ramo del case imposta poi solo ciò che cambia. Così è impossibile dedurre un latch.
• localparam per i nomi degli stati. Chi legge il modulo ragiona in termini di S0, S1, S2, S3, non di 3'd0, 3'd1. La sostituzione la fa il sintetizzatore.
• Nessuna uscita dal blocco sincronizzato. Tutta la logica del tipo "cosa fa questo stato" sta nel blocco combinatorio. Il blocco sincronizzato si occupa solo di mantenere lo stato corrente.

Moore e Mealy

Moore: l'uscita dipende solo dallo stato corrente. Mealy: l'uscita dipende dallo stato corrente e dagli ingressi correnti.

Nell'esempio precedente, detected viene impostato dentro il ramo S3 solo quando in corrisponde a uno dei pattern che completano la sequenza. È un'uscita di Mealy: dipende da in oltre che da state. Una versione di Moore avrebbe uno stato separato per "appena rilevato" e imposterebbe detected = 1 ogni volta che quello è lo stato corrente; l'impulso arriverebbe un ciclo dopo, ma non sarebbe mai sensibile a un glitch su in.

Entrambi gli stili sono validi. Nei libri di testo Moore è la scelta predefinita, perché le uscite non producono glitch quando gli ingressi cambiano a metà ciclo. Mealy è più veloce (nessuna latenza di registro per le uscite guidate dagli ingressi) e in molti casi produce hardware più piccolo. Scegli in base al protocollo che stai implementando.

Codifica degli stati: binaria, one-hot, Gray

Lo schema di bit assegnato a ogni stato conta per area e velocità:

• Binaria (S0 = 3'd0, S1 = 3'd1, ...): il registro di stato più piccolo, $\lceil \log_2 N \rceil$ bit per $N$ stati. La logica di decodifica più complessa.
• One-hot (S0 = 4'b0001, S1 = 4'b0010, ...): N bit per N stati. La logica di decodifica è banale (ogni stato è un wire) e le transizioni sono veloci. Sulle FPGA è spesso la scelta predefinita.
• Codice Gray: stati consecutivi differiscono di un solo bit. È utile quando i bit di stato attraversano domini di clock diversi.

La maggior parte degli strumenti di sintesi moderni sceglie la codifica per te (Vivado, Quartus e Design Compiler hanno tutti una modalità automatica che le prova e sceglie la migliore). Raramente devi specificarla. Quando serve, la maggior parte degli strumenti accetta un'annotazione attribute o un pragma (* fsm_encoding = "one_hot" *).

Una variante a tre blocchi

Ogni tanto vedrai la FSM divisa in tre parti: un blocco sincronizzato per lo stato, un blocco combinatorio per lo stato successivo e un blocco combinatorio per le uscite. È semplicemente il pattern a due blocchi con il calcolo delle uscite spostato in un blocco proprio:

// State register
always @(posedge clk) ...

// Next-state logic
always @(*) ...

// Output logic
always @(*) begin
    case (state)
        ...
    endcase
end

Lo stile con le uscite separate è utile quando le uscite sono tante e la logica dello stato successivo diventerebbe confusa se stessero nello stesso blocco. Per FSM piccole è eccessivo.

Cosa fa default in una FSM

L'istruzione case di ogni FSM dovrebbe avere un ramo default, per due motivi:

1. Sicurezza: se il registro di stato assume in qualche modo un valore non valido (corruzione, bug, reset parziale), default lo riporta in uno stato noto.
2. Suggerimento per la sintesi: quando i casi espliciti sono esaustivi (per esempio uno stato a 2 bit con tutti e 4 i valori gestiti), default: next_state = 'x; dice al sintetizzatore "ti garantisco che il default è irraggiungibile, ottimizza liberamente". Se in simulazione il percorso irraggiungibile viene raggiunto, la x risultante si propaga e fa emergere subito il bug.

default: begin
    next_state = S0;   // safe recovery
    // or
    next_state = 'x;   // unreachable, optimize freely
end

Scegli in base al fatto di aver dimostrato o meno che il default è davvero irraggiungibile.

A cosa fare attenzione

Dimenticare i valori predefiniti in cima al blocco combinatorio. Senza next_state = state e i valori predefiniti delle uscite, un ramo che non assegna tutto genera un latch.

Mettere le uscite nel blocco sincronizzato. Se detected <= 1 sta nel blocco always @(posedge clk), l'uscita è registrata e compare con un ciclo di ritardo. Può essere voluto (un'uscita "Mealy registrata"), ma è un errore di progetto frequente quando la specifica richiede un impulso immediato.

Mescolare blocking e non-blocking. Blocco sincronizzato: <=. Blocco combinatorio: =. Mescolarli nello stesso blocco crea una race condition.

Un blocco always combinatorio che legge next_state e assegna state. Crea un anello di retroazione che il simulatore non riesce a risolvere. Il blocco sincronizzato possiede state, quello combinatorio possiede next_state: nessuno dei due deve mai toccare la variabile dell'altro.

Cosa viene dopo

Ora puoi costruire qualsiasi controller tu sappia descrivere. Il prossimo capitolo fa un passo indietro rispetto al progetto sintetizzabile e tratta i testbench che lo mettono alla prova: come generare gli stimoli, osservare le uscite, registrare le forme d'onda e verificare che i tuoi moduli facciano davvero ciò che pensi.