# Finite State Machine
### 簡介
這篇文章，會以例子為主軸，用輔助說明的方式，講述 Finite State Machine 的想法與實作。
___

### Function


備註 : Xi 為無號數，並保證總和在 0 ~ 7 之間。

___

### Interface


#### Input

| Name | Width | Description |
| --- | --- | --- |
| clk | 1-bit | clock signal |
| rst | 1-bit | 用來初始化的訊號，當 rst == 1 時，系統進行 reset |
| start | 1-bit | 當 start == 1 時，系統開始進行運算|
| data | 3-bit | 從 ROM 中所讀出的資料，無號數 |

#### Output

| Name | Width | Description |
| --- | --- | --- |
| en | 1-bit | 控制 ROM 是否 Enable，當 en 為 1 時，才能進行讀取動作|
| addr | 3-bit | 讀取 ROM 的位置 |
| fin | 1-bit | 代表運算結束。fin 拉起為 1 時，testbench 會比對 result 是否正確 |
| result | 3-bit | 相加的值，無號數 |
___
### Top View

以下是 ADD , ADD_tb , ROM 之間的關係圖。
資料讀取的部分，ADD 輸出 en 與 addr 給 ROM，ROM 在 clk negative edge 時輸出 data 給 ADD。
其餘部分，clk , rst , start 的值由 ADD_tb 決定，輸出給 ADD。ADD 則輸出 fin , result 給 ADD_tb，檢查正確性。


___

### ROM

介紹 ROM 中存放資料的結構。
這次使用 8 * 3 bits 大小的 ROM，也就說有 8 個儲存空間，每一個空間都是 3 bits。

如下圖所示，X 的長度在 addr = 7 的位址，X 則是在 addr = 0 , 1 , 2 , ... 的位址。


___

### <font color = "red"> 一切都已經準備好了 ! 讓我們愉快地學習吧 !!! </font> :+1: :+1: :+1:


___

### Sequential Logic

首先，你要看懂這張圖，並明白 signal 和 block 做什麼事。


#### <font color = "blue"> 備註 : 使用天線寶寶配色，讓東西看起來很簡單 </font>

#### Block
| Name | Color | Note |
|---|---|---|
| CL | Gray | Combinational Circuit，輸出只會被現在的輸入影響 (你們之前寫的都是這種)|
| DFF |　Brown | D Flip Flop，當 clock 在 posedge/negedge 時，把 Q 的值設為 D。|

#### Signal

| Name | Color | CL/DFF | Factors | Note |
|---|---|---|---|---|
| input | Red | X | Testbench | 由 Testbench 給的值|
| state | Yellow | DFF | next_state | state 只受 DFF 影響。當 clock 在 posedge/negedge 時，把 state 的值設為 next_state|
| next_state | Purple | CL | input/state | next_state 只受 CL 影響。CL 根據 input 和 state 決定 next_state 為何 ( input/state 可以都參考、擇一參考，或是都不參考 ) |
| output | Green | CL | input/state | output 只受 CL 影響。CL 根據 input 和 state 決定 output 為何 ( input/state 可以都參考、擇一參考，或是都不參考 ) |
| clock |　Brown | X | Testbench | 由 Testbench 給的值|

___

### 題目解析

看完剛剛的那張圖後，我們差不多成功 50 % 了，真的是很容易呢 ~
接下來，我們來分析一下這個題目，要用到哪些變數，以及要做到什麼事

#### 變數 (以下不包括原本 module 就有的 I/O)
- num : 讀 ROM 時，要給 ROM 我們要讀的位置 ( addr )，所以我們要有個變數來產生 addr 的值。
- leng : 為了判斷我們是否在 X 的結尾，所以我們要有個變數存放 length(X)
- ans : 存放目前相加的總和
- state : 目前在哪個狀態，之後有更詳細的解釋。

#### 事情
- 初始化
- 讀取 ROM
- 相加並輸出結果
- Output Logic

之後的段落，會以事情為主軸，慢慢把 module 拼出來。
___

### 相加

因為相加最直觀，所以先講相加。

#### State Transition Graph
X 的長度為 leng，所以只需要讀 0 ~ leng - 1 位置的 data，也就是說 num = 0 ~ leng - 1。
然後，當 num == leng 時，就表示 X 都已經讀過並相加完成，可以結束了。


#### 變數
- num : 先假設前面 num 已初始化。num 不斷加 1，直到 num == leng 為止。
- leng : 先假設前面 leng 已設定值。leng 做判斷 num == leng 用。
- ans : 先假設前面 num 已初始為 0 。ans 不斷加上 data，直到 num == leng。
- state : 從 STG 可觀察出來，當 num < leng 時，state 維持在 SUM，當 num == leng 時，開始做其他事情。

#### Sequential Circuits

列出了變數後，來看看哪些要用 Sequential Circuit 吧 !!!
- num : 因為 "下一個 num" 是 "現在的 num" + 1，所以要用有記憶功能的 sequential circuit。
- leng : 因為 leng 在此只做判斷式用，所以先不需要。
- ans : 因為 "下一個 ans" 是 "現在的 ans" + data，所以要用有記憶功能的 sequential circuit。
- state : 因為 "下一個 state" 和 "現在的 state" 有關，所以要用有記憶功能的 sequential circuit。

所以，總共需要三個 Sequential Circuits ，以下用圖 和 code 分別表示。


always@(posedge clk)begin
    state <= next_state;
    num <= next_num;
    ans <= next_ans;
    end
end

always@(*)begin
    case(state)
        `SUM:begin
            next_num = num + 3'd1;
            next_state = state;
            next_ans = (num < leng)? ans + data : ans;
        end
    endcase
end

___

### 初始化

因為讀 ROM 很麻煩，所以來講初始化。
rst 是用來初始化的訊號，因為在 DFF 中，可以放初始化用的訊號，所以我們用 DFF 來做。當 rst 為 posedge 時，做初始化。


always@(posedge rst or posedge clk)begin
    if(rst == 1'b1)begin
        state <= `IDLE;
        num <= 3'd7;
        leng <= 3'd0;
        ans <= 3'd0;
    end
    else begin
        state <= next_state;
        num <= next_num;
        leng <= next_leng;
        ans <= next_ans;
    end
end

- 初始化值的部分和讀取 ROM 有關，所以在這裡，只要理解 ans 要初始化為 0 即可。
- D Flip Flop 在一個 edge trigger 的信號時，會把訊號判斷為 clock，兩個 edge trigger 的信號時，會把一個訊號判斷為 clock，另一個為 rst (初始化訊號)。
- <font color = "red"> 注意!! DFF 只能放一或二個 edge trigger 的信號，再多會合成不出來。 </font>

___
### Testbench 的特性
在讀 ROM 之前，先說明一下 Testbench 的特性。如果你有興趣，可以自行在 Testbench 做修改，看看會發生什麼結果。

- rst 用來初始化的訊號
- start 用來啟動系統的訊號
- 我們希望你在 start 為 1 之前，就準備好相加所需要的資料，也就是 length(X)。所以 rst 和 start 之間有一個 cycle 的差距，請在這個 cycle，把從 ROM 讀到的 length(X)，存入 leng
- 在 clk negedge 給 rst / start / data
- 我們希望你的 DFF 是在 posedge 時 trigger，所以為了保證 DFF 把 Q 的值設為 D 時，input 都已經穩定，我們統一在 negedge 給 rst / start / data。
- 承上個特性，在讀 ROM 時，就算設好了 en 和 addr，也不會立刻得到位置為 addr 的 data
- data 只在 start == 1 時給值

知道 Testbench 的特性後，就可以開始讀 ROM 了。
___
### 讀 ROM 及統整

這裡給出一種方法，但你可以多方嘗試，或用對你而言較為好理解的方法。

以下是方法的 State Transition Graph 和波型圖。



1. 初始值
初始化在前面已講過了，在此不贅述。<font color = "orange"> ( 波型圖中橘色部分 ) </font>

2. IDLE

IDLE 為開頭的 state。我們需要開頭的 state，原因如下 :
- 作為初始值用
- 在開頭的 state 把 length(X) 存入 leng 中

在 IDLE 要做的事 :
- 當 start == 1 時，讓 next_state 設為 SUM，然後等待 clk posedge 時，跳入狀態 SUM。
- " 讓 next_state 設為 SUM "，是 Combinational Circuit 要做的事
- " 等待 clk posedge 時，跳入狀態 SUM "，是 D Flip Flop 要做的事。只要你把 next_state 設為 SUM，到了 clk posedge ，D Flip Flop 會自動幫你跳入狀態 SUM，也就是讓 state = SUM。

- 當 start != 1，狀態不變。next_state 依舊為 IDLE，也就是 next_state = state。

- 在 IDLE 時，向 ROM 要 length(X)
- 當 start != 1，把 num(addr) 設為 7，en 設為 1。當 start == 1，代表拿到 length(X) 的值了 ( data == length(X) )， num(addr) 則設為 0，表示讀取 X[0] 的資料。
- data 在 start == 1 時，才會有值，所以讀取 length(X) 時，也要在 start == 1 的時候。
- start 為 1 是在 negedge ，而 D Flip Flop 是在 posedge trigger，所以中間有時間差。 我們要利用這個時間差，把 next_leng 設為 data，然後利用 D Flip Flop 在 clk posedge 時，把 next_leng 存入 leng。 <font color = "red"> ( 波型圖中紅色部分 ) </font>
- 承上一點，可以發現 leng 也要用 sequential circuit 存起來，下面補上 leng 的圖
- leng 初始化為任何值都可以。

always@(posedge rst or posedge clk)begin
    if(rst == 1'b1)begin
        state <= `IDLE;
        num <= 3'd7;
        leng <= 3'd0;
        ans <= 3'd0;
    end
    else begin
        state <= next_state;
        num <= next_num;
        leng <= next_leng;
        ans <= next_ans;
    end
end

always@(*)begin
    next_num = num + 3'd1;
    next_leng = leng;
    next_ans = ans;
    next_state = state;
    case(state)
        `IDLE:begin
            next_state = (start == 1'b1)? `SUM : `IDLE;
            next_num = (start == 1'b1)? 3'd0 : 3'd7;
            next_leng = (start == 1'b1)? data : leng;
        end
        `SUM:begin
            next_ans = (num < leng)? ans + data : ans;
        end
    endcase
end

3. ADD
<font color = "purple"> ( 波型圖中紫色部分 ) </font>
相加的 state，前面已敘述過，所以在此，只再多講一下結束和 leng 的部分。
- 結束
當 num == leng 時，代表相加完畢，要輸出結果了，不會再做任何事。所以在此，不多加一個結束的 state ，而是直接把 fin 設為 1 ，把 result 設為 ans。建議多加一個 start == 1 的判斷式，因為在未初始化時，num 和 leng 都是 X，fin 很可能判斷為一樣，就設定為 1 了。<font color = "green"> ( 波型圖中綠色部分 ) </font>
- leng
因為下一個 leng 等於現在的 leng，所以要把 next_leng 設為 leng

### Output Logic

還記得這張圖嗎 ?


從中可以發現， output 只受 combinational circuits 影響，不需要 D Flip Flop。
以下表格列出所有 Output。

Output
| Name | Factors | Note |
|---|---|---|
| en | X | 一直都是 1|
| addr | num | 與 num 同值 |
| fin | state / num / leng | 當 state == SUM 且 num == leng 時，fin 為 1，否則為 0 |
| result | ans | 與 ans 同值 |


### 總結

以下是合併後的 Code，其他檔案請到 ilms 的 lab3 的作業資訊裡下載。
備註 :
從 想法/Code 中可以發現，next_state/next_num/next_leng/next_ans 都與 state 有關。所以在畫圖表示時，紅色的 input 都要再加上 state 作為 CL 的判斷依據，但為了凸顯其他 input，所以省略不畫。

`define IDLE 1'd0
`define SUM 1'd1
module ADD(clk , rst , start , data , en , addr , fin , result);

    parameter datawidth = 3;
    parameter memwidth = 3;

    input clk , rst , start;
    input [datawidth - 1 : 0] data;
    output en , fin;
    output [memwidth - 1 : 0] addr;
    output [datawidth - 1 : 0] result;

    reg state , next_state;
    reg [memwidth - 1 : 0] num , next_num;
    reg [memwidth - 1 : 0] leng , next_leng;
    reg [datawidth - 1 : 0] ans , next_ans;

    always@(posedge rst or posedge clk)begin
        if(rst == 1'b1)begin
            state <= `IDLE;
            num <= 3'd7;
            leng <= 3'd0;
            ans <= 3'd0;
        end
        else begin
            state <= next_state;
            num <= next_num;
            leng <= next_leng;
            ans <= next_ans;
        end
    end

    always@(*)begin
        next_num = num + 3'd1;
        next_leng = leng;
        next_ans = ans;
        next_state = state;
        case(state)
            `IDLE:begin
                next_state = (start == 1'b1)? `SUM : `IDLE;
                next_num = (start == 1'b1)? 3'd0 : 3'd7;
                next_leng = (start == 1'b1)? data : leng;
            end
            `SUM:begin
                next_ans = (num < leng)? ans + data : ans;
            end
        endcase
    end

    assign en = 1'b1;
    assign addr = num;
    assign fin = (start == 1'b1 && num == leng)? 1'b1 : 1'b0;
    assign result = (fin == 1'b1)? ans : 3'd0;

endmodule

### Block Diagram (Datapath)

畫出 Block Diagram 會讓你的想法更清楚，用來檢視 Verilog Code 是不是有沒描述到的部分。

備註 :
1. 為了讓你們了解才畫的很繽紛，你們只要用同種顏色，然後標註一下每條線的名稱就可以了
2. 如果你們覺得大量的接線很麻煩 (像是 rst clk) 之類的，只要標註一下，不一定要連過去


### 推薦文章

[有限狀態機FSM coding style整理](http://www.cnblogs.com/oomusou/archive/2011/06/05/fsm_coding_style.html)


# [:maple_leaf:Homepage:maple_leaf:](https://hackmd.io/s/BkbSKFMuM)