Circular Buffers in VHDL

Introduction

In certain applications, a standard linear buffer in memory is awkward. Take for instance maintaining a statically sized input stream buffer (as is needed in maintaining an audio input buffer). The functionality of such a buffer requires the last element to be disposed of and the newest element to be inserted at the beginning of the buffer. This would require all elements but the last one to be shifted over by one address in memory. Doing so is time consuming and unneccessary.

This same functionality is offered by a circular buffer, which requires no shifting of blocks of memory.

Theory

To implement this functionality, a block of memory is sectioned off which accomodates the number of elements you need to store. For best performance, use a size that is a power of two. In these example images, a size of 8 elements is chosen (with indeterminate data width). Two internal registers must be maintained.

Fig. 1: Initial state of the buffer

Fig. 1 shows the 8 elements of the buffer (labelled 1 through 8) and the locations represented by the two pointers. As well, the "greyed out" look of the cell labels means they have not been written to. Note that the read pointer is at the end and the write pointer is at the start. These locations can be set arbitrarily so long as the read pointer is set to one memory address less than (including wrapping) the write pointer.

A write operation places the data to be written in the location pointed to by the write pointer, copies the value of the current write pointer into the read pointer, then increments the write pointer by 1. The state of the pointers after 3 write operations is shown in Fig. 2.

Fig. 2: After 3 write operations

The write pointer is always at the next location where data should be written, and the read pointer is always set to the last written element after a write operation. In Fig. 2, the darker labels mean elements 1, 2, and 3 have been written to.

Fig. 3: A read operation

Fig. 3 shows the result after a single read operation after the state of Fig. 2. To read, the data at the read pointer is placed on the output data bus, and the read pointer is decremented by one. In this case, element #3, the last element to be written to the buffer, is read.

Fig. 4: After another read operation

In Fig. 4, the next to last element to be written is read. This is the second read operation. Read operations continue in this manner, wrapping around from the left end to the right end of the buffer. When the read pointer reaches the write pointer, the last element has been read. This may or may not be important to the VHDL programmer.

Implementation

A simple implementation can be achieved in VHDL using a minimum of inputs and outputs. Again, make sure a power of two is chosen for the size of the buffer. This makes managing the pointers easier. The entity declaration is as follows:

entity circular_buffer is
  generic (ram_data_width : integer := 4;    -- width of data
           ram_address_width : integer := 1; -- width of address
           num_values : integer := 2);       -- number of values
  port(
       read : in std_logic;
       write : in std_logic;
       reset : in std_logic;
       datain : in std_logic_vector(ram_data_width-1 downto 0);
       dataout : out std_logic_vector(ram_data_width-1 downto 0);
       data_ready : out std_logic;
       clk : in std_logic
);
end circular_buffer;

The generics are used to control lpm_ram_dq as well as managing the circular buffer's address and data widths.

In an idle state, the read and write lines must be left low. The reset line should be chosen to be active high or low depending on preference.

To write to the buffer, a VHDL construct must put the data on the datain input signal, and set the write line to high. This initiates a write cycle. As soon as the data_ready line goes high, the operation is complete. The buffer is then ready to perform another operation.

To read from the buffer, simply set read to high and wait for the data_ready line to go high. On the rising edge of data_ready, The data on dataout will be valid. The data should be latched at this point. On the next cycle, the buffer is ready for another operation.

The read and write lines should be mutually exclusive.

Here is a proposed state machine for the circular buffer implementation. Note that the choice of a buffer size that is a power of two means the synthesized code can be smaller, as there is no need for bounds checking. Adding a '1' bit to the binary number '111' represented using three bits results in '000.'

Fig. 5: State Diagram

This can be adapted to whatever speed is needed for individual projects.