Homework Assignment 10 Solutions
1) We must first introduce feedback variables around which to organize
the analysis of this asynchronous feedback circuit. Drawn in Figure 1 is
one such choice of feedback variables. The buffers represent delays in
commiting new values for the feedback variables (P_{i} where i
e {1, 2, 3}) to the feedback variable (Q_{i
}where i e {1, 2, 3}).
We may now think of the circuit
as a combinational logic taking as inputs the Q_{i} and X
and generating outputs P_{i} and Z, where the outputs P_{i}
are fed back into the combinational logic after a delay to the inputs Q_{i}
(much like our picture of a synchronous sequential logic but with delay
buffers in place of flipflops). The combinational circuit at the core
of the system's behavior may then be drawn as in Figure 2.
We may now immediately extract from
the above circuit the following minterm equations:
P_{1} = ((Q_{2}
nand Q_{3}) nand Q_{1})
nand X = ( (not Q_{3})*
Q_{2}) + ((not Q_{2})
* Q_{1}) + (not X))
P_{2} = not(X * P_{1}
* ( Q_{3} nand Q_{2}))
=
(not X) + (X*(not Q_{1})
+ (X*Q_{2}*Q_{3})
+ (X*(not Q_{1})*Q_{3})
+ (X*(not Q_{1})*Q_{2})
+ (Q_{2}*Q_{3})
Z= P_{3}=not(P_{2}*(not
(P_{1}*Q_{3})))
= ( (not Q_{2})*Q_{1}*Q_{3})
+ ( (not X)*Q_{3}) +
(X*Q_{1}*(not Q_{2})*(not
Q_{3}))
The Karnaugh Maps are then as follows,
where the bold and italicized cells represent stable total states:
Karnaugh map for P_{1}
XQ_{1}
Q_{2}Q_{3}

00

01

11

10

00

1

1

1

0

01

1

1

1

0

11

1

1

0

0

10

1

1

1

0

Karnaugh map for P_{2}
XQ_{1}
Q_{2}Q_{3}

00

01

11

10

00

1

1

0

1

01

1

1

0

1

11

1

1

1

1

10

1

1

0

1

Karnaugh map for P_{3}=Z
XQ_{1}
Q_{2}Q_{3}

00

01

11

10

00

0

0

1

0

01

1

1

1

0

11

1

1

0

0

10

0

0

1

0 
This makes the computation of the state
and output sequences corresponding to a given input sequence rather transparent
Flow table starting with the unique stable X=0
and Z=0 total state(bold and italics means stable).
Q_{1}Q_{2}Q_{3}

X

0

1

110

110;0

101;1

101

111;1

101;1

111

111;1

010;0

010

110;0

010;0

So, starting with stable X=0 and Z=0
and subsequently <X>=<0, 1, 0, 1, ...> (with transitions in X consistent
with the fundamental mode assumption), we get the following sequence (ignoring
any race conditions) for internal state and output:
<Q_{1}Q_{2}Q_{3}Z>
= < 1100, 1000, 1011, 1111, 0100 ...>
where the ellipsis here means we
henceforth see repetitions of the sequence seen so far repeated.
b) For Q_{1}Q_{2}Q_{3}=111
and X=0, a transition of X to 1 makes, supposedly,
Q_{1}Q_{2}Q_{3} go from 111 >
010. This is a two variable transition. Under the fundamental mode assumption,
we will actually first see either
Q_{1}Q_{2}Q_{3}: 111 >
110 or Q_{1}Q_{2}Q_{3}:
111 > 011. We
furthermore cannot say which of these transitions will occur, as this
is determined (if it is deterministic) by the technology dependent timing
of the circuit. Looking at the Karnaugh maps, we see that the internal
state will subsequently stabilize at 100 or 010, as X:0>1
causes either
Q_{1}Q_{2}Q_{3}: 111 >
110 >100 or
Q_{1}Q_{2}Q_{3}: 111 >
011 >010.
This is therefore a critical race, as, we have shown, $
an input sequence such that $
two distinct sequences of resulting
stable states. The behavior of this asynchronous state machine is therefore
left undetermined.
2a) First pass at Compatibility diagram,
where X means the states are ostensibly incompatible (which is to
say the outputs are different) and Y that the states are ostensibly compatible
(which is to say outputs and next states are identical):
2

6~4 5~3

3

X

X

4

X

X

Y

5

Y

6~4 5~3

X

X

6

Y

6~4 5~3

X

X

Y

7

X

X

6~4 5~3

6~4 5~3

X

X

8

X

X

5~3

5~3

X

X

6~4


1

2

3

4

5

6

7

As there is an "X" in cell (3, 5) and there is an "X" in cell (4, 6),
the next pass completes the reduction:
2

X

3

X

X

4

X

X

Y

5

Y

X

X

X

6

Y

X

X

X

Y

7

X

X

X

X

X

X

8

X

X

X

X

X

X

X


1

2

3

4

5

6

7

So the compatibilities are 1~5~6, 3~4. The reduced table is therefore
X_{1}X_{2}

Z

00

01

11

10

1

6

5

2

0

1

4

3

2

0

8

4

3

7

1

8

6

5

7

1

8

4

5

7

1

c) This one is pretty straight forward:
Merged Flow Table
Q_{1}Q_{2}

AB

00

01

11

10

00

1

7

8

2

11

3

5

6

4

01

3

7

8

2

10

3

7

6

4

Glitchfree output assignment
AB

00

01

11

10

1

0



1

0

1









1

1

0



0

1
