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

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

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

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

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

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

下面我們來聊FIFO的內(nèi)部細(xì)節(jié)。首先我們說存儲單元，對于利用FlipFlop來實現(xiàn)的FIFO，存儲單元就是一個flop array。

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

其中DATA_WIDTH和DEPTH都是兩個參數(shù)parameter。

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

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

rd_ptr: 當(dāng)前讀出的位置。

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

當(dāng)有一次push操作的時候，wr_ptr要加1。當(dāng)有一次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]，我們需要的位數(shù)應(yīng)該是$clog2(DEPTH)。比如DEPTH=8，那么需要3位ptr用來取址。

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

空：wr_ptr == rd_ptr。

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

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

而且這樣做簡化了rd_ptr和wr_ptr加1的操作，直接利用2進(jìn)制的進(jìn)位加法，當(dāng)記到4‘b0111的時候再加1就直接變?yōu)?'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，那么當(dāng)wr_ptr記到3'b101的時候，下一次寫入就不能直接二進(jìn)制加1了，而是要回到3'b000。這個時候稍微方便一點的做法是設(shè)計一個計數(shù)器，用來計數(shù)當(dāng)前FIFO已經(jīng)被寫入但是還未讀出的數(shù)據(jù)個數(shù)。這樣做的好處是FIFO的空滿可以直接利用這個計數(shù)器與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是來自于寄存器輸出還是來自于組合邏輯電路輸出？如果是來自于組合邏輯輸出，如何優(yōu)化？
3. 如果希望full和empty也直接來自寄存器的輸出，要怎么更改設(shè)計？

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