This example is taken from D. D. Gajski, Principles of Digital Design, Prentice Hall, 1997, p.230.

Example 1.1. Modulo-4 counter

Derive the state table and state diagram for the sequential circuit shown in Figure 7.

Figure 7. Logic schematic of a sequential circuit.

SOLUTION:

STEP 1:     First we derive the Boolean expressions for the inputs of each flip-flops in the schematic, in terms of external input Cnt and the flip-flop outputs Q1 and Q0. Since there are two D flip-flops in this example, we derive two expressions for D1 and D0:

D0 = CntQ0 = Cnt'*Q0 + Cnt*Q0'

D1 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

These Boolean expressions are called excitation equations since they represent the inputs to the flip-flops of the sequential circuit in the next clock cycle.

STEP 2:     Derive the next-state equations by converting these excitation equations into flip-flop characteristic equations. In the case of D flip-flops, Q(next) = D. Therefore the next state equal the excitation equations.

STEP 3:     Now convert these next-state equations into tabular form called the next-state table.

Each row is corresponding to a state of the sequential circuit and each column represents one set of input values. Since we have two flip-flops, the number of possible states is four - that is, Q1Q0 can be equal to 00, 01, 10, or 11. These are present states as shown in the table.

For the next state part of the table, each entry defines the value of the sequential circuit in the next clock cycle after the rising edge of the Clk. Since this value depends on the present state and the value of the input signals, the next state table will contain one column for each assignment of binary values to the input signals. In this example, since there is only one input signal, Cnt, the next-state table shown has only two columns, corresponding to Cnt = 0 and Cnt = 1.

Note that each entry in the next-state table indicates the values of the flip-flops in the next state if their value in the present state is in the row header and the input values in the column header.

Each of these next-state values has been computed from the next-state equations in STEP 2.

STEP 4:     The state diagram is generated directly from the next-state table, shown in Figure 8.

Figure 8. State diagram

Each arc is labelled with the values of the input signals that cause the transition from the present state (the source of the arc) to the next state (the destination of the arc).

In general, the number of states in a next-state table or a state diagram will equal 2^m , where m is the number of flip-flops. Similarly, the number of arcs will equal 2^m x 2^k , where k is the number of binary input signals. Therefore, in the state diagram, there must be four states and eight transitions. Following these transition arcs, we can see that as long as Cnt = 1, the sequential circuit goes through the states in the following sequence: 0, 1, 2, 3, 0, 1, 2, ....  On the other hand, when Cnt = 0, the circuit stays in its present state until Cnt changes to 1, at which the counting continues.

Since this sequence is characteristic of modulo-4 counting, we can conclude that the sequential circuit in Figure 7 is a modulo-4 counter with one control signal, Cnt, which enables counting when Cnt = 1 and disables it when Cnt = 0.

To see how the states changes corresponding to the input signals Cnt, click on this image.

Below, we show a timing diagram, representing four clock cycles, which enables us to observe the behaviour of the counter in greater detail.

Figure 9. Timing Diagram

In this timing diagram we have assumed that Cnt is asserted in clock cycle 0 at t₀ and is disasserted in clock cycle 3 at time t₄. We have also assumed that the counter is in state Q1Q0 = 00 in the clock cycle 0. Note that on the clock's rising edge, at t₁, the counter will go to state Q1Q0 = 01 with a slight propagation delay; in cycle 2, after t₂, to Q1Q0 = 10; and in cycle 3, after t₃ to Q1Q0 = 11. Since Cnt becomes 0 at t₄, we know that the counter will stay in state Q1Q0 = 11 in the next clock cycle. To see the timing behaviour of the circuit click on this image .

In Example 1.1 we demonstrated the analysis of a sequential circuit that has no outputs by developing a next-state table and state diagram which describes only the states and the transitions from one state to the next. In the next example we complicate our analysis by adding output signals, which means that we have to upgrade the next-state table and the state diagram to identify the value of output signals in each state.

Example 1.2