In this next article I am going to explore a component commonly used in circuit design, specifically the FIFO buffer. A FIFO is a First-In-First-Out data structure. Our buffer design will utilize the register file created earlier.
Designing a FIFO
A FIFO is a memory buffer with a fixed storage capacity. And there are two basic operations that can be performed. First, you can write new data to the buffer until it is full. And you can also read data from the buffer until it is empty.
A FIFO is a memory component and therefore it is a synchronous circuit. So, the design will include the customary clk and rst signals. And we will also have read (rd) and write (wr) signals. And signals to indicate whether the buffer is full or empty. Finally, we will have an input bus Din and an output bus Dout.
You might be wondering why there are separate read and write signals. Couldn’t we use a single wr signal to encode whether we are reading or writing? The answer is that yes, we certainly could. However, that would obviously prevent us from simultaneously reading from and writing to the buffer. And that seems undesirable tradeoff given that a common use case for a FIFO is to buffer data between two circuits operating in parallel that read and write at slightly different rates. In return for one extra input signal, we get the ability to simultaneously read and write data.
Using a Circular Buffer
A FIFO is typically implemented in terms of a circular buffer, also referred to as a ring buffer. A circular buffer uses a read pointer and a write pointer to keep track of the data in a block of memory used as the buffer. When the two pointers are equal the buffer is empty. As we add data to the buffer the write pointer advances ahead of the read pointer. Likewise, as we read data from the buffer the read pointer advances towards the write pointer. The two pointers are wrapped back to the beginning of the buffer when the end is reached.
If you think about it, you should see that there are really three states for our buffer: empty, full, and non-empty. The meaning of the empty and full states should hopefully be clear. The non-empty state simply means that there is currently some unread data waiting in the buffer. We leave this state as implicit when the buffer is not full AND not empty.
On a rst, the buffer should be empty, so the read and write pointers are set to the same value. How then do we determine when the buffer is full? Remember that as we add data to the buffer, we are advancing the write pointer, wrapping the pointer if necessary. If no data is read, eventually the write pointer will “catch up” to the read pointer. When the write pointer is about to overtake the read pointer we have put as much data as possible into the buffer, and it is now full.
Register File for Storage
We can use a register file as the underlying storage for the buffer. And conveniently we created one that we can reuse for this purpose. To do so we will connect the FIFO Din and Dout ports to the wr_data and r_data ports of the register file. And so, data read and written into the FIFO becomes data read and written to the register file. The wr_addr line of the register file is connected to the FIFO’s write pointer. And the r_addr of the register file is connected to the FIFO’s read pointer. Finally, we will need some logic to determine when the wr_en of register file is set. For this, we want to enable writes to the register file when a write is requested via the wr signal AND when the FIFO is not full. So, the logic will look something like this: wr_en = wr & ~full.
Verilog Implementation
Let’s see how that all comes together in Verilog. Below is the complete FIFO implementation. Starting at the top we have two configurable parameters ADDR_BITS and DATA_WIDTH. The first parameter (ADDR_BITS) determines the number of words in our buffer (i.e. register file). It defaults to 3 address bits, giving 2 ** 3 = 8 entries. The second parameter (DATA_WIDTH) determines the width of a word in bits. It defaults to 8-bits wide, a byte.
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Configurable FIFO
//////////////////////////////////////////////////////////////////////////////////
module fifo
#(
parameter ADDR_BITS = 3,
DATA_WIDTH = 8
)
(
input clk, rst,
input wire wr, rd,
input wire [DATA_WIDTH - 1 : 0] Din,
output wire [DATA_WIDTH - 1 : 0] Dout,
output wire full, empty
);
// internal signals, r_ prefix means register type
wire wr_en;
reg r_full, r_empty;
reg r_full_next, r_empty_next;
reg [ADDR_BITS - 1 : 0] r_write_ptr, r_write_ptr_next, r_write_plus_one;
reg [ADDR_BITS - 1 : 0] r_read_ptr, r_read_ptr_next, r_read_plus_one;
// instantiate a register file
register_file #(.ADDR_BITS(ADDR_BITS), .REG_WIDTH(DATA_WIDTH)) regfile
(
.clk(clk), // pass in our clock
.wr_en(wr_en), // wire up write enable
.wr_data(Din), // Din writes data to register file
.r_data(Dout), // Dout reads data from register file
.wr_addr(r_write_ptr), // connect the write pointer to the write addr
.r_addr(r_read_ptr) // connect the read pointer to the read addr
);
// we can write to the register file only if it is not full
assign wr_en = wr & ~r_full;
// connect our state to output wires
assign full = r_full;
assign empty = r_empty;
// data path logic for fifo control
always @(posedge clk, posedge rst)
begin
if (rst)
begin
r_write_ptr <= 0;
r_read_ptr <= 0;
r_full <= 1'b0;
r_empty <= 1'b1;
end
else begin
r_write_ptr <= r_write_ptr_next; // update the write pointer
r_read_ptr <= r_read_ptr_next; // update the read pointer
r_full <= r_full_next; // update the full state
r_empty <= r_empty_next; // update the empty state
end
end
// control path logic - combinational logic
always @*
begin
// default to previous values
r_write_ptr_next = r_write_ptr;
r_read_ptr_next = r_read_ptr;
r_full_next = r_full;
r_empty_next = r_empty;
// compute the next ptr values
r_write_plus_one = r_write_ptr + 1;
r_read_plus_one = r_read_ptr + 1;
// handle rd when not empty
if (rd & ~r_empty)
begin
// can't be full if we weren't empty and just did a read
r_full_next = 1'b0;
// advance the read pointer
r_read_ptr_next = r_read_plus_one;
// if new/next read pointer now equals write pointer we are empty
if (r_write_ptr == r_read_plus_one)
r_empty_next = 1'b1;
end
// handle wr when not full
if (wr & ~r_full)
begin
// can't be empty if we weren't full and just did a write
r_empty_next = 1'b0;
// advance the write pointer
r_write_ptr_next = r_write_plus_one;
// if new/next write pointer now equals read pointer we are full
if (r_read_ptr == r_write_plus_one)
r_full_next = 1'b1;
end
end
endmodule
On line 27 you can see where we instantiate a register file, connecting to our FIFO signals. Then on lines 38 – 42 we use continuous assignments to compute the wr_en, full and empty signals. The full and empty states are buffered with registers for consistent timing. Then at line 45 we begin our sequential logic for the synchronous always block which handles rst and clk signals by resetting or updating internal state variables respectively.
And finally starting at line 63 is our combinational logic to update the internal state. First, we compute the next read and write positions. Then we handle the read and write cases one after the other. The logic for reading is quite simple, if rd is asserted and the buffer is not empty (~empty) then we can read a byte from the buffer. To do so we first set full to zero since we cannot be full if we were not empty and we are reading a value. Then, the next read pointer position is set. Last, we check whether the next read pointer position equals the write pointer position. If so, then the buffer must now be empty and we raise that signal.
Simulation Testbench
OK, now we have our FIFO code. How do we make sure that it is working correctly? That’s right, we need a test bench to exercise the code and prove that it works. Below is a very simple test bench that writes sequential byte values to the FIFO until it signals that it is full. Then it reads from the FIFO until it signals that it is empty. If all goes well, we should retrieve numbers from the buffer in proper sequence.
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// FIFO Testbench
//////////////////////////////////////////////////////////////////////////////////
module fifo_test();
localparam T = 20;
localparam ADDR_BITS = 3;
reg clk;
reg rd, wr, rst;
reg [7 :0] Din;
wire [7:0]Dout;
wire full, empty;
// declare the unit under test
fifo uut
(
.clk(clk),
.rst(rst),
.wr(wr),
.rd(rd),
.Din(Din),
.Dout(Dout),
.full(full),
.empty(empty)
);
// generate the clock signal
always
begin
#(T/2) clk = ~clk;
end
// set initial conditions
initial
begin
clk = 0;
rd = 0;
wr = 0;
rst = 1'b1;
#(T/2);
rst = 1'b0;
end
// perform some tests
initial
begin
// wait for reset to complete
@(negedge rst)
// fill the FIFO
@(negedge clk);
wr = 1'b1;
Din = 1;
while(~full)
begin
@(negedge clk);
Din = Din + 1;
end
// empty the FIFO
@(negedge clk);
wr = 1'b0;
rd = 1'b1;
wait(empty == 1'b1);
#(4*T);
$stop;
end
endmodule
Running the simulation produces the waveform shown below. From this you can see that after rst, the wr signal is raised for 8 clk cycles, during which the values 1 through 8 are written to Din. The empty signal is asserted until the first value of Din is written to the buffer on the rising edge of the second clk cycle after rst. Once the 8th value is written, the buffer signals that it is full. At this point we de-assert wr and assert rd at which point the value of Dout updates from 1 through 8 until once again the buffer signals empty.
The FIFO is working as expected! We now have a useful and configurable component that can be used in future projects.
And that’s it for now! As always, the source code for this project is on github.
Please remember to Like and Share these posts on social media. And remember that if you have feedback, questions or suggestions regarding this or other posts, please leave a comment!