FIFO的基本原理_fifo算法基本原理

1.FIFO简介

FIFO( First Input First Output)是指先进先出。

通常实现跨时钟域的处理有使用异步FIFO（结合格雷码）、锁存+握手信号和使用DMUX电路这几种方法

在系统设计中，以增加数据传输率、处理大量数据流、匹配具有不同传输率的系统为目的而广泛使用FIFO存储器，从而提高了系统性能。FIFO存储器是一个先入先出的双口缓冲器，即第一个进入其内的数据第一个被移出，其中一个是存储器的输入口，另一个口是存储器的输出口。对于单片FIFO来说，主要有两种结构：触发导向结构和零导向传输结构。触发导向传输结构的FIFO是由寄存器阵列构成的，零导向传输结构的FIFO是由具有读和写地址指针的双口RAM构成。

FIFO存储器是系统的缓冲环节，如果没有FIFO存储器，整个系统就不可能正常工作，它主要有几方面的功能：
1） 对连续的数据流进行缓存，防止在进机和存储操作时丢失数据；
2） 数据集中起来进行进机和存储，可避免频繁的总线操作，减轻CPU的负担；
3） 允许系统进行DMA操作，提高数据的传输速度。这是至关重要的一点，如果不采用DMA操作，数据传输将达不到传输要求，而且大大增加CPU的负担，无法同时完成数据的存储工作。

因此，选择合适的存储芯片对于提高系统性能很重要，在以往的设计中经常采用的是“乒乓型”存储方式，这种方式就是采用两片存储器，数据首先进入其中一片，当数据满时再让数据进入第二片存储器，同时通过逻辑控制，将第一片存储器中的数据取走，以此类推，两片轮流对数据进行缓存。这种方式有着较明显的缺点，首先是控制复杂，要有专门的逻辑来维护这种轮流机制;其次，数据流的流向要不断变化，限制了数据流的速率，还容易产生干扰。从数据传输上说，缓存芯片容量越大，对后续时序要求就越低，可减少总线操作的频次；但从数据存储上说，就意味着需要开辟更大的内存空间来进行进行缓冲，会增加计算机的内存开销，而且容量越大，成本也越高。因此，在综合考虑系统性能和成本的基础上，选择满足系统需要的芯片即可。

FIFO存储器分为写入专用区和读取专用区。读操作与写操作可以异步进行，写入区上写入的数据按照写入的顺序从读取端的区中读出，类似于吸收写入端与读出端速度差的一种缓冲器。计算机的串口，一般也都具有FIFO缓冲器（不是单一的FIFO存储器，而是嵌入在设备内部）。

2.FIFO原理

根据FIFO工作的时钟域分为同步/异步FIFO。同步FIFO是指读时钟和写时钟为同一个时钟在时钟沿来临时同时发生读写。异步FIFO读写时钟不一致，读写相互独立。

异步FIFO最核心的部分就是精确产生空满标志位，这直接关系到设计的成败。

为了定位读取和写入的位置需要进行读写指针的设置。

读指针：总是指向下一个将要读取的单元，复位时指向第一个单元（编号为0）。

写指针：总是指向当前要被读出的数据，复位时指向第一个单元（编号为0）。

当第一次读写指针相等时，表明FIFO为空，这种情况发生在复位操作时或者当读指针读出FIFO中最后一个字 后，追赶上写指针时，此时读空信号有效。

当读写指针再次相等时，表明FIFO为满，这种情况发生在，当写指针转了一圈折回来（wrapped around）又追上了读指针。

两种方式都是以读写指针相等作为判断标志，所以我们需要寻找其它的方法进行判断。

2.1 FIFO读写状态的判断方法

可以采用以下两种方法：

（1）额外位（extra bit）

一般情况下深度为$N=2^n$的FIFO其地址的位宽为$n$，其读写地址的位宽也为$n$。共有$N$个存储单元，若数据位宽为W则该FIFO的容量即为$N\ast W$bit。

现在在指针中添加额外的位（extra bit，即地址的MSB）变为$n＋\mathrm{１}$bit，该extra bit用于指示写指针是否递增并越过最后一个FIFO地址，若越过则将该MSB加1，其它位清零。对读指针也进行同样的操作。如对于深度为8的FIFO，需要采用３＋１bit是计数器：0000-1000、1001-1111，MSB作为折回标志，而低3位作为地址指针。

那么判断机制为：

如果两个指针的MSB不同，就说明写指针比读指针多折回一次：如r_addr=0000,且w_addr=1000,为满；

如果两个指针的MSB相同，就说明两个指针折回次数相等。再者其余位相等，则说明FIFO为空。

（2）设置数据计数器

设置一个data_counter, 当写使能有效时每写入一个data计数器同时加1；读操作时，每读出一个data时该计数器减1。如此，当data_counter为0时FIFO空，当data_counter计数至FIFO深度deep时，表示FIFO写满。

由于计数器会占用额外的资源，当FIFO较大时，这种方法可能会降低FIFO的读写速度。