Máy trạng thái hữu hạn trong Verilog: mẫu FSM chuẩn

FSM là gì

Máy trạng thái hữu hạn (finite state machine) là một bộ điều khiển:

• Tại mỗi thời điểm luôn ở một trong một tập cố định các trạng thái có tên.
• Chuyển giữa các trạng thái dựa trên đầu vào (và có thể cả trạng thái hiện tại).
• Tạo ra đầu ra phụ thuộc vào trạng thái hiện tại (và có thể cả đầu vào hiện tại).

Mô hình này bao quát một phần đáng kinh ngạc của thiết kế số: bộ điều khiển đèn giao thông, bộ truyền UART, bộ điều khiển bộ nhớ, bộ xử lý giao thức mạng, bộ giải mã lệnh, bất cứ thứ gì có các chế độ hoạt động rời rạc.

Điều khiến FSM khác với logic đường dữ liệu là chúng gồm các trạng thái, không phải các giá trị. Một bộ đếm tăng dần qua 1, 2, 3, 4. Một FSM đi qua IDLE, FETCHING, BUSY, DONE: cùng hình dạng, nhưng các trạng thái có tên và các lần chuyển đều mang ý nghĩa.

Mẫu hai tiến trình

FSM chuẩn trong Verilog dùng hai khối always:

1. Một khối theo clock chốt thanh ghi trạng thái ở mỗi sườn clock. Dùng phép gán non-blocking. Rất ngắn, thường chỉ ba dòng.
2. Một khối tổ hợp dùng case trên trạng thái hiện tại để tính trạng thái kế tiếp và các đầu ra. Dùng phép gán blocking. Phần code "đáng chú ý" nằm ở đây.

Cách tách này có ba lợi ích: nó buộc bạn nghĩ về trạng thái một cách tường minh, nó tạo ra phần cứng ánh xạ gọn gàng thành "một thanh ghi cộng một khối tổ hợp", và nó là chuẩn chung: ai đọc code Verilog của bạn cũng nhận ra ngay.

Ví dụ hoàn chỉnh: bộ phát hiện chuỗi bit

Một FSM kinh điển trong giảng dạy: phát hiện chuỗi bit 1011 trên một đầu vào nối tiếp. Xuất ra một xung dài một chu kỳ khi chuỗi hoàn tất.

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

Cấu trúc hai khối chính là ý đã nêu ở trên. Vài chi tiết gọn gàng đáng chỉ ra:

• Giá trị mặc định ở đầu khối tổ hợp. next_state = state (ở nguyên chỗ cũ) và detected = 1'b0 (không có xung) là các phép gán "không làm gì". Sau đó mỗi nhánh case chỉ gán những gì khác đi. Nhờ vậy không thể nào suy ra latch.
• localparam cho tên trạng thái. Người đọc module nghĩ theo S0, S1, S2, S3, chứ không theo 3'd0, 3'd1. Công cụ tổng hợp sẽ tự thay thế.
• Khối theo clock không tạo đầu ra. Toàn bộ logic "trạng thái này làm gì" nằm trong khối tổ hợp. Khối theo clock chỉ có một nhiệm vụ là giữ trạng thái hiện tại.

Moore và Mealy

Moore: đầu ra chỉ phụ thuộc vào trạng thái hiện tại. Mealy: đầu ra phụ thuộc vào trạng thái hiện tại và đầu vào hiện tại.

Trong ví dụ trên, detected được gán trong nhánh S3 chỉ khi in khớp với một trong các mẫu hoàn tất chuỗi mong đợi. Đó là đầu ra Mealy: nó phụ thuộc vào in bên cạnh state. Một phiên bản Moore sẽ có thêm một trạng thái riêng cho "vừa phát hiện" và gán detected = 1 mỗi khi đang ở trạng thái đó; đầu ra sẽ có xung chậm hơn một chu kỳ nhưng không bao giờ bị ảnh hưởng bởi glitch trên in.

Cả hai kiểu đều hợp lệ. Moore là mặc định trong sách giáo khoa vì đầu ra được bảo đảm không bị glitch khi đầu vào đổi giữa chu kỳ. Mealy nhanh hơn (đầu ra phụ thuộc đầu vào không phải chờ qua thanh ghi) và trong nhiều trường hợp cho phần cứng nhỏ hơn. Hãy chọn dựa trên giao thức bạn đang hiện thực.

Mã hóa trạng thái: nhị phân, one-hot, Gray

Mẫu bit gán cho mỗi trạng thái ảnh hưởng đến diện tích và tốc độ:

• Nhị phân (S0 = 3'd0, S1 = 3'd1, ...): thanh ghi trạng thái nhỏ nhất, $\lceil \log_2 N \rceil$ bit cho $N$ trạng thái. Logic giải mã nhiều nhất.
• One-hot (S0 = 4'b0001, S1 = 4'b0010, ...): N bit cho N trạng thái. Logic giải mã rất đơn giản (mỗi trạng thái là một wire); chuyển trạng thái nhanh. FPGA thường mặc định dùng cách này.
• Mã Gray: hai trạng thái liên tiếp chỉ khác nhau một bit. Hữu ích khi các bit trạng thái đi qua nhiều miền clock.

Phần lớn công cụ tổng hợp hiện đại tự chọn cách mã hóa cho bạn (Vivado, Quartus, Design Compiler đều có chế độ tự động thử từng cách và chọn cách tốt nhất). Bạn hiếm khi phải chỉ định. Khi cần chỉ định: hầu hết công cụ chấp nhận một chú thích attribute hoặc một pragma (* fsm_encoding = "one_hot" *).

Biến thể ba khối

Thỉnh thoảng bạn sẽ thấy FSM được chia thành ba phần: một khối theo clock cho trạng thái, một khối tổ hợp cho trạng thái kế tiếp, một khối tổ hợp cho đầu ra. Đó chỉ là mẫu hai khối với phần tính đầu ra được tách ra khối riêng:

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

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

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

Kiểu tách đầu ra hữu ích khi có nhiều đầu ra và logic trạng thái kế tiếp sẽ rối nếu để chung một khối. Với FSM nhỏ thì cách này là thừa.

default làm gì trong FSM

Câu lệnh case của mọi FSM đều nên có nhánh default. Có hai lý do:

1. An toàn: nếu thanh ghi trạng thái bằng cách nào đó nhận giá trị không hợp lệ (dữ liệu hỏng, bug, reset không trọn vẹn), default đưa nó về một trạng thái đã biết.
2. Gợi ý cho công cụ tổng hợp: khi các nhánh tường minh đã đầy đủ (ví dụ trạng thái 2 bit với cả 4 giá trị đều được xử lý), default: next_state = 'x; báo cho công cụ tổng hợp rằng "nhánh mặc định chắc chắn không thể xảy ra, cứ tối ưu thoải mái". Nếu khi mô phỏng nhánh tưởng như không thể xảy ra lại xảy ra, giá trị x sinh ra sẽ lan truyền và làm lộ bug ngay lập tức.

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

Hãy chọn dựa trên việc bạn đã chứng minh được nhánh mặc định thật sự không thể xảy ra hay chưa.

Những điều cần để ý

Quên giá trị mặc định ở đầu khối tổ hợp. Thiếu next_state = state và giá trị mặc định cho đầu ra, một nhánh không gán đủ mọi thứ sẽ sinh ra latch.

Đặt đầu ra trong khối theo clock. Nếu detected <= 1 nằm trong khối always @(posedge clk), đầu ra sẽ đi qua thanh ghi và xuất hiện chậm một chu kỳ. Điều đó có thể là cố ý (đầu ra "Mealy qua thanh ghi"), nhưng thường là lỗi thiết kế vô tình khi đặc tả yêu cầu một xung tức thời.

Trộn blocking và non-blocking. Khối theo clock: <=. Khối tổ hợp: =. Trộn hai loại trong cùng một khối sẽ gây race condition.

Khối always tổ hợp đọc next_state và gán state. Như vậy tạo ra một vòng phản hồi mà trình mô phỏng không giải được. Khối theo clock sở hữu state; khối tổ hợp sở hữu next_state; đừng bao giờ để khối này đụng vào biến của khối kia.

Tiếp theo

Giờ bạn đã dựng được mọi bộ điều khiển mà mình mô tả được. Chương tiếp theo tạm rời thiết kế tổng hợp được để nói về testbench dùng để kiểm thử nó: cách tạo kích thích, quan sát đầu ra, ghi dạng sóng và xác nhận module của bạn thật sự làm đúng những gì bạn nghĩ.