Guide to VHDL for embedded software developers: Part 3 - ALU logic & FSMs - Embedded.com

Guide to VHDL for embedded software developers: Part 3 – ALU logic & FSMs

Editor’s Note: Inthis series of articles based on his book – DesignRecipes for FPGAs – Peter Wilson provides a basic quick overview of VHDL(VHSIC hardware description language) followed by examples of its use indescribing – in HDL code form – functions familiar to most embedded softwaredevelopers such as arithmetic logic units (ALUs) and finite state machines(FSMs). It is not intended as a comprehensive VHDL reference. For that, herecommends “Digital System Design with VHDL,” by Mark Zwolinski; ”VHDL: Analysis and modeling of digital systems,” byZainalabedin Navabi or “Designer’s Guide to VHDL” by Peter Ashenden.

This third part in a series describes how low-level logic and arithmeticfunctions can be implemented in VHDL to build simple arithmetic logic unitsand finite state machines.

A central part of microprocessors is the ALU (Arithmetic Logic Unit) .This block in a processor takes a number of inputs from registers and as itsname suggests carries out either logic functions (such as NOT, AND, ORand XOR ) on the inputs,or arithmetic functions (addition or subtractionas a minimum ).

Logic functions
If we consider a simple inverter in VHDL, this takes a single input bit,inverts it and applies this to the output bit. This simple VHDL code sequenceis shown below:

Library ieee;
Use ieee.std_logic_1164.all;
Entity inverter is
     Port (
          A : in std_logic;
          Q : out std_logic
     );
End entity inverter;
Architecture simple of inverter is
Begin
     Q <= NOT A;
End architecture simple;

Clearly the inputs and output are defined as single std_logic pins, withdirection in and out respectively. The logic equation is also intuitive andstraightforward to implement. We can extend this be applicable to n bit logicbusses by changing the entity (the architecture remains the same ) andsimply assigning the input and outputs the type std_logic_vector instead ofstd_logic as follows:

Library ieee; Use ieee.std_logic_1164.all;
Entity bus_inverter is
    Port (
         A : in std_logic_vector(15 downto 0);
         Q : out std_logic_vector(15 downto 0)
    );
End entity bus_inverter;
Architecture simple of bus_inverter is
Begin
    Q <= NOT A;
End architecture simple;

As can be seen from the VHDL, we have defined a specific 16 bit bus inthis example, and while this is generally fine for processor design with afixed architecture, sometimes it is useful to have a more general case, witha configurable bus width. In this case we can modify the entity again tomake the bus width a parameter of the model:

Library ieee;
Use ieee.std_logic_1164.all;
Entity n_inverter is
     Generic (
          N : natural := 16
     );
     Port (
          A : in std_logic_vector((n-1) downto0);
          Q : out std_logic_vector((n-1) downto0)
     );
End entity n_inverter;
Architecture simple of n_inverter is
Begin
     Q <= NOT A;
End architecture simple;

We can of course create separate models of this for m to implement multiplelogic functions, but we can also create a compact multiple function logicblock by using a set of configuration pins to define which function is required.

Table 3

If we define a general logic block that has 2 n-bit inputs (A & B),a control bus (S) and an n-bit output (Q), then by setting the 2 bit controlword (S) we can select an appropriate logic function according to the Table3 above.

Clearly we could define more functions, and this would require more bitsfor the select function (S), but this limited set of functions demonstratesthe principle involved. We can define a modified entity as shown below:

Library ieee;
Use ieee.std_logic_1164.all;
Entity alu_logic is
    Generic (
          N : natural:= 16
    );
    Port (
         A : in std_logic_vector((n-1) downto 0);
         B : in std_logic_vector((n-1) downto 0);
         S : in std_logic_vector(1 downto 0);
         Q : out std_logic_vector((n-1) downto0)
    );
End entity alu_logic;

Now, depending on the value of the input word (S), the appropriate logicfunction can be selected. We can use the case statement introduced in theVHDL primer chapter of this book to define each state of S and which functionwill be carried out in a very compact form of VHDL:

Architecture basic of alu_logic is
Begin
    Case S is
        When “00” => Q <= NOT A;
        When “01” => Q <= A AND B;
        When “10” => Q <= A OR B;
        When “11” => Q <= A XOR B;
    End case;
End architecture basic;

Clearly this is an efficient and compact method of defining the combinatoriallogic for each state of the control word (S), but great care must be takento assign values for every combination to avoid inadvertent latches beingintroduced into the logic when synthesised.

1-bit adder
The arithmetic ‘hear t’ of an ALU is the addition function – the Adder.This starts form a simple 1 bit adder and is then extended to multiple bits,to whatever sized of addition function is required in the ALU. The basic designof a 1-bit adder is to take two logic inputs (a & b) and produce a sumand carry output according to the truth table in Table 4 below:


Table 4

This can be implemented using simple logic with a 2 input AND gate forthe carry, and a 2 input XOR gate for the sum function as shown in Figure1 below .

Figure 1. Simple 1 bit adder
This function has a carry-out (carry), but no carry-in, so to extend thisto multiple bit addition, we need to implement a carryin function (cin) anda carry-out (cout) as shown in Table 5 below and with an equivalentlogic function as shown in Figure 2 below .

Figure 2. A 1-Bit Adder with Carry-in and Carry-out


Table 5
As shown above, this can be implemented using standard VHDL logic functionswith bit inputs and outputs as follows.

First define the entity with the input and output por ts defined usingbit types:

entity full_adder is
port (sum, co : out bit;
a, b, ci : in bit);
end entity full_adder;

Then the architecture can use the standard built-in logic functions ina ‘dataflow’ type of model, where logic equations are used to define the behaviour,without any delays implemented in the model.

architecture dataflow of full_adder is
begin
   sum <= a xor b xor ci;
   co <= (a and b) or
         (a and ci) or
         (b and ci);
end architecture dataflow;

This model is now a simple building block that we can use to create multiplebit adders structurally by linking a number of these models together.

Structural n-bit addition
Using the simple 1-bit full adder defined previously, it is a simple matterto create a multiple bit full adder using this model as a building block.As an example, to create a 4 bit adder, with a single carry-in and singlebit carry-out, we can define a VHDL model as shown below:

entity four_bit_adder is
   port (sum: out bit_vector (3 downto 0); co : out bit;
        a, b : in bit_vector (3 downto 0); ci : in bit);
end entity four_bit_adder;

architecture simple of four_bit_adder is
   signal carry : bit_vector (3 downto 1);
begin
   fa0 : entity work.full_adder
       port map (sum(0),carry(1),a(0),b(0),ci);
   fa1 : entity work.full_adder
       port map (sum(1),carry(2),a(1),b(1),carry(1));
   fa2 : entity work.full_adder
       port map (sum(2),carry(3),a(2),b(2),carry(2));
   fa3 : entity work.full_adder
       port map (sum(3),co,a(3),b(3),carry(3));
end architecture simple;

This can obviously be extended to multiple bits by repeating the componentuse in the architecture for as many bits are required.

Configurable n-bit addition
While the structural approach is useful, it is clearly cumbersome and difficultto configure easily. A more sensible approach is to add a generic (parameter)to the model to enable the number of bits to be customised. For example, ifwe define an entity to add two logic vectors (as opposed to bit vectors usedpreviously), the entity will look something like this:

library IEEE;
use IEEE.std_logic_1164.all;

entity add_beh is
  generic(top : natural := 15);
    port (a :in_std_logic_vector (top downto 0);
          b : in std_logic_vector (top downto0);
          cin : in std_logic;
          sum : out std_logic_vector (top downto0);
          cout : out std_logic);
end entity add_beh;

As can be seen from this entity, we have a new parameter, top, which definesthe size of the input vectors (a and b) and the output sum (cout). We canthen use the same original logic equations that we defined for the initial1-bit adder and use more behavioural VHDL to create a much more readable model:

architecture behavior of add_beh is
begin
  adder: process(a,b,cin)
           variable carry : std_logic;
           variable tempsum : std_logic_vector(top
           downto 0);
         begin
           carry := cin;
           for i in 0 to top loop
               tempsum(i) := a(i)xor b(i) xor carry;
               carry := (a(i) andb(i))
                       or (a(i) and carry)
                       or (b(i) and carry);
         end loop;
      sum <= tempsum;
      cout <= carry;
   end process adder;
end architecture behavior;

This architecture shows how a single process (with sensitivity list a,b, cin) is used to encapsulate the addition. The process is activated whena, b or cin changes.

A for loop is used to calculated a temporary sum (tempsum) that incrementseach time around the loop if required and the final value is assigned to theoutput sum. Also, a stage by stage carry is calculated and used each timearound the loop. After the final loop, the value of carry is used to becomethe final carry-out.

Twos complement
An integral part of subtraction in logic systems is the use of ‘twos complement’.This enables us to execute a subtraction function using only an adder ratherthan requiring a separate subtraction function. Twos complement is an extensionto the basic ones complement (or basic inversion of bits) previously considered.

If we consider an ‘unsigned’ number system based on 4 bits, then the rangeof the numbers is 0–15 (0000–1111). If we consider a ‘signed’ system, however,the Most Significant Bit (MSB) is considered to be the sign ( or ) of thenumber system and therefore the range of numbers with 4 bits will insteadbe from 8 to 7. The method of conversion from positive to negative numberin binary logic is a simple two stage process of first inverting all thebits and then adding 1 to the result.

Consider an example. Take a number 00112. In signed number form, the MSBis 0, so the number is positive and the lower three bits 011 can be directlytranslated into decimal 3. To get the twos complement (3), we first invertall the bits to get 1100, and then add a single bit to get the final twoscomplement value 1101.

To check that this is indeed the inverse in binary, simply add the number0011 to its twos complement 1101 and the result should be 0000. This functioncan be implemented simply in VHDL using the following model:

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

entity twoscomplement is
   generic (
        n : integer := 8
   );
   port (

                input : in std_logic_vector((n-1)downto 0);
                output : out std_logic_vector((n-1)downto 0)

);
end;

architecture simple of twoscomplement is
begin
   process(input)
       variable inv : unsigned((n-1) downto 0);
   begin
       inv := unsigned(NOT input);
       inv := inv + 1;
       output <= std_logic_vector(inv);
   end process;
end;

As can be seen from the VHDL, we operate using logic functions first (NOT)and then convert to unsigned to utilise the addition function (inv 1), andfinally convert the result back into a std_logic_vector type. Also noticethat the generic n allows this model to be configured for any data size.

In this example, the test bench is used to check that the function isoperating correctly by using two test circuits back to back, inverting andre-inverting the input word and checking that the function returns the samevalue.

While this does not guarantee correct operation (the same bug couldbe present in both transfor ms! ), it is a simple quick check that is veryuseful and makes generation of test data and checks very easy as the inputand final output signal check can be XORd to check for differences:

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

entity twoscomplementtest is
end twoscomplementtest ;

architecture stimulus of twoscomplementtest is
    signal rst : std_logic := ‘0’;
    signal clk : std_logic:= ‘0’;
    signal count : std_logic_vector (7 downto 0);
    signal inverse : std_logic_vector (7 downto 0);
    signal check : std_logic_vector (7 downto 0);
    component twoscomplement
         port(
              input : in std_logic_vector(7downto 0);
              output : out std_logic_vector(7downto 0)
         );
    end component;
    for all : twoscomplement use entity
      work.twoscomplement ;
begin
   CUT1: twoscomplement port map(input => count,
     output => inverse);
   CUT2: twoscomplement port map(input => inverse,
     output => check);

   -- clock and reset process
   clk <= not clk after 1 us;
   process
   begin
     rst <= ‘0’,’1’ after 2.5 us;
     wait;
   end process;

   -- generate data
   process(clk, rst)
     variable tempcount : unsigned(7 downto 0);
begin
  if rst = ‘0’ then
   tempcount := (others => ‘0’);
  elsif rising_edge(clk) then
     tempcount := tempcount + 1;
  end if;
  count <= std_logic_vector(tempcount);
  end process;
end;

Whether the designer needs to implement a complete ALU from scratch, orif it is purely to understand the behavior of an existing architecture, thesefunctions are very useful in analyzing the behavior of ALUs and processors.

Finite State Machines in VHDL
Finite State Machines (FSM) are at the heart of most digital designs. Thebasic idea of a FSM is to store a sequence of different unique states andtransition between them depending on the values of the inputs and the currentstate of the machine.

The FSM can be of two types Moore (where the output of the state machineis purely dependent on the state variables) and Mealy (where the output candepend on the current state variable values AND the input values). The generalstructure of an FSM is shown in Figure 3 below.


Figure 3. Hardware State Machine Structure

State transition diagrams. The method of describing FSM from a design pointof view is using a state transition diagram (bubble chart) which shows thestates, outputs and transition conditions. A simple state transition diagramis shown in Figure 4 below.

Figure 4. State Transition Diagram
Interpreting this state transition diagram it is clear that there are fourbubbles (states). The transitions are controlled by two signals (‘rst’ and‘choice’), both of which could be represented by bit or std_logic types (oranother similar logic type). There is an implicit clock signal, which we shallcall ‘clk’ and the single output ‘out1’.

Implementing FSMs in VHDL. This transition diagram can beimplemented using a case statement in a process using the following VHDL:

library ieee;
use ieee.std_logic_1164.all;
 

entity fsm is
  port(
      clk, rst, choice : in std_logic;
      count : out std_logic
  );
end entity fsm;
architecture simple of fsm1 is
  type state_type is ( s0, s1, s2, s3 );
  signal current, next_state : state_type;

begin
  process ( clk )
  begin
      if ( clk = ‘1’ ) then
          current <= next_state;
      end if;
  end process;
process (current)

begin
    case current is
      when s0 =>
            out <= 0;
            if (rst = ‘1’) then
                  next <=s1;

            else
                 next <= s0;
            end if;
      when s1 =>
            out <= 1;
            if (choice = ‘1’) then
                 next <= s3;
            else
                 next <= s2;
            end if;
      when s2 =>
           out <= 2;
           next <= s0;
      when s3 =>
           out <= 3;
           next <= s0;
    end case;
  end process;
end;

The use of FSMs are a fundamental technique for designing control algorithmsin digital hardware. This last part in this series is purely an introductionto the key concepts and if the reader is not already fully familiar with thebasic concepts of digital hardware design, you are encouraged to obtain astandard text on digital design techniques to complement the practical implementationmethods described here.

To read Part 1 , go to “Essential VHDL commands .”
To read Part 2 , go to “More essential commands.”
To read more by Wilson , go to “A simple VGA interface .”

Used with permission from Newnes, a division of Elsevier.Copyright 2007, from “Design Recipies for FPGAs,” by Peter Wilson. For moreinformation about this title and other similar books, please visit www.elsevierdirect.com.

Dr. Peter Wilson has worked for many years as a seniordesign engineer in the electronics industry with Ferranti plc and as an EDAtechnical specialist with Analogy Inc. before joining the Department ofElectronics and Computer Science at the University of Southampton, U.K., wherehe is senior lecturer in Electronics. He is also a consultant in various aspectsof embedded systems design, including design and modeling with VHDL, Verilog,Verilog-AMS and VHDL-AMS.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.