Contact me for VHDL projects or assignments

Thursday, January 13, 2011

Implementation of stack in VHDL

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:


library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity stack is
port(   Clk : in std_logic;  --Clock for the stack.
        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 (255 downto 0) of std_logic_vector(15 downto 0);
signal stack_mem : mem_type := (others => (others => '0'));
signal stack_ptr : integer := 255;
signal full,empty : std_logic := '0';

begin

Stack_Full <= full;
Stack_Empty <= empty;

--PUSH and POP process for the stack.
PUSH : process(Clk,PUSH_barPOP,Enable)
begin
    if(rising_edge(Clk)) then
        --PUSH section.
        if (Enable = '1' and PUSH_barPOP = '1' and full = '0') then
             --Data pushed to the current address.
            stack_mem(stack_ptr) <= Data_In;
            if(stack_ptr /= 0) then
                stack_ptr <= stack_ptr - 1;
            end if;
            --setting full and empty flags
            if(stack_ptr = 0) then
                full <= '1';
                empty <= '0';
            elsif(stack_ptr = 255) then
                full <= '0';
                empty <= '1';
            else
                full <= '0';
                empty <= '0';
            end if;
           
        end if;
        --POP section.
        if (Enable = '1' and PUSH_barPOP = '0' and empty = '0') then
        --Data has to be taken from the next highest address(empty descending type stack).
            if(stack_ptr /= 255) then  
                Data_Out <= stack_mem(stack_ptr+1);
                stack_ptr <= stack_ptr + 1;
            end if;
            --setting full and empty flags
            if(stack_ptr = 0) then
                full <= '1';
                empty <= '0';
            elsif(stack_ptr = 255) then
                full <= '0';
                empty <= '1';
            else
                full <= '0';
                empty <= '0';
            end if;
           
        end if;
       
    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,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,
          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       
      wait for clk_period*3; --wait for 3 clock periods(simply)
        Enable <= '1';  --Enable the stack.
        PUSH_barPOP <= '1'; --Set for push operation.
        for i in 0 to 255 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 255 loop  --POP all elements from stack one by one.
            wait for clk_period;
        end loop;  
        Enable <= '0'; --Disable stack.
       
        wait for clk_period*3;
        Enable <= '1'; --Enable stack
        PUSH_barPOP <= '1';  --Set for push operation.
        Data_In <= X"FFFF";  --Push 65535 to stack.
        wait for clk_period;
        Data_In <= X"7FFF";  --Push 32767 to stack.
        wait for clk_period;   
        PUSH_barPOP <= '0';  --POP the above pushed values.
        wait for clk_period*2;
        Enable <= '0';     

      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 12.1. 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 using a less 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 implement the other 3 types of stacks too in VHDL.

9 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

Related Posts with Thumbnails

Download this article as PDF