A FIFO is a sequential data buffer that is very easy to use:

Write a sequence of data words into the FIFO, and read them out in the same sequence. Writing and reading can overlap. There is no explicit addressing.

Most practical implementations use a dual-ported memory (RAM), writing into one port, addressed by the internal write counter, and reading through the other port, addressed by the internal read counter. This allows the use of two totally independent clocks for write and read. This is often called asynchronous operation, although writing and reading are each synchronous operation in their respective clock domain.

Most FIFO designs require free-running clocks, where the write or read operation is controlled by the respective clock enable. A typical FIFO has a DATA IN bus, a DATA OUT bus, a free-running write clock with its Enable control, and a free-running read clock with its Enable control.

The data width of the FIFO must accommodate the application, but the exact depth is irrelevant, as long as it is deep enough. The user never sees the unused locations.

A FIFO is very easy to use, since it hides all functional and timing complexity from the user.

FLAGS

The FIFO uses an EMPTY flag to signal to the user that no more read operations should be started. At the other extreme, the FULL flag tells the user that no more write operation should be started.

Generating these flags requires that the two internal addressing counters be compared for equality (identity), although they are incremented by two independent clocks. This is a very tricky operation. To avoid uncontrolled asynchronous decoding spikes, the counters usually count in a Gray sequence, where only one bit changes on any increment. And the two clocks can interact and might cause metastable delays.

Even more complex is the decoding of Almost Empty and Almost Full conditions, especially when their offset values are programmable. The “Almost” flags are useful as a “friendly early warning”, before the harsh FULL or EMPTY flags become active, which must be obeyed instantly.

The user is isolated from all these complexities, but must accept certain timing ambiguities. The FULL and EMPTY flags will always go active exactly on-time, to stop further reading or writing, but these flags must of necessity be allowed to take a few clock periods to go inactive again. The “Almost” flags have a slight uncertainty caused by the unknown phase relationship between the two clocks.

When the first word is being written into an empty FIFO, EMPTY goes low, and waits for an enabled read clock to present the Data on the DATA OUT bus.

There is a special mode of operation, called First-Word-Fall-Through (FWFT), where the first word written into the empty FIFO directly, on its own, appears at the DATA OUT port.

The conventional mode can be called Pull, while FWFT can be called Push. The two modes differ only in their response to the first write into an empty FIFO.

The preceding described the most demanding case of a high-speed dual-clock (asynchronous) FIFO. In the special case where both clocks are identical (even if individually enabled) the internal decoding is much simpler, and the binary counters and the control can be designed like a synchronous state machine.

At low clock rates, the two clocks can be synchronized to each other, or the read and write operations can be time-multiplexed in a single-port memory.

Very small FIFOs can be implemented with flip-flops or register arrays, sometimes even with shift registers.

Conceptually, a FIFO always behaves like a shift register, but with independent control of write and read operation. The very first FIFOs were actually asynchronous shift registers, but today almost all FIFOs are based on dual-ported RAMs.

For a detailed description of the dedicated FIFO controller in the Virtex-5 FPGAs, click on

http://www.xilinx.com/support/documentation/user_guides/ug190.pdf

and go to page 138:

Many FPGA designs use block RAMs to implement FIFOs. In the Virtex-5 architecture, dedicated logic in the block RAM enables users to easily implement synchronous or multirate (asynchronous) FIFOs. This eliminates the need for additional CLB logic for counter, comparator, or status flag generation, and uses just one block RAM resource per FIFO. Both standard and first-word fall-through (FWFT) modes are supported.