# FIFO(First In First Out) 架構
此記憶體的特點是資料先進先出(後進後出)，不能像普通記憶體那樣可以由位址線決定讀取或寫入某個指定的位址，可根據其特性分為:
#### 1. 同步FIFO:
讀時脈和寫入時脈為同一個時脈。在clk edge同時發生讀寫操作
#### 2. 異步FIFO:
讀寫時脈不一致，讀寫時脈是互相獨立的

## 注意及困難點:
FIFO設計的困難在於如何判斷FIFO的空/滿狀態
為了確保資料正確的寫入或讀出，而不發生溢位或讀空的狀態出現，必須保證
> 1. FIFO在"**滿**"的情況，不能進行"**寫入**"操作。
> 2. FIFO在"**空**"的情況，不能進行"**讀取**"操作。

如何判斷FIFO的滿/空就成了FIFO設計的核心問題
## 讀寫指標的工作原理
> 1. 讀指標 : **下一個**將要被**寫入**的單元，重設時，指向第1個單元(編號為0)
> 2. 寫指標 : **目前**要被**讀出**的單元，重設時，指向第1個單元(編號為0)

## FIFO的「空」/「滿」偵測
當reset rd_ptr = wr_ptr ，FIFO就是"空"
每寫入一次數據wr_ptr加1，每讀取一次數據rd_ptr加1
1. 當rd_ptr 追上wr_ptr 就是**空**
2. 當wr_ptr 追上rd_ptr 就是**滿**

## 同步FIFO Code

module syn_fifo(clk, rstn, wr_en, rd_en, wr_data, rd_data, fifo_full, fifo_empty);

    //參數定義
    parameter   width = 8;
    parameter   depth = 8;
    parameter   addr  = 3;

    //輸入訊號
    input   clk;    //clk
    input   rstn;   //reset
    input   wr_en;  //write_enable
    input   rd_en;  //read_enable

    //write & read data 
    input   [width - 1 : 0] wr_data;    
    output  [width - 1 : 0] rd_data;    

    reg [width - 1 : 0] rd_data;

    //空 & 滿 判斷
    output  fifo_full;
    output  fifo_empty;

    //counter for 空 & 滿
    reg [$clog2(depth): 0] cnt;

    //定義 write & read ptr
    reg [depth - 1 : 0] wr_ptr;
    reg [depth - 1 : 0] rd_ptr;

    //定義fifo 寬度 深度
    reg [width - 1 : 0] fifo [depth - 1 : 0];

    //write ptr design +1
    always @ (posedge clk or negedge rstn) begin
        if(!rstn)
            wr_ptr <= 0;
        else if(wr_en && !fifo_full)    //write enable & fifo 未滿
            wr_ptr <= wr_ptr + 1;
        else
            wr_ptr <= wr_ptr;
    end

    //read ptr design +1
    always @ (posedge clk or negedge rstn) begin
        if(!rstn)
            rd_ptr <= 0;
        else if(rd_en && !fifo_empty)   //read enable & fifo not emepty
            rd_ptr <= rd_ptr + 1;
        else
            rd_ptr <= rd_ptr;
    end

    //input write data
    integer i;

    always @ (posedge clk or negedge rstn) begin
        if(!rstn) begin 
            for(i = 0; i < depth; i = i + 1)
                fifo[i] <= 0;
        end
        else if(wr_en)  
            fifo[wr_ptr] <= wr_data;
        else    
            fifo[wr_ptr] <= fifo[wr_ptr];
    end

    //read data
    always @ (posedge clk or negedge rstn) begin
        if(!rstn)
            rd_data <= 0;
        else if (rd_en)
            rd_data <= fifo[rd_ptr];   
        else
            rd_data <= rd_data;
    end

    //判断空满
    always @ (posedge clk or negedge rstn) begin
        if(!rstn)
            cnt <= 0;
        else if (wr_en && !rd_en && !fifo_full) //寫入 +1
            cnt <= cnt + 1;
        else if (!wr_en && rd_en && !fifo_empty) //讀取 -1
            cnt <= cnt - 1;
        else 
            cnt <= cnt;
    end

    //空满判断
    assign fifo_full = (cnt == depth)? 1 : 0;
    assign fifo_empty = (cnt == 0) ? 1 : 0;
endmodule

teatbench

module syn_fifo_tb;
    reg clk, rstn;
    reg wr_en, rd_en;

    wire fifo_full, fifo_empty;

    reg [7 : 0] wr_data;
    wire    [7 : 0] rd_data;


    //生成波形
    initial begin
        $fsdbDumpfile("wave.fsdb");
        $fsdbDumpvars(0, myfifo);
        $fsdbDumpon();
    end

    //例化
    syn_fifo myfifo(
        .clk(clk),
        .rstn(rstn),
        .wr_en(wr_en),
        .rd_en(rd_en),
        .fifo_full(fifo_full),
        .fifo_empty(fifo_empty),
        .wr_data(wr_data),
        .rd_data(rd_data)
    );

    initial begin
        rstn = 1;
        wr_en = 0;
        rd_en = 0;


        repeat(2) @(negedge clk);  
        rstn = 0;//1

        @(negedge clk);  
        rstn = 1;//2

        @(negedge clk);  
        wr_data = {$random}%60;//隨機產生0~59數字
        wr_en = 1;//3

        repeat(2) @ (negedge clk);
        wr_data = {$random}%60;//5

        @(negedge clk);
        wr_en = 0;//6
        rd_en = 1;//6

        repeat(4) @ (negedge clk);
        rd_en = 0;//10
        wr_en = 1;
        wr_data = {$random}%60;//10

        repeat(5) @ (negedge clk);
        wr_data = {$random}%60;//15

        repeat(2) @ (negedge clk);
        wr_en = 0;
        rd_en = 1;

        repeat(2) @ (negedge clk);
        rd_en = 0;
        wr_en = 1;
        wr_data = {$random}%60;

        repeat(3) @ (negedge clk);
        wr_en = 0;

        #50 $finish;
    end

    initial begin
        clk = 0;
        forever #5 clk = ~clk;
    end
endmodule

## 參考
1. https://zhuanlan.zhihu.com/p/463030740
1. https://cloud.tencent.com/developer/article/2060878