Midterm 1 Review: Sequential Sequence Problems | CSCI 343

Original Document: Type of problems for Midterm 1 (Partial Solutions)

Topics covered on the exam

• Design problems using f/f
  • Counters
  • Self-correcting circuits
  • State tables, state diagrams, and circuit diagrams
• Master-Slave Flip-Flop
  • Use case and how it works
  • Given the clock and input signals in a timing diagram, determine the output of the master and slave f/f
• Be familiar with shift registers and general registers

Must know the characteristic tables for the different flip-flop types. You will be given the excitation tables.

Problem 1: Designing a Traffic Light

Design a Traffic Light using D Flip-Flops. Define 6 states (000 — 101):

state 0 (R/R) $\to$ state 1 (G/R) $\to$ state 2 (Y/R) $\to$ state 3 (R/R) $\to$ state 4 (R/G) $\to$ state 5 (R/Y)

 

Solution

We have 6 valid states encoded in 3 bits $ABC$: 000 through 101. States 110 and 111 are unused. The circuit has no external input — it simply cycles through the 6 states on each clock edge.

State Diagram:

Draw the state table:

The next state is fixed for each present state (no input variable), so the table has one row per state. The state sequence is given directly by the problem, so we fill in the $Q(t+1)$ columns first (the unused states can optionally be included, filled in as Don’t Cares):

$$\begin{array}{ccc|ccc|ccc} & Q(t) & & & Q(t{+}1) & & \text{f/f} & \text{Inputs} & \\ \hline A & B & C & A & B & C & D_A & D_B & D_C \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & & & \\ 0 & 0 & 1 & 0 & 1 & 0 & & & \\ 0 & 1 & 0 & 0 & 1 & 1 & & & \\ 0 & 1 & 1 & 1 & 0 & 0 & & & \\ 1 & 0 & 0 & 1 & 0 & 1 & & & \\ 1 & 0 & 1 & 0 & 0 & 0 & & & \\ \color{red}1 & \color{red}1 & \color{red}0 & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & X & X & X & X & X & X \\ \end{array}$$

Fill in the flip-flop inputs:

Use the D flip-flop excitation table to determine the $D$ input values that produce each next-state transition:

$$\begin{array}{cc|c} Q(t) & Q(t+1) & D \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array}$$

Tip

D Flip Flops are very simple to work with since their input is exactly the output: $D = Q(t+1)$. So we could avoid referencing the excitation table outright and simply copy over the $Q(t+1)$ values onto the f/f inputs.

$$\begin{array}{ccc|ccc|ccc} & Q(t) & & & Q(t{+}1) & & \text{f/f} & \text{Inputs} & \\ \hline A & B & C & A & B & C & D_A & D_B & D_C \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \color{red}1 & \color{red}1 & \color{red}0 & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & X & X & X & X & X & X \\ \end{array}$$

Derive the flip-flop input expressions:

Unused states ABC = 110 and 111 are treated as Don’t Care conditions on the K-maps:

$D_A:$

$$D_A = BC + AC'$$

$D_B:$

$$D_B = BC' + A'B'C$$

$D_C:$

$$D_C = C'$$

Extending the Circuitry

We can extend the circuitry by connecting the flip-flops to the traffic lights. Consider this cross-intersection traffic light, where both sides are controlled by the same flip-flops. To distinguish the lights on either side, we use subscripts: $R_1, Y_1, G_1$ for Side 1 and $R_2, Y_2, G_2$ for Side 2. Each state maps to a specific combination of active lights:

State	$ABC$	Side 1 / Side 2
0	000	$R_1 / R_2$
1	001	$G_1 / R_2$
2	010	$Y_1 / R_2$
3	011	$R_1 / R_2$
4	100	$R_1 / G_2$
5	101	$R_1 / Y_2$
6	110	unused
7	111	unused

We can connect the flip flops to the lights with a 3×8 decoder, which takes a 3-bit input — each flip flop A, B, C contributing 1 bit — and enables exactly one of its 8 outputs.

We’ll use $D_j$ to refer to decoder output $j$ — that is, the wire that is enabled when the current state is $j$. We can’t wire a decoder output directly to a light, because some lights need to be on across multiple states (e.g. $R_1$ is on in states 0, 3, 4, and 5). So those lights get an OR gate that combines the relevant decoder outputs for the states where that light should be on:

• $G_1 = D_1$
• $Y_1 = D_2$
• $R_1 = D_0 + D_3 + D_4 + D_5$ (red is on in states 0, 3, 4, 5)
• $G_2 = D_4$
• $Y_2 = D_5$
• $R_2 = D_0 + D_1 + D_2 + D_3$ (red is on in states 0, 1, 2, 3)

Decoder outputs $D_6$ and $D_7$ (for unused states 110 and 111) are left unconnected — they don’t feed into any light.

 

Problem 2: Traffic Light with Emergency State

Extend Problem 1 by adding an emergency state:

• RY blink:
  • for $x = 1$: go into emergency state
  • for $x = 0$: go into next state

Consider the emergency state to be 110. We now have 7 states (0 to 6) and a 4-variable table for ABC and X. From the emergency state, $x=1$ stays in emergency and $x=0$ resets to 000. You can also consider that by 0/1 stays in the emergency state — in that case you will get different expressions for the f/f inputs.

 

Solution

We now have 7 valid states (000—110) and one input $x$, making this a 4-variable problem. State 111 is the only unused state.

The problem statement gives us a design choice — we’ll go with the one that returns to 000 from the emergency state when $x = 0$.

Draw the state table:

Each state now has two rows — one for $x=0$ (normal cycling) and one for $x=1$ (go to emergency):

$$\begin{array}{ccc|c|ccc|ccc} & Q(t) & & \text{Input} & & Q(t{+}1) & & \text{f/f} & \text{Inputs} & \\ \hline A & B & C & x & A & B & C & D_A & D_B & D_C \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 1 & & & \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & & & \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & & & \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & & & \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & & & \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & & & \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & & & \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & & & \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & & & \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & & & \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & & & \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & & & \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & & & \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & & & \\ \color{red}1 & \color{red}1 & \color{red}1 & 0 & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & 1 & X & X & X & X & X & X \\ \end{array}$$

Fill in the flip-flop inputs:

Use the D flip-flop excitation table to determine the $D$ input values that produce each next-state transition:

$$\begin{array}{cc|c} Q(t) & Q(t+1) & D \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array}$$ $$\begin{array}{ccc|c|ccc|ccc} & Q(t) & & \text{Input} & & Q(t{+}1) & & \text{f/f} & \text{Inputs} & \\ \hline A & B & C & x & A & B & C & D_A & D_B & D_C \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ \color{red}1 & \color{red}1 & \color{red}1 & 0 & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & 1 & X & X & X & X & X & X \\ \end{array}$$

Derive the flip-flop input expressions:

Unused state ABC = 111 (both $x$ values) treated as Don’t Care conditions on the K-maps:

$D_A:$

$$D_A = x + BC + A B'C'$$

$D_B:$

$$D_B = x + A'B'C + A'BC'$$

$D_C:$

$$D_C = x'A'C' + x'B'C'$$

State Diagram:

Note

We could have drawn the state diagram as a first step since the problem statement gave us all the information necessary to design the transitions.

 

Problem 3: Sequential Circuit with Two D Flip-Flops

A sequential circuit with two D f/f, $A$ and $B$; two inputs, $x$ and $y$; and one output $Z$ is specified by the following next-state and output functions:

$$\begin{aligned} A(t+1) &= x'y + xA \\ B(t+1) &= x'B + xA \\ Z &= B \end{aligned}$$

• Draw the circuit
• Derive the state table
• Derive the state diagram

Solution

Draw the state table:

$$\begin{array}{cc|cc|cc|c} Q(t) & & \text{Inputs} & & Q(t{+}1) & & \text{Output} \\ \hline A & B & x & y & A & B & Z \\ \hline 0 & 0 & 0 & 0 & & & \\ 0 & 0 & 0 & 1 & & & \\ 0 & 0 & 1 & 0 & & & \\ 0 & 0 & 1 & 1 & & & \\ 0 & 1 & 0 & 0 & & & \\ 0 & 1 & 0 & 1 & & & \\ 0 & 1 & 1 & 0 & & & \\ 0 & 1 & 1 & 1 & & & \\ 1 & 0 & 0 & 0 & & & \\ 1 & 0 & 0 & 1 & & & \\ 1 & 0 & 1 & 0 & & & \\ 1 & 0 & 1 & 1 & & & \\ 1 & 1 & 0 & 0 & & & \\ 1 & 1 & 0 & 1 & & & \\ 1 & 1 & 1 & 0 & & & \\ 1 & 1 & 1 & 1 & & & \\ \end{array}$$

Since we’re given the next-state functions directly, we can evaluate $A(t+1)$, $B(t+1)$, and $Z$ for each row by substituting the present state and inputs:

$$\begin{array}{cc|cc|cc|c} Q(t) & & \text{Inputs} & & Q(t{+}1) & & \text{Output} \\ \hline A & B & x & y & A & B & Z \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array}$$

Draw the state diagram:

Each of the four present states $AB$ becomes a node. Since there are two inputs $x$ and $y$, each state has four outgoing edges labeled $xy/Z$:

Draw the circuit:

In general, drawing the circuit requires knowing the f/f input expressions. You would derive them by filling in the $D_A$ and $D_B$ columns of the state table using the D flip-flop excitation table, then working through the K-maps to derive the minimized expressions.

In this problem, however, the next-state functions $A(t+1)$ and $B(t+1)$ are given directly. Because a D flip-flop passes its input straight through to its output — that is, $D = Q(t+1)$ — the next-state function and the D input expression are one and the same. So the next-state expressions from the problem statement can be used directly as the D input expressions:

$$D_A = x'y + xA \qquad D_B = x'B + xA$$

 

Problem 4: Full Adder Connected to a D Flip-Flop

A sequential circuit has one f/f $Q$; two inputs, $x$ and $y$; and one output $S$. It consists of a full adder circuit connected to a D f/f. Derive the state table and state diagram of the sequential circuit.

Hint

When adding two binary numbers, we add them one bit at a time (by column) and the carry that is generated by that addition will be remembered for the next one.

Solution

The circuitry that we build here is the adding core of a serial adder: it takes one bit from each number ($x$ and $y$), produces their sum bit $S$, and passes the carry forward to the next pair.

Recall the Full Adder:

A full adder takes 3 inputs: two addends ($x$ and $y$) and the carry-in ($C_\text{in}$). Its outputs are the sum ($S$) and the carry-out ($C_\text{out}$).

Identify the role of the flip flop $Q$:

Each column’s addition produces a carry-out that has to be remembered, since it becomes the carry-in for the next column. So the circuit needs some way to hold onto a single bit of state between one addition and the next — and remembering a bit of state is exactly the job of a flip-flop. We feed the adder’s $C_{out}$ into the flip-flop, and on the next addition it reappears at the flip-flop’s output, ready to serve as the $C_{in}$ for that addition.

• The carry-in to the adder is the current flip-flop state, $Q$.
• The sum output of the adder is the circuit’s output $S$.
• We know that the carry-out will be used as the next addition’s carry-in. We also know that by the characteristics of a D flip flop ($D = Q(t+1)$), its input will be exactly its output (the next state). So we can just compute the carry generated by the current addition and feed it into the flip flop’s input, and it will be available again as the next carry-in.

Draw the state table:

There is one flip-flop, so only two present states, $Q = 0$ and $Q = 1$. Each is paired with the four combinations of the inputs $x$ and $y$:

$$\begin{array}{c|cc|c|c} Q(t) & \text{Inputs} & & Q(t{+}1) & \text{Output} \\ \hline C_{in} & x & y & & \\ \hline 0 & 0 & 0 & & \\ 0 & 0 & 1 & & \\ 0 & 1 & 0 & & \\ 0 & 1 & 1 & & \\ 1 & 0 & 0 & & \\ 1 & 0 & 1 & & \\ 1 & 1 & 0 & & \\ 1 & 1 & 1 & & \\ \end{array}$$

For each row, we add the three bits $C_\text{in} + x + y$ and split the 2-bit result across the two output columns:

• The sum bit goes into the output $S$.
• The carry bit is the $C_\text{out}$, which (as established above) is wired through the flip-flop to become the next state $Q(t+1)$. So we just compute the carry bit from each row’s addition and fill it into $Q(t+1)$.

$$\begin{array}{c|cc|c|c} Q(t) & \text{Inputs} & & D = Q(t{+}1) & \text{Output} \\ \hline C_{in} & x & y & C_{out} & S \\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array}$$

As a sanity check, the rows match what the full adder should produce: the next state (the carry-out) is $1$ exactly when at least two of $\{x, y, Q\}$ are $1$, and the output $S$ is the XOR of the three bits.

Draw the state diagram:

With a single flip-flop the diagram has just two nodes, $Q = 0$ and $Q = 1$, and each transition is labeled $xy/S$ following the rows of the table above. For example, from $Q = 0$ the inputs $xy = 11$ generate a carry and move the circuit to $Q = 1$ with output $S = 0$.

 

Problem 5: Self-Correcting Sequential Circuit Design

A sequential circuit has three f/f $A$, $B$, $C$; one input $x$; one output $y$.

• Design the circuit using D f/f, treating unused states as don’t care conditions
• Analyze if the circuit is self-correcting

Solution

The transitions in the diagram are in the format input/output: the first value indicates the input variable driving the transition, and the second indicates the output of the circuit.

Draw the state table:

The state diagram tells us plenty of information upfront: the valid states, invalid states (the missing states), $x$ input values that drive the transition for each state, and the output $y$ for each transition. Using that information, we fill the state table (the unused states can optionally be included, filled in as Don’t Cares):

$$\begin{array}{ccc|c|ccc|ccc|c} & Q(t) & & \text{Input} & & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & \text{Output} \\ \hline A & B & C & x & A & B & C & D_A & D_B & D_C & y \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1 & & & & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & & & & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & & & & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & & & & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & & & & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & & & & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & & & & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & & & & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & & & & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & & & & 0 \\ \color{red}1 & \color{red}0 & \color{red}1 & 0 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}0 & \color{red}1 & 1 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}0 & 0 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}0 & 1 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & 0 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & 1 & X & X & X & X & X & X & X \\ \end{array}$$

Fill in the f/f inputs

Use the D flip-flop excitation table to determine the specific values of $D_A$, $D_B$, $D_C$ that will produce the next state values:

$$\begin{array}{cc|c} Q(t) & Q(t+1) & D \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array}$$ $$\begin{array}{ccc|c|ccc|ccc|c} & Q(t) & & \text{Input} & & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & \text{Output} \\ \hline A & B & C & x & A & B & C & D_A & D_B & D_C & y \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ \color{red}1 & \color{red}0 & \color{red}1 & 0 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}0 & \color{red}1 & 1 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}0 & 0 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}0 & 1 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & 0 & X & X & X & X & X & X & X \\ \color{red}1 & \color{red}1 & \color{red}1 & 1 & X & X & X & X & X & X & X \\ \end{array}$$

Derive the flip-flop input expressions:

Unused states ABC = 101, 110, 111 treated as Don’t Care conditions on the K-maps:

$D_A:$

$$D_A = A'B'x$$

$D_B:$

$$D_B = A + C'x' + BCx$$

$D_C:$

$$D_C = Ax + Cx' + A'B'x'$$

$y:$

$$y = A'x$$

Check for self-correction:

We plug each unused state into the derived expressions and trace where the circuit goes next.

Unused state ABC = 101:

$$\begin{aligned} D_A &= A'B'x = 0 & &\Rightarrow A \text{ reset to } 0 \\ D_B &= C'x' + A + BCx = 0 + 1 + 0 = 1 & &\Rightarrow B \text{ set to } 1 \\ D_C &= A'B'x' + Cx' + Ax = 0 + x' + x = 1 & &\Rightarrow C \text{ set to } 1 \end{aligned}$$ $$101 \to 011$$

State 011 is valid, so the circuit self-corrects out of state 101.

Unused state ABC = 110:

$$\begin{aligned} D_A &= A'B'x = 0 & &\Rightarrow A \text{ reset to } 0 \\ D_B &= C'x' + A + BCx = x' + 1 + 0 = 1 & &\Rightarrow B \text{ set to } 1 \\ D_C &= A'B'x' + Cx' + Ax = 0 + 0 + x = x & & \Rightarrow C \text{ dependent on } x \\ \end{aligned}$$ $$110 \to 01?$$

Invalid state 110 could transition to either of two states, so now we check the two cases:

• $x = 0$:

$$D_C = x = 0 \quad\Rightarrow\quad C \text{ reset to } 0$$ $$110 \xrightarrow{0} 010$$

• $x = 1$:

$$D_C = x = 1 \quad\Rightarrow\quad C \text{ set to } 1$$ $$110 \xrightarrow{1} 011$$

Both states 010 and 011 are valid, so the circuit self-corrects out of state 110.

Unused state ABC = 111:

$$\begin{aligned} D_A &= A'B'x = 0 & &\Rightarrow A \text{ reset to } 0 \\ D_B &= C'x' + A + BCx = 0 + 1 + x = 1 & &\Rightarrow B \text{ set to } 1 \\ D_C &= A'B'x' + Cx' + Ax = 0 + x' + x = 1 & &\Rightarrow C \text{ set to } 1 \end{aligned}$$ $$111 \to 011$$

State 011 is valid, so the circuit self-corrects out of state 111.

All unused states transition to valid states regardless of input, so the circuit is self-correcting.

Note

On the exam, you may be asked to analyze only one of the unused states for self-correction due to time constraints.

 

Problem 6: JK Flip-Flop Sequential Circuit

A sequential circuit has 2 JK f/f, one input $x$, and one output $y$. The logic diagram is shown below. Derive the state table and state diagram.

Solution

Get the expression of the f/f inputs (based on present states and external input) by tracing through the given circuit diagram. Based on present state and f/f inputs, get the next state.

f/f input expressions and $y$ output expression:

$$\begin{aligned} J_A &= B & \qquad J_B &= (x \oplus A)' \\ K_A &= B' & \qquad K_B &= (x \oplus A)' \end{aligned}$$ $$y = x \oplus A \oplus B$$

Draw the state table:

$$\begin{array}{cc|c|cc|cccc|c} Q(t) & & \text{Input} & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & & Output \\ \hline A & B & x & A & B & J_A & K_A & J_B & K_B & y \\ \hline 0 & 0 & 0 & & & & & & & \\ 0 & 0 & 1 & & & & & & & \\ 0 & 1 & 0 & & & & & & & \\ 0 & 1 & 1 & & & & & & & \\ 1 & 0 & 0 & & & & & & & \\ 1 & 0 & 1 & & & & & & & \\ 1 & 1 & 0 & & & & & & & \\ 1 & 1 & 1 & & & & & & & \\ \end{array}$$

Fill in the flip-flop inputs:

The f/f inputs and the $y$ output are the first thing we can compute, since they depend only on the present state and $x$, which we already have.

$$\begin{array}{cc|c|cc|cccc|c} Q(t) & & \text{Input} & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & & Output \\ \hline A & B & x & A & B & J_A & K_A & J_B & K_B & y \\ \hline 0 & 0 & 0 & & & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & & & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & & & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & & & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & & & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & & & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & & & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & & & 1 & 0 & 1 & 1 & 1 \\ \end{array}$$

Determine the next state:

With the f/f inputs in hand, each flip-flop’s next state follows from how a JK flip-flop behaves in response to its J/K inputs, as described by the JK characteristic table:

$$\begin{array}{cc|c} J & K & Q(t+1) \\ \hline 0 & 0 & Q(t) \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & Q'(t) \\ \end{array}$$

Fill in the next state values:

$$\begin{array}{cc|c|cc|cccc|c} Q(t) & & \text{Input} & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & & Output \\ \hline A & B & x & A & B & J_A & K_A & J_B & K_B & y \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \end{array}$$

State Diagram:

Draw the state diagram based on the state table. Each of the four present states AB becomes a node with a directed edge leading to the next state. The edges are labeled in the form x/y, where $x$ is the input driving the transition and $y$ is the resulting output:

 

Problem 7: SR Flip-Flop Implementation of Problem 6’s Circuit

Using the same circuit diagram from Problem 6, assume that it uses SR flip flops rather than JK flip flops. Derive the state table.

Solution

The f/f input expressions are the same as Problem 6, but now mapped to SR inputs:

$$\begin{aligned} S_A &= B & \qquad S_B &= (x \oplus A)' \\ R_A &= B' & \qquad R_B &= (x \oplus A)' \end{aligned}$$ $$y = x \oplus A \oplus B$$

Draw the state table:

$$\begin{array}{cc|c|cc|cccc|c} Q(t) & & \text{Input} & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & & Output \\ \hline A & B & x & A & B & S_A & R_A & S_B & R_B & y \\ \hline 0 & 0 & 0 & & & & & & & \\ 0 & 0 & 1 & & & & & & & \\ 0 & 1 & 0 & & & & & & & \\ 0 & 1 & 1 & & & & & & & \\ 1 & 0 & 0 & & & & & & & \\ 1 & 0 & 1 & & & & & & & \\ 1 & 1 & 0 & & & & & & & \\ 1 & 1 & 1 & & & & & & & \\ \end{array}$$

Fill in the flip-flop inputs:

Determine the f/f inputs given the above expressions:

$$\begin{array}{cc|c|cc|cccc|c} Q(t) & & \text{Input} & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & & Output \\ \hline A & B & x & A & B & S_A & R_A & S_B & R_B & y \\ \hline 0 & 0 & 0 & & & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & & & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & & & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & & & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & & & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & & & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & & & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & & & 1 & 0 & 1 & 1 & 1 \\ \end{array}$$

Determine the next state:

Use the SR f/f characteristics table to determine the next state:

$$\begin{array}{cc|c} S & R & Q(t+1) \\ \hline 0 & 0 & Q(t) \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & \text{invalid} \\ \end{array}$$ $$\begin{array}{cc|c|cc|cccc|c} Q(t) & & \text{Input} & Q(t{+}1) & & \text{f/f} & \text{Inputs} & & & Output \\ \hline A & B & x & A & B & S_A & R_A & S_B & R_B & y \\ \hline 0 & 0 & 0 & 0 & \textcolor{#e73a73}{?} & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & \textcolor{#e73a73}{?} & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & \textcolor{#e73a73}{?} & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & \textcolor{#e73a73}{?} & 1 & 0 & 1 & 1 & 1 \\ \end{array}$$

For flip-flop $B$: there are four rows where both $S$ and $R$ are 1, making $B$‘s next state undefined. This is a fundamental limitation of SR flip-flops compared to JK flip-flops — the JK design eliminates this invalid condition by toggling when both inputs are $1$.