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. Data is stored on demand and the oldest stored data is output on demand, with both operations occurring independently and at potentially different rates. This is in contrast to a shift register, which requires data to be concurrently stored and output, and for the oldest data to sequentially propagate through memory before it is output.
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 data stored in a FIFO typically have a fixed word size (number of bits), which is commonly referred to as the FIFO width. The maximum possible number of stored datums is known as the FIFO depth. Together, the width and depth determine the storage capacity of a FIFO.
FIFOs are used to exchange data between two hardware devices or between a hardware device and software. They are commonly used to exchange data between circuits that operate in different clock domains, and for buffering and flow control between data producers and consumers which, over finite intervals, operate at different data rates.
Interface ports
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.
Write and read agents
The external circuits connected to a FIFO's ports consist of a data producer (variously referred to as data source or write agent) that stores data in the FIFO and a data consumer (also known as data sink or read agent) 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.
Clock domain
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 and thus all write port signals are synchronized to the producer's clock. Similarly, the read port operates in the consumer's clock domain.
FIFO types
Every FIFO is categorized as either synchronous or asynchronous.
Synchronous FIFO
A synchronous FIFO is an electronic FIFO that uses a common clock for the read and write ports.
Since read and write operations take place in the same clock domain, the FIFO's status signals (buffer level, threshold flags) can be safely used by both the data producer and consumer without causing metastability. Consequently, a synchronous FIFO outputs a single, shared group of status signals.
Asynchronous FIFO
An asynchronous FIFO is an electronic FIFO that uses different clocks for the read and write ports.
To avoid errors due to metastability, a dedicated set of status signals (buffer level, threshold flags) is output for each clock domain. The circuitry used to circumvent metastability introduces additional latency (compared to synchronous FIFOs) into status flag updates when data is written to an empty FIFO or read from a full FIFO.
Memory attributes
To facilitate concurrent read and write operations, the memory in all asynchronous FIFOs and in many synchronous FIFOs is dual-ported, typically consisting of a register file or dual-ported RAM (random access memory). In asynchronous FIFOs, the memory is an asynchronous circuit that is accessible to logic operating in any clock domain.
Width
The data written to and read from a FIFO typically have the same, fixed word size (number of bits) — commonly known as the FIFO width — which matches the native word size of the internal memory.
Depth
The maximum number of words that can be stored in a FIFO is known as the FIFO depth. Although it is not required, the depth is usually an integer power of two, as this tends to simplify circuitry and improve speed performance.
To avoid overflow, the FIFO depth must be large enough to store the data resulting from the worst-case difference between data production and consumption rates, and the average bandwidths of the producer and consumer must match. Also, in asynchronous FIFOs, a small amount of additional depth is usually provided to allow for status latency.
Memory address registers
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). 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. When a MAR addresses the last location in memory, it will automatically roll over to the first memory address upon the next increment.
For any particular FIFO, the MARs may be implemented as either binary or Gray code counters. Binary counters are usually preferred in synchronous FIFOs, as this simplifies the FIFO circuitry. Gray code counters, or Gray code-encoded binary counters, are used in asynchronous FIFOs to avoid errors due to metastability.
Status signals
Buffer level
Many FIFOs output a binary value that indicates the current buffer level (number of words stored). Depending on its design, a FIFO may do this by either tracking the level with a counter or computing the level using pointer arithmetic. Synchronous FIFOs may use either method, whereas asynchronous FIFOs are restricted to using pointer arithmetic.
Tracking via counter
In a synchronous FIFO, the buffer level may be monitored by tracking it with a bidirectional binary counter. The count is incremented when data is written to the FIFO, and decremented when data is read. The binary count value output by the counter directly indicates the buffer level.
This method is not suited to asynchronous FIFOs because the read and write ports operate in different clock domains, which would require the counter to be controlled by two different clocks.
Calculation via pointer arithmetic
In asynchronous FIFOs, and in many synchronous FIFOs, the buffer level is calculated from the current memory addresses. This is easily done when the FIFO is neither empty nor full because the level is equal to the difference between the write and read addresses. However, when the FIFO is empty or full, the addresses are equal and thus would be ambiguous if used to compute level. Consequently, to distinguish between empty and full, it is common for each MAR to have one 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- counter (a counter with distinct output states) is used for a FIFO memory that can store 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 buffer level is the difference between the MAR output values: . For other output encodings (e.g., Gray code), the MAR outputs must be converted to binary before computing the difference. In either case, the difference is typically calculated by a MOD- binary subtractor, with any resulting arithmetic borrow (i.e., carry out) discarded.
Buffer threshold flags
A FIFO outputs individual status signals (flags) that indicate whether particular data level thresholds are met. All FIFOs output full and empty flags, and some may also output additional flags such as half full, almost full, and almost empty.
Status signals may be generated by directly comparing the synchronized read and write addresses or, if available, from the FIFO level. In the latter case, status signals are derived from the FIFO level via combinational logic or, in the case of full, by extracting the MSB. Depending on the FIFO design, the thresholds for almost full and almost empty flags (if implemented) may be application-specific constants or they may be programmable.
Usage
The FIFO status flags are used to notify the external data producer and consumer that critical thresholds have been reached. Typically the producer and consumer will respond to such notifications by suspending or resuming FIFO writing and reading, respectively. The producer or consumer (or both) may be a processor that polls status or receives status via interrupts, or it may be a purely hardware entity that uses the status signals to manage flow control.
In many FIFOs, the full and empty flags are used internally to qualify the write enable and read enable signals. Writing is inhibited when full is asserted: data is not written to memory and the write MAR is not incremented. Similarly, reading is inhibited when empty is asserted: the read MAR is not incremented, and typically the previous read data is output.
Address synchronization
In FIFOs that compute buffer level via pointer arithmetic, the read and write addresses 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 a series of two or more registers that are clocked by the other port. The first register synchronizes the address to the other port's clock, and subsequent register(s) mitigate any resulting metastability.
Gray code encoding
When incremented, a binary address will in many cases change by multiple bits at the same time (e.g., from 0111 to 1000}. If the changing bits happen to be sampled too close to the moment they change (and thereby violate the sampling register's setup or hold time), some may be sampled at their previous state and others at their new state, thus producing an invalid address in the destination clock domain which matches neither the previous nor the new address. When this happens, the buffer level calculated in the other clock domain will be incorrect.
To prevent such errors, the address is sent to the other clock domain as a Gray code value. Since every address increment changes only one Gray code bit, the address received by the other clock domain is guaranteed to match either the previous or new address if sampled when the bit is changing.
In some FIFOs this is done by implementing the MAR as a Gray code counter that directly outputs Gray code addresses, as shown below:
Alternatively, a MAR with binary encoded outputs may be used in conjunction with a binary-to-Gray code converter. This requires the converter output to be reclocked before it crosses clock domains, to eliminate Gray code glitches caused by binary bits changing at different times.
Address processing