Asynchronous Sequential

Circuits
 Asynch. vs. Synch.
Asynchronous circuits dont use
clock pulses
State transitions by changes in inputs
Storage Elements:
Clockless storage elements or
Delay elements
In many cases, as combinational
feedback
Normally much harder to design

2
Asynch. Sequential Circuit

x1 z1
x2 z2
inputs outputs
Combinational
xn zm
Circuit
y1 Y1
y2 Y2 Next
Current
State
State yk Yk

delay

delay

delay

3
 Asynch. Sequential Circuit
yi = Yi in steady state (but may be
different during transition)
Simultaneous change in two (or
more) inputs is prohibited.
The time between two changes must
be less than the time of stability.

4
 Advantages and Disadvantages

Advantages:
Low power
High performance
No need for clock
Disadvantages:
Complexity of design process

5
 Analysis

y1
x Y1

y2
Y2

1. Find feedback loops and name feedback variables appropriately.

2. Find boolean expressions of Yis in terms of yis and inputs.
Y1 = x.y1 + x.y2
Y2 = x.y1 + x.y2
6
 Analysis
3. Draw a map:
rows: yis
columns: inputs
entries: Yis
x x x
y1 y2 0 1 y1 y2 0 1 y1 y2 0 1

00 0 0 00 0 1 00 00 01

01 1 0 01 1 1 01 11 01

11 1 1 11 1 0 11 11 10

10 0 1 10 0 0 10 00 10

Y1 = x.y1 + x.y2 Y2 = x.y1 + x.y2 (Transition Table) Y1 Y2

7
 Analysis
4. To have a stable state, Y must be = y
(circled) 0
x
1y1 y2

00 00 01

01 11 01

(Transition Table) Y1 Y2
11 11 10

10 00 10

At y1y2x = 000, if x: 0 1
then Y1Y2: 00 01
then y1y2 = 01 (2nd row): stable
8
 Analysis
In general, if an input takes the circuit to
an unstable state, yis change until a
stable state is found.
x
y1 y2 0 1

00 00 01

01 11 01
General state of circuit:
11 11 10
y1y2x:
There are 4 stable states: 10 00 10

000, 011, 110, 101

and 4 unstable states.
9
 State Table
As synchronous:
next state
present
state X 0 X 1

00 00 01
01 11 01
10 00 10
11 11 10

10
 Flow Table
As Transition Table (but with symbolic states):
x
0 1

a a b

b c b

c c d

d a d

11
 Flow Table: Example 2
Two states, two inputs, one output.
x1 x2
00 01 11 10

a a ,0 a ,0 a ,0 b ,0

b a ,0 a ,0 b ,1 b ,0

Each row has more than one stable state.

If x1 = 0, state is a.
If x1x2 = 00 x1x2 = 10, then state becomes b.
For x1x2 = 11, state is either a or b.
If previously in x1x2 = 01, keeps state a,
If previously in x1x2 = 10, keeps state b.
Reminder: cannot go from 00 to 11. 12
 Circuit Design
From flow table to circuit:
Assign a unique binary value to each state,
x1 x2 x1 x2
00 01 11 10 00 01 11 10
y
a a ,0 a ,0 a ,0 b ,0 0 0 ,0 0 ,0 0 ,0 1 ,0

b a ,0 a ,0 b ,1 b ,0 1 0 ,0 0 ,0 1 ,1 1 ,0

x1 x2 x1 x2
00 01 11 10 00 01 11 10
y y
0 0 0 0 1 0 0 0 0 0

1 0 0 1 1 1 0 0 1 0

Map for Y (=x1x2+x1y) Map for output z (=x1x2y)

13
 Circuit Diagram

z = x1x2y
x1
x2 Y
Y = x1x2+x1y

14
 Race Condition
If two (or more) state variables
change in response to a change in
an input, there is a race condition.
E.g. from 00 to 11, due to delays
00 01 11 OR
00 10 11.

Critical Race:
If final steady state depends on the
order of changes in state vars.

15
 Race: Examples
Noncritical Cases:
x x
y 1y 2 0 1
y1y2 0 1

00 00 11 00 00 11

01 11 01 01

11 11 11 01

10 11 10 11

00 11 00 11 01
00 01 11 00 01
00 10 11 00 10 11 01

16
 Race: Examples

Critical Cases:
x x
y 1y 2 0 1
y1y2 0 1

00 00 11 00 00 11

01 11 01 01

11 11 11 11

10 10 10 10

00 11 00 11
00 01 11 00 01
00 10 00 10

17
 Instability

x1 Y
x2 Y = (x1 y) x2
x1 x2
00 01 11 10
y
0 0 1 1 0
For x1x2 = 11, there is no steady state.
Oscillation.
1 0 1 0 0
For x1x2 = 11, Y = y unstable.

18
THE END
20
21
22
23
 No-Race State Assignment
Must assign binary values to states such that:
one change in an input may not cause two changes in state variables.
because, due to delays, one of the variable change sooner and may stay in
an unwanted stable state.
From a, if x1x2 = 10 11, must go to c and stay there.
But by the following assignment, it may go to b and stay there.

x1 x2
00 01
00 01 11 10
a b
a a b c a

b a b b c

c a c c c c
11
a and b must be different in one bit,
a and c must be different in one bit.
24
 No-Race State Assignment
Impossible add one more row.
x1 x2
00 01 11 10

a a b d a

b a b b c
00 01
c d c c c a b
d a - c -

d is an intermediate c
(unstable) state.
d
10 11
- means any value can be
assigned (Except d=10).
25
 Example 2
x1 x2
00 01 11 10
00 01
a b a d a
a b
b b d b a

c c a b c

d c d d c d c
10 11

If there were no diagonal transition, it would be

possible
Impossible add some more rows.

26
 Example 2 y1 y2
x1 x2 00 01 11 10
00 01 11 10 y3
0 a b c g
a = 000 b a e a
1 e d f 0
b = 001 b d b a

c = 011 c g b c b is adjacent to a, c, d
c a through g
g = 010 - a - -
a d through e
110 - - - - d c through f
00 01
f = 111 c - - c
a b
d = 101 f d d f

e = 100 - - d -

d c
27
10 11