# Finite State Machine(FSM)
###### tags: `Digital IC Design`

[回到主頁面](https://hackmd.io/@derek8955/BkK2Nb5Jo/https%3A%2F%2Fhackmd.io%2FdpcBlBL8TlShpQ-wSi9Quw)

> Reference : https://flaviocopes.com/finite-state-machines/

### <font color = "blue"> What is FSM? </font>
|  |
|:-------------------------------------------------------------------------------- |
| <font color="axis">Example : </font>紅綠燈 (綠燈亮50s -> 黃燈亮8s -> 黃燈亮32s) |
| <font color="axis">Purpose : </font>FSM 可以幫助整個電路的運算過程切分成有限的狀態，方便控制整個電路的運作 |
|<font color="axis"> Machine type : </font> 常見的 FSM 有兩種方法，Mealy-machine, Moore-machine，有興趣可以去看這個[網站](https://www.csie.ntu.edu.tw/~b92025/DCL/DCL_Report4/DCL25_LAB4_Report.htm)|

### <font color = "blue"> Implement in verilog </font>

根據紅綠燈的例子，我們可以拆成三種主要型式:
- Current State
- Next State
- Output Logic

| current state | input | next state | output logic |
| --- | -------- | -------- | -------- |
| green | Timer is 50s | yellow | Green light on, others off |
| yellow | Timer is 8s | red | Yellow light on, others off |
| red | Timer is 32s | green | Red light on, others off |

module LIGHT( light, clk, rst_n );
output reg [1:0] light; // 0: green, 1:yellow, 2: red, 3: off 
input clk, rst_n;    
    
parameter STATE_IDLE = 2'd0, // initial state
          STATE_GREEN = 2'd1, 
          STATE_RED = 2'd2, 
          STATE_YELLOW = 2'd3;
    
parameter GREEN = 2'd0,
          YELLOW = 2'd1,
          RED = 2'd2,
          LIGHT_OFF = 2'd3;

reg [1:0] cur_state, nx_state;
reg [5:0] timer_r, timer_g;
reg [3:0] timer_y;

// timer
always @( posedge clk or negedge rst_n ) begin
    if( !rst_n ) timer_r <= 0;
    else if( cur_state == STATE_RED ) timer_r <= timer_r + 1;
    else timer_r <= 0;
end

always @( posedge clk or negedge rst_n ) begin
    if( !rst_n ) timer_y <= 0;
    else if( cur_state == STATE_YELLOW ) timer_y <= timer_y + 1;
    else timer_y <= 0;
end

always @( posedge clk or negedge rst_n ) begin
    if( !rst_n ) timer_g <= 0;
    else if( cur_state == STATE_GREEN ) timer_g <= timer_g + 1;
    else timer_g <= 0;
end
    
// current state: using sequential circuit
always @( posedge clk or negedge rst_n ) begin
    if( !rst_n ) cur_state <= STATE_IDLE;
    else cur_state <= nx_state;
end

// next state: using combinational circuit
always @( * ) begin
    case( cur_state )
    STATE_IDLE: nx_state = STATE_GREEN;
    STATE_GREEN: nx_state = ( timer_g == 50 )? STATE_YELLOW : STATE_GREEN;
    STATE_YELLOW: nx_state = ( timer_y == 8 )? STATE_RED : STATE_YELLOW;
    STATE_RED: nx_state = ( timer_r == 32 )? STATE_GREEN : STATE_RED;
    endcase
end

// output logic: 可以用 comb. 也可以 seq.
always @( * ) begin
    case( cur_state )
    STATE_IDLE: light = LIGHT_OFF;
    STATE_GREEN: light = GREEN;
    STATE_YELLOW: light = YELLOW;
    STATE_RED: light = RED;
    endcase
end
    
endmodule

:::danger
FSM coding style:
- 將 CS, NS, OL 分開來寫( 把 comb. 電路跟 seq. 電路拆開 )
- 使用 parameter 定義每個狀態
:::

[Related Paper: State Machine Coding Styles for Synthesis](http://www.sunburst-design.com/papers/CummingsSNUG1998SJ_FSM.pdf)