FIFO (electronic)

A FIFO is implemented as a circular buffer that employs two memory address registers (MARs) to store the addresses of (pointers to) the next memory locations to be accessed. The read MAR (RMAR) indicates the next location that data will be read from, and the write MAR (WMAR) indicates the next location that data will be written to.

Each MAR is implemented as a counter, with the count incremented every time data is transferred (WMAR incremented upon FIFO write; RMAR incremented upon FIFO read).^[1] Initially both MARs point to the first memory location and the FIFO is empty. A FIFO becomes full when the write address reaches the read address, and empty when the read address reaches the write address. Consequently, upon FIFO becoming full or empty, the read and write memory addresses are equal, and thus ambiguous if used to monitor the FIFO level (number of words stored).

In many FIFOs, to distinguish between empty and full, each MAR has an additional bit beyond what is needed to address memory. All MAR output bits except the most significant bit (MSB) (i.e., the LSBs) serve as the memory address. Conversely, all MAR output bits (including MSB) form an extended address that is used to monitor the FIFO level. More specifically, a MOD-${\displaystyle 2^{n}}$ counter (a counter with ${\displaystyle 2^{n}}$ distinct output states) is used for a FIFO memory that can store ${\displaystyle 2^{n-1}}$ data words. For example, a MOD-32 MAR is used to generate addresses in a FIFO having a 16-word memory.

In cases where the MARs employ binary counters, the current FIFO level (number of words stored) is the difference between their binary output values: ${\displaystyle level=WMAR-RMAR}$. For other output encodings (e.g., Gray code), the MAR outputs must be converted to binary before computing the difference. In either case, the following hold true:

• The FIFO is empty when RMAR and WMAR are equal
• The FIFO is full when RMAR and WMAR differ only in their MSBs

A FIFO typically outputs status signals that indicate whether particular data level thresholds are met. Common examples of such status flags include full, empty, half full, almost full, and almost empty.

A synchronous FIFO is an electronic FIFO that uses a common clock for reading and writing. Because read and write operations take place in the same clock domain, the MARs typically use binary output encoding for simplicity, and level detection and status flags may be implemented either via pointer arithmetic or by using a dedicated counter to monitor the FIFO level.

An asynchronous FIFO is an electronic FIFO that uses different clocks for reading and writing. To avoid errors due to metastability, asynchronous FIFOs typically use Gray code for the read and write pointers, and level detection and status flags are implemented via pointer arithmetic.

• Leaky bucket approach
• Ring buffer