今天咱們開始聊聊FIFO的設計。FIFO是一個數字電路中常見的模塊，主要作用是數據產生端和接受端在短期內速率不匹配時作為數據緩存。FIFO是指First In, First Out，即先進先出，跟大家排隊一樣。越早排隊的人排在越前面，輪到他的次序也越早，所以FIFO有些時候也被稱為隊列queue。

這一篇我們先介紹利用Flip flop來作為FIFO存儲單元的設計方法，這也是同步FIFO中最為簡單的內容，內容比較基礎。之后老李會帶大家了解基于SRAM的FIFO設計。 而且我們這里只講同步FIFO， 即寫入端和讀出端是屬于同一個時鐘域。如果寫入和讀出是不同的時鐘域，那么就是異步FIFO。關于異步FIFO之前老李在CDC系列里有講過，大家有興趣可以直接在公眾號底部點擊CDC可以了解。

我們先來看一個FIFO模塊需要那幾個基本的輸入輸出。

其中寫入端寫入操作為push，要寫入的data為D，當push為高時，數據D被寫入FIFO。對于寫入端，只需要在乎FIFO是不是滿：如果FIFO已經滿了，是不允許再寫入的。對于讀出端，數據讀出為pop，Q為讀出的數據。在讀出端，只需要在乎FIFO是不是空：如果為空，則不能進行pop操作。

對于讀出端來說，這里有一點需要明確：當FIFO里面有數據的時候，Q應該輸出當前FIFO最前面（最早進入）的那個數據，而不是需要pop才能輸出。也就是說，假設FIFO為空，這個時候我們寫入一個數據D1，那么在下一個周期，Q應該立刻變為D1，同時empty為0。當只有讀第二次寫入的數據的時候，我們才需要pop第一次，Q才會指向D2。 這樣的行為和一個D觸發器非常類似，所以上面我們才將輸入數據表示為D，輸出數據表示為Q，便于和D觸發器類比起來。為什么強調這一點，因為在后面利用SRAM來實現FIFO的時候如果要實現這一點是需要技巧的，我們后面會看到。(老李也見過要想讀出第一個數必須要先pop一次的FIFO設計，這種設計就不是很高效，要多花一個周期來才能讀出第一個數）。

另外FIFO還有一個特性，即當FIFO不是空也不是滿的時候，是允許讀和寫發生在同一個周期的，即一邊寫入，一邊讀出。這個對于Flip Flop來實現的FIFO很容易做到，但是對于SRAM來實現的FIFO就不是那么容易了，特別是SRAM只有一個端口，一個周期內要么讀，要么寫。這樣設計的時候就更需要技巧了，我們在后面的文章中再細聊。

下面我們來聊FIFO的內部細節。首先我們說存儲單元，對于利用FlipFlop來實現的FIFO，存儲單元就是一個flop array。

reg [DATA_WIDTH-1:0]    mem[DEPTH]

其中DATA_WIDTH和DEPTH都是兩個參數parameter。

然后我們需要兩個指針pointer，來分別用于讀和寫，分別為wr_ptr, rd_ptr。有人也喜歡用wr_addr， rd_addr。這兩個指針的意義為：

wr_ptr: 接下來要寫入的位置。

rd_ptr: 當前讀出的位置。

初始的時候，wr_ptr和rd_ptr都被reset成0，那么可以理解為，第一個要寫入的location是mem[0]，第一個要讀出的位置也是mem[0]。

當有一次push操作的時候，wr_ptr要加1。當有一次pop的時候，rd_ptr要+1。

那么我們可以寫出下面的邏輯

always_ff@(posedge clk) begin

if(!rst_n)

for(int i = 0; i < DEPTH; i++)

   mem[i] <= '0;

else begin

if(push & ~full)

   mem[wr_ptr] <= d;

end

end

assign q = mem[rd_ptr];

那么接下來有兩個問題：一是如何來判斷空和滿，另個一問題是如何給wr_ptr和rd_ptr加1。

在思考這兩個問題之前，我們看我們需要幾位來表示wr_ptr和rd_ptr。如果FIFO的深度是DEPTH，那么要來取址mem[DEPTH]，我們需要的位數應該是$clog2(DEPTH)。比如DEPTH=8，那么需要3位ptr用來取址。

再來回答上面兩個問題。通常我們有兩種方式來處理。第一種方式，如果DEPTH剛好是2的冪次，那么做法是給wr_ptr和rd_ptr各多分配一位。比如DEPTH=8，則分配4位給wr_ptr和rd_ptr。這樣做的好處是我們可以利用2進制的特性

空：wr_ptr == rd_ptr。

滿：wr_ptr把rd_ptr套圈了，即低位相等，但是MSB相反。

舉個例子當把mem[0]到mem[7]都寫完之后，wr_ptr 由4’b0111再加1就來到了4'b1000，而如果我們還沒有pop過的話rd_ptr就還停留在4‘b0000，這樣就是達到了套圈，FIFO變滿了。

而且這樣做簡化了rd_ptr和wr_ptr加1的操作，直接利用2進制的進位加法，當記到4‘b0111的時候再加1就直接變為4'b1000，這樣MSB自動表示是不是套圈，而低位可以直接用來取址mem。

localparam PTR_WIDTH = $clog2 (DEPTH) + 1;

logic [DATA_WIDTH-1:0] mem[DEPTH];

logic [PTR_WIDTH-1:0] wr_ptr;

logic [PTR_WIDTH-1:0] rd_ptr;

always_ff@(posedge clk) begin

if(!rst_n)

for(int i = 0; i < DEPTH; i++)

   mem[i] <= '0;

else begin

if(push & ~full)

   mem[wr_ptr[PTR_WIDTH-2:0]] <= d;

end

end

always_ff@(posedge clk) begin

if(!rst_n)

wr_ptr <= '0;

else

if(push & ~full)

  wr_ptr <= wr_ptr + 1'b1;

end

always_ff@(posedge clk) begin

if(!rst_n)

rd_ptr <= '0;

else

if(pop & ~empty)

  rd_ptr <= rd_ptr + 1'b1;

end

assign q = mem[rd_ptr[PTR_WIDTH-2:0]];

assign full = (rd_ptr[PTR_WIDTH-1] ^ wr_ptr[PTR_WIDTH-1]) &&

(rd_ptr[PTR_WIDTH-2:0] == wr_ptr[PTR_WIDTH-2:0]);

assign empty = rd_ptr == wr_ptr;

但是這樣做的限制在于DEPTH必須是2的冪次方個。 如果不是，比如是6，那么當wr_ptr記到3'b101的時候，下一次寫入就不能直接二進制加1了，而是要回到3'b000。這個時候稍微方便一點的做法是設計一個計數器，用來計數當前FIFO已經被寫入但是還未讀出的數據個數。這樣做的好處是FIFO的空滿可以直接利用這個計數器與0和與DEPTH相比較而得到。老李更推薦這一種寫法，而且這個時候wr_ptr和rd_ptr也不需要多加1位。

localparam PTR_WIDTH = $clog2 (DEPTH);

logic [DATA_WIDTH-1:0] mem[DEPTH];

logic [PTR_WIDTH-1:0] wr_ptr;

logic [PTR_WIDTH-1:0] rd_ptr;

logic [PTR_WIDTH:0] cnt; //current fifo count

always_ff@(posedge clk) begin

if(!rst_n)

for(int i = 0; i < DEPTH; i++)

   mem[i] <= '0;

else begin

if(push & ~full)

   mem[wr_ptr] <= d;

end

end

always_ff@(posedge clk) begin

if(!rst_n)

wr_ptr <= '0;

else

if(push & ~full)

  wr_ptr <= (wr_ptr == DEPTH-1) ? '0 : (wr_ptr + 1'b1);

end

always_ff@(posedge clk) begin

if(!rst_n)

rd_ptr <= '0;

else

if(pop & ~empty)

  rd_ptr <= (rd_ptr == DEPTH-1) ? '0 : (rd_ptr + 1'b1);

end

always_ff@(posedge clk) begin

if(!rst_n)

cnt <= '0;

else begin

//only push, no pop

if(push && !pop && !full)

  cnt <= cnt + 1'b1;

//only pop, no push

else if(!push && pop && !empty)

  cnt <= cnt - 1'b1;

//no pop or push,

//pop and push in the same cycle

// else cnt <= cnt;

end

end

assign q = mem[rd_ptr];

assign full = cnt == DEPTH;

assign empty = cnt == '0;

這就是基于Flip Flop的同步FIFO的基本原理，還是比較簡單直接的，RTL code加起來也就幾十行。下面老李希望大家思考幾個問題：

1. 什么時候使用基于Flip-flop的同步FIFO？什么時候使用基于SRAM的FIFO？
2. 最后的q是來自于寄存器輸出還是來自于組合邏輯電路輸出？如果是來自于組合邏輯輸出，如何優化？
3. 如果希望full和empty也直接來自寄存器的輸出，要怎么更改設計？

最后再附送一個老李一個老朋友的作為面試官的出的面試題，大家可以自己思考一下：如何設計一個深度為1的同步FIFO？