Section7.4Designing Sequential Circuits
¶We will now consider a more general set of steps for designing sequential circuits. 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.
The following steps form a good method for a first working design:
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.
Choose a binary code for the states, and create a binarycoded 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.
Choose a particular type of flipflop. This choice is often dictated by the components you have on hand.
Add columns to the state table that show the input required to each flipflop in order to effect each transition that is required.
Simplify the input(s) to each flipflop. Karnaugh maps or algebraic methods are good tools for the simplification process.
Draw the circuit.
Here are two examples to illustrated this process.
Example7.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.

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.

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\) 
Since JK flipflops are very general we will use those.

We need two flipflops, one for each bit. So we add columns to the state table showing the input required to each JK flipflop 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 flipflop is so versatile, including the “don't cares” helps find simpler circuit realizations.

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*}

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 flipflop, 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 flipflop, remember that the state of the flipflop 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 assemblyline 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 decisionmaking 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.
Example7.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.

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 

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 highorder bit represents the prediction, and the loworder 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}\) 
We will use JK flipflops for the circuit.

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}\) 

We use Karnaugh maps to derive equations for the JK flipflop 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*}

The circuit to implement this predictor is: