ELEN 500 Advanced Logic Design

Homework Assignment 6

Due Thursday November 12, 1998

1. For the STGs in Figure 7.4 on page 258 of Chapter 7 find:

(a) For the diagram on the left, show that states S1 and S2 are equivalent by listing all possible urns and output sequences (of length 4) starting in S1 or S2. You may represent it in cubes if you prefer.

Solution:

Starting from S1
Input	Output	Run
0000	0000	S1 S2 S1 S2 S1
0001	0001	S1 S2 S1 S2 S4
0010	0010	S1 S2 S1 S4 S2
0011	0010	S1 S2 S1 S4 S3
0100	0100	S1 S2 S4 S2 S1
0101	0101	S1 S2 S4 S2 S4
0110	0100	S1 S2 S4 S3 S3
0111	0101	S1 S2 S4 S3 S1
1000	1000	S1 S4 S2 S1 S2
1001	1001	S1 S4 S2 S1 S4
1010	1010	S1 S4 S2 S4 S2
1011	1010	S1 S4 S2 S4 S3
1100	1000	S1 S4 S3 S3 S3
1101	1001	S1 S4 S3 S3 S1
1110	1010	S1 S4 S3 S1 S2
1111	1011	S1 S4 S3 S1 S4

Starting from S2
Input	Output	Run
0000	0000	S2 S1 S2 S1 S2
0001	0001	S2 S1 S2 S1 S4
0010	0010	S2 S1 S2 S4 S2
0011	0010	S2 S1 S2 S4 S3
0100	0100	S2 S1 S4 S2 S1
0101	0101	S2 S1 S4 S2 S4
0110	0100	S2 S1 S4 S3 S3
0111	0101	S2 S1 S4 S3 S1
1000	1000	S2 S4 S2 S1 S2
1001	1001	S2 S4 S2 S1 S4
1010	1010	S2 S4 S2 S4 S2
1011	1010	S2 S4 S2 S4 S3
1100	1000	S2 S4 S3 S3 S3
1101	1001	S2 S4 S3 S3 S1
1110	1010	S2 S4 S3 S1 S2
1111	1011	S2 S4 S3 S1 S4

(b) For the diagram on the right find a distinguishing sequence for each pair of states (S!, S3), (S1, S4) and (S1, S4) which might be three different sequences. For each sequence give the run (of states) and output sequences.

Solution:

Starting from S1
Input	Output	Run
000	000	S1 S1 S1 S1
001	001	S1 S1 S1 S4
010	010	S1 S1 S4 S1
011	010	S1 S1 S4 S3
100	100	S1 S4 S1 S1
101	101	S1 S4 S1 S4
110	100	S1 S4 S3 S3
111	101	S1 S4 S3 S1

Starting from S3
Input	Output	Run
000	000	S3 S3 S3 S3
001	001	S3 S3 S3 S1
010	010	S3 S3 S1 S1
011	011	S3 S3 S1 S4
100	100	S3 S1 S1 S1
101	101	S3 S1 S1 S4
110	110	S3 S1 S4 S1
111	110	S3 S1 S4 S3

Starting from S4
Input	Output	Run
000	000	S4 S1 S1 S1
001	001	S4 S1 S1 S4
010	010	S4 S1 S4 S1
011	010	S4 S1 S4 S3
100	000	S4 S3 S3 S3
101	001	S4 S3 S3 S1
110	010	S4 S3 S1 S1
111	011	S4 S3 S1 S4

To distinguish

(S1,S3)

011

110

111

(S1,S4)

100

101

110

111

(S3,S4)

011

100

101

110

111