IE1204 Digital Design
F12: Asynchronous
Sequential Circuits
(Part 1)
Masoumeh (Azin) Ebrahimi ([email protected])
Elena Dubrova ([email protected])
KTH / ICT / ES
• BV pp. 584-640
This lecture
IE1204 Digital Design, Autumn2016
Asynchronous Sequential
Machines
• An asynchronous sequential machine is
a sequential machine without flip-flops
• Asynchronous sequential machines are
constructed by analyzing combinational
logic circuits with feedback
• Assumption: Only one signal in a
circuit can change its value at any
time
IE1204 Digital Design, Autumn2016
Golden rule
IE1204 Digital Design, Autumn2016
Asynchronous state machines
• Asynchronous state machines are used
when it is necessary to keep the
information about a state, but no clock
is available
– All flip-flops and latches are asynchronous
state machines
– Useful to synchronize events in situations
where metastability is/can be a problem
IE1204 Digital Design, Autumn2016
• To analyze the behavior of an
asynchronous circuit, we use ideal
gates and summarize their delays to a
single block with delay Δ
Asynchronous sequential circuit:
SR-latch with NOR gates
IE1204 Digital Design, Autumn2016
R
S
Q
Y y
Delay
Ideal gates
(Delay = 0)
Q
a
R
S
SR-latch
• By using a delay block, we can treat
– y as the current state
– Y as the next state
Analysis of a sequential
asynchronous circuit
IE1204 Digital Design, Autumn2016
R
S
Q
Y y
• Thus, we can produce a state table where the
next state Y depends on the inputs and the
current state y
State table
IE1204 Digital Design, Autumn2016
R
S
Q
Y
y
)( ySRY ++=
State table
IE1204 Digital Design, Autumn2016
)( ySRY ++=
Present
Next
state
state
SR = 00
01 10 11
y
Y Y Y
Y
0 0 0 1 0
1 1 0 1 0
)11(10111
)11(01011
)10(10101
)10(01001
)01(10110
)01(11010
)00(10100
)00(00000
)(
++=
++=
++=
++=
++=
++=
++=
++=
++= ySRYRSy
From statefunction to
truth table
Note: BV uses this binary code
• Since we do not have flip-flops, but only
combinational circuits, a state change can cause
additional state changes
• A state is
– stable if Y(t) = y(t + Δ)
– unstable if Y(t) ≠ y(t + Δ)
Stable states
IE1204 Digital Design, Autumn2016
Present
Next
state
state
SR = 00
01 10 11
y
Y Y Y
Y
0 0 0 1 0
1 1 0 1 0
yY
=
stable
• Stable states (next state = present state) are
circled
Excitation table
IE1204 Digital Design, Autumn2016
Present
Next
state
state
SR = 00
01 10 11
y
Y Y Y
Y
0 0 0 1 0
1 1 0 1 0
R
S
Q
Y
y
0
0
0
1
0
R
S
Q
Y
y
1
0
0
0
1
• When dealing with asynchronous
sequential circuits, a different
terminology is used
– The state table called flow table
– The state-assigned state table is called
excitation table
Terminology
IE1204 Digital Design, Autumn2016
Flow table (Moore)
IE1204 Digital Design, Autumn2016
Present
Next state
Output
state
SR = 00
01 10
11
Q
A A A B A 0
B B A B A 1
10
00
11
01
00
10
A0
¤
B1
¤
11
01
SR
Flow Table (Mealy)
IE1204 Digital Design, Autumn2016
Present
Next state Output,Q
state
SR = 00
01 10
11 00 01 10 11
A A A B A 0 0 0
B B A B A 1 1
-
-
-
10/1
00/1
11/0
01/0
00/0
10 /-
A B
01-
¤
11-
¤
SR/ Q
Do not care ('-') has been chosen for output decoder since output changes
directly after the state transition (basic implementation)
Asynchronous Moore compatible
IE1204 Digital Design, Autumn2016
· Asynchronous sequential circuits have similar
structure as synchronous sequential circuits
· Instead of flip-flops one have a "delay block"
R
S
Q
Y
y
1
0
0
1
0
Asynchronous Mealy compatible
IE1204 Digital Design, Autumn2016
· Asynchronous sequential circuits have similar
structure as synchronous sequential circuits
· Instead of flip-flops one have a "delay block"
Analysis of Asynchronous Circuits
• The analysis is done using the following steps:
1) Replace the feedbacks in the circuit with a
delay element D. The input of the delay element
represents the next state Y while the output y
represents the current state.
2) Find out the next-state and output expressions
3) Set up the corresponding excitation table
4) Create a flow table and replace the encoded
states with symbolic states
5) Draw a state diagram if necessary
IE1204 Digital Design, Autumn2016
D-latch state function
IE1204 Digital Design, Autumn2016
Q
1D
C1
QD
C
Q
D
C
Y
y
CyCDY ×+×=
• Master-slave D flip-flop is designed
using two D-latches
Example
Master-slave D flip-flop
IE1204 Digital Design, Autumn2016
D
Clk
Q
Q
D
C
Q
y
s
y
m
Master Slave
Q
D
Clk
Q
Q
s
ss
mm
yQ
CyDCY
yCCDY
=
+=
+=
The equations for the next state:
• From these equations, we can directly
deduce excitation table
Excitation table
IE1204 Digital Design, Autumn2016
Present
Next
state
state
CD = 00
01 10 11
Output
y
m
y
s
Ym Y
s
Q
00 00 00 00 10 0
01 00 00 01 11 1
10 11 11 00 10 0
11 11 11 01 11 1
s
ss
mm
yQ
CyDCY
yCCDY
=
+=
+=
Excitation table
• We define four states S1, S2, S3, S4
and get the following flow table
Flow table
IE1204 Digital Design, Autumn2016
Present
Nextstate
Output
state
CD = 00 01 10
11
Q
S1 S1 S1 S1 S3 0
S2 S1 S1 S2 S4 1
S3 S4 S4 S1 S3 0
S4 S4S4 S2S4 1
Present
Next
state
state CD = 00 01 10 11
Output
y
m
y
s
Y
m
Y
s
Q
00 00 00 00 10 0
01 00 00 01 11 1
10 11 11 00 10 0
11 11110111 1
Excitation table
Flow table
• Remember: Only one input can be
changed simultaneously
• Thus, some transitions never occur!
Flow table
IE1204 Digital Design, Autumn2016
Present
Nextstate
Output
state
CD = 00
01 10 11
Q
S1 S1 S1 S1 S3 0
S2 S1 S1 S2 S4 1
S3 S4 S4 S1 S3 0
S4 S4S4 S2S4 1
• State S3
– The only stable state is S3 with input combination 11
– Only one input can be changed => possible transitions are (11 =>
01, 11 => 10)
• These transitions originate in S3!
• The input combination 00 in S3 is not possible!
• The input combination 00 is set to don’t care!
Flow table
(Impossible transitions)
IE1204 Digital Design, Autumn2016
Present
Nextstate
Output
state
CD = 00
01 10 11
Q
S1 S1S1S1S3 0
S2 S1 S1 S2 S4 1
S3 S4 S4 S1 S3 0
S4 S4S4S2S4 1
• State S2
– The only stable state is S2 with input combination 10
– Only one entry can be changed => possible transitions are (10 =>
11, 10 => 00)
• These transitions originate in S2!
• The input combination 01 in S2 is not possible!
• The input combination 01 is set to don’t care!
Flow table
(Impossible transitions)
IE1204 Digital Design, Autumn2016
Present
Next
state
Output
state
CD = 00 01 10
11
Q
S1 S1 S1 S1 S3 0
S2 S1 S2 S4 1
S3 S4 S1 S3 0
S4 S4S4S2S4 1
S1
-
State Diagram
Master-slave D flip-flop
IE1204 Digital Design, Autumn2016
x1
0x
10
11
S21
¤
S41
¤
10
11
x0
0x
11
S10
¤
S30
¤
10
0x0x
CD
Present
Next
state
Output
state
CD = 00 01 10
11
Q
S1 S1 S1 S1 S3 0
S2 S1 S2 S4 1
S3 S4 S1 S3 0
S4 S4S4 S2S4 1
-
-
Flow table
State diagram
Synthesis of asynchronous
circuits
• The synthesis is carried out using the following
steps:
1) Create a state diagram according to the functional
description
2) Create a flow table and reduce the number of states
if possible
3) Assign codes to the states and create excitations table
4) Determine expressions (transfer functions) for the
next state and outputs
5) Construct a circuit that implements the above
expressions
IE1204 Digital Design, Autumn2016
• Input x
• Output z
• z = 1 if the number of pulses applied to x is odd
• z = 0 if the number of pulses applied to x is even
Example: Serial Parity Generator
Step 1: Create a state diagram
IE1204 Digital Design, Autumn2016
A/0 B/1
D/0 C/1
x = 0
x = 1
x = 1
x = 0
x = 0
x = 1
x = 1
x = 0
A/0
B/1
C/1
D/0
A/0
1 0
x
z
odd
even
Step 2: Flow table
Pres
state
Next State z
x=0 x=1
A A B 0
B C B 1
C C D 1
D A D 0
IE1204 Digital Design, Autumn2016
Flow table
State diagram
Step 3: Assign state codes
Pres
state
Next State z
x=0 x=1
A A B 0
B C B 1
C C D 1
D A D 0
IE1204 Digital Design, Autumn2016
Flow table
Excitation table
Pres
state
Next State z
x=0 x=1
y
2
y
1
Y
2
Y
1
00 00 01 0
01 10 01 1
10 10 11 1
11 00 11 0
A:00, B:01, C:10, D:11 - binary code?
Which encoding is good?
Step 3: Assign state codes
Which encoding is good?
IE1204 Digital Design, Autumn2016
Next State
Pres
state
X=0 1
Q
y
2
y
1
Y
2
Y
1
00 00 01 0
01 10 01 1
10 10 11 1
11 00 11 0
Bad encoding (HD=2!)
Suppose
X = 1 Y
2
Y
1
= 11
Then
X ® 0 ® Y
2
Y
1
= 00?
11 ® 10!
11 ® 01 ® 10! ? ® 00
We will never reach 00?
Assume à A:00, B:01, C:10, D:11
Step 3: Assign state codes
Which encoding is good?
Pres
state
Next State z
x=0 x=1
y
2
y
1
Y
2
Y
1
00 00 01 0
01 10 01 1
10 10 11 1
11 00 11 0
Pres
state
Next State z
x=0 x=1
y
2
y
1
Y
2
Y
1
00 00 01 0
01 11 01 1
11 11 10 1
10 00 10 0
Poor encoding (HD = 2)
If we are in 11 under input w = 1 and
input change to w = 0, the circuit
should change to 00
Good encoding (HD = 1)
IE1204 Digital Design, Autumn2016
A:00, B:01, C:11, D:10
A:00, B:01, C:10, D:11
Step 4:
Draw Karnaugh maps
Pres
state
Next State z
x=0 x=1
y
2
y
1
Y
2
Y
1
00 00 01 0
01 11 01 1
11 11 10 1
10 00 10 0
Y
2
= xy
1
+ y
2
y
1
+ xy
2
0 1 1 0
0 0 1 1
y
2
y
1
x 00 01 11 10
0
1
0 1 1 0
1 1 0 0
y
2
y
1
x 00 01 11 10
0
1
Y
1
= xy
2
+y
2
y
1
+ xy
1
0 1
0 1
y
1
y
2
0
1
0 1
z = y
1
IE1204 Digital Design, Autumn2016
They red circles are needed to avoid hazards (see later Section)!
What is a Hazard?
• Hazard is a term that means that there is a
danger that the output value is not stable, but
it can have glitches at certain input
combinations
• Hazard occurs when paths from different
inputs to the output have different lengths
• To avoid this, we must add implicants to
cover the ”dangerous” transitions
IE1204 Digital Design, Autumn2016
Examples of hazard: MUX
0 1 1 0
0 0 1 1
x 00 01 11 10
0
1
Y
2
= x y
1
+ y
2
y
1
+ x y
2
Q
x
y
1
y
2
Q
x
y
1
y
2
During the transition from the (xy
2
y
1
) = (111) to (011), the output Q has
a glitch, as the path from x to Q is longer through the upper AND gate
than through the lower AND gate (racing).
MORE ABOUT hazard in the next lecture!
IE1204 Digital Design, Autumn2016
y
2
y
1
Step 5: Complete circuit
0 1 1 0
0 0 1 1
y
2
y
1
x 00 01 11 10
0
1
0 1 1 0
1 1 0 0
y
2
y
1
x 00 01 11 10
0
1
Y
1
= xy
2
+y
2
y
1
+xy
1
0 1
0 1
y
1
y
2
0
1
0 1
z = y
1
IE1204 Digital Design, Autumn2016
Y
2
= x y
1
+ y
2
y
1
+ x y
2
y
2
y
1
z
x
• In asynchronous sequential circuits, it is impossible to
guarantee that the two state variables change value
simultaneously
– Thus, a transition 00 => 11 results in
• a transition 00 => 01 => ???
• a transition 00 => 10 => ???
• To ensure correct operation, all state transitions
MUST have Hamming distance 1
– The Hamming distance is the number of bits in which two
binary numbers differ
• Hamming distance between 00 and 11 is 2
• Hamming distance between 00 and 01 is 1
More on state encoding
IE1204 Digital Design, Autumn2016
State encoding
• Procedure to obtain good codes:
1) Draw the transition diagram along the
edges of the hypercube defined by the
codes
2) Remove any crossing lines by
a) swapping two adjacent nodes
b) exploiting available unused states
c) introducing more dimensions in the hypercube
IE1204 Digital Design, Autumn2016
State encoding
Example: Serial Parity Generator
C = 10 D = 11
A = 00 B = 01
x = 1
x = 1
x = 0 x = 0
Poor coding -
Hamming Distance = 2
(Intersecting lines)
IE1204 Digital Design, Autumn2016
Pres
state
Next State z
x=0 x=1
y
2
y
1
Y
2
Y
1
00 00 01 0
01 10 01 1
10 10 11 1
11 00 11 0
10
11
00
01
A:00, B:01, C:10, D:11
State encoding
Example: Serial Parity Generator
D = 10 C = 11
A = 00 B = 01
x = 1
x = 1
x = 0 x = 0
Good coding
Hamming Distance = 1
(No intersecting lines)
IE1204 Digital Design, Autumn2016
Pres
state
Next State z
x=0 x=1
y
2
y
1
Y
2
Y
1
00 00 01 0
01 11 01 1
11 11 10 1
10 00 10 0
A:00, B:01, C:11, D:10
10
11
00
01
swapping two adjacent nodes
State encoding
Exploiting unused states
C = 10
A = 00 B = 01
01
01
00
10
Poor coding
00
IE1204 Digital Design, Autumn2016
Present
Nextstate
Output
state
r2r1 = 00
01 10 11
g
2
g
1
A A B C 00
B A B C B 01
C A B C C 10
-
In the transition from B to C (or C to B) has the Hamming distance 2!
Danger to get stuck in an unspecified state (with code 11)!
Flow table from Fig. 9.21a of BV textbook
10
11
00
01
Note: BV uses this binary code
• Solution: Introduce a transition state that
ensures that you do not end up in an
unspecified state!
State encoding
Exploiting aunused states
IE1204 Digital Design, Autumn2016
Good coding
C = 10
A = 00 B = 01
01
01
00
10
00
01
10
Present
Next
state
state
r
2
r
1
= 00
01
Output
y
2
y
1
Y
2
Y
1
g
2
g
1
A 00 00 01 00
B 01 0 0 01 01
D 11 01
dd
-
C 10 00 11 10
11
01
-
-
10
10
10
11
10
10
Transition state
Present
Nextstate
Output
state
r
2
r
1
=000111
10
g
2
g
1
A A B
C
00
B A B
C
B
01
C A B
CC
10
-
D = 11
exploiting available unused states
• One can increase the number of dimensions
in order to implement stable state transitions
State encoding: Additional states
(more dimensions)
IE1204 Digital Design, Autumn2016
A B
D C
C, F
A B
D E
G
A B
D C
G
E F
If it is not possible to redraw a diagram for HD = 1, we can add more states
by adding extra dimensions. We take the nearest largest
hypercube and draw the transitions through the available non steady
states.
more dimensions
State encoding: Additional states
(more dimensions)
IE1204 Digital Design, Autumn2016
• It's easier to draw a "flat" 3D cube
(perspective, is then from the front)
000
100
010
110
101
011
111
001
011
111
000
100
010
110
001
101
State minimization
• Procedure for minimizing the number of states
1. Form equivalence classes
2. Minimize equivalence classes (state reduction)
3. Form state diagrams either for Mealy or Moore
4. Merge compatible states in classes. Minimize the number
of classes simultaneously. Each state can only belong to
one classes
5. Construct the reduced flow table by merging rows in the
selected classes
6. Repeat steps 3-5 to see if more minimizations can be done
IE1204 Digital Design, Autumn2016
• Candy machine has two inputs:
– N: nickel (5 cents)
– D: dime (10 cents)
• A candy bar costs 10 cents
• The machine will not return any change if
there is 15 cents in the candy machine (a
candy bar returned)
• The output z is active if there is enough
money for a piece of candy
Example
Candy Machine (BV page 610)
IE1204 Digital Design, Autumn2016
State Diagram and Flow Chart
Pres
state
Next State z
X=00 01 10 11
A A B C - 0
B DB - - 0
C A- C - 1
D DE F - 0
E AE - - 1
F A- F - 1
A flow table that contains only
one stable state per row is called
primitive flow table.
IE1204 Digital Design, Autumn2016
(X = DN)
A/0
0
B/0N
N
C/1D
D
D/0
0
E/1N
N
F/1D
D
0
0
0 0
0 means N=D=0,
i.e. no coin is
deposited
· You can’t insert two coins at the same time!
State Diagram and Flow Chart
IE1204 Digital Design, Autumn2016
A/0
0
B/0
N
N
C/1
D
D
D/0
0
E/1
N
N
F/1
D
D
0
0
0 0
0 means N=D=0,
i.e. no coin is
deposited
State Minimization means that
two states may be equivalent,
and if so, replaced by one state
to simplify the state diagram,
and network.
One can easily see that state C
and F could be replaced by one
state, as a candy always be
ejected after a Dime regardless
of previous state.
1. Forming equivalence classes. To be in the same
class, the following should hold for states:
– Outputs must have the same value
– Stable states must be at the same positions
– Don’t cares for next state must be in the same positions
2. Minimize equivalence classes (state-reduction)
Step 1: Form and minimize
equivalence classes
IE1204 Digital Design, Autumn2016
State reduction
Next State Q
Pres
state
X=00
01
10 11
A
A
BC - 0
B
D
B- - 0
C
A
-C - 1
D
D
EF - 0
E
A
E- - 1
F
A
-F - 1
Primitive flow table
IE1204 Digital Design, Autumn2016
• Outputs must have the same
value
• Stable states must be at the same
positions
• Don’t cares for next state must be
in the same positions
P
2
= (AD)(B)(CF)(E)
P
2
= (AD)(B)(CF)(E)
P
1
= (ABD)(CEF)
State reduction
IE1204 Digital Design, Autumn2016
P
2
= (AD)(B)(CF)(E)
P
3
= (A)(D)(B)(CF)(E)
P
3
= P
4
• Successors must be in the same class
C,F
00
® (AD), (AD)
C,F
01
® -, -
C,F
10
® (CF), (CF)
C,F
11
® -, -
A,D
00
® (AD), (AD)
A,D
01
® (B),(E)
A,D
10
® (CF), (CF)
A,D
11
® -, -
Next State QPres
state
01
10 11
A
A
BC - 0
B
D
B- - 0
C
A
-C - 1
D
D
EF - 0
E
A
E- - 1
F
A
-F - 1
Primitive flow table
Next State Q
Pres
state
X=00
01
10 11
A
A
BC - 0
B DB- - 0
C A-C - 1
D
D
EC - 0
E
A
E- - 1
Resulting flow table
3. Construct state diagram either for Mealy or Moore
4. Merge compatible states in groups. Minimize the
number of groups simultaneously. Each state may
belong to one group only.
5. Construct the reduced flow table by merging rows in
the selected groups
6. Repeat steps 3-5 to see if more minimizations can
be done
Step 2:
Merging states
IE1204 Digital Design, Autumn2016
• Two states are compatible and can be
merged if the following applies
1. at least one of the following conditions apply to
all input combinations
• both S
i
and S
j
have the same successor, or
• both S
i
and S
j
are stable, or
• the successor of S
i
or S
j
, or both, is unspecified
2. For a Moore machine, in addition the following
should hold
• both S
i
and S
j
have the same output values whenever
specified (not necessary for a Mealy machine)
Merging states
IE1204 Digital Design, Autumn2016
Merging states
Next State Q
Pres
state
X=00
01
10 11
A
A
BC - 0
B DB- - 0
C A-C - 1
D
D
EC - 0
E
A
E- - 1
Resulting flow table
C
A
E
B D
Compatibility graph
Mealy-compatible: In state A (X = 00) the
output is 0, in state C the output is 1
Moore
compatible
Each row will be a point
in a compatibility graph
IE1204 Digital Design, Autumn2016
• both S
i
and S
j
have the same successor, or
• both S
i
and S
j
are stable, or
• the successor of S
i
or S
j
, or both, is unspecified
Moreover, both S
i
and S
j
must have the same output
whenever specified
An illustrative example
Primitive flow table
Pres
state
Next State Q
X=00 01 10 11
A A F C - 0
B AB - H 1
C G- C D 0
D -F - D 1
E G- E D 1
F -F - K 0
G GB J - 0
H -L E H 1
J G- J - 0
K -B E K 1
L AL - K 1
P
1
= (AG) (BL) (C) (D) (E) (F) (HK) (J)
P
2
= (A) (G) (BL) (C) (D) (E) (F) (HK) (J)
P
3
= P
2
Equivalence classes
Pres
state
Next State Q
X=00 01 10 11
A A F C - 0
B AB - H 1
C G- C D 0
D -F - D 1
E G- E D 1
F -F - H 0
G GB J - 0
H -B E H 1
J G - J - 0
Reduced flow table
IE1204 Digital Design, Autumn2016
An illustrative example (cont'd)
Next State Q
Pres
state
X=00
01
10 11
A AFC - 0
B
A
B- H 1
C
G
-C D 0
D -F- D 1
E
G
-E D 1
F
-
F- H 0
G
G
BJ - 0
H
-
BE H 1
J
G
-J - 0
Reduced flow table
IE1204 Digital Design, Autumn2016
B A C D
H F J G E
Next State QPres
state
X=00
01
10 11
A AAC B 0
B ABD B 1
C G-C D 0
D GAD D 1
G GBG - 0
An illustrative example (cont'd)
Reduced flow table
Next State Q
Pres
state
X=00
01
10 11
A AAC B 0
B ABD B 1
C G-C D 0
D GAD D 1
G GBG - 0
Final flow table
Next State Q
Pres
state
X=00
01
10 11
A
A
AC B 0
B ABD B 1
C CBC D 0
D
C
AD D 1
IE1204 Digital Design, Autumn2016
B A D C G
Summary
• Asynchronous state machines
– Based on analysis of combinational circuits with feedback
– All flip-flops and latches are asynchronous state machines
• A similar theory as for synchronous state
machines can be applied
– Only one input or state variable can be changed at a time!
– We must also take into account the problem with hazards
• Next lecture: BV pp. 640-648, 723-724
IE1204 Digital Design, Autumn2016