FIFO (electronic)

In digital electronics, a FIFO (acronym for first-in, first-out) is a digital circuit that stores incoming data in internal memory and outputs the stored data in the order it was received. The oldest stored data is typically output with little or no delay. This is in contrast to a shift register, which requires data to sequentially propagate through memory before it is output. FIFOs are commonly used for buffering and flow control between hardware devices or between software and hardware devices which, over finite intervals, operate at different data rates.

A FIFO primarily consists of a pair of counters that serve as read and write memory address registers, an addressable memory array, and status and control logic. The memory typically is dual-ported to allow concurrent FIFO read and write operations, and consists of a register file or dual-ported RAM (random access memory). Although it is not required, the memory storage capacity (in words) is usually an integer power of two, as this tends to simplify circuitry and improve speed performance. The data written to and read from a FIFO typically have a fixed word size (number of bits) equal to that of the internal memory.

A FIFO has two electrical interfaces known as the write port and read port, through which it exchanges data and status information with external circuits. The external circuitry consists of a data producer that stores data in the FIFO and a data consumer that fetches the stored data. More specifically, the producer sends data to and receives status information from the write port, and the consumer receives both data and status from the read port.

Each port operates in the clock domain of the external circuit it is connected to, meaning that the port and external circuit share a common clock signal. The write port operates in the producer's clock domain annd thus all write port signals are synchronized to the producer's clock. Similarly, the read port operates in the consumer's clock domain.

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

An asynchronous FIFO is an electronic FIFO that uses different clocks for the read and write ports. To avoid errors due to metastability, the MARs typically use Gray code encoding, level detection is implemented via pointer arithmetic, and a dedicated set of status signals (buffer level, threshold flags) is output for each clock domain.

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 associated with a particular port, and thus operates in that port's clock domain.

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.

For any particular FIFO, the MARs may be implemented as either binary or Gray code counters. Binary counters are usually preferred when FIFO read and write operations use a common clock, as this simplifies the FIFO circuitry. Gray code counters are used when FIFO read and write operations use independent clocks (i.e., they operate different clock domains).

FIFOs typically output a binary value indicating the current buffer level (number of words stored). Depending on its design, a FIFO may do this by tracking the level with a bidirectional counter that counts up and down as data is written and read, or it may compute the level using pointer arithmetic.

In the latter case, when the FIFO is neither empty nor full, the buffer level is equal to the difference between the write and read memory addresses. However, when the FIFO is empty or full, the memory addresses are equal and thus would be ambiguous if used to compute level. Consequently, to distinguish between empty and full, each MAR has an additional bit beyond what is needed to address memory. The resulting extended address (XADDR) is used to compute the FIFO level, while all bits of XADDR other than the most significant bit (MSB) (i.e., the LSBs) serve as the memory address.

In general, 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 are binary counters, the FIFO level is the difference between the MAR 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. The difference is typically calculated by a MOD-n binary subtractor, with any resulting arithmetic borrow discarded.

FIFOs typically output individual status signals (flags) that indicate whether particular data level thresholds are met. Common examples of such status flags include full and empty, half full, almost full, and almost empty. Status signals are derived from the FIFO level via combinational logic or, in the case of full, by extracting the MSB.

A FIFO's read and write addresses are both used to calculate the buffer level, so both must be synchronized to a common clock to ensure stable inputs for the binary subtractor. This requirement is inherently satisfied in synchronous FIFOs because read and write ports use the same clock. However, asynchronous FIFOs use different clocks for read and write ports, and consequently the buffer level must be independently calculated for each port in its own clock domain. This requires the current address of each port to be synchronized to the other port's clock, a process known as clock domain crossing.

Clock domain crossing is typically implemented by sequentially passing a port's current address through two or more registers that are clocked by the other port. The first register synchronizes the address to the other port's clock, and the subsequent register (or registers) mitigate any resulting metastability.

• Leaky bucket approach