Designing a
synchronous finite state machine (FSM) is a common task for a digital logic
engineer. A finite state machine can be divided in to two types: Moore and
Mealy state machines. Fig. 1 has the general structure for Moore and Fig. 2
has general structure for Mealy. The current state of the machine is stored
in the state memory, a set of n flip-flops clocked by a single clock signal
(hence �synchronous� state machine). The state vector (also current state,
or just state) is the value currently stored by the state memory. The next
state of the machine is a function of the state vector in Moore; function of
state vector and the inputs in Mealy.
Fig. 1: Moore State Machine
Fig. 2: Mealy State Machine
Verilog
Coding
The logic in a state machine is described using a case
statement or the equivalent (e.g., if-else). All possible combinations of
current state and inputs are enumerated, and the appropriate values are
specified for next state and the outputs. A state machine may be coded as in
Code 1 using two separate case statements, or, as in code 2, using only one.
A single case statement may be preferred for Mealy machines where the
outputs depend on the state transition rather than just the current state.
Consider the
case of 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. When reset, state goes to 00;
If input is 1, state will be 01 and if input is 0, state goes to 10. 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.
Following code the Verilog
implementation of the state machine. Note that we updated outp and state in
separate always blocks, it will be easy to design. inp is serial input, outp
is serial output, clk is clock and rst is asynchronous reset. I have used
nonblocking statements for assignments because we use previous state to
decide the next state, so state should be registered.
module fsm( clk, rst, inp, outp);
input clk, rst, inp;
output outp;
reg [1:0] state;
reg outp;
always @( posedge clk, posedge rst )
begin
if( rst )
state <= 2'b00;
else
begin
case( state )
2'b00:
begin
if( inp ) state <= 2'b01;
else state <= 2'b10;
end
2'b01:
begin
if( inp ) state <= 2'b11;
else state <= 2'b10;
end
2'b10:
begin
if( inp ) state <= 2'b01;
else state <= 2'b11;
end
2'b11:
begin
if( inp ) state <= 2'b01;
else state <= 2'b10;
end
endcase
end
end
always @(posedge clk, posedge rst)
begin
if( rst )
outp <= 0;
else if( state == 2'b11 )
outp <= 1;
else outp <= 0;
end
endmodule
|
Here is a testbench that can be used
to test all these examples. This testbench generates both directed and
random test values. We can specify the sequence in the first part.
module fsm_test;
reg clk, rst, inp;
wire outp;
reg[15:0] sequence;
integer i;
fsm dut( clk, rst, inp, outp);
initial
begin
clk = 0;
rst = 1;
sequence = 16'b0101_0111_0111_0010;
#5 rst = 0;
for( i = 0; i <= 15; i = i + 1)
begin | |