Circular FIFO in VHDL

[Binome]

Hi,
I want to create a circular FIFO to reuse the free memory. Here is my code:

library	ieee;
use		ieee.std_logic_1164.all;
use		ieee.numeric_std.all;

entity ring_fifo is
	generic(
		fifo_length	: integer:=8;
		data_width	: integer:=4);

	port(
		clk			: in std_logic;
		rst			: in std_logic;
		ren			: in std_logic;
		wen			: in std_logic;
		dataout		: out std_logic_vector(data_width-1 downto 0);
		datain		: in  std_logic_vector(data_width-1 downto 0);
		empty		: out std_logic;
		err			: out std_logic;
		full		: out std_logic);
	end ring_fifo;

architecture arc of ring_fifo is

	type memory_type is array (0 to fifo_length-1) of std_logic_vector(data_width-1 downto 0);

	signal memory	: memory_type := (others => (others => '0'));
	signal readptr,writeptr	: integer range 0 to fifo_length-1 := 1;
	signal rcycle,wcycle : std_logic := '0';
	signal full0	: std_logic := '0';
	signal empty0	: std_logic := '1';

begin
	full <= full0;
	empty <= empty0;
		
	fifo0: process(clk,rst)
	begin
		if rst='1' then
			readptr <= 0;
			writeptr <= 0;
			rcycle <= '0';
			wcycle <= '0';
			full0 <= '0';
			empty0 <= '1';
			err <= '0';
		elsif rising_edge(clk) then
			if (wen='1' and full0='0') then 
				memory(writeptr) <= datain ;
				if (writeptr=fifo_length-1) then
					wcycle <= not wcycle;
					writeptr <= 0;
				else
					writeptr <= writeptr+1;
				end if;
			end if;

			if (ren='1' and empty0='0') then 
				dataout <= memory(readptr);
				if (readptr=fifo_length-1) then
					rcycle <= not rcycle;
					readptr <= 0;
				else
					readptr <= readptr+1;
				end if;
			end if ;
			
				if ((writeptr + 1 = readptr)) or ((writeptr=fifo_length-1) and (readptr=0)) then
					full0 <= '1';
				else
					full0 <= '0';
				end if;
					
				if (readptr = writeptr) then
					empty0 <= '1';
				else
					empty0 <= '0';
				end if;
				
				if (empty0='1' and ren='1') or (full0='1' and wen='1') then
					err <= '1';
				else
					err <= '0';
				end if;
		end if; 
	end process;
end arc;

I tried to write words without reading and I've got problems: full and err signals are being 1 only during one cycle and err is one cycle too late.
Do you know a solution?
Thanks.

 

[TrickyDicky]

How about using a testbench to debug your code?
You have no overrun or underrun protection. So if you write to a full fifo or read from an empty fifo it will cause it to think it's empty/full again.

Secondly, if you used unsigned type for the readptr and write ptr, and limited memory size to 2^n, then you dont need to worry about resetting to 0 or chcking for 0, as it will automatically rollover.

 

[Binome]

I've corrected things and am still working on it...

I don't understand the overrun/underrun point. I thought full/empty signals would be enough. It's not?

Here's my new code:

library	ieee;
use		ieee.std_logic_1164.all;
use		ieee.numeric_std.all;

entity ring_fifo is
	generic(
		fifo_length	: integer:=8;
		data_width	: integer:=4);

	port(
		clk			: in std_logic;
		rst			: in std_logic;
		ren			: in std_logic;
		wen			: in std_logic;
		dataout		: out std_logic_vector(data_width-1 downto 0);
		datain		: in  std_logic_vector(data_width-1 downto 0);
		empty		: out std_logic;
		err			: out std_logic;
		full		: out std_logic);
	end ring_fifo;

architecture arc of ring_fifo is

	type memory_type is array (0 to fifo_length-1) of std_logic_vector(data_width-1 downto 0);

	signal memory	: memory_type := (others => (others => '0'));
	signal readptr,writeptr	: integer range 0 to fifo_length-1 := 1;
	signal rcycle,wcycle : std_logic := '0';
	signal full0	: std_logic := '0';
	signal empty0	: std_logic := '1';

begin
	full <= full0;
	empty <= empty0;

	err <= '1' when (empty0='1' and ren='1') or (full0='1' and wen='1')
				else '0';

	fifo0: process(clk,rst)
	begin
		if rst='1' then
			readptr <= 0;
			writeptr <= 0;
			full0 <= '0';
			empty0 <= '1';
		elsif rising_edge(clk) then
			if wen='1' and not(writeptr=readptr and wcycle/=rcycle) then 
				memory(writeptr) <= datain ;
				if (writeptr=fifo_length-1) then
					writeptr <= 0;
					wcycle <= not wcycle;
				else
					writeptr <= writeptr+1;
				end if;
			end if;

			if (ren='1' and not(readptr=writeptr and rcycle=wcycle)) then 
				dataout <= memory(readptr);
				if (readptr=fifo_length-1) then
					readptr <= 0;
					rcycle <= not rcycle;
				else
					readptr <= readptr+1;
				end if;
			end if ;
			
				if ((writeptr + 1 = readptr)) or ((writeptr=fifo_length-1) and (readptr=0)) then
					full0 <= '1';
				else
					full0 <= '0';
				end if;
					
				if (readptr=writeptr and wcycle=rcycle) then
					empty0 <= '1';
				else
					empty0 <= '0';
				end if;
				
		end if; 
	end process;
end arc;

I do have a testbench and this component seems to behave pretty well. Do you see some evident errors?

 

[TrickyDicky]

The problem comes because full and empty lag the write/read requests by 1 clock cycle. So they will not prevent overrun or underrun if you use them direcly.

With your new code you can never read and write at the same time. Also, the initial setup requires a read before you can do a write.

 

[K-J]

I do have a testbench and this component seems to behave pretty well. Do you see some evident errors?

- The signals rcycle and wcycle serve no useful purpose.
- The logic for when you allow read and write is flawed. The user only sees 'full' and 'empty'. Based on those signals only they will assert 'ren' or 'wen' but what you have written does not reflect that at all. You're comparing pointers and checking 'wcycle' and 'rcycle' to potentially inhibit the read/write to the fifo which means that there will be cases where the user writes to a fifo that you say is not full, but the write is ignored. The if statement should be nothing more than "if wen='1' and full='0' then...", nothing more, nothing less. Similar comment for the read side. In fact, if you look at your logic for 'err', which is correct, you could just say "if wen='1' and 'err='0' then..."
- Your computation for full is not correct. If readptr is currently 0 because it has just wrapped, and writeptr is at the maximum of 'fifo_length-1' then 'writept+1' will not equal 'readptr' so you will not set 'full0' to 1, but the next value for writeptr will be 0 and the fifo will be full.

Kevin Jennings

 

[Binome]

The problem comes because full and empty lag the write/read requests by 1 clock cycle. So they will not prevent overrun or underrun if you use them direcly.

I don't understand what could happen/why there's a problem/how to correct it.

With your new code you can never read and write at the same time. Also, the initial setup requires a read before you can do a write.

Yes, the simulation shows me that. But why?
And I don't understand the initialization problem.

 

[Binome]

@K-J
When writing I'm using "if wen and $the conditions for not full$" and not "if wen and not full" because there would be a 1-cycle lag I don't want. What should I do?
My new code is:

library	ieee;
use		ieee.std_logic_1164.all;
use		ieee.numeric_std.all;

entity ring_fifo is
	generic(
		fifo_length	: integer:=8;
		data_width	: integer:=4);

	port(
		clk			: in std_logic;
		rst			: in std_logic;
		ren			: in std_logic;
		wen			: in std_logic;
		dataout		: out std_logic_vector(data_width-1 downto 0);
		datain		: in  std_logic_vector(data_width-1 downto 0);
		empty		: out std_logic;
		err			: out std_logic;
		full		: out std_logic);
	end ring_fifo;

architecture arc of ring_fifo is

	type memory_type is array (0 to fifo_length-1) of std_logic_vector(data_width-1 downto 0);

	signal memory	: memory_type := (others => (others => '0'));
	signal readptr,writeptr	: integer range 0 to fifo_length-1 := 1;
	signal rcycle,wcycle : std_logic := '0';
	signal full0	: std_logic := '0';
	signal empty0	: std_logic := '1';

begin
	full <= full0;
	empty <= empty0;

	err <= '1' when (empty0='1' and ren='1') or (full0='1' and wen='1')
				else '0';

	fifo0: process(clk,rst)
	begin
		if rst='1' then
			readptr <= 0;
			writeptr <= 0;
			full0 <= '0';
			empty0 <= '1';
			rcycle <= '0';
			wcycle <= '0';
		elsif rising_edge(clk) then
			if wen='1' and not(writeptr=readptr and wcycle/=rcycle) then 
				memory(writeptr) <= datain ;
				if (writeptr=fifo_length-1) then
					writeptr <= 0;
					wcycle <= not wcycle;
				else
					writeptr <= writeptr+1;
				end if;
			end if;

			if (ren='1' and not(readptr=writeptr and rcycle=wcycle)) then 
				dataout <= memory(readptr);
				if (readptr=fifo_length-1) then
					readptr <= 0;
					rcycle <= not rcycle;
				else
					readptr <= readptr+1;
				end if;
			end if ;
			
				if (writeptr+1=readptr and wcycle/=rcycle) or (writeptr=fifo_length-1 and readptr=0 and wcycle=rcycle) then
					full0 <= '1';
				else
					full0 <= '0';
				end if;
					
				if (readptr=writeptr and wcycle=rcycle) then
					empty0 <= '1';
				else
					empty0 <= '0';
				end if;
				
		end if; 
	end process;
end arc;

Is this better?

 

[K-J]

@K-J
When writing I'm using "if wen and $the conditions for not full$" and not "if wen and not full" because there would be a 1-cycle lag I don't want.

If there is a one cycle lag, then it is because you haven't generated the full flag to occur on the proper clock cycle. On the clock cycle immediately after the fifo write that causes the fifo to become full, you must set full to 1 otherwise your fifo will not work correctly. Similarly, on the clock cycle immediately after the fifo read that causes the fifo to become empty, you must set empty to 1 otherwise your fifo will not work correctly.

What should I do?

See my previous post. The 'if' statement that inhibits writing (reading) when full (empty) must be how I wrote it otherwise you will have a condition that does not work because your conditions for inhibiting the read or write do not agree with the fifo status of full and empty.

Kevin Jennings

 

[TrickyDicky]

I don't understand what could happen/why there's a problem/how to correct it.

Just as K-J said, you are generating full and empty on one clock, and reading them on the next. But the read addr and write addr were matched on the clock before, so they will move on as if they are not full anymore.

Yes, the simulation shows me that. But why?
And I don't understand the initialization problem.

Because you have these rcycle and wcycle signals. They toggle on every read/write. They both start at 0. You code means you can only do a read when they are both the same value, and you can only do a write when they are different. As K-J said, they are not needed and just hinter your progress.

 

[Binome]

Hi both,
here is my new code:

library	ieee;
use		ieee.std_logic_1164.all;
use		ieee.numeric_std.all;

entity ring_fifo is
	generic(
		fifo_length	: integer:=8;
		data_width	: integer:=4);

	port(
		clk			: in std_logic;
		rst			: in std_logic;
		ren			: in std_logic;
		wen			: in std_logic;
		dataout		: out std_logic_vector(data_width-1 downto 0);
		datain		: in  std_logic_vector(data_width-1 downto 0);
		empty		: out std_logic;
		err			: out std_logic;
		full		: out std_logic);
	end ring_fifo;

architecture arc of ring_fifo is

	type memory_type is array (0 to fifo_length-1) of std_logic_vector(data_width-1 downto 0);

	signal memory	: memory_type := (others => (others => '0'));
	signal readptr,writeptr	: integer range 0 to fifo_length-1 := 1;
	signal rcycle,wcycle : std_logic := '0';
	signal full0	: std_logic := '0';
	signal empty0	: std_logic := '1';

begin
	full <= full0;
	empty <= empty0;

	err <= '1' when (empty0='1' and ren='1') or (full0='1' and wen='1')
				else '0';

	fifo0: process(clk,rst)
	begin
		if rst='1' then
			memory <= (others => (others => '0'));
			readptr <= 0;
			writeptr <= 0;
			full0 <= '0';
			empty0 <= '1';
			rcycle <= '0';
			wcycle <= '0';
		elsif rising_edge(clk) then
			if (wen='1' and full0='0') then
				memory(writeptr) <= datain ;
				if (writeptr=fifo_length-1) then
					writeptr <= 0;
					wcycle <= not wcycle;
				else
					writeptr <= writeptr+1;
				end if;
			end if;

			if (ren='1' and empty0='0') then
				dataout <= memory(readptr);
				if (readptr=fifo_length-1) then
					readptr <= 0;
					rcycle <= not rcycle;
				else
					readptr <= readptr+1;
				end if;
			end if ;
			
				if (writeptr+1=readptr and wcycle/=rcycle) or (writeptr=fifo_length-1 and readptr=0 and wcycle=rcycle) then
					full0 <= '1';
				else
					full0 <= '0';
				end if;
					
				if (readptr=writeptr and wcycle=rcycle) then
					empty0 <= '1';
				else
					empty0 <= '0';
				end if;
				
		end if; 
	end process;
end arc;

The simulation results are showing that, indeed, read and write operations seem not possible at the same time but I don't understand why...

@TrickyDicky:
I don't exactly understand the problem with rcycle and wcycle. It seemed to me that was necessary to have a circular FIFO. Maybe I'm wrong. Help me having a working component, please.

 

[TrickyDicky]

with a fifo like this, you should always be able to read and write in the same cycle. rcycle and wcycle are not required.

 

[Binome]

Sorry but I still don't understand.
wcycle and rcycle are tested to assert full0 and empty0 and you tell me they're not required. Why?
And you tell I can read and write in the same cycle, not before. Explain the difference. You didn't tell me why the precedent version was wrong.
I thought I could easily understand VHDL but it seems I'm not! Explain the differences in the language I don't see.

 

[TrickyDicky]

Your full and empty flags should be set to be a function of the read and write addresses, and the ren/wren flags.

eg.

if wren and (not rden) and wraddr = (rd_addr-1) then
  full <= '1';
end if;

I dont really know wht you're tryig to acheive with your read and wr cycle signals. You have clearly written a dual port ram that should be capable of reading and writing to the ram at the same time. I assume this is some personal project, because altera and xilinx already provide fifo IPs for free.

 

[ads-ee]

I assume this is some personal project, because altera and xilinx already provide fifo IPs for free.

Tricky, more likely a school assignment given to students that only know software and barely understand what a gate is.

Sorry but I still don't understand.
wcycle and rcycle are tested to assert full0 and empty0 and you tell me they're not required. Why?
And you tell I can read and write in the same cycle, not before. Explain the difference. You didn't tell me why the precedent version was wrong.
I thought I could easily understand VHDL but it seems I'm not! Explain the differences in the language I don't see.

Binome, You're problem isn't with the understanding VHDL it's with understanding the architecture of a FIFO. If you don't really understand how a FIFO has to function then you're going to end up writing a FIFO that doesn't work (like yours).

1. A FIFO needs to either use a dual port RAM, or if both read/write sides use the same clock it can be run at 2x the frequency and the RAM can be a single port RAM with a read and write access allowed on each 1x clock period.
2. The FIFO needs two pointers, a read pointer and a write pointer.
3. Writes to the FIFO increment the write pointer
4. Reads from the FIFO decrement the read pointer
5. Simultaneous reads/writes both decrement and increment the pointers respectively.
6. the pointers are compared to each other to generate the flags full and empty. This is done in a combinational circuit (No Flip-Flops!). More advanced methods will use the write/read strobes and saved pointers to generate registered full and empty flags (but this is more complex and more prone to having subtle errors).
7. Writes should not be allowed (to increment the write pointer) when the full flag is asserted. (overflow)
8. Reads should not be allowed (to decrement the read pointer) when the empty flag is asserted. (underflow)

You probably started coding this FIFO before you even sat down and drew a block diagram of a FIFO and determined what hardware you needed to implement it.

 

[Binome]

OK, I'll think about the functions.
rcycle and wcycle were meant to implement a cyclic fifo (aka ring buffer) but if it is so difficult to implement, I'll use altera's dual port fifo to do it.

 

[ads-ee]

It's not difficult to write a FIFO (that is all a ring buffer is). Your problem seems to be is you're thinking like a software programmer (a.k.a. using a ring buffer, reuse the free memory) instead of like a hardware engineer.

Here is a paper on writing FIFOs, don't be scared off by the asynchronous part. You can write synchronous single clock FIFOs using the same techniques or simplify the design, as needed, as you don't have to cross any clock domains.

 

[K-J]

OK, I'll think about the functions.
rcycle and wcycle were meant to implement a cyclic fifo (aka ring buffer) but if it is so difficult to implement, I'll use altera's dual port fifo to do it.

That's too bad, because it looks like you're probably pretty close. It appears to me if you just delete the signals wcycle and rcycle (and all places where they are used) from your code and do nothing else, that your fifo might actually work. So where you go to use it like this...
if (writeptr+1=readptr and wcycle/=rcycle) or (writeptr=fifo_length-1 and readptr=0 and wcycle=rcycle) then
Instead you do this...
if (writeptr+1=readptr ) or (writeptr=fifo_length-1 and readptr=0) then

wcycle and rcycle as you have them implemented have nothing to do with implementing a fifo or a ring buffer. All they do is tell you when the pointers are wrapping around, but that in itself is not important to the operation of the fifo.

But if the point of the assignment really is not to write your own fifo, then yes it is better to just use code that has been more thoroughly tested.

Kevin Jennings

 

[Binome]

@ads-ee
I don't see any paper in your post. Did you forget it or didn't I search in the right place?
It's too bad because I'd like to read about that.

@K-J
I've removed all references to wcycle and rcycle. My new code is:

library	ieee;
use		ieee.std_logic_1164.all;
use		ieee.numeric_std.all;

entity ring_fifo is
	generic(
		fifo_length	: integer:=8;
		data_width	: integer:=4);

	port(
		clk			: in std_logic;
		rst			: in std_logic;
		ren			: in std_logic;
		wen			: in std_logic;
		dataout		: out std_logic_vector(data_width-1 downto 0);
		datain		: in  std_logic_vector(data_width-1 downto 0);
		empty		: out std_logic;
		err			: out std_logic;
		full		: out std_logic);
	end ring_fifo;

architecture arc of ring_fifo is

	type memory_type is array (0 to fifo_length-1) of std_logic_vector(data_width-1 downto 0);

	signal memory	: memory_type := (others => (others => '0'));
	signal readptr,writeptr	: integer range 0 to fifo_length-1 := 1;
	signal full0	: std_logic := '0';
	signal empty0	: std_logic := '1';

begin
	full <= full0;
	empty <= empty0;

	err <= '1' when (empty0='1' and ren='1') or (full0='1' and wen='1')
				else '0';

	fifo0: process(clk,rst)
	begin
		if rst='1' then
			memory <= (others => (others => '0'));
			readptr <= 0;
			writeptr <= 0;
			full0 <= '0';
			empty0 <= '1';
		elsif rising_edge(clk) then
			if (wen='1' and full0='0') then
				memory(writeptr) <= datain ;
				if (writeptr=fifo_length-1) then
					writeptr <= 0;
				else
					writeptr <= writeptr+1;
				end if;
			end if;

			if (ren='1' and empty0='0') then
				dataout <= memory(readptr);
				if (readptr=fifo_length-1) then
					readptr <= 0;
				else
					readptr <= readptr+1;
				end if;
			end if ;
			
				if (writeptr+1=readptr) or (writeptr=fifo_length-1 and readptr=0) then
					full0 <= '1';
				else
					full0 <= '0';
				end if;
					
				if (readptr=writeptr) then
					empty0 <= '1';
				else
					empty0 <= '0';
				end if;
				
		end if; 
	end process;
end arc;

My problem is that I saw full and empty being asserted one cycle too late so I made them asserted concurrently and not after a register like that:

	full0<= '1' when (writeptr+1=readptr) or (writeptr=fifo_length-1 and readptr=0)
				else '0';
								
	empty0<='1'	when (readptr=writeptr) 
				else '0';

just after the "begin" but full is 'X' when writeptr=fifo_length-1 so I'm confused...

 

[FvM]

I don't see any paper in your post. Did you forget it or didn't I search in the right place?
It's too bad because I'd like to read about that.

Maybe your display is to dim to show links clearly. Just sweep over the post text to find the link. (Like in an advanture game...)

 

[TrickyDicky]

Ads-ee did put a link in his post
http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO1.pdf

Using your non-registered outputs, you actually lose one entry in the fifo. Write address is not the address of the last value to be written, it is the address of the next value to be written. To make it registered, you can make it also a function of wen and ren.

if wren and (not rden) and wraddr = (rd_addr-1) then
  full <= '1';
end if;

Here, a new value is being written without a value being taken, with the wr address about to catch up with read address, hence you know you are full on the next clock cycle.

Another quirk you may want to investigate - if you make the wraddr and rdaddr unsigned type instead of integer, there is never the need to check for special roll over cases, because FF + 1 = 00. You can also work out how full the fifo is by taking the different between the two pointers:

howfull <= wr_addr - rd_addr;

Here, this always works, as rd_addr always lags wr_addr. Ill give some examles.

Lets assume the addresses are 4 bits.

rdaddr = 0x5
wr_addr = 0x9
howfull = 0x9 - 0x5 = 0x4 (4 elements in the fifo)

eg 2.

rd_addr = 0xF
wr_addr = 0xB
howfull = 0xB - 0xF = 0xC (12)

The only thing you have to be careful of is when rdaddr = wraddr, and howfull would be 0, but by monitoring the rden and wren, it should be clear whether you are full or empty.