12. Sequential Circuit Design 12.1.

State Table/Diagram Specification

o Objectives o There is no algorithmic way to construct the state
This section deals with the design of sequential circuits table from a word description of the circuit. Instead,
including the following: we provide a few examples to illustrate the technique.
n A discussion of the construction of state/output tables or o It is convenient to group sequential circuits as to
diagrams from a word description or flow chart whether the
specification of sequential behavior
n generate sequences,
n A formal synthesis technique for realizing state tables and
diagrams n detect sequences, or
n A less formal technique based on transition equations
n transform sequences

o Reading Assignment
n Chapter 8, Sections 1-4, 6,7.

Elec 326 12.1 Sequential Circuit Design Elec 326 12.2 Sequential Circuit Design

o Sequence Generation: o Example: An arbitrary sequence generator

n Example: An up/down mod 6 counter: Six states and two
inputs X & Y. The inputs have the following effect:
XY = 00: Do nothing (no state changes)
XY = 01: Count up
XY = 11: Reset to state 0
XY = 10: Count down X
Q 0 1 Y2Y1Y0
00 01 11 10 0
0 1
1 2
3
2
4
3
5
4
6
5
7
Q*
Elec 326 12.3 Sequential Circuit Design Elec 326 12.4 Sequential Circuit Design

1
o Sequence detection n Alternative Solution
n Example: Detect an even number of 1s

1
0
0 0 1 1 0

n Example: Detect 00110 1

1 0
0 1

Elec 326 12.5 Sequential Circuit Design Elec 326 12.6 Sequential Circuit Design

o Alogrithmic State Machine (ASM) Charts

n Example: Universal length 4 sequence detector n This section illustrates the correspondence between flow charts and
u This one detects 1011 or 0101 or 0001 or 0111 state diagrams. Both provide a means of specifying sequence
generators.
n ASM Nodes:
State name

Output signals 0 (False) Conditional outputs

1 (True)
or actions Condition or actions (Mealy type)
expression
(Moore type)

(a) State box (b) Decision box (c) Conditional output box
o Sequence transformation u The state boxes correspond to the states of a state diagram.
n Serial binary adder (arbitrary length operands) u The decision boxes are used to designate the next state a given state

11/0 u For Moore outputs, the output signals that are asserted (= 1) for a given
00/0 01/0 state are listed in that state’s box.
01/1 0 1 10/0
10/1 11/1 u For Mealy outputs, the output signals that are asserted for a given state and
00/1 configuration of input signals are listed in a conditional output box.

Elec 326 12.7 Sequential Circuit Design Elec 326 12.8 Sequential Circuit Design

2
o Moore Model Example o Mealy Model Example
1
inputs: X,Y
A
1 outputs: A,B,C,D
1000
00,01 10,11 inputs: X,Y
1 outputs: A,B,C
0 1
X 2 3
1100 01 00 0011 --/100
2 3 11 10
00 01
A,B C,D 10 11 0-/110 2

0 4 1-/001 01/110
Y
1001
-0/010
1 C
4 00,01 11/101 3
5 10,11
A,D 5
0010
00,01 10,11

Elec 326 12.9 Sequential Circuit Design Elec 326 12.10 Sequential Circuit Design

12.2. Formal Sequential Circuit Synthesis o State Assignment

o Summary of Design Steps n Any assignment of Èlog2n˘ state variables will work, but
different ones can give radically different circuits.
n Assign state vectors to states; the state assignment problem u Example: mod 6 counter
n Construct the transition table
0 0 0
n Pick a flip-flop type for each state variable and use the flip- 1 1
flop’s application tables to construct an excitation table 0 1 2
1
1
n Derive excitation and output equations from the excitation 5
1
4
1
4
table. 0 0 0

n Construct a logic diagram from the excitation and output

equations.

Elec 326 12.11 Sequential Circuit Design Elec 326 12.12 Sequential Circuit Design

3
 n Number of possible state assignments:
u Assume we have k bits to encode n states (course k ≥ Èlog 2n˘ ). n There is no known way to get the best assignment other
Then we have m = 2 k possible state vectors. than trying every possible one, which is not practical.
u The number of ways to pick n of the m state vectors to encode the u Note that if took this approach we would have to do a complete
states is given by design for each assignment and compare all the resulting designs.

() n n!
m = m!•(n-m)!
n Guidelines for selecting good (but not necessarily optimal)
state assignments:
u Given m state vectors, we can pick any one for the first state, any u Choose 0…00 or 1…11 for the initial reset state.
one of the remaining m-1 for the second state, etc. In general we
can assign the m state vectors to states in m! ways. u Minimize the number of state variables that change on each
u Therefore the number of different state assignments for encoding n transition.
states with m state vectors (where m = 2 k) is
u Maximize the number of state variables that don’t change n a group
n! of related states (a group in which most transitions stay in the
• m!
m!•(n-m)! group)
u For n = 5 and m = 8 we have 6720 different possible state u Consider using more than the minimum number of state variables.
assignments. E.g., one-hot assignments.
u Trying all possible state assignments to find the best one is not an
option.

Elec 326 12.13 Sequential Circuit Design Elec 326 12.14 Sequential Circuit Design

o Example 2
o Construct the transition table from the state table or Q
XY
00 01 10
XY
00 01 10
state graph and the chosen state assignment. 0 - 000
0 0 1 5 0 0 1 1 - 001
n Example 1. 1 0 2 0 0 0 0 2 - 010
2 0 3 1 0 0 0 3 - 011
X 3 0 4 2 0 0 0 4 - 100
X Q1Q0 0 1 Y 4 0 5 3 0 0 0 5 - 101
Q 0 1 Y 5 0 0 4 0 1 0 State Assignment
A - 00 00 01 0 Q* Z
00
A A B 0 B - 01 01 00 10 0 State Table
B A C 0 C - 10 10 00 10 1
C A C 1 dd dd d XY XY
State Assignment 11 Q2Q1Q0 00 01 10 00 01 10
Q* Q*1Q*2
State Table Transition Table 000 000 001 101 0 0 1
001 000 010 000 0 0 0
010 000 011 001 0 0 0
011 000 100 010 0 0 0
100 000 101 011 0 0 0
101 000 000 100 0 1 0
110 ddd ddd ddd d d d
111 ddd ddd ddd d d d
Q*2Q*1Q*0 Z
Transition Table
Elec 326 12.15 Sequential Circuit Design Elec 326 12.16 Sequential Circuit Design

4
 o Select the Flip-Flop Type o Construct the Excitation Table
n The four main types of flip-flops are SR, D, T and JK. n Recall that the excitation table specifies the values for the
u The choice of flip-flop type can affect the complexity of the flip-flop input signals needed to cause the transitions in the
combinational logic in the resulting sequential circuit.
transition table.
u Of three common types, the most versatile is the JK, since it can be
easily converted into the other two. n Flip-Flop Application Table
l Any on can be converted into one of the other type, but some of these u These tables list the flip-flop inputs signals needed for each
conversions take more logic than others.
possible transition of the flip-flop’s state.
u The T flip-flop is the one most suitable for counters, since it usually
results in less logic than the other types.
l This is because extra logic internal to the flip-flop is exactly what is needed to
Q Æ Q* D Q Æ Q* SR Q Æ Q* T Q Æ Q* JK
implement counters.
0Æ0 0 0Æ0 0d 0Æ0 0 0Æ0 0d
u D flip-flops are the ones found in almost all PLDs. 0Æ1 1 0Æ1 1d 0Æ1 1 0Æ1 1d
l If your design is targetted for a PLD, you are usually stuck with D flip-flops. 1Æ0 0 1Æ0 d1 1Æ0 1 1Æ0 d1
1Æ1 1 1Æ1 d0 1Æ1 0 1Æ1 d0
D Flip-Flop SR Flip-Flop T Flip-Flop JK Flip-Flop

n Use these flip-flop application tables to convert a transition

table into an excitation table.
Elec 326 12.17 Sequential Circuit Design Elec 326 12.18 Sequential Circuit Design

n Example 1 n Example 2
u Chose JK flip-flops for both state variables to get the following: u For this example we chose a T flip-flop for Q 2, a D flip-flop for Q1
X X and a JK flip-flop for Q 0.
Q1Q0 0 1 Y Q1Q0 0 1 Y l While it is not usual to mix the flip-flop types in the same circuit, this example
shows that it is easy to do and provides an example of how to design with
00 00 01 0 00 0d 0d 0d 1d 0 these three flip-flop types.
01 00 10 0 01 0d d1 1d d1 0
10 00 10 1 10 d1 0d d0 0d 1
11 dd dd d 11 dd dd dd dd d XY XY XY XY
Q*1Q*2 J1K1J0K0 Q2Q1Q0 00 01 10 00 01 10 Q2Q1Q0 00 01 10 00 01 10
Transition Table Excitation Table
000 000 001 101 0 0 1 000 000 001 1d0d1d 0 0 1
001 000 010 000 0 0 0 001 001 010 0d0dd1 0 0 0
010 000 011 001 0 0 0 010 010 011 0dd11d 0 0 0
u Note the rather high percentage of don’t care entries. This is 011 000 100 010 0 0 0 011 011 100 0dd0d1 0 0 0
common with JK flip-flops. 100 000 101 011 0 0 0 100 100 101 d11d1d 0 0 0
101 000 000 100 0 1 0 101 101 000 d00d1d 0 1 0
u Note that had we used D flip-flops the transition table and 110 ddd ddd ddd d d d 110 ddd ddd dddddd d d d
excitation tables would have had the same entries. 111 ddd ddd ddd d d d 111 ddd ddd dddddd d d d
Q*2Q*1Q*0 Z T2D1J0K0 Z
Transition Table Excitation Table

Elec 326 12.19 Sequential Circuit Design Elec 326 12.20 Sequential Circuit Design

5
o Derive of Excitation and Output Equations n Example 1 X
n Since the flip-flop part of excitation table consistes of the Q1Q0 0 1 Y
truth tables for all the flip-flop input signals and the output 00 0d 0d 0d 1d 0
part consists of truth tables for all the output signals, the 01 0d d1 1d d1 0
design of sequential circuits has now been reduced to the 10 d1 0d d0 0d 1
11 dd dd dd dd d
design of some combinational circuits. J1K1J0K0
n Note that there are don’t care entries whenever Excitation Table

u There are fewer states than possible state vectors. J1 X K1 X J0 X K0 X Y X

0 0 d d 0 1 d d 0 0
u SR or JK flip-flops are used
0 1 d d d d 1 1 0 0
l Since truth tables with don’t care entries frequently result in circuit Q0 Q0 Q0 Q0 Q0
simplifications, this favors JK flip-flops. d d d d d d d d d d
Q1 Q1 Q1 Q1 Q1
d d 1 0 0 0 d d 1 1

J1 = X • Q0 K1 = X' J0 = X • Q1' K0 = 1 Y= Q1

n Example 2. Exercise.

Elec 326 12.21 Sequential Circuit Design Elec 326 12.22 Sequential Circuit Design

n Using JK flip-flops X
o Construct the logic diagram Q2 Q1 Q0 0 1

0 0 0 0x 0x 1x 0x 1x 0x
n Example 1 0
0
0
1
1
0
0x
0x
1x
x0
x1
1x
0x
1x
1x
x1
x0
0x
0 1 1 1x x1 x1 1x x1 x0
1 0 0 x0 0x 1x x0 1x 0x
1 0 1 x0 1x x1 x0 1x x0
1 1 0 x0 x0 1x x1 x1 0x
1 1 1 x1 x1 x1 x1 x1 x0

X J Q
QO J2 K2, J1 K1, J0 K0

J1 = X • Q0
K Q
K1 = X'
J0 = X • Q1' Q1
K0 = 1 J Q Y
Y= Q1 1 K Q

CK

n Example 2. Exercise.
J2 = K2 = Q0•Q1 + X•Q1 J1 = K1 = X + Q0 J0 = K0 = X'

Elec 326 12.23 Sequential Circuit Design Elec 326 12.24 Sequential Circuit Design

6
12.3. Transition Expressions and Lists n Verification that previous example satisfies constraints:
o Transition expressions are Boolean expressions used Node A: (X'•Y')•(X•Y') = 0
to label the edges of a state graph. When the (X'•Y')•Y = 0
expression is true the transition associated with that (X•Y')•Y =0
edge is taken. X'•Y' X'•Y' X'•Y' + X•Y' + Y = 1
n Example: Node B: (X'•Y')•(X'•Y) = 0
X•Y' (X'•Y')•X = 0
A B
X'•Y (X'•Y)•X = 0
Y X
X+Y X•Y' X'•Y' + X'•Y + X = 1
Node C: (X•Y)•(X•Y') = 0
D C
X•Y (X•Y)•X' = 0
X'•Y' X'
(X•Y')•X' = 0
o Requirements on edge labels: X•Y + X•Y' + X' = 1
n Mutual Exclusion: No two edges leaving a node can both Node D: (X'•Y') (X+Y) = 0
be active. (X'•Y') + (X+Y) = 1
n All Inclusion: The logical sum of the expressions must be
1.

Elec 326 12.25 Sequential Circuit Design Elec 326 12.26 Sequential Circuit Design

o Transition Lists o Synthesizing from Transition Lists

Q Q1,Q0 Trans. Exp. Q* Q1*,Q0*

Q Q1,Q0 Trans. Exp. Q* Q1*,Q0* A 00 X'•Y' A 00

A 00 X•Y' B 01
A 00 X'•Y' A 00 A 00 Y D 10
A 00 X•Y' B 01 B 01 X'•Y' B 01
B 01 X'•Y D 10
A 00 Y D 10 B 01 X C 11
B 01 X'•Y' B 01 C 11 X•Y D 10
C 11 X•Y' A 00
B 01 X'•Y D 10 C 11 X' C 11
B 01 X C 11 D 10 X'•Y' D 10
D 10 X+Y A 00
C 11 X•Y D 10
C 11 X•Y' A 00 Q0* = (Q=0)•X•Y' + (Q=1)•X'•Y' + (Q=1)•X + (Q=3)•X'
C 11 X' C 11 = Q1'•Q0'•X•Y' + Q1'•Q0•X'•Y' + Q1'•Q0•X + Q1•Q0•X'
D 10 X'•Y' D 10
D 10 X+Y A 00 Q1* = (Q=0)•Y + (Q=1)•X'•Y + (Q=1)•X + (Q=3)•X•Y + (Q=3)•X' + (Q=2)•X'•Y'

= Q1'•Q0'•Y + Q1'•Q0•X'•Y + Q1'•Q0•X + Q1•Q0•X•Y

+ Q1•Q0•X' + Q1•Q0'•X'•Y'
Elec 326 12.27 Sequential Circuit Design Elec 326 12.28 Sequential Circuit Design

7
12.4. Sequential Circuit Design With Sequential PLDs n Mealy Outputs:
u A function of inputs and flip-flop outputs
o General Structure u Stable tPD after input change and tCO +tPD after clock
Clock
n Moore Outputs:
D Q

Q
u A function of flip-flops only
D Q State u Stable tCO+t PD after clock
Q Variables

D Q
n Registered Moore Outputs
Q u Delayed one clock cycle, so equations must be modified.
Primary AND-OR Array l Assume out = /Q1*Q2 + /Q2*Q3
Inputs Mealy Outputs
l Assume Q1* = exp1, Q2* = exp2, Q3 = exp3
Moore Outputs l Then a registered version of out would be given by

D Q
rout := /exp1*exp2 + /exp2*exp3;
Q
Registered u Stable tCO after clock instead of tCO +tPD
Moore Outputs
D Q
u There are no glitches on a registered Moore output
Q

Elec 326 12.29 Sequential Circuit Design Elec 326 12.30 Sequential Circuit Design

12.5. Tips & Tricks

n Registered Moore outputs can be combined with state o Order the rows and columns of transition and excitation tables
variables with the proper state assignment in the same order as Karnaugh map rows and columns.
o Consider one-hot state assignments.
State State Assignment Output
A 000 00
B x10 10 12.6. Pitfalls
C x11 11 o Not using the same row ordering in excitation tables
D 100 00 and the corresponding Karnaugh maps.
o Using invalid transition equations.

Elec 326 12.31 Sequential Circuit Design Elec 326 12.32 Sequential Circuit Design

8
12.7. Review
o How to construct a state graph, state table or ASM
from a word description of a sequential circuit's
behavior.
o The formal technique for designing sequential circuits
consisting of the following steps:
n State assignment and construction of the transition table
n Selection of flip-flop type and construction of the excitation
table
n Derivation of the flip-flop input equations and output
equations from the excitation table
o The use of transition lists and expressions to simplify
the design of sequential circuits.

Elec 326 12.33 Sequential Circuit Design