Brian Lu

1．什麼是FIFO？
FIFO是英文First In First Out 的縮寫，是一種先進先出的資料暫存器，他與普通記憶體的區別是沒有外部讀寫位址線，這樣使用起來非常簡單，但缺點就是只能順序寫入資料，順序的讀出資料，其資料位址由內部讀寫指針自動加1完成，不能像普通記憶體那樣可以由位址線決定讀取或寫入某個指定的位址。

2．什麼情況下用FIFO？
FIFO一般用於不同時鐘域之間的資料傳輸，比如FIFO的一端時AD資料獲取，另一端時電腦的PCI匯流排，假設其AD採集的速率為16位元 100K SPS，那麼每秒的數據量為100K×16bit=1.6Mbps,而PCI匯流排的速度為33MHz，匯流排寬度32bit,其最大傳輸速率為1056Mbps,在兩個不同的時鐘域間就可以採用FIFO來作為資料緩衝。另外對於不同寬度的資料介面也可以用FIFO，例如單片機位元8位元資料輸出，而DSP可能是16位元資料登錄，在單片機與DSP連接時就可以使用FIFO來達到資料匹配的目的。

3．FIFO的一些重要參數
FIFO的寬度：也就是英文資料裡常看到的THE WIDTH，它只的是FIFO一次讀寫操作的資料位元，就像MCU有8位和16位，ARM 32位等等，FIFO的寬度在單片成品IC中是固定的，也有可選擇的，如果用FPGA自己實現一個FIFO，其資料位元，也就是寬度是可以自己定義的。

FIFO的深度：THE DEEPTH，它指的是FIFO可以存儲多少個N位元的資料（如果寬度為N）。如一個8位的FIFO，若深度為8，它可以存儲8個8位元的資料，深度為12 ，就可以存儲12個8位元的資料，FIFO的深度可大可小，個人認為FIFO深度的計算並無一個固定的公式。在FIFO實際工作中，其資料的滿/空標誌可以控制資料的繼續寫入或讀出。在一個具體的應用中也不可能由一些參數算數精確的所需FIFO深度為多少，這在寫速度大於讀速度的理想狀態下是可行的，但在實際中用到的FIFO深度往往要大於計算值。一般來說根據電路的具體情況，在兼顧系統性能和FIFO成本的情況下估算一個大概的寬度和深度就可以了。而對於寫速度慢於讀速度的應用，FIFO的深度要根據讀出的資料結構和讀出資料的由那些具體的要求來確定。
滿標誌：FIFO已滿或將要滿時由FIFO的狀態電路送出的一個信號，以阻止FIFO的寫操作繼續向FIFO中寫資料而造成溢出（overflow）。
空標誌：FIFO已空或將要空時由FIFO的狀態電路送出的一個信號，以阻止FIFO的讀操作繼續從FIFO中讀出資料而造成無效資料的讀出（underflow）。
讀時鐘：讀操作所遵循的時鐘，在每個時鐘沿來臨時讀數據。
寫時鐘：寫操作所遵循的時鐘，在每個時鐘沿來臨時寫資料。
讀指針：指向下一個讀出位址。讀完後自動加1。
寫指針：指向下一個要寫入的位址的，寫完自動加1。
讀寫指標其實就是讀寫的位址，只不過這個位址不能任意選擇，而是連續的。

4．FIFO的分類
根均FIFO工作的時鐘域，可以將FIFO分為同步FIFO和非同步FIFO。同步FIFO是指讀時鐘和寫時鐘為同一個時鐘。在時鐘沿來臨時同時發生讀寫操作。非同步FIFO是指讀寫時鐘不一致，讀寫時鐘是互相獨立的。

5．FIFO設計的難點
FIFO設計的難點在於怎樣判斷FIFO的空/滿狀態。為了保證資料正確的寫入或讀出，而不發生益處或讀空的狀態出現，必須保證FIFO在滿的情況下，不能進行寫操作。在空的狀態下不能進行讀操作。怎樣判斷FIFO的滿/空就成了FIFO設計的核心問題。由於同步FIFO幾乎很少用到，這裡只描述非同步FIFO的空/滿標誌產生問題。
在用到觸發器的設計中，不可避免的會遇到亞穩態的問題（關於亞穩態這裡不作介紹，可查看相關資料）。在涉及到觸發器的電路中，亞穩態無法徹底消除，只能想辦法將其發生的概率將到最低。其中的一個方法就是使用格雷碼。格雷碼在相鄰的兩個碼元之間只由一位元變換(二進位碼在很多情況下是很多碼元在同時變化)。這就會避免計數器與時鐘同步的時候發生亞穩態現象。但是格雷碼有個缺點就是只能定義2^n的深度，而不能像二進位碼那樣隨意的定義FIFO的深度，因為格雷碼必須迴圈一個2^n，否則就不能保證兩個相鄰碼元之間相差一位的條件，因此也就不是真正的各雷碼了。第二就是使用冗餘的觸發器，假設一個觸發器發生亞穩態的概率為P，那麼兩個及聯的觸發器發生亞穩態的概率就為P的平方。但這回導致延時的增加。亞穩態的發生會使得FIFO出現錯誤，讀/寫時鐘採樣的位址指標會與真實的值之間不同，這就導致寫入或讀出的位址錯誤。由於考慮延時的作用，空/滿標誌的產生並不一定出現在FIFO真的空/滿時才出現。可能FIFO還未空/滿時就出現了空/滿標誌。這並沒有什麼不好，只要保證FIFO不出現overflow or underflow 就OK了。
很多關於FIFO的文章其實討論的都是空/滿標誌的不同演算法問題。
在Vijay A. Nebhrajani的《非同步FIFO結構》一文中，作者提出了兩個關於FIFO空/滿標誌的演算法。
第一個演算法：構造一個指標寬度為N+1，深度為2^N位元組的FIFO（為便方比較將格雷碼指標轉換為二進位指標）。當指標的二進位碼中最高位元不一致而其它N位都相等時，FIFO為滿（在Clifford E. Cummings的文章中以格雷碼表示是前兩位均不相同，而後兩位LSB相同為滿，這與換成二進位表示的MSB不同其他相同為滿是一樣的）。當指針完全相等時，FIFO為空。這也許不容易看出，舉個例子說明一下：一個深度為8位元組的FIFO怎樣工作（使用已轉換為二進位的指標）。FIFO_WIDTH=8，FIFO_DEPTH= 2^N = 8，N = 3，指針寬度為N+1=4。起初rd_ptr_bin和wr_ptr_bin均為“0000”。此時FIFO中寫入8個位元組的資料。wr_ptr_bin =“1000”，rd_ptr_bin=“0000”。當然，這就是滿條件。現在，假設執行了8次的讀操作，使得rd_ptr_bin =“1000”，這就是空條件。另外的8次寫操作將使wr_ptr_bin 等於“0000”，但rd_ptr_bin 仍然等於“1000”，因此FIFO為滿條件。
顯然起始指標無需為“0000”。假設它為“0100”，並且FIFO為空，那麼8個位元組會使wr_ptr_bin =“1100”，, rd_ptr_bin 仍然為“0100”。這又說明FIFO為滿。
在Vijay A. Nebhrajani的這篇《非同步FIFO結構》文章中說明了怎樣運用格雷碼來設置空滿的條件，但沒有說清為什麼深度為8的FIFO其讀寫指針要用3+1位的格雷碼來實現，而3+1位的格雷碼可以表示16位的深度，而真實的FIFO只有8位，這是怎麼回事？而這個問題在Clifford E. Cummings的文章中得以解釋。三位格雷碼可表示8位的深度，若在加一位最為MSB，則這一位加其他三位組成的格雷碼並不代表新的位址，也就是說格雷碼的0100表示表示7，而1100仍然表示7，只不過格雷碼在經過一個以0位MSB的迴圈後進入一個以1為MSB的迴圈，然後又進入一個以0位MSB的迴圈，其他的三位碼仍然是格雷碼，但這就帶來一個問題，在0100的迴圈完成後，進入1000，他們之間有兩位發生了變換，而不是1位，所以增加一位MSB的做法使得該碼在兩處：0100~1000，1100~0000有兩位碼元發生變化，故該碼以不是真正的格雷碼。增加的MSB是為了實現空滿標誌的計算。Vijay A. Nebhrajani的文章用格雷碼轉二進位，再轉格雷碼的情況下提出空滿條件，僅過兩次轉換，而Clifford E. Cummings的文章中直接在格雷碼條件下得出空滿條件。其實二者是一樣的，只是實現方式不同罷了。

第二種演算法：Clifford E. Cummings的文章中提到的STYLE #2。它將FIFO位址分成了4部分，每部分分別用高兩位元的MSB 00 、01、 11、 10決定FIFO是否為going full 或going empty (即將滿或空)。如果寫指針的高兩位MSB小於讀指針的高兩位MSB則FIFO為“幾乎滿”，

若寫指針的高兩位MSB大於讀指針的高兩位MSB則FIFO為“幾乎空”。


在Vijay A. Nebhrajani的《非同步FIFO結構》第三部分的文章中也提到了一種方法，那就是方向標誌與門限。設定了FIFO容量的75%作為上限，設定FIFO容量的25%為下限。當方向標誌超過門限便輸出滿/空標誌，這與Clifford E. Cummings的文章中提到的STYLE #2可謂是異曲同工。他們都屬於保守的空滿判斷。其實這時輸出空滿標誌FIFO並不一定真的空/滿。
說到此，我們已經清楚地看到，FIFO設計最關鍵的就是產生空/滿標誌的演算法的不同產生了不同的FIFO。但無論是精確的空滿還是保守的空滿都是為了保證FIFO工作的可靠。

6．關於FIFO的一點的思考

關於FIFO丟資料的問題，其實各位對同一個問題的理解有偏差，才造成了相互誤解。如果在理想狀況下（時鐘同步不回出現錯碼），FIFO由讀寫指標控制是不會丟數的，（這不是廢話嗎，現實中哪來的理想狀況！）且慢，我的意思是說丟資料並不是讀寫誰快誰慢造成的，在正確的設置空滿標誌演算法的情況下，資料的overflow 和underflow 是不會發生的。而往往現實中因為亞穩態的存在，才出現了丟數的情況，也就是說是只要讀寫時鐘不同步，在採樣的過程中採樣出錯，使得本該是0100的變成了1101等等，就會出現讀寫的錯誤，我們稱其為丟數，其原因就是在時鐘同步指標的時候出現亞穩態，由於二進位碼加1的時候很多位同時變化，所以很容易出現亞穩態。因此才用格雷碼將此問題發生的概率比降到最小，其次用多餘的觸發器使其概率進一步降低，也就是說錯誤難免，但我們可以將其發生的概率降到最低，並且在出現錯誤時也不會錯的態離譜（詳見Vijay A. Nebhrajani的《非同步FIFO結構》第二篇）。
    二進位碼指標並非不好用，在前面也提到了它有自身的優勢，由於通過設置握手信號，指標可以有多位元同時變化，二進位指標每次移動可以跳躍過任意的長度，這樣給FIFO的某些功能的實現帶來了方便(例如，硬體直接控制FIFO從緩存的資料流程中丟棄一個出錯的包)；而格雷碼指標一般只能做遞增或遞減的移動。設置握手信號雖然可以保證指標不出錯，但這樣你來我往的經過三四個回合才能開始傳資料，所以對於高速的場合就不適用了。



以上是我的學習FIFO的一些體會，文中很多觀點和理解主要來自Vijay A. Nebhrajani的《非同步FIFO結構》和Clifford E. Cummings的《Simulation and Synthesis Techniques for Asynchronous FIFO design》和《Simulation and Synthesis Techniques for Asynchronous
FIFO Design with Asynchronous Pointer Comparisons》以及網上的有關FIFO的一些文章看過前兩篇文章的同學可能更容易理解我所說的問題，沒有看過的也許會覺得我說的不知所云。瞭解FIFO的工作原理是每個數字設計者應該掌握i的，但在實際應用中還是推薦大家使用EDA軟體提供的FIFO模組，他們都是經過驗證的，不會有什麼問題。

這裡我先拋磚了，有玉的各位不要吝嗇儘管扔啊，水準有限還望大家指正