Maszyny stanów w Verilogu: standardowy wzorzec FSM

Czym jest FSM

Automat skończony (FSM, finite state machine) to kontroler, który:

• W każdej chwili znajduje się w jednym ze stałego zbioru nazwanych stanów.
• Przechodzi między stanami na podstawie wejść (i ewentualnie bieżącego stanu).
• Generuje wyjścia zależne od bieżącego stanu (i być może od bieżących wejść).

To obejmuje zaskakująco dużą część projektowania cyfrowego: sterowniki sygnalizacji świetlnej, nadajniki UART, kontrolery pamięci, obsługę protokołów sieciowych, dekodery instrukcji, wszystko, co ma odrębne tryby pracy.

FSM różni się od logiki ścieżki danych tym, że operuje na stanach, a nie na wartościach. Licznik przechodzi przez 1, 2, 3, 4. FSM przechodzi przez IDLE, FETCHING, BUSY, DONE: ten sam kształt, ale stany mają nazwy, a przejścia mają znaczenie.

Wzorzec z dwoma procesami

Standardowy FSM w Verilogu używa dwóch bloków always:

1. Blok taktowany, który zapamiętuje rejestr stanu na każdym zboczu zegara. Używa przypisania nieblokującego. Jest malutki, zwykle ma trzy linie.
2. Blok kombinacyjny, który używa case na bieżącym stanie, żeby obliczyć następny stan i wyjścia. Używa przypisania blokującego. Tu znajduje się "ciekawy" kod.

Taki podział ma trzy zalety: zmusza do jawnego myślenia o stanie, daje sprzęt, który czysto odpowiada schematowi "jeden rejestr plus jeden blok kombinacyjny", i jest standardem, więc każdy, kto czyta twój kod w Verilogu, od razu go rozpozna.

Przykład: detektor sekwencji

Klasyczny dydaktyczny FSM: wykryj sekwencję bitów 1011 na wejściu szeregowym. Gdy sekwencja się zakończy, wygeneruj impuls trwający jeden cykl.

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

Struktura z dwoma blokami to punkt opisany wyżej. Warto zwrócić uwagę na szczegóły, które utrzymują porządek:

• Wartości domyślne na początku bloku kombinacyjnego. next_state = state (zostań w miejscu) i detected = 1'b0 (brak impulsu) to przypisania typu "nic nie rób". Każda gałąź case ustawia potem tylko to, co się różni. Dzięki temu nie da się utworzyć zatrzasku.
• localparam dla nazw stanów. Każdy, kto czyta moduł, myśli kategoriami S0, S1, S2, S3, a nie 3'd0, 3'd1. Podstawienia dokonuje syntezator.
• Brak wyjść w bloku taktowanym. Cała logika "co robi ten stan" znajduje się w bloku kombinacyjnym. Blok taktowany odpowiada wyłącznie za przechowywanie bieżącego stanu.

Moore a Mealy

Moore: wyjście zależy tylko od bieżącego stanu. Mealy: wyjście zależy od bieżącego stanu i bieżących wejść.

W powyższym przykładzie detected jest ustawiane w gałęzi S3 tylko wtedy, gdy in pasuje do jednego z oczekiwanych wzorców kończących sekwencję. To wyjście Mealy'ego: zależy od in, a nie tylko od state. Wersja Moore'a miałaby osobny stan "właśnie wykryto" i ustawiałaby detected = 1, gdy ten stan jest bieżący. Impuls pojawiłby się cykl później, ale nigdy nie byłby wrażliwy na zakłócenie na in.

Oba style są poprawne. W podręcznikach domyślny jest Moore, bo wyjścia na pewno nie wygenerują zakłóceń, gdy wejścia zmienią się w trakcie cyklu. Mealy jest szybszy (brak opóźnienia rejestru dla wyjść sterowanych wejściami) i w wielu przypadkach daje mniejszy sprzęt. Wybieraj zależnie od implementowanego protokołu.

Kodowanie stanów: binarne, one-hot, Gray

Wzorzec bitów przypisany do każdego stanu ma znaczenie dla powierzchni i szybkości:

• Binarne (S0 = 3'd0, S1 = 3'd1, ...): najmniejszy rejestr stanu, $\lceil \log_2 N \rceil$ bitów dla $N$ stanów. Najwięcej logiki dekodującej.
• One-hot (S0 = 4'b0001, S1 = 4'b0010, ...): N bitów dla N stanów. Logika dekodująca jest trywialna (każdy stan to jeden przewód), a przejścia są szybkie. FPGA często domyślnie używają tego kodowania.
• Kod Graya: kolejne stany różnią się jednym bitem. Przydaje się, gdy bity stanu przechodzą między domenami zegara.

Większość współczesnych narzędzi do syntezy sama wybiera kodowanie (Vivado, Quartus i Design Compiler mają tryb automatyczny, który próbuje każdego i wybiera najlepsze). Rzadko trzeba je określać. Gdy już trzeba: większość narzędzi akceptuje adnotację attribute albo pragmę (* fsm_encoding = "one_hot" *).

Wariant z trzema blokami

Czasem spotkasz FSM podzielony na trzy części: jeden blok taktowany dla stanu, jeden blok kombinacyjny dla następnego stanu i jeden blok kombinacyjny dla wyjść. To po prostu wzorzec z dwoma blokami, w którym obliczanie wyjść wydzielono do osobnego bloku:

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

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

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

Styl z wydzielonymi wyjściami przydaje się, gdy wyjść jest dużo, a logika następnego stanu byłaby zagracona, gdyby siedziały w tym samym bloku. Dla małych automatów to przesada.

Co robi default w FSM

Instrukcja case każdego automatu powinna mieć gałąź default. Z dwóch powodów:

1. Bezpieczeństwo: jeśli rejestr stanu jakimś sposobem przyjmie nieprawidłową wartość (uszkodzenie, błąd, częściowy reset), default przywraca go do znanego stanu.
2. Wskazówka dla syntezy: gdy jawne warianty są wyczerpujące (na przykład 2-bitowy stan z obsłużonymi wszystkimi 4 wartościami), default: next_state = 'x; mówi syntezatorowi "gwarantuję, że wariant domyślny jest nieosiągalny, optymalizuj swobodnie". Jeśli nieosiągalna ścieżka jednak zostanie osiągnięta w symulacji, powstałe x rozprzestrzeni się i od razu ujawni błąd.

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

Wybierz zależnie od tego, czy masz pewność, że wariant domyślny jest naprawdę nieosiągalny.

Na co uważać

Brak wartości domyślnych na początku bloku kombinacyjnego. Bez next_state = state i domyślnych wartości wyjść gałąź, która nie przypisuje wszystkiego, tworzy zatrzask.

Wyjścia w bloku taktowanym. Jeśli detected <= 1 znajduje się w bloku always @(posedge clk), wyjście jest rejestrowane i pojawia się cykl później. Może to być celowe (tzw. rejestrowane wyjście Mealy'ego), ale to też częsty przypadkowy błąd projektowy, gdy specyfikacja wymaga natychmiastowego impulsu.

Mieszanie przypisań blokujących i nieblokujących. Blok taktowany: <=. Blok kombinacyjny: =. Mieszanie obu w jednym bloku to wyścig.

Kombinacyjny blok always, który odwołuje się do next_state i przypisuje state. Tworzy to pętlę sprzężenia zwrotnego, której symulator nie potrafi rozwiązać. Blok taktowany jest właścicielem state, a blok kombinacyjny właścicielem next_state. Żaden z nich nie powinien dotykać zmiennej drugiego.

Co dalej

Potrafisz już zbudować każdy kontroler, który umiesz opisać. Następny rozdział robi krok wstecz od projektowania syntezowalnego i omawia testbenche, które ten projekt sprawdzają: jak podawać pobudzenie, obserwować wyjścia, zapisywać przebiegi i weryfikować, czy moduły naprawdę robią to, czego się po nich spodziewasz.