A FIFO (first in first out) buffer allows for temporary storage for transmission of data between subsystems. It is a very common construct used in digital systems, but why do we need them?
As an example, let’s say that we have a keyboard subsystem that, when a key is pressed, sends corresponding ASCII data to a UART subsystem, which then serially passes the data on to a receiving PC. Assuming that data is directly relayed between the keyboard and UART subsystems, there is risk of data corruption if another key is pressed before the last key’s ASCII data has been processed by the UART subsystem. This condition is known as data overrun, and can be avoided by inserting a data buffer such as a FIFO between the keyboard and UART subsystems. If the baud rate for a UART is high enough, then the likelihood of data overrun occurring is limited by how fast a user can mash the keyboard’s keys (which for the previous implementation was unlikely). Regardless, it is a good idea to provide data buffers between subsystems that are not instantaneous in their processing of sent and received data.
In this post I will briefly detail how to implement a FIFO buffer in Verilog HDL using the Block RAM on a Xilinx Spartan 3 FPGA. The implementation will allow us to specify the number of words (pieces of data) in the FIFO as well as word width (number of bits per word). We will be able to read from and write to the FIFO, assuming it isn’t in an empty or full state, which we will keep track of and signal out from the FIFO to make the utilizing subsystem aware.
First we will need to consider how to utilize the block RAM of our FPGA. Block RAM are dedicated memory blocks within an FPGA, separate from regular logic cells. For the Spartan 3E FPGAs they contain 18K bits per block RAM, and can be organized into various different data widths (i.e. 256 x 64). As an example, the Basys 2 FPGA board uses an XC3D100E Spartan 3E FPGA which has 4 block RAMs for a total of 72K bits.
The benefit to using block RAM instead of the distributed RAM of the logic cells (16 x 1 LUT per cell) is that we can easily implement intermediate sized memory storage without sacrificing the logic cells that are used to build our digital designs.
For the FIFO we will want to implement a dual port block RAM, dual port meaning that there will be separate ports for reading and writing to the RAM. We will clearly communicate the type of block RAM we want to Xilinx ISE to infer from our HDL by following the proper template given on page 145 of the Xilinx XST User Guide .
We begin the module by including parameters for the number of words and word width so they can be set by the circuit utilizing this module, in this instance the FIFO. Following the template we include a clk input, write enable input to signal when to write to the RAM, read/write addresses, data in, and two ports for data out. Inside the module we instantiate ram using the parameters DATA_WIDTH and ADDRESS_WIDTH. This dual port block ram will have synchronous read/write, which is inferred in the always clock. The input data is written to ram on a positive clock edge. The internal registers that store the input read/write addresses are synchronously updated as well, which causes the two data outputs for the read/write addresses to be updated synchronously with the clock.
Next we will implement the FIFO, using the block RAM module to instantiate the buffer’s data storage. We will base our FIFO on a circular-queue design, which is also known as a ring buffer.
The FIFO buffer module will have a signal for write, which when asserted will write the input data to the buffer at the write_address, and then increment write_address by 1 index. When the read input is asserted, the read_address will be incremented by 1 and the data in the buffer at the previous read_address will be left behind. We will need to keep track of when the buffer is empty or full, to know when we can appropriately read or write from it. We will do this by creating two sets of pointer registers, one to keep track of the current read/write addresses and another to keep track of the following read/write addresses (the incremented values). By incrementing the read/write addresses, a ring buffer design is created, as each address pointer can transition all the way to the max address index and back to 0 again.
Above are examples of writing to and reading from a ring buffer with 8 addresses. The buffer is initialized with read/write addresses being 0. When we write ‘O’ to the buffer we place ‘O’ at index 0 and increment the write_address to 1. After writing 3 more inputs to the buffer, the write address is then at index 3.
At this point, the data that is read from the buffer is at read_address which is pointing to index 0 in the buffer. When we read once we increment the read_address to 1, leaving behind the data at index 0 to be overwritten later. Now the data read from the buffer is at index 1. We can read again, and move the read_address to index 2.
Now when we read again, the read_address will catch up with the write_address at index 3, which means that the buffer will be in an “empty” state where we should not allow the read operation to occur, as it will increment read_address to an index that hasn’t been written to yet.
To reiterate, when we are to read from the FIFO and the read address following a potential read operation is the same as the current write address, then the read address pointer has caught up with the write address pointer, signifying that the buffer will now be empty. Likewise, when we are to write to the FIFO and the write address following a write operation is the same as the current read address, then the write address pointer has caught up with the read address pointer, signifying that the buffer will now be full.
In the HDL implementation, write_en (write enable) signal is routed to the block RAM’s write_en input port, and is asserted when the FIF0 write input is asserted and the FIFO isn’t currently full.
The next state logic for the address pointer registers is handled in an always block with a priority routing network, for a read, write, or read/write operation. Note that when a read operation occurs, we check if read_address_after (next index after read operation) is equal to the current write_address, and if so set empty_reg to 1, which will prevent a subsequent read operation until a write operation occurs. Likewise, when a write operation occurs, we check if write_address_after (next index after write operation) is equal to the current read_address, and if so we set full_reg to 1, which will prevent a subsequent write operation to occur until a read operation occurs.
The FIFO buffer module also has size parameters that can set the size of the block RAM that is instantiated, and thus sets the size of the FIFO buffer. This will allow it to serve as a ready made tool in the future when data buffers between subsystems are needed (I’m looking at you VGA monitor).