Skip to main content

Section 7.4 Designing Sequential Circuits

We will now consider a more general set of steps for designing sequential circuits.  1  Design in any field is usually an iterative process, as you have no doubt learned from your programming experience. You start with a design, analyze it, and then refine the design to make it faster, less expensive, etc. After gaining some experience, the design process usually requires fewer iterations.

I wish to thank Dr. Lynn Stauffer for her valuable suggestions for this section.

The following steps form a good method for a first working design:

  1. From the word description of the problem, create a state table and/or state diagram showing what the circuit must do. These form the basic technical specifications for the circuit you will be designing.

  2. Choose a binary code for the states, and create a binary-coded version of the state table and/or state diagram. For \(N\) states, the code will need \(log_{2}N\) bits. Any code will work, but some codes may lead to simpler combinational logic in the circuit.

  3. Choose a particular type of flip-flop. This choice is often dictated by the components you have on hand.

  4. Add columns to the state table that show the input required to each flip-flop in order to effect each transition that is required.

  5. Simplify the input(s) to each flip-flop. Karnaugh maps or algebraic methods are good tools for the simplification process.

  6. Draw the circuit.

Here are two examples to illustrated this process.

Example 7.4.1.

Design a counter that has an \(Enable\) input When \(Enable = \binary{1}\) it increments through the sequence \(0, 1, 2, 3, 0, 1,\dots \) with each clock tick. \(Enable = \binary{0}\) causes the counter to remain in its current state.

  1. First we create a state table and state diagram:

    \(Enable = \binary{0}\) \(Enable = \binary{1}\)
    Current Next Next
    \(n\) \(n\) \(n\)
    \(0\) \(0\) \(1\)
    \(1\) \(1\) \(2\)
    \(2\) \(2\) \(3\)
    \(3\) \(3\) \(0\)

    At each clock tick the counter increments by one if \(Enable = \binary{1}\text{.}\) If \(Enable = \binary{0}\) it remains in the current state. We have only shown the inputs because the output is equal to the state.

  2. A reasonable choice is to use the binary numbering system for each state. With four states we need two bits. We will let \(n = n_1n_0\text{,}\) giving the state table:

    \(Enable = \binary{0}\) \(Enable = \binary{1}\)
    Current Next Next
    \(n_1\) \(n_0\) \(n_1\) \(n_0\) \(n_1\) \(n_0\)
    \(0\) \(0\) \(0\) \(0\) \(0\) \(1\)
    \(0\) \(1\) \(0\) \(1\) \(1\) \(0\)
    \(1\) \(0\) \(1\) \(0\) \(1\) \(1\)
    \(1\) \(1\) \(1\) \(1\) \(0\) \(0\)

  3. Since JK flip-flops are very general we will use those.

  4. We need two flip-flops, one for each bit. So we add columns to the state table showing the input required to each JK flip-flop to cause the correct state transition. Referring to Figure 7.3.16, we see that \(JK = \binary{00}\) keeps the current state, \(JK = \binary{01}\) resets it (to \(\binary{0}\)), \(JK = \binary{10}\) sets it (to \(\binary{1}\)), and \(JK = \binary{11}\) complements the state. We use \(X\) when the input can be either \(\binary{0}\) or \(\binary{1}\text{.}\)

    \(Enable = \binary{0}\) \(Enable = \binary{1}\)
    Current Next Next
    \(n_1\) \(n_0\) \(n_1\) \(n_0\) \(J_1\) \(K_1\) \(J_0\) \(K_0\) \(n_1\) \(n_0\) \(J_1\) \(K_1\) \(J_0\) \(K_0\)
    \(0\) \(0\) \(0\) \(0\) \(0\) \(X\) \(0\) \(X\) \(0\) \(1\) \(0\) \(X\) \(1\) \(X\)
    \(0\) \(1\) \(0\) \(1\) \(0\) \(X\) \(X\) \(0\) \(1\) \(0\) \(1\) \(X\) \(X\) \(1\)
    \(1\) \(0\) \(1\) \(0\) \(X\) \(0\) \(0\) \(X\) \(1\) \(1\) \(X\) \(0\) \(1\) \(X\)
    \(1\) \(1\) \(1\) \(1\) \(X\) \(0\) \(X\) \(0\) \(0\) \(0\) \(X\) \(1\) \(X\) \(1\)

    Notice the “don't care” entries in the state table. Since the JK flip-flop is so versatile, including the “don't cares” helps find simpler circuit realizations.

  5. We use Karnaugh maps, using \(E\) for \(Enable\text{.}\)

    This yields the funtions:

    \begin{gather*} J_0(E,n_1,n_0) = E\\ K_0(E,n_1,n_0) = E\\ J_1(E,n_1,n_0) = E \cdot n_0\\ K_1(E,n_1,n_0) = E \cdot n_0 \end{gather*}

  6. The circuit to implement this counter is:

    The timing of the binary counter is shown here when counting through the sequence \(3, 0, 1, 2, 3\) (\(\binary{11}, \binary{00}, \binary{01}, \binary{10}, \binary{11}\)).

    \(Q_i.JK\) is the input to the \(i^{th}\) JK flip-flop, and \(n_i\) is its output. (Recall that \(J = K\) in this design.) When the \(i^{th}\) input, \(Q_i.JK\text{,}\) is applied to its JK flip-flop, remember that the state of the flip-flop does not change until the second half of the clock cycle. This can be seen when comparing the trace for the corresponding output, \(n_i\text{,}\) in the figure.

    Note the short delay after a clock transition before the value of each \(n_i\) actually changes. This represents the time required for the electronics to completely settle to the new values.

Except for very inexpensive microcontrollers, most modern CPUs execute instructions in stages. An instruction passes through each stage in an assembly-line fashion, called a pipeline. The action of the first stage is to fetch the instruction from memory, as will be explained in Chapter 8.

After an instruction is fetched from memory, it passes onto the next stage of the pipeline. Simultaneously, the first stage of the pipeline fetches the next instruction from memory. The result is that the CPU is working on several instructions at the same time. This provides some parallelism, thus improving execution speed.

Almost all programs contain conditional branch points—places where the next instruction to be fetched can be in one of two different memory locations. Unfortunately, the decision of which of the two instructions to fetch is not known until the decision-making instruction has moved several stages into the pipeline. In order to maintain execution speed, as soon as a conditional branch instruction has passed on from the fetch stage, it is helpful if the CPU can predict where to fetch the next instruction from. In this next example we will design a circuit to implement a prediction circuit.

Example 7.4.2.

Design a circuit that predicts whether a conditional branch is taken or not. The predictor continues to predict the same outcome, take the branch or do not take the branch, until it makes two mistakes in a row.

  1. We use “Yes” to indicate when the branch is taken and “No” to indicate when it is not. The state diagram shows four states:

    Let us begin in the “No” state. The prediction is that the next branch will also not be taken. The notation in the state bubbles is \(\frac{\mathrm{state}}{\mathrm{output}}\text{,}\) showing that the output in this state is also “No.”

    The input to the circuit is whether or not the branch was actually taken. The arc labeled “N” shows the transition when the branch was not taken. It loops back to the “No” state, with the prediction (the output) that the branch will not be taken the next time. If the branch is taken, the “Y” arc shows that the circuit moves into the “fromNo” state, but still predicting no branch the next time.

    From the “fromNo” state, if the branch is not taken (the prediction is correct), the circuit returns to the “No” state. However, if the branch is taken, the “Y” shows that the circuit moves into the “Yes” state. This means that the circuit predicted incorrectly twice in a row, so the prediction is changed to “Yes.”

    You should be able to follow this state diagram for the other cases and convince yourself that both the “fromNo” and “fromYes” states are required.

    It leads to the state table, which provides technical specifications for our circuit:

    Taken = No Taken = Yes
    Current Next Next
    State Prediction State Prediction State Prediction
    No No No No fromNo No
    fromNo No No No Yes Yes
    fromYes Yes No No Yes Yes
    Yes Yes fromYes Yes Yes Yes

  2. Since there are four states, we need two bits. We will let \(\binary{0}\) represent “No” and \(\binary{1}\) represent “Yes.” The input is whether the branch is actually taken (\(\binary{1}\)) or not (\(\binary{0}\) ). And the output is the prediction of whether it will be taken (\(\binary{1}\)) or not (\(\binary{0}\) ).

    We choose a binary code for the state, \(s_1s_0\text{,}\) such that the high-order bit represents the prediction, and the low-order bit what the last input was. That is:

    State Prediction \(s_1\) \(s_0\)
    No No \(\binary{0}\) \(\binary{0}\)
    fromNo No \(\binary{0}\) \(\binary{1}\)
    fromYes Yes \(\binary{1}\) \(\binary{0}\)
    Yes Yes \(\binary{1}\) \(\binary{1}\)

    Leading to the state table in binary:

    Input = \(\binary{0}\) Input = \(\binary{1}\)
    Current Next Next
    \(s_1\) \(s_0\) \(s_1\) \(s_0\) \(s_1\) \(s_0\)
    \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\)
    \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\)
    \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\)
    \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\)

  3. We will use JK flip-flops for the circuit.

  4. Next we add columns to the binary state table showing the JK inputs required in order to cause the correct state transitions.

    Input = \(\binary{0}\) Input = \(\binary{1}\)
    Current Next Next
    \(s_1\) \(s_0\) \(s_1\) \(s_0\) \(J_1\) \(K_1\) \(J_0\) \(K_0\) \(s_1\) \(s_0\) \(J_1\) \(K_1\) \(J_0\) \(K_0\)
    \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{X}\) \(\binary{0}\) \(\binary{X}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{X}\) \(\binary{1}\) \(\binary{X}\)
    \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{X}\) \(\binary{X}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{X}\) \(\binary{X}\) \(\binary{0}\)
    \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{X}\) \(\binary{1}\) \(\binary{0}\) \(\binary{X}\) \(\binary{1}\) \(\binary{1}\) \(\binary{X}\) \(\binary{0}\) \(\binary{1}\) \(\binary{X}\)
    \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{X}\) \(\binary{0}\) \(\binary{X}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{X}\) \(\binary{0}\) \(\binary{X}\) \(\binary{0}\)

  5. We use Karnaugh maps to derive equations for the JK flip-flop inputs.

    This yields the functions:

    \begin{gather*} J_0(In,s_1,s_0) = In\\ K_0(In,s_1,s_0) = In'\\ J_1(In,s_1,s_0) = In \cdot s_0\\ K_1(In,s_1,s_0) = In' \cdot s_0' \end{gather*}

  6. The circuit to implement this predictor is: