Design a Counter Using a Finite State Machine

FPGA designs with Verilog and SystemVerilog

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.

Fig. 7.1 State diagrams for Edge detector : Moore Design

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.

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.

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

Fig. 7.5 Reason for glitches and solution

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.

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.

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.

Fig. 7.9 Regular Moore machine

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

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.

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

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

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

Fig. 7.15 RTL view generated by Listing 7.12

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.

Fig. 7.17 State diagram for programmable square-wave generator

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

Fig. 7.19 State diagram for Mod-m counter

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.

Design a Counter Using a Finite State Machine

Source: https://verilogguide.readthedocs.io/en/latest/verilog/fsm.html

Share this post