HDLBits刷題筆記

以下是在做HDLBits時的一些刷題筆記，截取一些重要內容并加上自己的理解，方便以后翻閱查找

Circuits

Fsm1

到狀態機了，這在FPGA設計部分是核心的核心，一定要好好學！好好學！好好學！

我們之前的筆記提到過，想要利用HDL這種并行處理語言完成順序的邏輯功能是有兩個成熟的方法論的。一個是狀態機（State Machine），另一個是流水線（Pipeline）。這兩種方法論在數學上的表達區別就是狀態機的狀態state一定是可以組成環形的，而流水線的階段stage首尾不會相連，如下就是二者在邏輯拓撲上的區別：

基本上就是狀態機是一個不斷循環的機器，而流水線就是一條順序的數據處理線，不會有循環結構出現。由于這篇筆記的重點不是流水線，就先簡單介紹一下流水線，之后的大篇幅都留給狀態機就好。流水線其實可以非常簡單，一個寄存器就可以看作一個簡單的一階流水線，例如如下代碼：

reg [7:0]r;
reg [7:0]r_buf;
always@(posedge clk)beginr_buf <= r;
end

大家不要看這個代碼簡單，其實在項目中用得很多，而且一般的項目就是用一階或二階寄存器組成流水線，用來寄存數據或者優化時序。

當然，如果你學過微機原理，應該聽過CPU為了加快數據處理速率會有高階流水線。沒錯，CPU里流水線的概念和FPGA里的完全一致，我們甚至可以用FPGA實現一個CPU流水線，進而完成CPU的功能。如果大家好奇，可以在網上找一找OpenMIPS的書籍和資料，里面就用FPGA實現了一個簡單的五級流水線CPU。

通過上述兩個簡單的例子，大家應該也能看出流水線的核心就是輸出的處理和流動，它主要就是關注如何更快地處理一件事。簡而言之，流水線是一個加速器。在技術實現上，流水線可以將一個復雜的組合電路分開，并在模塊之間通過寄存器存儲，這樣，多個數據就可以在同一時間處于該任務的不同處理階段，極大地提高了數據處理的吞吐率。在本質上，流水線就是將一個復雜的組合邏輯路分解成小階段stages，并在每個階段之間插入寄存器。而流水線的常見工作場景就是那些需要高速數據處理甚至需要優化時序的場景（高速場景下時序收斂會變困難），例如：1.高速的通信領域需要流水線優化時序;2.數字信號處理或者復雜的算數運算實現；3.圖像和視頻處理；4.CPU指令處理流水線。

好了，關于流水線就記這么多筆記，因為一般來說對于通用的FPGA編程，流水線最常見的作用就是添加幾個寄存器用來優化時序。至于想要學習像DSP、圖像視頻處理、CPU這類細分領域的流水線，就要學習專業領域的內容了，通用性并不強。

接下來就都是關于狀態機的內容了。狀態機的重要程度要比流水線高得多，原因就是狀態機是一套非常通用的方法論，你也許不需要在高速場景下編程，所以可能用不到流水線；但只要你想實現任何稍微復雜點的任務或功能，無論是在高速還是低速，抑或是通信或者IC等不同領域，你都離不開狀態機，它在FPGA編程中幾乎無處不在。 先說一下什么是狀態機。狀態機，全稱有限狀態機（Finite State Machine, FSM），描述了一個設備在有限數量的狀態之間轉換的行為。我們剛剛了解了流水線，那就接著話茬，如果說流水線是一個加速器，那么狀態機就是一個控制器，關注的是“何時”做什么事。

狀態機的核心作用是根據當前的狀態和外部輸入，來決定下一步的操作和要轉換到的狀態。它本質上是一個時序控制器，非常適合用于實現任何涉及多個步驟、需要決策或遵循特定順序的任務。對于任何狀態機，都有三個重要的組成：一定數量的狀態、狀態間跳轉的條件以及狀態機的輸出。對于如何狀態機輸出方式的不同，可以進一步細分為Moore型與Mealy型狀態機，如下是二者的根本區別：

狀態機類型	Moore型	Mealy型
輸出決定因素	輸出僅取決于當前的狀態	輸出取決于當前狀態和當前的輸入

到現在為止就是有關狀態機的主要理論知識。但是還不夠，我們需要用Verilog代碼實現呀！假設我們現在要完成一個最最簡單的狀態機，那就是去檢測2’b10序列，只要檢測到2’b10序列，我們就輸出一個1。在這個例子中我們選用Mealy型狀態機。那么寫的思路是怎樣的呢？狀態機狀態機，那我們需要狀態呀，我可以定義IDLE(初始狀態)和GOT_1（檢測到1’b1）兩個狀態，這部分可以用parameter來實現。狀態機初始化在IDEL狀態，只要檢測到1，我們就進入GOT_1狀態。而到了GOT_1狀態，我們就立刻檢查輸入，如果輸入是0，我們就檢測到了10序列，反之我們重新進入IDEL狀態。將上述語言轉化為代碼就是如下效果：

module fsm_1_segment(input  wire clk,input  wire rst,input  wire din,output reg  dout
);parameter IDLE = 1'b0, GOT_1 = 1'b1; //狀態定義reg current_state;always @(posedge clk or posedge rst) beginif (rst) begincurrent_state <= IDLE;dout          <= 1'b0;end else begin// 默認輸出為0dout <= 1'b0;case (current_state)IDLE:if (din)current_state <= GOT_1;// else, current_state保持不變GOT_1:if (!din) begindout          <= 1'b1; // 檢測到'0'，立即輸出1current_state <= IDLE;  // 同時返回IDLEend elsecurrent_state <= GOT_1; // 如果是'1'，保持在GOT_1endcaseendend
endmodule

這種最直接在一個時序always塊中實現狀態機的寫法就稱為一段式狀態機，其實在這個簡單例子的情況下看上去邏輯還算清晰。但如果仔細閱讀代碼你就會發現兩個問題：第一個問題是由于整個塊是寫在時序always塊中的，所以dout也被綜合成寄存器，這樣就導致我們的輸出不及時。我們舉個例子，例如現在已經處于GOT_1狀態，并且我輸入了一個0，在這個時鐘周期內我們是不會輸出1的，需要等到下一個時鐘周期dout才會被更新。或許這就是你想要的結果，但是在這個例子中我希望狀態機能夠及時響應我的輸出，也就是說dout應該放在組合邏輯中進行賦值。

第二個問題是always塊的復雜程度，我們這個簡單的例子狀態和輸出變量比較少，但是如果狀態多起來呢？狀態跳轉復雜起來呢？輸入輸出量多起來呢？全擠在一個時序always塊中也不是個辦法，那就嘗試分離。怎么分離呢？我們可以想象，如果狀態機的規模一旦變大，一段式狀態機里就會全是各種狀態跳轉以及輸出內容的條件判斷，這些條件判斷其實就是靠組合邏輯的各種邏輯門完成的,而我們時序always塊中真正的寄存器其實就是current_state這個變量。所以一個簡單的想法應運而生，我們試著把耦合在這個時序always塊中的組合邏輯抽離出來，重新寫在一個always@(*)中。當然也順便把dout也寫在這個組合邏輯塊中，為了加快狀態機的反應速度，于是有了下面的寫法：

module fsm_2_segment(input  wire clk,input  wire rst,input  wire din,output reg  dout
);parameter IDLE = 1'b0, GOT_1 = 1'b1;reg current_state, next_state;// --- 第一段: 狀態寄存器 (時序邏輯) ---always @(posedge clk or posedge rst) beginif (rst)current_state <= IDLE;elsecurrent_state <= next_state;end// --- 第二段: 狀態跳轉與輸出邏輯 (組合邏輯) ---always @(*) begin// 必須賦默認值，防止生成鎖存器next_state = current_state;dout       = 1'b0;case (current_state)IDLE:if (din)next_state = GOT_1;GOT_1:if (!din) begindout       = 1'b1; // 檢測到'0'，輸出1next_state = IDLE;end elsenext_state = GOT_1;endcaseend
endmodule

千萬不要忘了之前的知識，雖然current_state和next_state在定義時都是reg類型，但是current_state是在時序always塊中賦值，會被綜合成一個真正的寄存器；而next_state寫在always@(*)中，仍然是一個組合邏輯，只會被綜合成線網和邏輯門的組合。

上面這種把狀態寄存器的更新與狀態跳轉和輸出邏輯分離的狀態機寫法就被成為二段式狀態機。這樣做略微提升了代碼的可讀性，但是你仔細想想就會發現這樣做并沒有解決根本問題，因為狀態跳轉和輸出邏輯才是狀態機中占行數最多的部分，這兩部分現在仍然擠在一個always(*)塊中。一段式狀態機會有一個臃腫的時序always塊，而二段式狀態機產生了一個臃腫的alway@(*)塊。那么可以再優化一點嗎？當然可以，我們接著把狀態跳轉和輸出邏輯拆成獨立的兩個alway@(*)進行賦值就好了，所以有了如下寫法：

module fsm_3_segment(input  wire clk,input  wire rst,input  wire din,output reg  dout
);parameter IDLE = 1'b0, GOT_1 = 1'b1;reg current_state, next_state;// --- 第一段: 狀態寄存器 (時序邏輯) ---always @(posedge clk or posedge rst) beginif (rst)current_state <= IDLE;elsecurrent_state <= next_state;end// --- 第二段: 下一狀態邏輯 (組合邏輯) ---always @(*) beginnext_state = current_state; // 默認保持當前狀態case (current_state)IDLE:if (din)next_state = GOT_1;GOT_1:if (!din)next_state = IDLE;endcaseend// --- 第三段: 輸出邏輯 (組合邏輯) --- 與二段式狀態機波形相同always @(*) begindout = 1'b0; // 默認輸出為0if (current_state == GOT_1 && !din)dout = 1'b1;end/* --- 第三段：輸出邏輯（時序邏輯）--- 與一段式狀態機波形相同always @(posedge clk or posedge rst) beginif(rst)dout <= 1'b0;else if (current_state == GOT_1 && !din)dout <= 1'b1;end*/
endmodule

這樣做就清晰多了，這種將狀態寄存器、下一狀態邏輯、輸出邏輯分成三個獨立部分的寫法可維護性強了不少，被稱為三段式狀態機。大家觀察不難發現，三段式狀態機的輸出其實既可以寫成時序邏輯（慢一拍輸出，和一段式狀態機一樣），也可以寫成組合邏輯（當前時鐘周期輸出，和二段式狀態機一樣），這樣的靈活度大大提高，即三段式完全可以替代一段式和二段式狀態機，但一段式和二段式狀態機相互之間不能替代。一般來說，在公司里做落地項目的，都是使用三段式狀態機寫法。學習或者不太嚴謹的項目中，那就無所謂了，但是還是建議使用三段式狀態機。

我們這里給出三種狀態機寫法的區別：

狀態機類型	狀態改變	下一狀態判斷邏輯	輸出邏輯
一段式	時序邏輯	（耦合在時序邏輯中的）組合邏輯	時序邏輯
二段式	時序邏輯	組合邏輯	組合邏輯
三段式	時序邏輯	組合邏輯	時序邏輯或者組合邏輯（取決于需要）

接下來給出三段式狀態機的基本模板，其實挺公式化的，用用就記住了：

/*預備工作：狀態定義+reg類型的兩個state（注意位寬一致）*/
parameter IDLE = 2'00,STATE_0 = 2'01,STATE_1 = 2'10,...;
localparam PL_STATE_BITS = $(IDLE); //參數化保持位寬一致
reg[PL_STATE_BITS-1:0] current_state, next_state;/*第一段：狀態更新 時序邏輯*/
always @(posedge clk or posedge rst) begin //可選同步和異步復位if (rst)current_state <= IDLE;elsecurrent_state <= next_state;
end/*第二段：條件跳轉 組合邏輯*/
//這部分推薦使用case+if的組合
always @(*) beginnext_state = current_state; case (current_state)IDLE:if (...)next_state = ...;STATE_0:if (...)next_state = ...;endcase
end/*第三段：輸出控制類型一 組合邏輯 當前時鐘周期立刻輸出*/
//這部分寫法自由，也常用case+if的組合，當輸出邏輯判斷簡單或輸出情況很少時也常用assign + ?:的組合。但是一定注意對于assign，out_comb是wire類型；對于always，out_comb是reg類型。
always @(*) beginout_comb = 1'b0; // 默認輸出為0if (current_state == ...)out_comb = ...;
end/*第三段：輸出控制類型二 時序邏輯 下一時鐘周期輸出*/
always @(posedge clk or posedge rst)begin //可選同步和異步復位if (rst)out_ff <= ...;else if (current_state == ...)out_ff <= ...;
end

之后沒啥意外就都用三段式狀態機的寫法了，養成一個好習慣。

現在我們知道了如何用Verilog實現一個狀態機了，現在需要具體化一點，那就是如何用代碼分別實現Moore型和Mealy型狀態機，還是剛剛那個檢測10序列的例子，如下是Moore型狀態機：

module fsm_3_segment_moore(input  wire clk,input  wire rst,input  wire din,output wire dout // Moore型輸出用wire更直觀，可以用assign語句
);// 1. 狀態定義: 增加了一個SUCCESS狀態parameter IDLE    = 2'b00;parameter GOT_1   = 2'b01;parameter SUCCESS = 2'b10; // 新增狀態，用于產生輸出// 狀態寄存器需要2位來表示3個狀態reg [1:0] current_state, next_state;// --- 第一段: 狀態寄存器 (時序邏輯) ---// 這部分結構完全不變，只是寄存器位寬變了always @(posedge clk or posedge rst) beginif (rst)current_state <= IDLE;elsecurrent_state <= next_state;end// --- 第二段: 下一狀態邏輯 (組合邏輯) ---// 這部分邏輯需要修改以包含新的SUCCESS狀態always @(*) beginnext_state = current_state; // 默認保持當前狀態case (current_state)IDLE:if (din)next_state = GOT_1;GOT_1:if (!din)// 當檢測到"10"中的'0'時，跳轉到SUCCESS狀態next_state = SUCCESS;else// 如果是"11"，則保持在GOT_1，因為這個'1'可以是新序列的開始next_state = GOT_1;SUCCESS:// 在成功狀態停留一個周期后，必須離開// 如果當前輸入是'1'，它可以是新序列的開始if (din)next_state = GOT_1;elsenext_state = IDLE;endcaseend// --- 第三段: 輸出邏輯 (組合邏輯) ---// *** 這是從Mealy到Moore最核心的改變 ***// 輸出只依賴于 current_state，與 din 無關。// 使用連續賦值語句 assign 會更簡潔清晰assign dout = (current_state == SUCCESS);/*// 如果想繼續使用always塊的寫法：always @(*) beginif (current_state == SUCCESS)dout = 1'b1;elsedout = 1'b0;end*/
endmodule

至于Mealy型狀態機剛剛說到三段式狀態機的時候就已經給出代碼了。對比一下不難看出，Mealy型狀態機由于輸出可以受輸入直接影響，所以在檢測到1的時候就可以直接在組合邏輯中判斷新輸入的數據是否是0；Moore型狀態機由于輸出是不能受輸入數據直接影響的，所以為了檢測10序列必須多出一個狀態用來確定10序列是否成功輸入，進而影響輸出。所以Mealy型狀態機的優點就是快一些，完成同樣的功能條件下，比Moore型狀態機需要的狀態數更少。但問題也很明顯,Mealy狀態機輸出信號是異步的并且是組合邏輯，容易產生毛刺。至于Moore型狀態機，他的輸出完全在時序邏輯的控制下，所以雖然反應比Mealy類型慢，但是輸出卻穩定得多。于是，我們得到以下兩種狀態機的區別：

狀態機類型	Moore型	Mealy型
輸出決定因素	輸出僅取決于當前的狀態	輸出取決于當前狀態和當前的輸入
輸出時序	輸出信號與時鐘同步，通常在狀態轉換完成后才更新，因此輸出是穩定的，不會出現毛刺	輸出信號是異步的，對輸入的任何變化都會立即做出反應，可能產生毛刺
狀態數量	為了在不同輸入下產生不同輸出，可能需要更多的狀態	通常可以用更少的狀態來實現相同的功能
響應速度	對輸入的響應會延遲一個時鐘周期，因為輸出需要等待下一個狀態的到來	對輸入的響應速度更快，可以在當前時鐘周期內立即改變輸出
硬件實現	通常更容易設計和調試，因為輸出是可預測且穩定的	設計上可能更復雜，需要仔細處理時序問題，以避免由于輸入信號的不穩定而導致錯誤的輸出

圍繞狀態機控制能力強的特點，我們可以總結出以下常見應用場合：1.用戶接口和通用事件處理（例如，實現一個自動售貨機代碼）；2.通信協議實現（ I2C、SPI、UART、CAN等協議實現）；3.控制單元和仲裁器(CPU的控制單元、DDR內存控制器、總線仲裁器);4.復雜算法的任務流程管理。等等。

有了這些知識儲備，這一題的答案也就迎刃而解了，如下：

這一題還是比較簡單，因為題目直接把A和B兩個狀態顯式地給了出來，下一題就給出需要自己確定狀態數了。

Fsm1s

這一記錄一下主要是想要補充一個知識點，然后吐槽一下模板里的代碼。先說補充的點吧，那就是狀態機的表述方式，主要有四種方法：自然語言描述、狀態轉移表、狀態轉移圖和HDL代碼。

還是拿上面那個簡單的2’b10序列檢測狀態機例子說明，用自然語言描述就是：如果Mealy狀態機，一共使用IDLE(初始狀態)和GOT_1（檢測到1’b1）兩個狀態。狀態機初始化在IDEL狀態，只要檢測到1，我們就進入GOT_1狀態，反之保持IDEL狀態。而到了GOT_1狀態，我們就立刻檢查輸入，如果輸入是0，我們就檢測到了10序列，反之我們重新進入IDEL狀 態。如果使用Moore狀態機，一共使用IDEL、GOT_1和SUCCESS三個狀態。狀態機初始化在IDEL狀態，只要檢測到1，我們就進入GOT_1狀態，反之保持IDEL狀態。在GOT_1狀態下如果輸入1，就進入SUCCESS狀態，反之保持GOT_1狀態。在SUCCESS狀態下，如果輸入1，就回到GOT_1狀態，反之回到IDEL狀態。同時，只有在SUCCESS狀態下才輸出1。

其實我們如果想要從零開始寫一個狀態機，一般都是（在心中）先用自然語言想清楚的。但是自然語言描述的狀態機不簡潔，也不容易轉化成代碼，進而有了兩種方法進一步對自然語言抽象，首先就是狀態轉移表，主要以現態、輸入、次態和輸出四部分內容為表頭，首先是Mealy型狀態機：

其次是Moore型狀態機：

表的大小取決于狀態的數量和輸入的類型數量。

狀態轉移表其實很適合那些喜歡用表格來表達邏輯關系的人，如果你喜歡使用圖像來思考，也可以使用狀態轉移圖，以下是兩種狀態機的狀態轉移圖：

對于Mealy型狀態機，由于其輸出受輸入直接影響，所以輸出寫在了狀態轉移箭頭旁邊（輸入/輸出）；而對于Moore型狀態機，由于其輸出只受狀態影響，所以其輸出寫在了表示狀態的圓圈內。

最后是狀態機的代碼表示，上一題已經給過了，這里不再啰嗦。

一般來說對于簡單的狀態機，可以直接從自然語言轉化成代碼；但是對于相對復雜的狀態機，就需要先從自然語言轉換到狀態轉移圖（表），以此為踏板再轉化成代碼。

再說回本題，本題的提示是有問題的，我們來看看槽點：

這是HDLBits給的模板，乍一看是一個一段式狀態機，那我們先按一段式狀態機的思路來寫。但你看看這個模板，就會發現，如果真是一段式狀態機，那么就不需要next_state這個變量，一個present_state足以勝任；其次，即便真的需要next_state這個變量，提示中22行present_state = next_state; 竟然用了阻塞賦值！這是一個明顯的錯誤,我們這里先按一段式狀態機的思路來把代碼寫下來：

但是仿真的波形錯誤了：

從波形就可以看出來，我們的輸出比案例慢了一個時鐘周期，所以顯然答案希望我們使用組合邏輯給out賦值，但是又只有二段式或者三段式狀態機才能在輸出時用組合邏輯。這不純純矛盾？？？很疑惑的我被整無奈了。。。所以就用三段式的組合邏輯輸出重新寫了一下，于是得到答案：

Fsm2

這一題引入了兩位輸入，但是換湯不換藥：

Fsm3onehot

這題提出了一個很重要的編碼概念：one-hot編碼，即獨熱碼。獨熱碼是一種用N位寄存器來表示N個狀態的編碼方法。其核心思想是，在任何時刻，這N位寄存器中有且僅有一位為高電平（1），其余所有位都為低電平（0）。顯然獨熱碼是非常消耗硬件資源的，如下是其和二進制編碼的區別：

從上表可以看出：

• 二進制編碼：使用了最少的觸發器。log_2(4)=2 個觸發器。
• 獨熱碼：使用了與狀態數量相等的觸發器，即4個。

那我們為什么我們還是要使用獨熱碼呢？因為獨熱碼有以下優點：

• 解碼邏輯極其簡單，速度快 (High Speed)

  這是獨熱碼最核心、最突出的優點。由于每一位直接對應一個狀態，判斷當前是否處于某個特定狀態變得異常簡單。對于獨熱碼，判斷是否在S2狀態，只需檢查 current_state[2] 是否為1；而對于二進制編碼，判斷是否在S2狀態（編碼10），則需要檢查 current_state == 2’b10，這在硬件上需要一個與門 (current_state[1] && !current_state[0])。當狀態數量增多時，二進制碼的解碼邏輯會變得越來越復雜，組合邏輯路徑變長，從而限制了狀態機的最高運行時鐘頻率。而獨熱碼的解碼邏輯始終只是檢查一位，因此組合邏輯路徑非常短，非常有利于高速設計。

• 狀態轉換邏輯更簡單

  在計算下一個狀態時，邏輯也常常被簡化。因為每個狀態的轉換只涉及“熄滅”當前位和“點亮”下一位，這使得生成下一狀態的組合邏輯也可能更簡單、更快。

• 安全性與可預測性

  由于任何時候只允許一位為1，系統很容易檢測到非法狀態（例如，同時有兩位為1，或者全為0）。這為設計增加了一層內在的錯誤檢測機制，有助于設計一個更魯棒的系統。

那么獨熱碼的缺點也很明顯：

• 消耗更多的觸發器
  這是獨熱碼最顯著的缺點。N個狀態需要N個觸發器，而二進制編碼只需要log_2(N)
• 狀態數量受限
  對于狀態數量非常龐大的狀態機，使用獨熱碼會急劇增加寄存器的數量，可能導致資源緊張。

說白了，使用獨熱碼的本質就是用面積換性能。

說回這一題，題目的意思并不是讓你直接編程一個one-hot狀態機，而是為了檢查你是否理解了one-hot編碼每次只有一位會為1的精髓。說白了，這一題對于狀態A、B、C、D的one_hot編碼就是4’b0001、4’b0010、4’b0100、4’b1000;而模板代碼中給的A=0、B=1…其實只是狀態A、B、C、D的索引,并不是獨熱碼本身。也就是說，如果state處于A狀態，那么state[ A]就為1，state[ B ]以及其他位就是0。本題就是希望你使用獨熱碼的這一特點利用簡單的邏輯計算來確定下一狀態，本質上就是一個真值表的問題，答案如下：

剛好下一題的答案就是用one-hot編碼進行編寫，如下：

Exams/ece241 2013 q4

這一題的題干提出了一個任務需求，而我們需要將這個需求用狀態機的語言描述出來最后再用代碼實現。如下是問題的譯文：

簡而言之就是我們需要做一個蓄水池的控制器，控制依據就是靜態水位和動態水位的變化情況。根據靜態水位，我們分了三個擋位；而根據動態水位是增高還是降低，我們給了一個dfr控制。所以我有了一個簡單想法：那就是分為4個狀態，即4個水位高度，然后根據這個狀態直接控制fr的輸出，至于dfr則需要進一步判斷上一個水位的狀態再來輸出。

我們其實還需要補充一些假設,這些在題目中沒有明確說明：第一，水位的變化是連續的，例如，水位如果是已經是最低，那么水位只會往上漲到次低位，不可能在下個時鐘突然變成最高位；第二，水位的變化就是離散的，只有四個離散水位，不存在中間值；第三，dfr復位的值為1，而且在一個完整的state狀態下需要保持住賦值狀態。

最后分析一下輸出，顯然fr和我假設的四個狀態是一一對應的，是靜態的，所以直接使用組合邏輯輸出就好；而dfr不同，他需要你記住上一個狀態，擁有記憶功能，所以需要使用時序邏輯進行輸出。進而得到我的答案：

module top_module (input clk,input reset,input [3:1] s,output fr3,output fr2,output fr1,output dfr
); parameter 	PS_HIGH = 4'b1000,PS_MEDH = 4'b0100,PS_MEDL = 4'b0010,PS_LOW  = 4'b0001;localparam PL_STATE_BITS = $bits(PS_HIGH);reg [PL_STATE_BITS-1:0]current_state,next_state;always@(posedge clk)beginif(reset)begincurrent_state <= PS_LOW;end else begincurrent_state <= next_state; endendalways@(*)begin/*狀態機的寫法思路*/next_state = current_state;       case(current_state)PS_HIGH:if(s == 3'b011) beginnext_state <= PS_MEDH; endPS_MEDH:if(s == 3'b111)beginnext_state <= PS_HIGH; end else if(s == 3'b001)beginnext_state <= PS_MEDL; endPS_MEDL:if(s == 3'b000)beginnext_state <= PS_LOW; end else if(s == 3'b011) beginnext_state <= PS_MEDH; endPS_LOW:if(s == 3'b001)beginnext_state <= PS_MEDL; endendcase/*這樣寫不是狀態機的思路，但也可以完成功能if(s == 3'b000)beginnext_state <= PS_LOW; end else if(s == 3'b001)beginnext_state <= PS_MEDL; end else if(s == 3'b011) beginnext_state <= PS_MEDH; end else if(s == 3'b111)beginnext_state <= PS_HIGH; end*/end/*靜態輸出 不需要有記憶功能，所以使用組合邏輯*/reg[3-1:0]r_fr;always@(*)beginr_fr = 3'b000; case(current_state)PS_HIGH: r_fr = 3'b000;PS_MEDH :r_fr = 3'b001;PS_MEDL :r_fr = 3'b011;PS_LOW  :r_fr = 3'b111;endcaseendassign {fr3,fr2,fr1} = r_fr;/*動態輸出 需要有記憶功能，所以使用時序邏輯*/always@(posedge clk)beginif(reset)begindfr <= 1'b1;end else begincase(current_state)PS_HIGH :if(next_state == PS_MEDH) dfr = 1'b1;else dfr = dfr;PS_MEDH :if(next_state == PS_MEDL) dfr = 1'b1;else if(next_state == PS_HIGH) dfr = 1'b0;else dfr = dfr;PS_MEDL :if(next_state == PS_LOW) dfr = 1'b1;else if(next_state == PS_MEDH) dfr = 1'b0;else dfr = dfr;PS_LOW  :if(next_state == PS_MEDL) dfr = 1'b0;else dfr = dfr;endcaseend end
endmodule

值得分析一下的是示例的答案：

看上去很簡潔，主要原因是示例中狀態的設置更巧妙。我們來分析一下，示例中的狀態分為了六種，剛好對應了fr和dfr組合起來的六種輸出。用自然語言描述就是，A1代表水位最低且dfr輸出為1，B1代表水位次低且dfr輸出為0，B2代表水位次低且dfr輸出為1，…。于是，在這種情況下，fr的輸出和dfr就能統一在一起了。那么dfr輸出需要的記憶功能呢？其實在這個例子中這個記憶功能就被融和到了狀態轉化的組合邏輯always塊中。

從這個例子可以看出，狀態機設計的靈魂就是狀態的選取。狀態數量的選取以及每個狀態所需完成的功能會深深影響整個狀態機設計的復雜程度。示例的思路其實是從輸出結果出發，有幾個輸出結果就定義幾個狀態；而我在編寫的時候是從實際情況出發的，也就是比較符合人的直觀思維。其實，這兩種思路是都是可以的，到底是正著思考（從實際出發）還是倒著思考（從結果出發）取決于具體問題，很多時候也需要將兩個思維結合起來設計狀態機。

Lemmings1

這一題我們就仿照上一題示例的思路來確定狀態機的狀態數。我們從輸出出發，輸出情況一共就兩種，即向左走和向右走，所以我們就定義兩種狀態，于是得到下面的答案：

當然上面的狀態轉移里的邏輯表達式還可以利用公式A+A·B=A進行簡化，簡化完就是示例中的答案：

Lemmings2

這一題還是先從輸出出發，輸出一共有三種，那么我們就先按照三種狀態來分析，即左走、右走和下落。但是如果你直接這樣去寫就會發現很難完成“當地面恢復時下落狀態會回到下落前的行走狀態”這個功能，說白了，這部分也是需要記憶功能的。例如，如果我們從下落狀態恢復到左走或右走狀態，就需要引入別的控制變量來記憶這個方向信息，我們試著這么寫一下，得到答案：

答案中的flag變量就是要額外引入的控制變量。現在我們試著正著考慮實際情況，下落本身的狀態也是可以包含方向信息的，Lemming在下落過程中可以朝向左邊，也可以朝向右邊。于是我們可以進一步引入向左下落和向右下落兩個狀態，這樣狀態本身就把方向記憶住了，不需要引入額外控制信號了，于是答案如下：

顯然對于這一題，通過正向思考設計狀態機會更簡單一些。

Lemmings3

這一題又加上了挖掘這一狀態，同上一個問題，挖掘時也需要記憶之前走路的方向，所以我們需要給挖掘兩個狀態位，否則就需要引入別的控制變量，答案如下：

module top_module(input clk,input areset,    // Freshly brainwashed Lemmings walk left.input bump_left,input bump_right,input ground,input dig,output walk_left,output walk_right,output aaah,output digging ); parameter 	LEFT = 3'd1,RIGHT = 3'd2,FALL_LEFT = 3'd3,FALL_RIGHT = 3'd4,DIGGING_LEFT = 3'd5,DIGGING_RIGHT = 3'd6;reg [2:0] current_state,next_state;always@(posedge clk,posedge areset)beginif(areset)begincurrent_state <= LEFT; end else begincurrent_state <= next_state; endend    always@(*)beginnext_state = current_state;case(current_state)LEFT: if(!ground) next_state = FALL_LEFT;else if(dig) next_state = DIGGING_LEFT;else if(bump_left) next_state = RIGHT;else next_state = LEFT;RIGHT:if(!ground) next_state = FALL_RIGHT;else if(dig) next_state = DIGGING_RIGHT;else if(bump_right) next_state = LEFT;else next_state = RIGHT;FALL_LEFT:if(ground) next_state = LEFT;else next_state = FALL_LEFT;FALL_RIGHT:if(ground) next_state = RIGHT;else next_state = FALL_RIGHT;DIGGING_LEFT:if(!ground) next_state = FALL_LEFT;else next_state = DIGGING_LEFT; DIGGING_RIGHT:if(!ground) next_state = FALL_RIGHT;else next_state = DIGGING_RIGHT; endcaseendassign walk_left = current_state == LEFT;assign walk_right = current_state == RIGHT;assign aaah = current_state == FALL_LEFT || current_state == FALL_RIGHT;assign digging = current_state == DIGGING_LEFT || current_state == DIGGING_RIGHT;endmodule

Lemmings4

這一題需要根據角色下落的時間來判斷接觸到地面后會不會死亡。其實還是兩種思路，一種是加入FALL_LEFT_0,…,FALL_LEFT_19這么多個下落狀態來記憶下落周期，但是顯然狀態機的狀態數太多，并不合理；另一種思路就是引入額外控制變量，用來記憶下落時間。所以答案如下：

module top_module(input clk,input areset,    // Freshly brainwashed Lemmings walk left.input bump_left,input bump_right,input ground,input dig,output walk_left,output walk_right,output aaah,output digging ); parameter 	LEFT = 3'd1,RIGHT = 3'd2,FALL_LEFT = 3'd3,FALL_RIGHT = 3'd4,DIGGING_LEFT = 3'd5,DIGGING_RIGHT = 3'd6,DEAD = 3'd7;reg [2:0] current_state,next_state;always@(posedge clk,posedge areset)beginif(areset)begincurrent_state <= LEFT; end else begincurrent_state <= next_state; endend    reg [7:0]cnt;//用于記錄時間下落時間always@(posedge clk,posedge areset)beginif(areset)begincnt <= '0; end else if(aaah)begin //下落時cnt <= cnt + 1; end else begin //只要不在下落就歸零cnt <= '0; endendwire dead_flag = cnt >= 20;always@(*)beginnext_state = current_state;case(current_state)LEFT: if(!ground) next_state = FALL_LEFT;else if(dig) next_state = DIGGING_LEFT;else if(bump_left) next_state = RIGHT;else next_state = LEFT;RIGHT:if(!ground) next_state = FALL_RIGHT;else if(dig) next_state = DIGGING_RIGHT;else if(bump_right) next_state = LEFT;else next_state = RIGHT;FALL_LEFT:if(ground && dead_flag) next_state = DEAD;else if(ground && !dead_flag) next_state = LEFT;else next_state = FALL_LEFT;FALL_RIGHT:if(ground && dead_flag) next_state = DEAD;else if(ground && !dead_flag) next_state = RIGHT;else next_state = FALL_RIGHT;DIGGING_LEFT:if(!ground) next_state = FALL_LEFT;else next_state = DIGGING_LEFT; DIGGING_RIGHT:if(!ground) next_state = FALL_RIGHT;else next_state = DIGGING_RIGHT; DEAD:next_state = DEAD;endcaseendalways@(*)beginwalk_left 	= 1'b0;walk_right	= 1'b0;	aaah		= 1'b0;digging		= 1'b0;        if(current_state == DEAD)beginwalk_left 	= 1'b0;walk_right	= 1'b0;	aaah		= 1'b0;digging		= 1'b0;end else beginwalk_left = current_state == LEFT;walk_right = current_state == RIGHT;aaah = current_state == FALL_LEFT || current_state == FALL_RIGHT;digging = current_state == DIGGING_LEFT || current_state == DIGGING_RIGHT;endendendmodule

Fsm onehot

這一題與Fsm3onehot類似，是希望你充分利用One-hot編碼的特點根據邏輯運算獲得的狀態轉移邏輯和輸出邏輯編寫，答案如下：

Fsm ps2

本題就是在設計一個數據流的解析器。在通信類項目中數據流的解析任務非常常見，基本也都是通過狀態機來實現，一般來說，數據流解析都有這么幾個關鍵問題：怎么確定數據包的包頭和包尾？怎么確定數據包是否需要被丟棄（或者說怎么確定數據包解析成功）？需要進一步提取一個數據包內的哪些內容（例如TCP包中的源地址目的地址等）？

對于本題，其實就是確定一個三字節長度的數據包，只有一個指明包頭的控制位in[3]。簡要來說，本題要完成的功能就是只要第一個in[3]被置為1，則認為是包頭，隨后緊跟的兩個字節就是包的其他內容（無論此時in[3]是否再次被置為1）；多出兩個字節的內容不再認為是有效數據，除非in[3]再次被置為1。

本題有兩種思路，第一種是借助計數器。此時狀態機只要三個狀態，即空閑、包身和完成狀態，通過計數器來確定包尾，答案如下：

當然，由于本題的數據是連續的，并且只有三個字節，我們也完全不需要計數器，因為計數功能完全可以通過添加更多狀態數來實現，此時答案如下：

注意，本題的Hint建議使用4個狀態，但是我們上面已經證明只要引入額外的控制變量也可以使用三個狀態實現功能。其次，Hint中畫的狀態轉移圖其實和我們剛剛第二種方法是一模一樣的:

Fsm ps2data

這一題需要注意的就是數據的捕獲是在不同的時鐘周期下，意味著必須使用時序always塊讓out_bytes擁有記憶功能，答案如下：

Fsm serial

這一題的數據位數比較多，就不能簡單通過增添狀態來寫狀態機了，必須引入計數器來控制。由于現在多了一個結束位，并且要考慮丟包情況，所以選用狀態就要比Fsm ps2中多兩個，如下為本題答案：

Fsm serialdata

這一題的關鍵就是怎么捕獲數據，我先使用for循環實現，答案如下：

module top_module(input clk,input in,input reset,    // Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,DROP = 3'd3,DONE = 3'd4;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? END:DATA;END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginfor(int i=0;i <= 8-1 ;i++)beginout_byte[i] <= (cnt == i) ? in : out_byte[i];  //這一步很關鍵，注意每一位的自保持endend else beginout_byte <= out_byte;endendendmodule

但其實這樣寫就麻煩了，最簡單的方式是利用向量移位來完成（Hint中的提醒），改進后答案如下：

module top_module(input clk,input in,input reset,    // Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,DROP = 3'd3,DONE = 3'd4;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? END:DATA;END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginout_byte <= {in,out_byte[7:1]}; //注意使用右移end else beginout_byte <= out_byte;endendendmodule

向量的移位是處理串行數據捕獲的最常用方式

Fsm serialdp

這一題加上了校驗位，我采用的方法是給狀態機加上校驗狀態。至于校驗模塊這一題已經給了，我們直接例化就好，但是需要注意模塊的reset信號賦值時機，答案如下：

module top_module(input clk,input in,input reset,    		// Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,CHECK = 3'd3,DROP = 3'd4,DONE = 3'd5;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? CHECK:DATA; //8位數據CHECK: next_state = odd != in ? END : DROP;	//第九位是奇偶校驗END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginout_byte <= {in,out_byte[7:1]}; //注意使用右移end else beginout_byte <= out_byte;endendwire parity_rst = !in & (current_state == IDEL || current_state == DONE); //起始位設置reset信號wire odd;parity parity_u(.clk(clk),.reset(parity_rst),.in(in),.odd(odd));endmodule

當然不使用例子給的校驗模塊反而更簡單，直接利用異或運算獲取向量里1的奇偶個數，答案如下：

module top_module(input clk,input in,input reset,    		// Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,CHECK = 3'd3,DROP = 3'd4,DONE = 3'd5;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? CHECK:DATA; //8位數據CHECK: next_state = ^out_byte != in ? END : DROP;	//第九位是奇偶校驗END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginout_byte <= {in,out_byte[7:1]}; //注意使用右移end else beginout_byte <= out_byte;endend
endmodule

Fsm hdlc

本題是一個序列檢測器，對于序列檢測器，一般的方法就是根據序列長度選取狀態數目，而不是借助計數器。所以本題答案如下：

module top_module(input clk,input reset,    // Synchronous resetinput in,output disc,output flag,output err);parameter IDEL = 4'd0,G_1X1= 4'd1,G_1X2= 4'd2,G_1X3= 4'd3,G_1X4= 4'd4,G_1X5= 4'd5,G_1X6= 4'd6,DISC = 4'd7,FLAG = 4'd8,ERR  = 4'd9;reg[4-1:0]current_state,next_state;always@(posedge clk)beginif(reset)current_state <= IDEL;else current_state <= next_state;endalways@(*)beginnext_state = current_state;case(current_state)IDEL :next_state = in ? G_1X1:IDEL;G_1X1:next_state = in ? G_1X2:IDEL;G_1X2:next_state = in ? G_1X3:IDEL;G_1X3:next_state = in ? G_1X4:IDEL;G_1X4:next_state = in ? G_1X5:IDEL;G_1X5:next_state = in ? G_1X6:DISC;G_1X6:next_state = in ? ERR:FLAG;DISC: next_state = in ? G_1X1:IDEL;FLAG: next_state = in ? G_1X1:IDEL;ERR:  next_state = in ? ERR :IDEL;endcaseendassign disc = current_state == DISC;assign flag = current_state == FLAG;assign err = current_state == ERR;endmodule

未完待續

本篇文章截止到Circuits — Finite State Machine — Sequence recognition（Fsm hdlc）。