Mealy 型序列偵測器：偵測 10011

題目說明

請設計一個名為 fsm 的 Mealy 型有限狀態機，用來偵測單一位元序列輸入 IN。

當連續輸入序列為：

10011

時，輸出 MATCH 必須在最後一個輸入位元 1 到達時立即變為 1。

其他情況下：

MATCH = 0

此序列偵測器必須支援：

• 連續輸入
• 重疊偵測
• 多次偵測
• Mealy 型輸出

例如輸入：

100110011

包含兩次 10011：

10011
    10011

因此 MATCH 應在第 5 個與第 9 個輸入位元時為 1。

模組介面

Mealy FSM

Mealy 型有限狀態機的輸出同時取決於：

目前狀態

以及：

目前輸入

因此，當狀態已經記錄到：

1001

且目前輸入為：

1

時，可以立即輸出：

MATCH = 1

狀態定義

使用以下五個狀態：

當位於 S4 且輸入 IN = 1 時，完整序列 10011 被偵測到。

狀態轉移

S0

尚未匹配任何有效前綴。

IN = 0 → S0
IN = 1 → S1

S1

已匹配：

1

IN = 0 → S2
IN = 1 → S1

若再次輸入 1，這個新輸入仍可能是下一個 10011 的開頭，因此保持在 S1。

S2

已匹配：

10

IN = 0 → S3
IN = 1 → S1

S3

已匹配：

100

IN = 0 → S0
IN = 1 → S4

S4

已匹配：

1001

IN = 0 → S2
IN = 1 → S1，且 MATCH = 1

當 IN = 1 時，完整偵測到：

10011

偵測完成後轉到 S1，因為最後一個 1 也可能是下一個序列的第一個位元。

當 IN = 0 時，目前尾端為：

10

因此轉到 S2，以支援重疊偵測。

重置行為

當：

RST = 1

時：

• 狀態回到 S0
• MATCH 為 0

本題使用高電位有效非同步重置。

設計要求

• 模組名稱必須為 fsm。
• 必須偵測序列 10011。
• 必須使用 Mealy FSM。
• 必須支援連續偵測。
• 必須支援重疊序列。
• MATCH 只在完整序列最後一個位元到達時為 1。
• 其他週期 MATCH 必須為 0。
• RST 為高電位有效重置。
• 狀態暫存器必須在 CLK 上升沿更新。

程式設計模板

module fsm (
    input  IN,
    input  CLK,
    input  RST,
    output MATCH
);

    // Write your code here

endmodule