Chapter 22

Finite State Machines in VHDL and Verilog

Abstract

Finite State Machines (FSMs) are at the heart of most digital design. The basic idea of an FSM is to store a sequence of different unique states and transition between them depending on the values of the inputs and the current state of the machine. The FSM can be of two types Moore (where the output of the state machine is purely dependent on the state variables) and Mealy (where the output can depend on the current state variable values AND the input values).

Keywords

Finite state machines

Mealy

Moore

22.1 Introduction

Finite State Machines (FSMs) are at the heart of most digital design. The basic idea of an FSM is to store a sequence of different unique states and transition between them depending on the values of the inputs and the current state of the machine. The FSM can be of two types: Moore (where the output of the state machine is purely dependent on the state variables) and Mealy (where the output can depend on the current state variable values AND the input values).1 The general structure of an FSM is shown in Figure 22.1:

f22-01-9780080971292
Figure 22.1 Hardware state machine structure.

22.2 State Transition Diagrams

One method of describing Finite State Machines from a design point of view is using a state transition diagram (bubble chart) which shows the states, outputs and transition conditions.2 A simple state transition diagram is shown in Figure 22.2.

f22-02-9780080971292
Figure 22.2 State transition diagram.

Interpreting this state transition diagram, it is clear that there are four bubbles (states). The transitions are controlled by two signals (rst and choice), both of which could be represented by bit or std_logic types (or another similar logic type). There is an implicit clock signal, which we shall call clk and the single output out1.

22.3 Implementing Finite State Machines in VHDL

This transition diagram can be implemented 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 ;

It must be noted that not all state machines will neatly have a number of states exactly falling to a power of 2, and so unused states must also be managed using the “when-others” approach described elsewhere in this book.

It is also the case that the two processes can be combined into a single process, which can reduce the risk of glitches being introduced by the synthesis tools, especially from incorrect assignments. It can also make debugging simpler.

22.4 Implementing Finite State Machines in Verilog

The transition diagram can also be implemented in Verilog, again using two case statements (one for the state transitions and one for the outputs):

module   fsm   (

 count ,   // Output Value

 clk, // Clock

 rst, // Reset

 choice // Decision /Choice Value

 );

output [1:0] count;

input clk;

input rst;

input choice;

reg [1:0] count;

reg [1:0] state; // state variable

parameter s0=0, s1=1, s2=2, s3=3;

always @(state)

 begin

 case (state)

 s0:

 count = 2’b00;

 s1:

 count = 2’b01;

 s2:

 count = 2’b10;

 s3:

 count = 2’b11;

 default:

 count = 2’b00;

 endcase

end

always @(posedge clk or posedge rst)

begin

 if (rst == 0)

 state = s0;

 else

 case (state)

 s0:

 state = s1;

 s1:

 if (choice)

 state = s3;

 else

 state = s2;

 s2:

 state = s0;

 s3:

 state = s0;

 endcase

end

endmodule

22.5 Testing the Finite State Machine Model

Whether the VHDL or Verilog is being used, a test bench is required to evaluate the behavior and check that it is correct. In this example, Verilog has been used, but the principle is the same for both HDLs. The idea is to reset the FSM, then clock through the sequence with choice = 0 (which will go from state S0 to S1 and then S2, returning to S0), and then the choice is set to 1, and this time the sequence will go from state S0 to S1 and then S3, returning to S0. The output variable (counter_output) shows the state number as an output. The simulation is shown in Figure 22.3.

f22-03-9780080971292
Figure 22.3 FSM simulation results.

22.6 Summary

Finite State Machines are a fundamental technique for designing control algorithms in digital hardware. This chapter of this book is purely an introduction to the key concepts and if the reader is not already fully familiar with the basic concepts of digital hardware design, you are encouraged to obtain a standard text on digital design techniques to complement the practical implementation methods described in this book.

1 Although in fact it is also possible to have a hybrid of the two approaches.

2 Another method is the algorithmic state machine approach, which shows actions and decisions separately, so is closer in some regards to a flow chart.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.22.248.208