Chapter 9

Asynchronous Sequential Logic

9-1

Outline

Analysis Procedure
Circuits with Latches
Asynchronous Sequential Circuits
Design Procedure
Reduction of State and Flow Tables
Race-Free State Assignment
Hazards
Design Example
9-2

1
 Sequential Circuits
Consist of a combinational circuit to which storage elements are connected to form a feedback p
Specified by a time sequence of inputs, outputs, and internal states
Two types of sequential circuits:
Synchronous

Asynchronous primary difference

9-3

Synchronous vs. Asynchronous

Asynchronous sequential circuits
Internal states can change at any instant of time when there is a change in the input variables
No clock signal is required
Have better performance but hard to design due to timing problems

Synchronous sequential circuits

Synchronized by a periodic train of clock pulses
Much easier to design (preferred design style)

9-4
 Why Asynchronous Circuits ?
Used when speed of operation is important
Response quickly without waiting for a clock pulse
Used in small independent systems
Only a few components are required
Used when the input signals may change independently of internal clock
Asynchronous in nature
Used in the communication between two units that have their own independent cl
Must be done in an asynchronous fashion

Definitions of Asyn. Circuits

Inputs / Outputs
Delay elements:
Only a short term memory
May not really exist due to original gate delay
Secondary variable:
Current state (small y)
Excitation variable:
Next state (big Y)
Have some delay in response to input changes
9-6
Operational Mode
Steady-state condition:
Current states and next states are the same
Difference between Y and y will cause a transition
Fundamental mode:
No simultaneous changes of two or more variables
The time between two input changes must be longer than the time it takes the circuit to a stable
The input signals change one at a time and only when the circuit is in a stable condition

Outline
Asynchronous Sequential Circuits

Circuits with Latches
Design Procedure
Analysis Procedure
Reduction of State and Flow Tables
Race-Free State Assignment
Hazards
Design Example
9-8
Transition Table
Transition table is useful to analyze an asynchronous circuit from the circuit diagram
Procedure to obtain transition table:
Determine all feedback loops in the circuits
Mark the input (yi) and output (Yi) of each feedback loop
Derive the Boolean functions of all Y’s
Plot each Y function in a map and combine all maps into one table
Circle those values of Y in each square that are equal to the value of y in the same row

An Example of Transition Table

feedback
Y1 = xy1 + x’y2 Y2 = xy’1 + x’y2
feedback
Y = Y1Y2

inputs

current states

stable !!

9-10
 State Table
When input x changes from 0 to 1 while y=00:
Y changes to 01 € unstable
y becomes 01 after a short delay € stable at the second row
The next state is Y=01
Each row must have at least one stable state
Analyze each state in this way can obtain its state table

y1y2x : total state

4 stable total states: 000,011,
110,101
Present Next State 9-11

State X=0 X=1

0 0 0 0 0 1
0 1 1 1 0 1
1 0 0 0 1 0
1 1 1 1 1 0

Flow Table
Similar to a transition table except the states are represented by letter symbols
Can also include the output values
Suitable to obtain the logic diagram from it
Primitive flow table: only one stable state in each row (ex: 9-4(a))

Equivalent to 9-3(c) if a=00, b=01, c=11, d=10

9-12
 Flow Table to Circuits
Procedure to obtain circuits from flow table:
Assign to each state a distinct binary value (convert to a transition table)
Obtain circuits from the map
Two difficulties:
The binary state assignment (to avoid race)
The output assigned to the unstable states

Ex: from the flow table 9-4(b)

9-13

Race Conditions
Race condition:
two or more binary state variables will change value when one input variable changes
Cannot predict state sequence if unequal delay is encountered
Non-critical race:
The final stable state does not depend on the change order of state variables
Critical race:
The change order of state variables will result in different stable states
Should be avoided !!
9-14
 Race-Free State Assignment
Race can be avoided by proper state assignment
Direct the circuit through intermediate unstable states with a unique state-variable change
It is said to have a cycle
Must ensure that a cycle will terminate with a stable state
Otherwise, the circuit will keep going in unstable states
More details will be discussed in Section 9-6
9-15
 Outline
Asynchronous Sequential Circuits
Analysis Procedure

Design Procedure
Reduction
withofLatches
State and Flow Tables
Circuits
Race-Free State Assignment
Hazards
Design Example
9-17

Latches in Asynchronous Circuits

The traditional configuration of asynchronous circuits is using one or more feedback loops
No real delay elements
It is more convenient to employ the SR latch as a memory element in asynchronous circuits
Produce an orderly pattern in the logic diagram with the memory elements clearly visible
SR latch is also an asynchronous circuit
Will be analyzed first using the method for asynchronous circuits
9-18
SR Latch with NOR Gates

S=1, R=1 (SR = 1)

should not be used
feedback  SR = 0 is normal mode

* should be carefully checked first9-19

SR Latch with NAND Gates

S=0, R=0 (S’R’ = 1)

should not be used
feedback  S’R’ = 0 is normal mode

* should be carefully checked first 9-20

 Analysis Procedure
Procedure to analyze an asynchronous sequential circuits with SR latches:
Label each latch output with Yi and its external feedback path (if any) with yi
Derive the Boolean functions for each Si and Ri
Check whether SR=0 (NOR latch) or S’R’=0 (NAND latch) is satisfied
Evaluate Y=S+R’y (NOR latch) or Y=S’+Ry (NAND latch)
Construct the transition table for Y=Y1Y2…Yk
Circle all stable states where Y=y
9-21

Analysis Example
S1=x1y2 R1=x’1x’2  S1R1 = x1y2x’1x’2 = 0 (OK) S2=x1x2 R2=x’2y1  S2R2 = x1x2x’2y1 =Y10=S 1 + R’1y1
(OK)
=x1y2 + (x1+x2)y1
=x1y2+x1y1+x2y1
Y2=S2 + R’2y2
=x1x2 + (x2+y’1)y2
=x1x2+x2y2+y’1y2

feedback

critical race !! 9-22

 Implementation Procedure
Procedure to implement an asynchronous sequential circuits with SR latches:
Given a transition table that specifies the excitation function Y = Y1Y2…Yk, derive a pair of maps f
Derive the Boolean functions for each Si and Ri
(do not to make Si and Ri equal to 1 in the same minterm square)
Draw the logic diagram using k latches together with the gates required to generate the S and R

Implementation Example
Excitation table: list the required S and R for each possible transition from y to Y

y = 1 (outside) € 0 (inside)
 S=0, R=1 from excitation table 9-24
Debounce Circuit
Mechanical switches are often used to generate binary signals to a digital circuit
It may vibrate or bounce several times before going to a final rest
Cause the signal to oscillate between 1 and 0
A debounce circuit can remove the series of pulses from a contact bounce and produce a single s
Position A (SR=01) € bouncing (SR=11) € Position B (SR=10) Q = 1 (set) € Q = 1 (no change) € Q = 0 (reset)

Outline
Asynchronous Sequential Circuits
Analysis Procedure
Circuits with Latches

Reduction of State and Flow Tables
Race-Free State Assignment
Design Procedure
Hazards
Design Example
9-26
Design Procedure
Obtain a primitive flow table from the given design specifications
Reduce the flow table by merging rows in the primitive flow table
Assign binary state variables to each row of the reduced flow to obtain the transition tabl
Assign output values to the dashes associated with the unstable states to obtain the outp
Simplify the Boolean functions of the excitation and output variables and draw the logic d

Input Output

a
Primitive Flow Table
State D
0
G
1
Q
0
Comments
D=Q because G=1
b Design1 example:
1 1gatedD=Q
latchbecause G=1
c Accept0 the 0value of D
0 when G=1states a or d
After
d Retain1 this 0value after
0 G goes to state
After 0 (D chas no effects now)
e Obtain1 the 0 flow table
1 After states
by listing all b orpossible
f states
f Dash marks
0 0 are given
1 whenAfter state e
both inputs change simultaneously
Outputs of unstable states are don’t care

9-28
 Reduce the Flow Table
Two or more rows can be merged into one row if there are
non-conflicting states and outputs in every columns
After merged into one row:
Don’t care entries are overwritten
Stable states and output values are included
A common symbol is given to the merged row
Formal reduction procedure is given in next section
9-29
 Implementation with SR Latch
Listed according to the transition table and the excitation table of SR latch

9-31

Outputs for Unstable States

Objective: no momentary false outputs occur when the circuit switches between stable states
If the output value is not changed, the intermediate unstable state must have the same output value
0 € 1 (unstable) € 0 (X)

0
0 € 0 (unstable) € 0 (O)
If the output value changed, the intermediate outputs are don’t care
It makes no difference when the output change occurs
1

9-32
 Outline
Asynchronous Sequential Circuits
Analysis Procedure
Circuits with Latches
Design Procedure

Race-Free State Assignment
Hazards
Reduction of State and Flow Tables
Design Example
9-33

State Reduction
Present
Two states are equivalent if they have the same output and go to Next(equivalent)
the same State Output
next states for each possible inpu
x: (a,b) are equivalent (c,d) are equivalent State x=0 x=1 x=0 x=1
a c b 0 1
State reduction procedure is similar in both sync. & async. sequential circuits
b d a 0 1
or completely specified state tables:
c a d 1 0
use implication table
d b d 1 0
or incompletely specified state tables:
use compatible pairs
9-3
 Implication Table Method (1/2)
Step 1: build the implication chart
ab iff de
bc since outputs are not equivalent
d and e are the same
Present Next State Output
State x=0 x=1 x=0 x=1
a d b 0 0
b e a 0 0
c g f 0 1
d a d 1 0
e a d 1 0
f c b 0 0
g a e 1 0

9-35

Implication Table Method (2/2)

Step 2: delete the node with unsatisfied conditions
Step 3: repeat Step 2 until equivalent states found
af because cd

equivalent states :
(a,b) (d,e) (d,g) (e,g)
bf because ce
d == e == g
Present Next State Output
State x=0 x=1 x=0 x=1
a d a 0 0
c d f 0 1
d a d 1 0
f c a 0 0

*Reduced State Table*9-36

 Merge the Flow Table
The state table may be incompletely specified
Some next states and outputs are don’t care
Primitive flow tables are always incompletely specified
Several synchronous circuits also have this property
Incompletely specified states are not “equivalent”
Instead, we are going to find “compatible” states
Two states are compatible if they have the same output
and compatible next states whenever specified
Three procedural steps:
Determine all compatible pairs
Find the maximal compatibles
Find a minimal closed collection of compatibles
9-37

Compatible Pairs
 Implication tables are used to find compatible states
 We can adjust the dashes to fit any desired condition
 Must have no conflict in the output values to be merged
compatible pairs :
(a,b) (a,c) (a,d)
(b,e) (b,f)
(c,d) (e,f)

output output
conflict ! conflict !

9-38
 Maximal Compatibles
A group of compatibles that contains all the possible combinations of compatible states
Obtained from a merger diagram
A line in the diagram represents that two states are compatible
n-state compatible € n-sided fully connected polygon
All its diagonals connected
Not all maximal compatibles are necessary
9-39

Closed Covering Condition

The set of chosen compatibles must cover all the states and must be closed
Closed covering
The closure condition is satisfied if
There are no implied states
The implied states are included within the set
Ex: if remove (a,b) in the right
(a,c,d) (b,e,f) are left in the set
All six states are still included
No implied states according to its implication table 9-23(b)

9-40
Closed Covering Example

*(a,b) (c,d,e) € (X) implied (b,c) is not included in the set

* better choice: (a,d) (b,c) (c,d,e) all implied states

are included 9-41

Outline
Asynchronous Sequential Circuits
Analysis Procedure
Circuits with Latches
Design Procedure
Reduction of State and Flow Tables

Hazards
Design Example
Race-Free State Assignment 9-42
Race-Free State Assignment
Objective: choose a proper binary state assignment to
prevent critical races
Only one variable can change at any given time when a state transition occurs
States between which transitions occur will be given
adjacent assignments
Two binary values are said to be adjacent if they differ in only one variable
To ensure that a transition table has no critical races, every possible state transition should be ch
A tedious work when the flow table is large
Only 3-row and 4-row examples are demonstrated

3-Row Flow Table Example (1/2)

Three states require two binary variables
Outputs are omitted for simplicity
Adjacent info. are represented by a transition diagram
a and c are still not adjacent in such an assignment !!
Impossible to make all states adjacent if only 3 states are used

b has a transition to c

9-44
 3-Row Flow Table Example (2/2)
 A race-free assignment can be obtained if we add an
extra row to the flow table
 Only provide a race-free transition between the stable states
 The transition from a to c must now go through d
 00 € 10 € 11 (no race condition)

don’t care but cannot be 10

(cannot stable) 9-45

4-Row Flow Table Example (1/2)

Sometimes, just one extra row may not be sufficient to prevent critical races
More binary state variables may also required
With one or two diagonal transitions, there is no way of using two binary variables that satisfy all adjacency

9-46
 4-Row Flow Table Example (2/2)
still has only 4 stable states

9-47

Multiple-Row Method
Multiple-row method is easier
May not as efficient as in above
shared-row method
Each stable state is duplicated with exactly the same output
Behaviors are still the same
While choosing the next states, choose the adjacent one

can be used to any 4-row flow table

9-48
 Outline
Asynchronous Sequential Circuits
Analysis Procedure
Circuits with Latches
Design Procedure
Reduction of State and Flow Tables
Race-Free State Assignment

Design Example
9-49

Hazards

Hazards
Unwanted switching appears at the output of a circuit
Due to different propagation delay in different paths
May cause the circuit to mal-function
Cause temporary false-output values in combinational circuits
Cause a transition to a wrong state in asynchronous circuits
Not a concern to synchronous sequential circuits
Three types of hazards:

9-50
 Circuits with Hazards
Static hazard: a momentary output change when no output change should occur
If implemented in sum of products:
no static 1-hazard € no static 0-hazard or dynamic hazard
Two examples for static 1-hazard:

 
Œ
 Œ 


ŒŒ

9-51

Hazard-Free Circuit
Hazard can be detected by inspecting the map
The change of input results in a change of covered product term
€ Hazard exists
Ex: 111 € 101 in (a)
To eliminate the hazard, enclose the two minterms in another product term
Results in redundant gates

Redundant !!
9-52
Remove Hazard with Latches
Implement the asynchronous circuit with SR latches can also remove static hazards
A momentary 0 has no effects to the S and R inputs of a NOR latch
A momentary 1 has no effects to the S and R
inputs of a NAND latchReplaced by a latch

Hazards exist !!
9-53

Implementation with SR Latches

Given:
S = AB + CD R = A’C
For NAND latch, use complemented inputs
S’ = (AB + CD)’Merged !!
= (AB)’(CD)’
R’ = (A’C)’
Q = (Q’S)’
= [Q’(AB)’(CD)’]’
€ Two-level circuits
(this is the output we want)

9-54
Essential Hazards
Besides static and dynamic hazards, another type of hazard in asynchronous circuit
Caused by unequal delays along two or more paths that originate from the same in
Cannot be corrected by adding redundant gates
Can only be corrected by adjusting the amount of delay in the affected path
Each feedback path should be examined carefully !!

Outline
Asynchronous Sequential Circuits
Analysis Procedure
Circuits with Latches
Design Procedure
Reduction of State and Flow Tables
Race-Free State Assignment
Hazards


9-56

Design Example
 Recommended Design Procedure
State the design specifications
Derive a primitive flow table
Reduce the flow table by merging the rows
Make a race-free binary state assignment
Obtain the transition table and output map
Obtain the logic diagram using SR latches
9-57

Primitive Flow Table

 Design a negative-edge-triggered
T flip-flop
 Two inputs: T(toggle) and C(clock)
 T=1: toggle, T=0: no change
 One output: Q
Input Output
State T C Q Comments
a 1 1 0 Initial output is 0
b 1 0 1 After state a
c 1 1 1 Initial output is 1
d 1 0 0 After state c
e 0 0 0 After states d or f
f 0 1 0 After states e or a
g 0 0 1 After states b or h
h 0 1 1 After states g or c 9-58
Merging the Flow Table
Compatible pairs:
(a,f) (b,g) (b,h) (c,h)
(d,e) (d,f) (e,f) (g,h)
Maximal compatible set:
(a,f) (b,g,h) (c,h) (d,e,f)
abcd

9-59
Logic Diagram

9-61