一种异步FIFO的设计方法

本文所研究的FIFO,从硬件的观点来看，就是一块数据内存。它有两个端口，一个用来写数据，就是将数据存入FIFO；另一个用来读数据，也就是将数据从FIFO当中取出。与FIFO操作相关的有两个指针，写指针指向要写的内存部分，读指针指向要读的内存部分。FIFO控制器通过外部的读写信号控制这两个指针移动，并由此产生FIFO空信号或满信号。

对于异步FIFO而言，数据是由某一个时钟域的控制信号写入FIFO，而由另一个时钟域的控制信号将数据读出FIFO。也就是说，读写指针的变化动作是由不同的时钟产生的。因此，对FIFO空或满的判断是跨时钟域的。如何根据异步的指针信号对FIFO的满状态或空状态进行正确的判断是本文研究的重点。此外，设计过程中的一些细节问题也将在文中涉及到。

1 指针以及满空信号的产生

为了更好地说明问题，先探讨一下同步FIFO指针移动以及满空信号的产生过程。对于同步FIFO，读写指针都指向一个内存的初始位置，每进行一次读写操作，相应的指针就递增一次，指向下一个内存位置。当指针移动到了内存的最后一个位置时，它又重新跳回初始位置。在FIFO非满或非空的情况下，这个过程将随着读写控制信号的变化一直进行下去。如果FIFO处于空的状态，下一个读动作将会导致向下溢出（underflow）, 一个无效的数据被读入；同样，对于一个满了的FIFO，进行写动作将会导致向上溢出（overflow）, 一个有用的数据被新写入的数据覆盖。这两种情况都属于误动作，因此需要设置满和空两个信号，对满信号置位表示FIFO处于满状态，对满信号复位表示FIFO非满，还有空间可以写入数据；对空信号置位表示FIFO处于空状态，对空信号复位表示FIFO非空，还有有效的数据可以读出。

当读指针和写指针相等也就是指向同一个内存位置的时候，FIFO可能处于满或空两种状态。可以通过不同的方法判断或区分FIFO究竟是处于满状态还是空状态，也就是究竟是写指针从后赶上了读指针， 还是读指针从后赶上了写指针。本文所应用的方法是设置一个额外的状态位，指针由它的地址位以及状态位组成。地址位随着相应的操作递增，指针由内存的最后位置返回到初始位置的时候状态位取反。 因此，当读写指针的地址位和状态位全部吻合的时候，读写指针经历了相同次数的循环移动，也就是说，FIFO处于空状态(图1(a))；如果读写指针的地址位相同而状态位相反，写指针比读指针多循环一次，标志FIFO处于满状态（图1(b)）。


2 二进制指针和格雷码指针的同步

二进制指针是由一位状态位和若干位二进制编码的地址位组成的（例如由三位地址和一位状态位构成的指针的变化：0000→0001→0010→0011→0100→0101→0110→0111→1000→1001→1010→1011→1100→1101→1110→1111）。如果在不同的时钟域内直接同步二进制指针，有可能产生问题。例如，当读指针从0111向1000变化的时侯，指针所有的位都要变化，如果写时钟恰好在读指针的变化时刻采样，写者得到的读指针值有可能是从0000到1111中的任何一个。所以二进制指针不宜被直接同步，但可以通过一对握手信号同步二进制指针。
例如，读指针被读者存入一个寄存器时，读者就发出一个就绪信号。当写者看到就绪信号时，读取读指针，发出一个收到数据的确认信号。当读者看到确认信号时，就收回就绪信号，然后用当前的读指针值刷新寄存器（图2）。在收到确认信号前，存放读指针的寄存器内容保持不变，确保了被读取的指针的正确性。

为了能够在不同的时钟域内直接同步指针，可以对指针使用格雷码的编码方式，也就是指针每次移动只变化一位，这样就避免了由于指针多位同时变化而无法直接同步的问题。图3表示了一个三位地址的内存用于格雷码编码的FIFO。n位地址的内存需要n+1位的格雷码。使用最高位（也就是第n-1位）作为状态位，从第n-2到第0位作为地址的第n-2位到第0位；对状态位（也就是第n-1位）和第n-2位进行位异或运算产生地址的第n-2位（也就是地址的最高位）。通过对图3的观察可以得知，四位格雷码编码的指针和三位二进制加状态位编码的指针具有同样的功能：指针产生的地址循环遍历8个内存地址， 每一次遍历后状态位取反。值得注意的一点，是当指针从0100变化到1100的时候，相应的地址由100变为000，状态位和一位地址同时发生了变化，所以不能同步由另一个时钟域格雷码指针产生的状态位和地址位，此时应该直接由另一个时钟域同步指针来完成，由同步后的指针产生相应的状态位和地址位。


3 保守的满空判断

对于异步FIFO设计，无论是采用握手还是直接同步的方法来获取对方时钟域的指针，对满空信号的判断总是"保守"的。

（1）满空信号的复位（满信号复位表示FIFO非满， 空信号复位表示FIFO非空）和实际FIFO的情况相比有一定的延迟。例如，空信号是由读者用读指针与同步或握手后得到的写指针进行比较产生的。由于同步或握手需要一定的时间，在这段时间，写者可能向FIFO写入新的数据，写指针发生了变化，此时FIFO已经非空，但此刻空信号仍然没有复位。对于写者而言，满信号的复位也会遇到相同的问题。不过，在通常情况下，FIFO只要确保不会向下溢出或向上溢出，复位的延迟就不会导致向下溢出或向上溢出，是可以接受的。

（2）满空信号的置位（满信号置位表示FIFO满， 空信号置位表示FIFO空）和FIFO的实际情况相比没有延迟。例如，同样考虑FIFO为空的情况，读者使用读指针和同步或握手后的写指针进行比较，由于FIFO为空，写动作不会发生，相应的写指针也保持不变，因此读者获得的就是当时的写指针值。这样就能马上对空信号置位。同样地，在FIFO满的情况下，由于读指针不发生变化，写者得到的是当前的读指针值，能够马上判断FIFO为满。
从以上两点的讨论可以得出结论，FIFO满空判断是保守的，写者可能在FIFO还有一定空间时停止写数据，但不会在FIFO已经满了的情况下继续写数据；读者可能在FIFO还有一些有效的数据时停止读数据，但是不会在FIFO已经空的情况下继续读数据。保守的满空判断能够满足FIFO的功能要求。