FINITE STATE MACHINES (FSM)
This document describes how to write a finite state machine (FSM) in Verilog. FSM is a behavioral model used to design a computer programs. It will have finite number of states associated with transitions. Functionality of the digital circuit can also be represented with the help of a finite state machine. There are different ways to construct FSM. Today in this lab we will learn to build FSM using flip flops. FSM consists of combinational, sequential and output logic. Combinational logic is used to decide the next state of the FSM, sequential logic is used to store the current state of the FSM. The output logic is a mixture of both combinational and sequential logic as shown in the figure below.
M ealy M achine O nly C om binational Logic S equential Logic C ircuit C om binational Logic
N ext S tate Logic
N ext P resent S tate FF’s
S tate O utput Logic
outputs
C LK
More specifically, a hardware implementation requires a register to store state variables, a block of combinational logic which determines the state transition, and a second block of combinational logic that determines the output of an FSM.
A common classification used to describe the type of an FSM is Mealy and Moore state machines.
• •
Mealy State Machine: Its output depends on current state and current inputs. In the above picture, the dotted line makes the circuit a mealy state machine. Moore State Machine: Its output depends on current state only. In the above picture, when dotted line is removed the circuit becomes a Moore state machine.
Depending on the need, we can choose the type of state machine. In general, we end up using Mealy FSM. The tradeoff in using the Moore machine is that sometimes the Moore machine will require more states to specify its function than the Mealy machine. The Mealy machine allows you to specify different output behavior for a single state.
FSM IN VERILOG
By looking at Figure, we will express the following in Verilog: 1. A state encoding for each state. 2. A mechanism for keeping track of the current state. 3. Transitions from state to state. 4. Output values based on the current state. We will construct the moore machine first. Example: Consider a circuit to detect a pair of 1's or 0's in the single bit input. That is, input will be a series of one's and zero's. If two one's or two zero's comes one after another, output should go high. Otherwise output should be low. Here is a Moore type state transition diagram for the circuit.
Since we have only 4 states, let us take two bit to represent the states S0=00, S1=01,S2=10, and S3=11. When reset, state goes to S0; If input is 1, state will be S1 and if input is 0, state goes to S2. State will be 11 if input repeats. After state 11, goes to 10 state or 01 depending on the inp, since overlapping pair should not be considered. That is, if 111 comes, it should consider only one pair
Step 1: A state encoding for each state. State encoding is done using verilog parameters. Parameter are symbolic constants with global or module scope. State encoding is shown in line number 7 in the example program. Step2: A mechanism for keeping track of the current state.
Create a reg element of the appropriate width and use its value as our current state. As shown in line 4 and 5.
Step3: Transitions from state to state. To make transition form one state to another state, you can use always and case statements (or ifelse statements) of verilog. As shown from line 8 to 24.
Step4: The final step in specifying a Moore FSM is assigning output values based on Current State. Fortunately, this is simple with assign statements. As shown from the line 34 to 41.
1. module fsm( clock, reset, inp, Oput); 2. input clock, reset, inp; 3. output Oput; 4. reg [1:0] state; 5. reg[1:0] nextstate; 6. reg Oput; 7. parameter S0=2'b00,S1=2'b01,S2=2'b10,S3=2'b11;//State Definition 8. always @( state ) 9. begin 10. case( state ) 11. S0: 12. begin if( inp ) nextstate 