7. Finite state machine

7.1. Introduction

In previous chapters, we saw various examples of the combinational circuits and sequential circuits. In combinational circuits, the output depends on the current values of inputs only; whereas in sequential circuits, the output depends on the current values of the inputs along with the previously stored information. In the other words, storage elements, e.g. flip flogs or registers, are required for sequential circuits.

The information stored in the these elements can be seen as the states of the system. If a system transits between finite number of such internal states, then finite state machines (FSM) can be used to design the system. In this chapter, various finite state machines along with the examples are discussed. Further, please see the SystemVerilog-designs in Chapter 10, which provides the better ways for creating the FSM designs as compared to Verilog.

7.2. Comparison: Mealy and Moore designs

section{}label{} FMS design is known as Moore design if the output of the system depends only on the states (see Fig. 7.1); whereas it is known as Mealy design if the output depends on the states and external inputs (see Fig. 7.2). Further, a system may contain both types of designs simultaneously.

Note

Following are the differences in Mealy and Moore design,

  • In Moore machine, the outputs depend on states only, therefore it is ‘synchronous machine’ and the output is available after 1 clock cycle as shown in Fig. 7.3. Whereas, in Mealy machine output depends on states along with external inputs; and the output is available as soon as the input is changed therefore it is ‘asynchronous machine’ (See Fig. 7.16 for more details).
  • Mealy machine requires fewer number of states as compared to Moore machine as shown in Section 7.3.1.
  • Moore machine should be preferred for the designs, where glitches (see Section 7.4) are not the problem in the systems.
  • Mealy machines are good for synchronous systems which requires ‘delay-free and glitch-free’ system (See example in Section Section 7.7.1), but careful design is required for asynchronous systems. Therefore, Mealy machine can be complex as compare to Moore machine.

7.3. Example: Rising edge detector

Rising edge detector generates a tick for the duration of one clock cycle, whenever input signal changes from 0 to 1. In this section, state diagrams of rising edge detector for Mealy and Moore designs are shown. Then rising edge detector is implemented using Verilog code. Also, outputs of these two designs are compared.

7.3.1. State diagrams: Mealy and Moore design

Fig. 7.2 and Fig. 7.1 are the state diagrams for Mealy and Moore designs respectively. In Fig. 7.2, the output of the system is set to 1, whenever the system is in the state ‘zero’ and value of the input signal ‘level’ is 1; i.e. output depends on both the state and the input. Whereas in Fig. 7.1, the output is set to 1 whenever the system is in the state ‘edge’ i.e. output depends only on the state of the system.

../_images/MooreEdgeDetector.jpg

Fig. 7.1 State diagrams for Edge detector : Moore Design

../_images/MealyEdgeDetector.jpg

Fig. 7.2 State diagrams for Edge detector : Mealy Design

7.3.2. Implementation

Both Mealy and Moore designs are implemented in Listing 7.1. The listing can be seen as two parts i.e. Mealy design (Lines 37-55) and Moore design (Lines 57-80). Please read the comments for complete understanding of the code. The simulation waveforms i.e. Fig. 7.3 are discussed in next section.

Listing 7.1 Edge detector: Mealy and Moore designs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// edgeDetector.v
// Moore and Mealy Implementation

module edgeDetector
(
    input wire clk, reset, 
    input wire level, 
    output reg Mealy_tick, Moore_tick
);

localparam  // 2 states are required for Mealy
    zeroMealy = 1'b0,
    oneMealy =  1'b1;
    
localparam [1:0] // 3 states are required for Moore
    zeroMoore = 2'b00,
    edgeMoore = 2'b01, 
    oneMoore = 2'b10;

reg stateMealy_reg, stateMealy_next; 
reg[1:0] stateMoore_reg, stateMoore_next;

always @(posedge clk, posedge reset)
begin
    if(reset) // go to state zero if rese
        begin
        stateMealy_reg <= zeroMealy;
        stateMoore_reg <= zeroMoore;
        end
    else // otherwise update the states
        begin
        stateMealy_reg <= stateMealy_next;
        stateMoore_reg <= stateMoore_next;
        end
end

// Mealy Design 
always @(stateMealy_reg, level)
begin
    // store current state as next
    stateMealy_next = stateMealy_reg; // required: when no case statement is satisfied
    
    Mealy_tick = 1'b0; // set tick to zero (so that 'tick = 1' is available for 1 cycle only)
    case(stateMealy_reg)
        zeroMealy: // set 'tick = 1' if state = zero and level = '1'
            if(level)  
                begin // if level is 1, then go to state one,
                    stateMealy_next = oneMealy; // otherwise remain in same state.
                    Mealy_tick = 1'b1;
                end
        oneMealy: 
            if(~level) // if level is 0, then go to zero state,
                stateMealy_next = zeroMealy; // otherwise remain in one state.
    endcase
end

// Moore Design 
always @(stateMoore_reg, level)
begin
    // store current state as next
    stateMoore_next = stateMoore_reg; // required: when no case statement is satisfied
    
    Moore_tick = 1'b0; // set tick to zero (so that 'tick = 1' is available for 1 cycle only)
    case(stateMoore_reg)
        zeroMoore: // if state is zero,
            if(level) // and level is 1
                stateMoore_next = edgeMoore; // then go to state edge.
        edgeMoore:
            begin
                Moore_tick = 1'b1; // set the tick to 1.
                if(level) // if level is 1, 
                    stateMoore_next = oneMoore; // go to state one,
                else    
                    stateMoore_next = zeroMoore; // else go to state zero.
            end
        oneMoore: 
            if(~level) // if level is 0,
                stateMoore_next = zeroMoore; // then go to state zero.      
    endcase
end
endmodule

7.3.3. Outputs comparison

In Fig. 7.3, it can be seen that output-tick of Mealy detector is generated as soon as the ‘level’ goes to 1, whereas Moore design generate the tick after 1 clock cycle. These two ticks are shown with the help of the two red cursors in the figure. Since, output of Mealy design is immediately available therefore it is preferred for synchronous designs.

../_images/edgeDetectorWave.jpg

Fig. 7.3 Simulation waveforms of rising edge detector in Listing 7.1

7.3.4. Visual verification

Listing 7.2 can be used to verify the results on the FPGA board. Here, clock with 1 Hz frequency is used in line 19, which is defined in Listing 6.5. After loading the design on FPGA board, we can observe on LEDs that the output of Moore design displayed after Mealy design, with a delay of 1 second.

Listing 7.2 Visual verification of edge detector
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// edgeDetector_VisualTest.v

module edgeDetector_VisualTest
(
    input wire CLOCK_50, reset, 
    input wire[1:0] SW,
    output wire[1:0] LEDR
);

wire clk_Pulse1s;

// clock 1 s
clockTick #(.M(50000000), .N(26)) 
    clock_1s (.clk(CLOCK_50), .reset(reset), 
                    .clkPulse(clk_Pulse1s));

                    
// edge detector
edgeDetector edgeDetector_VisualTest(.clk(clk_Pulse1s), .reset(reset), 
            .level(SW[1]), .Moore_tick(LEDR[0]) , .Mealy_tick(LEDR[1]));
            
endmodule

7.4. Glitches

Glitches are the short duration pulses which are generated in the combinational circuits. These are generated when more than two inputs change their values simultaneously. Glitches can be categorized as ‘static glitches’ and ‘dynamic glitches’. Static glitches are further divided into two groups i.e. ‘static-0’ and ‘static-1’. ‘Static-0’ glitch is the glitch which occurs in logic ‘0’ signal i.e. one short pulse i.e. ‘high-pulse (logic-1)’ appears in logic-0 signal (and the signal settles down). Dynamic glitch is the glitch in which multiple short pulses appear before the signal settles down.

Note

Most of the times, the glitches are not the problem in the design. Glitches create problem when it occur in the outputs, which are used as clock for the other circuits. In this case, glitches will trigger the next circuits, which will result in incorrect outputs. In such cases, it is very important to remove these glitches. In this section, the glitches are shown for three cases. Since, clocks are used in synchronous designs, therefore Section Section 7.4.3 is of our main interest.

7.4.1. Combinational design in asynchronous circuit

Fig. 7.4 shows the truth-table for \(2 \times 1\) multiplexer and corresponding Karnaugh map is shown in Fig. 7.5. Note that, the glitches occurs in the circuit, when we exclude the ‘red part’ of the solution from the Fig. 7.5, which results in minimum-gate solution, but at the same time the solution is disjoint. To remove the glitch, we can add the prime-implicant in red-part as well. This solution is good, if there are few such gates are required; however if the number of inputs are very high, whose values are changing simultaneously then this solution is not practical, as we need to add large number of gates.

../_images/glitch_table.jpg

Fig. 7.4 Truth table of \(2 \times 1\) Multiplexer

../_images/glitch_sol.jpg

Fig. 7.5 Reason for glitches and solution

../_images/glitches.jpg

Fig. 7.6 Glitches (see disjoint lines in ‘z’) in design in Listing 7.3

Listing 7.3 Glitches in multiplexer
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// glitchEx.vhd

// 2x1 Multiplexer using logic-gates

module glitchEx(
    input wire in0, in1, sel,
    output wire z
); 

wire not_sel;
wire and_out1, and_out2;
    
assign not_sel = ~sel; 
assign and_out1 = not_sel & in0; 
assign and_out2 = sel & in1; 
assign z = and_out1 | and_out2; // glitch in signal z
    
//  // Comment above line and uncomment below line to remove glitches
//  z <= and_out1 or and_out2 or (in0 and in1); 
endmodule 

7.4.2. Unfixable Glitch

Listing 7.4 is another example of glitches in the design as shown in Fig. 7.7. Here, glitches are continuous i.e. these are occurring at every change in signal ‘din’. Such glitches are removed by using D-flip-flop as shown in Section Section 7.4.3. Since the output of Manchester code depends on both edges of clock (i.e. half of the output changes on +ve edge and other half changes at -ve edge), therefore such glitches are unfixable; as in Verilog both edges can not be connected to one D flip flop.

../_images/manchesterGlitch.jpg

Fig. 7.7 Glitches in Listing 7.4

Listing 7.4 Glitches in Manchester coding
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// manchester_code.vhd

module manchester_code
(
    input wire clk, din,
    output wire dout
);

// glitch will occure on transition of signal din
assign dout = clk ^ din; 

endmodule  

7.4.3. Combinational design in synchronous circuit

Combination designs in sequential circuits were discussed in Fig. 4.1. The output of these combination designs can depend on states only, or on the states along with external inputs. The former is known as Moore design and latter is known as Mealy design as discussed in Section Section 7.2. Since, the sequential designs are sensitive to edge of the clock, therefore the glitches can occur only at the edge of the clock. Hence, the glitches at the edge can be removed by sending the output signal through the D flip flop, as shown in Fig. 7.8. Various Verilog templates for sequential designs are shown in Section Section 7.5 and Section 7.6.

../_images/combSeqBlockGlitchFree.jpg

Fig. 7.8 Glitch-free sequential design using D flip flop

7.5. Moore architecture and Verilog templates

Fig. 7.8 shows the different block for the sequential design. In this figure, we have three blocks i.e. ‘sequential logic’, ‘combinational logic’ and ‘glitch removal block’. In this section, we will define three process-statements to implemented these blocks (see Listing 7.6). Further, ‘combinational logic block’ contains two different logics i.e. ‘next-state’ and ‘output’. Therefore, this block can be implemented using two different block, which will result in four process-statements (see Listing 7.5).

Moore and Mealy machines can be divided into three categories i.e. ‘regular’, ‘timed’ and ‘recursive’. The differences in these categories are shown in Fig. 7.9, Fig. 7.10 and Fig. 7.11 for Moore machine. In this section, we will see different Verilog templates for these categories. Note that, the design may be the combinations of these three categories, and we need to select the correct template according to the need. Further, the examples of these templates are shown in Section Section 7.7.

../_images/regular.jpg

Fig. 7.9 Regular Moore machine

../_images/timed.jpg

Fig. 7.10 Timed Moore machine : next state depends on time as well

../_images/recursive.jpg

Fig. 7.11 Recursive Moore machine : output ‘z’ depends on output i.e. feedback required

7.5.1. Regular machine

Please see the Fig. 7.9 and note the following points about regular Moore machine,

  • Output depends only on the states, therefore no ‘if statement’ is required in the process-statement. For example, in Lines 85-87 of Listing 7.5, the outputs (Lines 86-87) are defined inside the ‘s0’ (Line 86).
  • Next-state depends on current-state and and current external inputs. For example, the ‘state_next’ at Line 49 of Listing 7.5 is defined inside ‘if statement’ (Line 48) which depends on current input. Further, this ‘if statement’ is defined inside the state ‘s0’ (Line 47). Hence the next state depends on current state and current external input.

Note

In regular Moore machine,

  • Outputs depend on current external inputs.
  • Next states depend on current states and current external inputs.
Listing 7.5 Verilog template for regular Moore FSM : separate ‘next_state’ and ‘output’ logic
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// moore_regular_template.v

module moore_regular_template
#( parameter
        param1 : <value>,
        param2 : <value>
)
(
    input wire clk, reset,
    input wire [<size>] input1, input2, ...,
    output reg [<size>] output1, output2
); 

localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;
    
    reg[<size_state>] state_reg, state_next;  


// state register : state_reg
// This process contains sequential part and all the D-FF are 
// included in this process. Hence, only 'clk' and 'reset' are 
// required for this process. 
always @(posedge clk, posedge reset) begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// next state logic : state_next
// This is combinational of the sequential design, 
// which contains the logic for next-state
// include all signals and input in sensitive-list except state_next
// next state logic : state_next
// This is combinational of the sequential design, 
// which contains the logic for next-state
// include all signals and input in sensitive-list except state_next
always @(input1, input2, state_reg) begin 
    state_next = state_reg; // default state_next
    case (state_reg)
        s0 : begin
            if (<condition>) begin  // if (input1 = 2'b01) then
                state_next = s1; 
            end
            else if (<condition>) begin  // add all the required conditionstion
                state_next = ...; 
            end
            else begin // remain in current state
                state_next = s0; 
            end
        end
        s1 : begin
            if (<condition>) begin // if (input1 = 2'b10) then
                state_next = s2; 
            end
            else if (<condition>) begin // add all the required conditionstions
                state_next = ...; 
            end
            else begin// remain in current state
                state_next = s1; 
            end
        end
        s2 : begin
            ...
        end
    endcase
end 
    
// combination output logic
// This part contains the output of the design
// no if-else statement is used in this part
// include all signals and input in sensitive-list except state_next
always @(input1, input2, ..., state_reg) begin
    // default outputs
    output1 = <value>;
    output2 = <value>;
    ...
    case (state_reg)  
        s0 : begin
            output1 = <value>;
            output2 = <value>;
            ...
        end
        s1 : begin
            output1 = <value>;
            output2 = <value>;
            ...
        end
        s2 : begin
            ...
        end
    endcase
end 
    
// optional D-FF to remove glitches
always @(posedge clk, posedge reset)
begin 
    if (reset) begin
        new_output1 <= ... ;
        new_output2 <= ... ;
    end
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end 

endmodule

Listing 7.6 is same as Listing 7.5, but the ouput-logic and next-state logic are combined in one process block.

Listing 7.6 Verilog template for regular Moore FSM : combined ‘next_state’ and ‘output’ logic
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// moore_regular_template2.v

module moore_regular_template2
#( parameter
        param1 : <value>,
        param2 : <value>
)
(
    input wire clk, reset,
    input wire [<size>] input1, input2, ...,
    output reg [<size>] output1, output2
); 

localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;
    
    reg[<size_state>] state_reg, state_next;  


// state register : state_reg
// This process contains sequential part and all the D-FF are 
// included in this process. Hence, only 'clk' and 'reset' are 
// required for this process. 
always @(posedge clk, posedge reset) begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// next state logic : state_next
// This is combinational of the sequential design, 
// which contains the logic for next-state
// include all signals and input in sensitive-list except state_next
// next state logic : state_next
// This is combinational of the sequential design, 
// which contains the logic for next-state
// include all signals and input in sensitive-list except state_next
always @(input1, input2, state_reg) begin 
    state_next = state_reg; // default state_next
    case (state_reg)
        s0 : begin
            output1 = <value>;
            output2 = <value>;
            ...
            if (<condition>) begin  // if (input1 = 2'b01) then
                state_next = s1; 
            end
            else if (<condition>) begin  // add all the required conditionstion
                state_next = ...; 
            end
            else begin // remain in current state
                state_next = s0; 
            end
        end
        s1 : begin
            output1 = <value>;
            output2 = <value>;
            ...
            if (<condition>) begin // if (input1 = 2'b10) then
                state_next = s2; 
            end
            else if (<condition>) begin // add all the required conditionstions
                state_next = ...; 
            end
            else begin// remain in current state
                state_next = s1; 
            end
        end
        s2 : begin
            ...
        end
    endcase
end 
            
// optional D-FF to remove glitches
always @(posedge clk, posedge reset)
begin 
    if (reset) begin
        new_output1 <= ... ;
        new_output2 <= ... ;
    end
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end 

endmodule

7.5.2. Timed machine

If the state of the design changes after certain duration (see Fig. 7.10), then we need to add the timer in the Verilog design which are created in Listing 7.5 and Listing 7.5. For this, we need to add one more process-block which performs following actions,

  • Zero the timer : The value of the timer is set to zero, whenever the state of the system changes.
  • Stop the timer : Value of the timer is incremented till the predefined ‘maximum value’ is reached and then it should be stopped incrementing. Further, it’s value should not be set to zero until state is changed.

Note

In timed Moore machine,

  • Outputs depend on current external inputs.
  • Next states depend on time along with current states and current external inputs.

Template for timed Moore machine is shown in Listing 7.7, which is exactly same as Listing 7.6 except with following changes,

  • Timer related constants are added at Line 22-27.
  • An ‘always’ block is added to stop and zero the timer (Lines 44-54).
  • Finally, timer related conditions are included for next-state logic e.g. Lines 64 and 67 etc.
Listing 7.7 Verilog template timed Moore FSM : separate ‘next_state’ and ‘output’ logic
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// moore_timed_template.vhd

module moore_timed_template 
#( parameter
        param1 : <value>,
        param2 : <value>
)
(
    input wire clk, reset,
    input wire [<size>] input1, input2, ...,
    output reg [<size>] output1, output2
);

localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;
    
    reg[<size_state>] state_reg, state_next;  

// timer
localparam T1 = <value>;
localparam T2 = <value>;
localparam T3 = <value>;
...
reg [<size>] t; //<size> should be able to store max(T1, T2, T3) 


// state register : state_reg
// This process contains sequential part and all the D-FF are 
// included in this process. Hence, only 'clk' and 'reset' are 
// required for this process. 
always @(posedge clk, posedge reset) begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// timer 
always @(posedge clk, posedge reset) begin 
    if (reset) begin
        t <= 0;
    end
    else begin
        if state_reg != state_next then  // state is changing
            t <= 0;
        else
            t <= t + 1;  
    end
end
        
// next state logic : state_next
// This is combinational of the sequential design, 
// which contains the logic for next-state
// include all signals and input in sensitive-list except state_next
always @(input1, input2, state_reg) begin 
    state_next = state_reg; // default state_next
    case (state_reg)
        s0 : begin
            if (<condition> & t >= T1-1) begin  // if (input1 = 2'b01) then
                state_next = s1; 
            end
            else if (<condition> & t >= T2-1) begin  // add all the required conditionstion
                state_next = ...; 
            end
            else begin // remain in current state
                state_next = s0; 
            end
        end
        s1 : begin
            if (<condition> & t >= T3-1) begin // if (input1 = 2'b10) then
                state_next = s2; 
            end
            else if (<condition> & t >= T2-1) begin // add all the required conditionstions
                state_next = ...; 
            end
            else begin// remain in current state
                state_next = s1; 
            end
        end
        s2 : begin
            ...
        end
    endcase
end 
    
// combination output logic
// This part contains the output of the design
// no if-else statement is used in this part
// include all signals and input in sensitive-list except state_next
always @(input1, input2, ..., state_reg) begin
    // default outputs
    output1 = <value>;
    output2 = <value>;
    ...
    case (state_reg)  
        s0 : begin
            output1 = <value>;
            output2 = <value>;
            ...
        end
        s1 : begin
            output1 = <value>;
            output2 = <value>;
            ...
        end
        s2 : begin
            ...
        end
    endcase
end 
    
// optional D-FF to remove glitches
always @(posedge clk, posedge reset)
begin 
    if (reset) begin
        new_output1 <= ... ;
        new_output2 <= ... ;
    end
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end 

endmodule 

7.5.3. Recursive machine

In recursive machine, the outputs are fed back as input to the system (see Fig. 7.11). Hence, we need additional process-statement which can store the outputs which are fed back to combinational block of sequential design, as shown in Listing 7.8. The listing is same as Listing 7.7 except certain signals and process block are defined to feedback the output to combination logic; i.e. Lines 29-31 contain the signals (feedback registers) which are required to be feedback the outputs. Here, ‘_next’ and ‘_reg’ are used in these lines, where ‘next’ value is fed back as ‘reg’ in the next clock cycle inside the ‘always’ statement which is defined in Lines 63-75. Lastly, ‘feedback registers’ are also used to calculate the next-state inside the ‘if statement’ e.g. Lines 91 and 96. Also, the value of feedback registers are updated inside these ‘if statements’ e.g. Lines 93 and 102.

Note

In recursive Moore machine,

  • Outputs depend on current external inputs. Also, values in the feedback registers are used as outputs.
  • Next states depend current states, current external input, current internal inputs (i.e. previous outputs feedback as inputs to system) and time (optional).
Listing 7.8 Verilog template recursive Moore FSM : separate ‘next_state’ and ‘output’ logic
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
// moore_recursive_template.v

module moore_recursive_template 
#( parameter
		param1 : <value>,
		param2 : <value>
)
(
	input wire clk, reset,
	input wire [<size>] input1, input2, ...,
	output reg [<size>] output1, output2, new_output1, new_output2
);

localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;

    reg[<size_state>] state_reg, state_next;  

// timer
localparam T1 = <value>;
localparam T2 = <value>;
localparam T3 = <value>;
...
reg [<size>] t; //<size> should be able to store max(T1, T2, T3) 

// recursive : feedback register
reg [<size>] r1_reg, r1_next;
reg [<size>] r2_reg, r2_next, ;
...


// state register : state_reg
// This always-block contains sequential part & all the D-FF are 
// included in this always-block. Hence, only 'clk' and 'reset' are 
// required for this always-block. 
always(posedge clk, posedge reset)
begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// timer (optional)
always @(posedge clk, posedge reset) begin
    if (reset) begin
        t <= 0;
    end
    else begin
        if state_reg != state_next then  // state is changing
            t <= 0;
        else
            t <= t + 1;  
    end
end

// feedback registers: to feedback the outputs
always @(posedge clk, posedge reset)
begin
    if (reset) begin
        r1_reg <= <initial_value>;
        r2_reg <= <initial_value>;
        ...
    end
    else begin
        r1_reg <= r1_next;
        r2_reg <= r2_next;
        ...
    end
end



//  next state logic : state_next
//  This is combinational of the sequential design, 
//  which contains the logic for next-state
//  include all signals and input in sensitive-list except state_next
always @(input1, input2, state_reg) begin 
    state_next = state_reg; //  default state_next
    r1_next = r1_reg; //  default next-states
    r2_next = r2_reg;
    ...
    case (state_reg) 
        s0 : begin
            if <condition> & r1_reg == <value> & t >= T1-1 begin //  if (input1 = '01') then
                state_next = s1; 
                r1_next = <value>;
                r2_next = <value>;
                ...
            end
            elsif <condition> & r2_reg == <value> & t >= T2-1 begin  //  add all the required conditions
                state_next = <value>; 
                r1_next = <value>;
                ...
            end
            else begin //  remain in current state
                state_next = s0; 
                r2_next = <value>;
                ...
            end
        end
        s1 : begin 
            ...
    end case;
end process; 
    
// next state logic and outputs
// This is combinational of the sequential design, 
// which contains the logic for next-state and outputs
// include all signals and input in sensitive-list except state_next
always @(input1, input2, ..., state_reg) begin 
    state_next = state_reg; // default state_next
    // default outputs
    output1 = <value>;
    output2 = <value>;
    ...
    // default next-states
    r1_next = r1_reg;
    r2_next = r2_reg;
    ...
    case (state_reg)
        s0 : begin
            output1 = <value>;
            output2 = <value>;
            if (<condition> & r1_reg = <value> & t >= T1-1) begin // if (input1 = 2'b01) then
                ...
                r1_next = <value>;
                r2_next = <value>;
                ...
                state_next = s1; 
            end
            else if (<condition> & r2_reg = <value> & t >= T2-1) begin // add all the required coditions
                r1_next = <value>;
                ...
                state_next = ...; 
            end
            else begin // remain in current state
                r2_next = <value>;
                ...
                state_next = s0; 
            end
        end
        s1 : begin
            output1 = <value>;
            output2 = <value>;
            if (<condition> & r1_reg = <value> & t >= T3-1) begin // if (input1 = 2'b01) then
                ...
                r1_next = <value>;
                r2_next = <value>;
                ...
                state_next = s1; 
            end
            else if (<condition> & r2_reg = <value> & t >= T1-1) begin // add all the required coditions
                r1_next = <value>;
                ...
                state_next = ...; 
            end
            else begin // remain in current state
                r2_next = <value>;
                ...
                state_next = s1; 
            end
        end
    endcase
end  
    
// optional D-FF to remove glitches
always @(posedge clk, posedge reset)
begin 
    if (reset) begin 
        new_output1 <= ... ;
        new_output2 <= ... ;
    end
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end
endmodule  

7.6. Mealy architecture and Verilog templates

Template for Mealy architecture is similar to Moore architecture. The minor changes are required as outputs depend on current input as well, as discussed in this section.

7.6.1. Regular machine

In Mealy machines, the output is the function of current input and states, therefore the output will also defined inside the if-statements (Lines 49-50 etc.). Rest of the code is same as Listing 7.6.

Listing 7.9 Verilog template for regular Mealy FSM : combined ‘next_state’ and ‘output’ logic
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// mealy_regular_template.v

module mealy_regular_template 
#( parameter 
		param1 = <value>, 
		param2 = <value>,
)
(
	input wire clk, reset,
	input wire [<size>] input1, input2, ...,
	output reg [<size>] output1, output2
);

localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;
    
    reg[<size_state>] state_reg, state_next; 

// state register : state_reg
// This `always block' contains sequential part and all the D-FF are 
// included in this process. Hence, only 'clk' and 'reset' are 
// required for this process. 
always(posedge clk, posedge reset)
begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// next state logic and outputs
// This is combinational part of the sequential design, 
// which contains the logic for next-state and outputs
// include all signals and input in sensitive-list except state_next
always @(input1, input2, ..., state_reg) begin 
    state_next = state_reg; // default state_next
    // default outputs
    output1 = <value>;
    output2 = <value>;
    ...
    case (state_reg)
        s0 : begin
            if (<condition>) begin // if (input1 == 2'b01) then
                output1 = <value>;
                output2 = <value>;
                ...
                state_next = s1;
            end
            else if <condition> begin  // add all the required conditionstions
                output1 = <value>;
                output2 = <value>;
                ...
                state_next = ...; 
            end
            else begin // remain in current state
                output1 = <value>;
                output2 = <value>;
                ...
                state_next = s0; 
            end
        end
        s1 : begin
            ...
        end
    endcase
end  
    
// optional D-FF to remove glitches
always(posedge clk, posedge reset) begin 
    if (reset) begin
        new_output1 <= ... ;
        new_output2 <= ... ;
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end 
endmodule 

7.6.2. Timed machine

Listing 7.10 contains timer related changes in Listing 7.9. See description of Listing 7.7 for more details.

Listing 7.10 Verilog template for timed Mealy FSM : combined ‘next_state’ and ‘output’ logic
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
// mealy_timed_template.v

module mealy_timed_template 
#( parameter
        param1 : <value>,
        param2 : <value>
)
(
    input wire clk, reset,
    input wire [<size>] input1, input2, ...,
    output reg [<size>] output1, output2
);


localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;
    
    reg[<size_state>] state_reg, state_next;  

// timer
localparam T1 = <value>;
localparam T2 = <value>;
localparam T3 = <value>;
...
reg [<size>] t; //<size> should be able to store max(T1, T2, T3) 

// state register : state_reg
// This always-block contains sequential part and all the D-FF are 
// included in this always-block. Hence, only 'clk' and 'reset' are 
// required for this always-block. 
always @(posedge clk, posedge reset) begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// timer 
always @(posedge clk, posedge reset) begin 
    if (reset) begin
        t <= 0;
    end
    else begin
        if state_reg != state_next then  // state is changing
            t <= 0;
        else
            t <= t + 1;  
    end
end

// next state logic and outputs
// This is combinational of the sequential design, 
// which contains the logic for next-state and outputs
// include all signals and input in sensitive-list except state_next
always @(input1, input2, ..., state_reg) begin 
    state_next = state_reg; // default state_next
    // default outputs
    output1 = <value>;
    output2 = <value>;
    ...
    case (state_reg )
        s0 : begin
            if (<condition> & t >= T1-1) begin // if (input1 = '01') then
                output1 = <value>;
                output2 = <value>;
                ...
                state_next = s1; 
            end
            else if (<condition> & t >= T2-1) begin // add all the required conditionstions
                output1 = <value>;
                output2 = <value>;
                ...
                state_next = ...; 
            end
            else begin // remain in current state
                output1 = <value>;
                output2 = <value>;
                ...
                state_next = s0; 
            end
        end
        s1 : begin
            ...
        end
    endcase
end
    
// optional D-FF to remove glitches
always @(posedge clk, posedge reset)
begin 
    if (reset) begin
        new_output1 <= ... ;
        new_output2 <= ... ;
    end
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end 

endmodule

7.6.3. Recursive machine

Listing 7.11 contains recursive-design related changes in Listing 7.10. See description of Listing 7.8 for more details.

Listing 7.11 Verilog template for recursive Mealy FSM : combined ‘next_state’ and ‘output’ logic
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// mealy_recursive_template.v

module mealy_recursive_template is 
#( parameter
		param1 : <value>,
		param2 : <value>
)
(
	input wire clk, reset,
	input wire [<size>] input1, input2, ...,
	output reg [<size>] output1, output2, new_output1, new_output2
);

localparam [<size_state>] // for 4 states : size_state = 1:0
    s0 = 0,
    s1 = 1,
    s2 = 2,
    ... ;
    
    reg[<size_state>] state_reg, state_next;  

// timer (optional)
localparam T1 = <value>;
localparam T2 = <value>;
localparam T3 = <value>;
...
reg [<size>] t; //<size> should be able to store max(T1, T2, T3) 

// recursive : feedback register
reg [<size>] r1_reg, r1_next;
reg [<size>] r2_reg, r2_next;
...

// state register : state_reg
// This process contains sequential part & all the D-FF are 
// included in this process. Hence, only 'clk' and 'reset' are 
// required for this process. 
always(posedge clk, posedge reset)
begin
    if (reset) begin
        state_reg <= s1;
    end
    else begin
        state_reg <= state_next;
    end
end 

// timer (optional)
always @(posedge clk, posedge reset) begin
    if (reset) begin
        t <= 0;
    end
    else begin
        if state_reg != state_next then  // state is changing
            t <= 0;
        else
            t <= t + 1;  
    end
end

// feedback registers: to feedback the outputs
always @(posedge clk, posedge reset)
begin
    if (reset) begin
        r1_reg <= <initial_value>;
        r2_reg <= <initial_value>;
        ...
    end
    else begin
        r1_reg <= r1_next;
        r2_reg <= r2_next;
        ...
    end
end

// next state logic and outputs
// This is combinational of the sequential design, 
// which contains the logic for next-state and outputs
// include all signals and input in sensitive-list except state_next
always @(input1, input2, ..., state_reg) begin 
    state_next = state_reg; // default state_next
    // default outputs
    output1 = <value>;
    output2 = <value>;
    ...
    // default next-states
    r1_next = r1_reg;
    r2_next = r2_reg;
    ...
    case (state_reg)
        s0 : begin
            if (<condition> & r1_reg == <value> & t >= T1-1) begin // if (input1 = 2'b01) then
                output1 = <value>;
                output2 = <value>;
                ...
                r1_next = <value>;
                r2_next = <value>;
                ...
                state_next = s1; 
            end
            else if (<condition> & r2_reg == <value> & t >= T2-1) begin // add all the required coditions
                output1 = <value>;
                output2 = <value>;
                ...
                r1_next = <value>;
                ...
                state_next = ...; 
            end
            else begin // remain in current state
                output1 = <value>;
                output2 = <value>;
                ...
                r2_next = <value>;
                ...
                state_next = s0; 
            end
        end
        s1 : begin
            ...
        end
    endcase
end  
    
// optional D-FF to remove glitches
always @(posedge clk, posedge reset)
begin 
    if (reset) begin 
        new_output1 <= ... ;
        new_output2 <= ... ;
    end
    else begin
        new_output1 <= output1; 
        new_output2 <= output2; 
    end
end

endmodule  

7.7. Examples

7.7.1. Regular Machine : Glitch-free Mealy and Moore design

In this section, a non-overlapping sequence detector is implemented to show the differences between Mealy and Moore machines. Listing 7.12 implements the ‘sequence detector’ which detects the sequence ‘110’; and corresponding state-diagrams are shown in Fig. 7.12 and Fig. 7.13. The RTL view generated by the listing is shown in Fig. 7.15, where two D-FF are added to remove the glitches from Moore and Mealy model. Also, in the figure, if we click on the state machines, then we can see the implemented state-diagrams e.g. if we click on ‘state_reg_mealy’ then the state-diagram in Fig. 7.14 will be displayed, which is exactly same as Fig. 7.13.

Further, the testbench for the listing is shown in Listing 7.13, whose results are illustrated in Fig. 7.16. Please note the following points in Fig. 7.16,

  • Mealy machines are asynchronous as the output changes as soon as the input changes. It does not wait for the next cycle.
  • If the output of the Mealy machine is delayed, then glitch will be removed and the output will be same as the Moore output (Note that, there is no glitch in this system. This example shows how to implement the D-FF to remove glitch in the system (if exists)).
  • Glitch-free Moore output is delayed by one clock cycle.
  • If glitch is not a problem, then we should use Moore machine, because it is synchronous in nature. But, if glitch is problem and we do not want to delay the output then Mealy machines should be used.
../_images/Moore_seq_det_state.jpg

Fig. 7.12 Non-overlap sequence detector ‘110’ : Moore design

../_images/Mealy_seq_det_state.jpg

Fig. 7.13 Non-overlap sequence detector ‘110’ : Mealy design

../_images/Altera_Mealy_seq_det_state.jpg

Fig. 7.14 State diagram generated by Quartus for Mealy machine in Listing 7.12

../_images/Mealy_Moore_RTL_glitchfree.jpg

Fig. 7.15 RTL view generated by Listing 7.12

../_images/Mealy_MooreGlitchFree.jpg

Fig. 7.16 Mealy and Moore machine output for Listing 7.13

Listing 7.12 Glitch removal using D-FF
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
// sequence_detector.v
// non-overlap detection : 110

module sequence_detector
(
    input wire clk, reset,
    input wire x,
    output wire z_mealy_glitch, z_moore_glitch,
    output reg z_mealy_glitch_free, z_moore_glitch_free
);

// Moore
localparam [1:0]
    zero_moore = 0,
    one_moore = 1,
    two_moore = 2, 
    three_moore = 3;

// size is [1:0] to store 4 states
reg[1:0] state_reg_moore, state_next_moore;

// Mealy
localparam [1:0]
    zero_mealy = 0,
    one_mealy = 1,
    two_mealy = 2, 
    three_mealy = 3;
    
// size is [1:0] to store 4 states
reg[1:0] state_reg_mealy, state_next_mealy;

reg z_moore, z_mealy;

always @(posedge clk, posedge reset) begin 
    if (reset) begin 
        state_reg_moore <= zero_moore; 
        state_reg_mealy <= zero_mealy; 
    end
    else begin
        state_reg_moore <= state_next_moore;
        state_reg_mealy <= state_next_mealy;
    end
end 

// Moore
always @(state_reg_moore, x) begin 
    z_moore = 1'b0; 
    state_next_moore = state_reg_moore; // default 'next state' is 'current state'
    case(state_reg_moore)  
        zero_moore : 
            if (x == 1'b1 )
                state_next_moore = one_moore;
        one_moore : begin
            if (x == 1'b1)
                state_next_moore = two_moore;
            else 
                state_next_moore = zero_moore;
        end
        two_moore :
            if (x == 1'b0)
                state_next_moore = three_moore; 
        three_moore : begin
            z_moore = 1'b1;
            if (x == 1'b0)
                state_next_moore = zero_moore; 
            else
                state_next_moore = one_moore;
        end
    endcase
end 

// Mealy
always @(state_reg_mealy, x) begin 
    z_mealy = 1'b0; 
    state_next_mealy = state_reg_mealy; // default 'next state' is 'current state'
    case (state_reg_mealy) 
        zero_mealy :
            if (x == 1'b1)
                state_next_mealy = one_mealy;
        one_mealy :
            if (x == 1'b1) 
                state_next_mealy = two_mealy;
            else
                state_next_mealy = zero_mealy;
        two_mealy : begin
            state_next_mealy = zero_mealy;
            if (x == 1'b0)
                z_mealy <= 1'b1;
            else 
                state_next_mealy = two_mealy;
        end
    endcase
end 

// D-FF to remove glitches
always @(posedge clk, posedge reset) begin
    if (reset == 1'b1) begin
        z_mealy_glitch_free <= 1'b0;
        z_moore_glitch_free <= 1'b0;
    end
    else begin
        z_mealy_glitch_free <= z_mealy; 
        z_moore_glitch_free <= z_moore;
    end
end 

assign z_mealy_glitch = z_mealy; 
assign z_moore_glitch = z_moore;

endmodule 

        
Listing 7.13 Testbench for Listing 7.12
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
-- sequence_detector_tb.vhd

library ieee; 
use ieee.std_logic_1164.all;

entity sequence_detector_tb is
end sequence_detector_tb; 

architecture arch of sequence_detector_tb is 
    constant T : time := 20 ps;
    signal clk, reset : std_logic; -- input
    signal x : std_logic;
    signal z_moore_glitch, z_moore_glitch_free : std_logic;
    signal z_mealy_glitch, z_mealy_glitch_free : std_logic;
begin 
    sequence_detector_unit : entity work.sequence_detector
                port map (clk=>clk, reset=>reset, x=>x,
                z_moore_glitch=>z_moore_glitch, z_moore_glitch_free => z_moore_glitch_free,
                z_mealy_glitch=>z_mealy_glitch, z_mealy_glitch_free => z_mealy_glitch_free
            );
                
    -- continuous clock
    process
    begin
        clk <= '0';
        wait for T/2;
        clk <= '1';
        wait for T/2;
    end process;
    
    -- reset = 1 for first clock cycle and then 0
    reset <= '1', '0' after T/2;
    
    x <= '0', '1' after T, '1' after 2*T, '0' after 3*T;   
end; 

7.7.2. Timed machine: programmable square wave

Listing 7.14 generates the square wave using Moore machine, whose ‘on’ and ‘off’ time is programmable (see Lines 6 and 7) according to state-diagram in Fig. 7.17. The simulation waveform of the listing are shown in Fig. 7.18.

../_images/program_s_wave.jpg

Fig. 7.17 State diagram for programmable square-wave generator

../_images/square_wave_ex.jpg

Fig. 7.18 Simulation waveform of Listing 7.14

Listing 7.14 Square wave generator
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// square_wave_ex.vhd

module square_wave_ex
#( parameter 
        N = 4, // Number of bits to represent the time
        on_time = 3'd5,
        off_time = 3'd3
)
(
    input wire clk, reset,
    output reg s_wave
);

localparam 
    onState = 0, 
    offState = 1;
reg state_reg, state_next;
reg[N-1:0] t = 0;

always @(posedge clk, posedge reset) begin 
    if (reset == 1'b1)
        state_reg <= offState; 
    else
        state_reg <= state_next;
end

always @(posedge clk, posedge reset) begin
    if (state_reg != state_next)
        t <= 0;
    else
        t <= t + 1;
end

always @(state_reg, t) begin
    case (state_reg)
        offState : begin
            s_wave = 1'b0; 
            if (t == off_time - 1) 
                state_next = onState;
            else
                state_next = offState; 
        end
        onState : begin
            s_wave = 1'b1; 
            if (t == on_time - 1)
                state_next = offState;
            else
                state_next = onState;
        end
    endcase
end
endmodule 

7.7.3. Recursive Machine : Mod-m counter

Listing 7.15 implements the Mod-m counter using Moore machine, whose state-diagram is shown in Fig. 7.19. Machine is recursive because the output signal ‘count_moore_reg’ (Line 50) is used as input to the system (Line 32). The simulation waveform of the listing are shown in Fig. 7.20

../_images/counter_state_diagram.jpg

Fig. 7.19 State diagram for Mod-m counter

../_images/counterEx.jpg

Fig. 7.20 Simulation waveform of Listing 7.15

Note

It is not good to implement every design using FSM e.g. Listing 7.15 can be easily implement without FSM as shown in Listing 6.4. Please see the Section Section 7.8 for understading the correct usage of FSM design.

Listing 7.15 Mod-m Counter
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// counterEx.v
// count upto M

module counterEx 
#( parameter 
        M = 6,
        N = 4 // N bits are required for M
    )
(
    input wire clk, reset,
    output wire out_moore
);

localparam
    start_moore = 0,
    count_moore = 1;
    
reg state_moore_reg, state_moore_next;
reg[N-1:0] count_moore_reg, count_moore_next;

always @(posedge clk, posedge reset) begin 
    if (reset == 1'b1) begin
        state_moore_reg <= start_moore;
        count_moore_reg <= 0;
    end
    else begin
        state_moore_reg <= state_moore_next;
        count_moore_reg <= count_moore_next;
    end
end

always @(count_moore_reg, state_moore_reg)
begin 
    case (state_moore_reg) 
        start_moore : begin 
            count_moore_next = 0;
            state_moore_next = count_moore;
        end
        count_moore : begin
            count_moore_next = count_moore_reg  + 1;
            if ((count_moore_reg  + 1) == M - 1)
                state_moore_next = start_moore;
            else
                state_moore_next = count_moore;
        end
    endcase
end 

    
assign out_moore = count_moore_reg;

endmodule

7.8. When to use FSM design

We saw in previous sections that, once we have the state diagram for the FSM design, then the Verilog design is a straightforward process. But, it is important to understand the correct conditions for using the FSM, otherwise the circuit will become complicated unnecessary.

  • We should not use the FSM diagram, if there is only ‘one loop’ with ‘zero or one control input’. ‘Counter’ is a good example for this. A 10-bit counter has 10 states with no control input (i.e. it is free running counter). This can be easily implemented without using FSM as shown in Listing 6.3. If we implement it with FSM, then we need 10 states; and the code and corresponding design will become very large.
  • If required, then FSM can be use for ‘one loop’ with ‘two or more control inputs’.
  • FSM design should be used in the cases where there are very large number of loops (especially connected loops) along with two or more controlling inputs.

7.9. Conclusion

In this chapter, Mealy and Moore designs are discussed. Also, ‘edge detector’ is implemented using Mealy and Moore designs. This example shows that Mealy design requires fewer states than Moore design. Further, Mealy design generates the output tick as soon as the rising edge is detected; whereas Moore design generates the output tick after a delay of one clock cycle. Therefore, Mealy designs are preferred for synchronous designs.