VHDL coding tips and tricks: Implementation of stack in VHDL

Thursday, January 13, 2011

Implementation of stack in VHDL

CODE UPDATED AFTER DEBUGGING ON 23rd Oct 2017!


I have been getting some requests for a Stack implementation in VHDL. This article is for all those readers.

A stack is simply a Last In First Out(LIFO) memory structure. Every stack has a stack pointer(SP) which acts as an address for accessing the elements. But normally the user of the stack is not concerned with the absolute address of the stack, he is only concerned with the PUSH and POP instructions. I am not going into theory of stack in detail, but for some basics check the wikipedia stack page.

There are basically 4 types of stacks:

  1. Empty descending - Stack pointer(SP) points to the address where you can push the latest data. And after pushing the data, stack pointer(SP) is reduced by one till it becomes zero. Stack grows downwards here.
  2. Empty ascending - Same as type (1) , but stack grows upwards here. After the PUSH operation, SP is incremented by one.
  3. Fully descending - SP points to the last data which is pushed.Stack grows downward.
  4. Fully ascending - SP points to the last data which is pushed, but stack grows upward here.
Out of the above 4 types I have implemented the first type, Empty descending in VHDL. The depth of the stack is 256 and width is 16 bits. That means using a single PUSH or POP operation you can only store or retrieve a maximum of 16 bits. Also the maximum number of elements which can be stored in the stack are 256. Of course, with a small edit you can change the width and depth of the stack. Check out the code below:

--Empty descending stack implementation in VHDL.
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity stack is
port(   Clk : in std_logic;  --Clock for the stack.
          Reset : in std_logic; --active high reset.    
        Enable : in std_logic;  --Enable the stack. Otherwise neither push nor pop will happen.
        Data_In : in std_logic_vector(15 downto 0);  --Data to be pushed to stack
        Data_Out : out std_logic_vector(15 downto 0);  --Data popped from the stack.
        PUSH_barPOP : in std_logic;  --active low for POP and active high for PUSH.
        Stack_Full : out std_logic;  --Goes high when the stack is full.
        Stack_Empty : out std_logic  --Goes high when the stack is empty.
        );
end stack;

architecture Behavioral of stack is

type mem_type is array (0 to 255) of std_logic_vector(15 downto 0);
signal stack_mem : mem_type := (others => (others => '0'));
signal full,empty : std_logic := '0';
signal prev_PP : std_logic := '0';
signal SP : integer := 0;  --for simulation and debugging. 

begin

Stack_Full <= full; 
Stack_Empty <= empty;

--PUSH and POP process for the stack.
PUSH : process(Clk,reset)
variable stack_ptr : integer := 255;
begin
     if(reset = '1') then
          stack_ptr := 255;  --stack grows downwards.
          full <= '0';
          empty <= '0';
          Data_out <= (others => '0');
          prev_PP <= '0';
    elsif(rising_edge(Clk)) then
     --value of PUSH_barPOP with one clock cycle delay.
          if(Enable = '1') then
                prev_PP <= PUSH_barPOP; 
          else
                prev_PP <= '0';
          end if;   
            --POP section.
        if (Enable = '1and PUSH_barPOP = '0and empty = '0') then
          --setting empty flag.           
                if(stack_ptr = 255) then
                     full <= '0';
                     empty <= '1';
                else
                     full <= '0';
                     empty <= '0';
                end if;
                --when the push becomes pop, before stack is full. 
                if(prev_PP = '1and full = '0') then
                    stack_ptr := stack_ptr + 1;
                end if; 
        --Data has to be taken from the next highest address(empty descending type stack).              
                Data_Out <= stack_mem(stack_ptr);
            if(stack_ptr /= 255) then   
                stack_ptr := stack_ptr + 1;
            end if;         
        end if;
      
          --PUSH section.
        if (Enable = '1and PUSH_barPOP = '1and full = '0') then
                --setting full flag.
                if(stack_ptr = 0) then
                     full <= '1';
                     empty <= '0';
                else
                     full <= '0';
                     empty <= '0';
                end if; 
                --when the pop becomes push, before stack is empty.
                if(prev_PP = '0and empty = '0') then
                    stack_ptr := stack_ptr - 1;
                end if;
                --Data pushed to the current address.       
                stack_mem(stack_ptr) <= Data_In; 
            if(stack_ptr /= 0) then
                stack_ptr := stack_ptr - 1;
            end if;     
        end if;
          SP <= stack_ptr;  --for debugging/simulation.
        
    end if; 
end process;

end Behavioral;

Let me explain little bit about the code. For using this stack entity in your project you need to apply a clock signal to the port Clk. For either PUSH or POP operation to happen, you have make the Enable signal high. Data can be pushed into the stack by applying the data at the Data_In port with '1' on the PUSH_barPOP port. Data can be popped from the stack by applying a '0' on the PUSH_barPOP port. The popped data will be available on the Data_Out port.
I have also included two status signals so that you can manage the stack better. Stack_Full goes high when the stack is full, and Stack_Empty goes high when there is no data available in the stack. The Enable signal should be controlled by checking these status signals so that stack overflow doesn't happen.

For testing the code I have written a testbench which I am sharing here:

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.std_logic_arith.ALL;

ENTITY stack_tb IS
END stack_tb;

ARCHITECTURE behavior OF stack_tb IS 
   --Inputs and outputs
   signal Clk,reset,Enable,PUSH_barPOP,Stack_Full,Stack_Empty : std_logic := '0';
   signal Data_In,Data_Out : std_logic_vector(15 downto 0) := (others => '0');
    --temporary signals
    signal i : integer := 0;
   -- Clock period definitions
   constant Clk_period : time := 10 ns;

BEGIN
    -- Instantiate the Unit Under Test (UUT)
   uut: entity work.stack PORT MAP (
          Clk => Clk,
             reset => reset,
          Enable => Enable,
          Data_In => Data_In,
          Data_Out => Data_Out,
          PUSH_barPOP => PUSH_barPOP,
          Stack_Full => Stack_Full,
          Stack_Empty => Stack_Empty
        );

   -- Clock process definitions
   Clk_process :process
   begin
        Clk <= '0';
        wait for Clk_period/2;
        Clk <= '1';
        wait for Clk_period/2;
   end process;

   -- Stimulus process
   stim_proc: process
   begin        
        reset <= '1';  --apply reset for one clock cycle.
        wait for clk_period;
        reset <= '0';
      wait for clk_period*3; --wait for 3 clock periods(simply)
         Enable <= '1'; --Enable stack
        wait for clk_period*3;  --wait for 3 clock periods(simply)
        PUSH_barPOP <= '1';  --Set for push operation.
        Data_In <= X"FFFF";  --Push something to stack.
        wait for clk_period;
        Data_In <= X"7FFF";  --Push something to stack.
        wait for clk_period;
          Data_In <= X"2FFF";  --Push something to stack.
        wait for clk_period;    
        PUSH_barPOP <= '0';  --POP two of the above pushed values.
        wait for clk_period*2;
          PUSH_barPOP <= '1';  --Set for push operation.
        Data_In <= X"1234";  --Push something to stack.
        wait for clk_period;
        Data_In <= X"5678";  --Push something to stack.
        wait for clk_period;    
        PUSH_barPOP <= '0';  --POP all the above pushed values.
          wait for clk_period*10;   --wait for some time.
          PUSH_barPOP <= '1';  --Set for push operation.
        Data_In <= X"0020";  --Push something to stack.
        wait for clk_period;
          PUSH_barPOP <= '0';  --pop what was pushed.
          wait for clk_period*10;
           Enable <= '0';   --disable stack.
            
            wait for clk_period*10; --wait for some time.
        Enable <= '1';  --Enable the stack.
        PUSH_barPOP <= '1'; --Set for push operation.
        for i in 0 to 257 loop  --Push integers from 0 to 255 to the stack.
            Data_In <= conv_std_logic_vector(i,16);
            wait for clk_period;
        end loop;   
        Enable <= '0';  --disable the stack.
        wait for clk_period*2;
        Enable <= '1'; --re-enable the stack.
        PUSH_barPOP <= '0';  --Set for POP operation.
        for i in 0 to 257 loop  --POP all elements from stack one by one.
            wait for clk_period;
        end loop;   
        Enable <= '0'; --Disable stack.

      wait;
   end process;

END;

I am not including a waveform file because it is too lengthy to put up as a single image. The above codes where tested succussfully using the Xilinx Webpack 14.6. The code is also synthesisable.

Just as a side note, I got a More than 100% resources used error when I tried to synthesis the code for spartan 3. But for spartan 6 devices, there is no such error. So always check whether your device can handle this design. Usage of resources can also be decreased, by specifying a smaller width and depth for the stack.

If you need variations of this stack design contact me. I help students to get their coding work done for a fee. Also I suggest, for learning purposes, you try to implement the other 3 types of stacks by yourself.

12 comments:

  1. The sensitivity list is wrong - process(Clk,PUSH_barPOP,Enable) should only have Clk in it.

    ReplyDelete
  2. @foam : The sensitivity list need not contain PUSH_barPOP and Enable signal names. But at the same time there is nothing wrong in it also. Removing those signal names from the sensitivity list doesnt change the logic or simplify it.
    But since the whole logic is synchronous with the clk, other signals are not required inside the sensitivity list.

    ReplyDelete
  3. Hi,

    your stack code is complete, it does not take into account the condition when the stack is full and you do a pop, in this circumstance you not pre-increment the stack point.

    ReplyDelete
  4. @Herbert : can you explain what do you mean.Do you mean there is a bug in the code or it is complete?

    ReplyDelete
  5. sir i need the vhdl codes of remaing stack.. please kindly mail to my i.d..sir as my project submission is so nearer sir... am doing project on this only..ple send the codes of fully ascending and fully descending..

    ReplyDelete
  6. hey..plz recheck this code this code is not properly working..n for the next dont misguide the studunts with these types of error..

    ReplyDelete
  7. the code is buggy.. the stack does not work for one push and one pop.

    ReplyDelete
  8. Default values for signals are not synthesizable. You need to use a reset.

    ReplyDelete
  9. @Alex, Stick, I need to use this stack. can you please point out the bugs and provide a bug free implementation

    ReplyDelete
  10. @Alex, Stick can you please point out specifically the bugs. and it will be nice if you can provide bug free implementation

    ReplyDelete
  11. Hello, who can help me?
    I have a problem with this code.
    Insufficient number of macrocells. The design needs at least 4146 but only 36. how I can solve this problem?

    ReplyDelete