Unit 15 Solutions
189
15.25 (c) (cont.)
00 01 11 10
00
01
0
0
0
0
1
1
0
0
X Q1
Q2 Q300 01 11 10
00
01
0
0
0
0
0
0
1
0
X Q1
Q2 Q300 01 11 10
00
01
0
0
1
1
0
1
1
0
X Q1
Q2 Q3
Q1
Q2 Q30 1
00
01
1
1
0
0
00 01 11 10
00
01
0
0
X
X
1
1
X
X
X Q1
Q2 Q300 01 11 10
00
01
0
0
0
0
0
0
1
0
X Q1
Q2 Q3
00 01 11 10
00
01
X
X
1
1
X
X
1
1
X Q1
Q2 Q300 01 11 10
00
01
X
X
X
X
X
X
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
0
X
1
X
0
X
1
X
X Q1
Q2 Q300 01 11 10
00
01
X
1
X
0
X
0
X
1
X Q1
Q2 Q3
15.25 (d)
B I-B
C-I
C I-C
C-G
B-C
I-G
D
E I-D
C-E
A ≡ I
B ≡ H
D ≡ F
15.26 (a) Present
State
Next State
X = 0 1
Output
A A C1
B B A1
C C G1
D A C0
E D E0
Unit 15 Solutions
190
15.26 (b) 1. (A, D)×2
2. (A, C)×2 (A, B) (C, G) (D, E)×2
3. (A, B, C) (D, E, G)
Q1
Q2 Q30 1
15.26 (d)
00 01 11 10
00
01
0
0
X
X
0
1
X
X
X Q1
Q2 Q300 01 11 10
00
01
0
0
0
1
0
0
0
0
X Q1
Q2 Q300 01 11 10
00
01
0
X
0
X
1
X
1
X
X Q1
Q2 Q3
00 01 11 10
00
01
X
X
1
0
X
X
1
0
X Q1
Q2 Q300 01 11 10
00
01
X
X
X
X
X
X
X
X
X Q1
Q2 Q300 01 11 10
00
01
X
0
X
1
X
0
X
1
X Q1
Q2 Q3
Again, Z = Q1
‘:
Q1Q2Q3
Q1
+Q2
+Q3
+
X = 0 1
Z
000 000 001 1
010 010 000 1
15.26 (c)
00 01 11 10
00
01
0
0
0
1
0
1
0
1
X Q1
Q2 Q300 01 11 10
00
01
0
0
0
1
0
0
0
0
X Q1
Q2 Q3
00 01 11 10
00
01
0
1
0
0
1
1
1
0
X Q1
Q2 Q3
Q1
Q2 Q30 1
00
01
1
1
0
0
Unit 15 Solutions
191
Present
State
Next State
X = 0 1
Output
X = 0 X = 1
S0 S1 S4 0 0
S1 S1 S2 0 0
15.27 (a) 1. (S0, S1, S5) (S0, S2, S4) (S1, S3, S5)
2. (S1, S4) (S1, S2)×2 (S3, S4)×2 (S2, S5)
3. (S0, S1, S3, S4)
S0 = 000. S1 = 010, S2 = 011, S3 = 101, S4 = 001,
S5 = 110
00 01 11 10
00
01
1
X
1
X
X Q1
Q2 Q300 01 11 10
00
01
1
X
1
X
1
X Q1
Q2 Q300 01 11 10
00
01
1
X
1
1
X
1
X Q1
Q2 Q3
00 01 11 10
00
01
X
X
X
X
X
1
R1 = X + Q3‘
X Q1
Q2 Q300 01 11 10
00
01
X
X
X
X
X
R2 = Q2Q3
X Q1
Q2 Q300 01 11 10
00
01
X
X
1
X
R3 = X’Q1
X Q1
Q2 Q3
00 01 11 10
00
01
1
X
X
X
X Q1
Q2 Q300 01 11 10
00
01
1
X
1
X
1
X Q1
Q2 Q300 01 11 10
00
01
X
X
1
X
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
X
X
X Q1
Q2 Q3
One alternative assignment:
Q
Q Q
00 01 11 10
1
2 3
S0
Q
Q Q 0 1
00
1
2 3
15.27 (b)
D1 = XQ1
‘Q2
‘ + Q2 + X’Q1Q3
‘; D2 = X; D3 = X’Q2‘
Z = X’Q1
‘Q2 + XQ1Q3
(a)
Unit 15 Solutions
192
1. (S2, S3) (S4, S5) (S0, S2) (S1, S5)
2. (S1, S2) (S0, S5) (S1, S3) (S3, S4)×2 (S0, S4)
S0 = 000, S1 = 001, S2 = 010, S3 = 110, S4 = 111,
S5 = 011
Present
State
Next State
X = 0 1
Z
S0 S2 S10
Q1Q2Q3
Q1
+Q2
+Q3
+
X = 0 1
Z
000 010 001 0
0
Q
Q Q
0
00 01 11 10
23
3
1 2
15.28
00 01 11 10
00
01
0
0
X
X
0
0
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
1
1
X
X
0
0
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
0
X
X
X
1
X
X
X
X Q1
Q2 Q3
00 01 11 10
00
X
X
X
X
K1 = 0
X Q1
Q2 Q3
00 01 11 10
00
01
X
X
X
X
X
X
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
X
0
X
X
X
1
X
X
X Q1
Q2 Q3
Q1+
X Q1
Q2 Q300 01 11 10
00
01
0
0
X
X
0
0
X
X
00 01 11 10
00
01
1
1
X
X
0
0
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
0
1
X
X
1
0
X
X
X Q1
Q2 Q3
00 01 11 10
00
0
X
0
X
T1 = X’Q1‘Q2
X Q1
Q2 Q3
00 01 11 10
00
01
1
1
X
X
0
0
X
X
X Q1
Q2 Q3
00 01 11 10
00
01
0
0
X
X
1
1
X
X
X Q1
Q2 Q3
15.28 (a) 15.28 (b)
Unit 15 Solutions
193
15.29 See solutions to 14.22 for the state table.
I. (S0, S1, S7) (S2, S6) (S3, S4, S5) (S0, S6) (S1, S7)
(S2, S3, S5)
II. (S1, S6) (S6, S7) (S1, S2)×2 (S3, S7) (S3, S4)×2
(S4, S5)
Q1Q2Q3
Q1
+Q2
+Q3
+
X = 0 1
Z
X = 0 X = 1
000 001 100 00 00
001 001 110 00 00
15.30 See FLD p. 761 for the state table.
I. (S0, S1) (S2, S3) (S4, S5, S7) (S0, S2, S3) (S1, S4)
(S5, S6, S7)
II. (S1, S3) (S1, S2) (S3, S4)×2 (S2, S5) (S5, S6)×2
(S6, S7)
Q1Q2Q3
Q1
+Q2
+Q3
+
X = 0 1
Z
X = 0 X = 1
000 001 011 00 00
001 001 010 00 00
X Q
Q Q 00 01 11 10
00
01
0
0
0
1
1
1
1
0
1
2 3 00 01 11 10
00
01
1
1
0
1
0
0
0
1
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
0
0
0
0
0
1
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
1
1
0
1
0
1
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
0
0
0
0
0
0
X Q
Q Q
1
2 3
Unit 15 Solutions
15.30 (cont.)
15.31
Present
State
Next State
00 01 11 10 Z
S0 S0 S1 S1 S00
S3 S2 S3 S2 S31
See p. 158 in this manual for the state
table.
I. (S0, S1)×3 (S2, S3)×2 (S0, S2) (S1, S3)
Q1Q2
Q1
+Q2
+
00 01 11 10
Z
00 00 01 01 00 0
11 10 11 10 11 1
S0
Q
Q 0 1
0
1S1
S2
S3
1
2
00 01 11 10
00
01
0
0
1
1
1
1
0
1
X X
Q Q2
2
1
1
0
Q
Q 0 1
0
10
1
1
1
2
X Q
Q Q 00 01 11 10
00
01
0
0
X
X
0
0
X
X
1
2 3
00 01 11 10
00
01
1
X
1
X
1
X
0
X
X Q
Q Q
1
2 3
00 01 11 10
00
01
X
X
0
0
X
X
0
0
X Q
Q Q
1
2 3
00 01 11 10
00
01
X
X
X
X
X
X
X
X
X Q
Q Q
1
2 3
00 01 11 10
00
01
X
0
X
1
X
1
X
1
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
1
1
0
0
1
1
X Q
Q Q
1
2 3
00 01 11 10
00
0
0
1
0
X Q
Q Q
1
2 3
00 01 11 10
00
01
1
1
1
0
1
0
0
0
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
0
0
0
0
0
0
X Q
Q Q
1
2 3
00 01 11 10
00
0
0
0
0
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
0
1
1
1
0
0
X Q
Q Q
1
2 3
00 01 11 10
00
01
0
0
0
0
0
0
0
1
X X
Q Q2
2
1
1
Row reduction of the solution to 14.6 given on FLD p. 762 easily gives 4 states. Renaming them gives:
Unit 15 Solutions
195
15.32 See answers to 14.23 for the state table.
The four-state table is minimum.
I. (S0, S1)×3 (S0, S3) (S1, S2) (S2, S3)×3
Q1Q2
Q1
+Q2
+
00 01 11 10
Z
00 01 01 00 00 0
15.33
Present
State
Next State
W = 0 1
Z
0 1
0 1 3 0 0
1 3 5 0 0
2 4 7 1 0
ABC
A+B+C+
W = 0 1
Z
0 1
000 001 011 0 0
001 011 101 0 0
010 100 111 1 0
0 ≡ 1 ≡ 3 ≡ 5
Q1
0 1
Q2
0
Q1
0 1
0
1
Q2
00 01 11 10
00
01
0
0
1
0
0
1
1
0
W A
B C
00 01 11 10
00
01
0
1
1
0
1
0
1
0
W A
B C
00 01 11 10
00
01
1
1
1
0
1
1
0
1
W A
B C
00 01 11 10
00
01
0
0
0
1
0
1
0
1
W A
B C
00 01 11 10
00
01
0
1
1
0
1
0
1
0
W A
B C
00 01 11 10
00
01
1
0
1
1
1
0
0
0
W A
B C
X X
Q Q 00 01 11 10
00
01
0
0
0
0
0
1
0
0
2
2
1
100 01 11 10
00
01
1
1
1
1
0
0
0
0
X X
Q Q2
2
1
1
Unit 15 Solutions
196
15.33
(cont.)
Present
State
Next State
W = 0 1
Output
0 1
S0 S0 S0 0 0
Present
State
Next State
W = 0 1
Output
0 1
000 000 000 0 0
I. None
II. (4, 7) (6, 7) (2, 4) (2, 6)
Assignment:
S0 = 000, S2 = 100, S4 = 111, S6 = 110, S7 = 101
15.34 By inspecting incoming arrows, we get:
D0 = Q0
+ = X’Y’Q0 + XYQ3
D1 = Q1
+ = XQ0 + Y’Q1 + XY’Q3
D2 = Q2
+ = X’YQ0 + X’Q2 + X’YQ3
D3 = Q3
+ = YQ1 + XQ2 + X’Y’Q3
S = YQ1 + XQ2
P = X’Y’Q3
By inspecting incoming arrows, we get:
Q0
+ = D0 = X’YQ0 + Y’Q1 + X’YQ2
+ = D1 = XY’Q0 + XYQ1 + Y’Q2
15.35
S0
S2
S1
X’Y
0
X
0
XY
S
X’Y’
0
S0
A
B C 0 1
00
S2
Q2Q1Q0
Clr, Ld, Cnt
X = 0 1
15.36 Clr = Q1‘ + Q0‘ + x
Ld = Q1Q0
15.37 (a) By inspecting incoming arrows, we get:
DA = QA
+ = X
DB = QB
+ = X’QA
DC = QC
+ = X’QB
Q1Q0
Q1
+Q0
+
X = 0 1
Z
X = 0 X = 1
00 01 00 0 0
15.37 (b)
Unit 15 Solutions
197
Q1Q0
s1
s0
X = 0 1
Z
X = 0 X = 1
00 01 11 0 0
15.37 (c) For the counter, a better state assignment is A = 00,
B = 01, C = 10 and D = 11.
Q3Q2 Q1Q0
s1
s0
X = 0 1
Z
X = 0 X = 1
15.37 (d) For the shift register, the state assignment A = 0000,
B = 1000, C = 1100 and D = 1110 makes use of the
shift function.
Q3Q2 Q1Q0
s1
s0
X = 0 1
Z
X = 0 X = 1
0000 01 11 0 0
1000 01 11 0 0
15.37 (d)
(cont.)
Another possibility is to duplicate state D and use
1110 and 1111 as state assignments for the two D’s.
15.38 (a) Q1+ = XQ1 + XQ2 = XQ1 + XQ2(Q1 + Q1‘)
= XQ1 + XQ2Q1‘ = (X + Q1‘)(X’ + Q2‘ + Q1)Q1
+ (X’Q1 + XQ2Q1‘)Q1‘
= (X’Q1 + XQ2Q1‘)‘Q1 + (X’Q1 + XQ2Q1‘)Q1‘
so T1 = (X’Q1 + XQ2Q1‘)
Q2+ = XQ1 + XQ2‘ = XQ1(Q2 + Q2‘) + XQ2‘
= XQ1Q2 + XQ2‘
Q1Q2
Q1+Q2+
X = 0 1
00 00 01
15.38 (b)
Q1Q2
T1T2
X = 0 1
00 00 01
15.38 (c) Q1+ = XQ1 + XQ2 = XQ1 + XQ2(Q1 + Q1‘)
= XQ1 + XQ2Q1‘
so J1 = XQ2, K1 = X’
J1K1, J2K2
Q1Q2X = 0 X = 1
00 0-, 0- 0-, 1-
01 0-, -1 1-, -1
15.38 (d)
15.39 (a) Q1+ = J1Q1‘ + K1‘Q1 = Q2Q1‘ + Q1‘Q1 = Q2Q1‘
so T1 = Q1 + Q2Q1‘ = Q1 + Q2
Q2+ = J2Q2‘ + K2‘Q2 = (X + Q1‘)Q2‘ + (1)‘Q2
= (X + Q1‘)Q2‘
so T2 = Q2 + (X + Q1‘)Q2‘
Unit 15 Solutions
Q1Q2
Q1+Q2+
X = 0 1
00 01 01
15.39 (b)
Q1Q2
T1T2
X = 0 1
00 01 01
J1K1, J2K2
Q1Q2X = 0 X = 1
15.39 (c) Q1+ = S1 + R1‘Q1 = Q2Q1‘ + Q1‘Q1
so S1 = Q2Q1‘ and R1 = Q1
Q2+ = S2 + R2‘Q2 = (X + Q1‘)Q2‘ + (Q2)‘Q2
so S2 = (X + Q1‘)Q2‘ and R2 = Q2
15.39 (d) S1R1, S2R2
Q1Q2X = 0 X = 1
00 0-, 10 0-, 10
15.40 S7 ~ S9 and S8 ~ S10 so the table reduces to
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
S0
S1
S2
0
0
S1
S3
S4
0
0
S
S
S
S
0
0
S
S
S
0
0
S5
S8
S7
0
0
S
S
S
0
0
S
S
S
1
0
S
S
S
0
1
S
S
0
0
Now S3 ~ S6 and S4 ~ S5 so the table reduces to
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
S0
S1
S2
0
0
S
1
S
3
S
4
0
0
S7
S6
S2
S1
S8
S1, S3
S2, S4
S1, S5
S2, S6
S0, S1
S3, S5
S4, S6
S0, S3S0, S7S0, S9
S0, S10
S1, S9
S2, S8
S3, S9
S4, S8
S0, S5
S5, S9
S6, S8
S7, S9
S0, S8
S8, S9
S9, S10
S8, S9
The implication chart verifies the answer.
S
S
S
0
0
S7
S0
S0
1
0
Unit 15 Solutions
199
15.41 (a)
S2
S1
S1, S4
S1, S3
S2, S3
S3, S4
S2, S3
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
S0 S1 S3
A
A
B
0
0
S0 S2 S3
B
C
B
0
0
S
0
S
1
S
4
C
A
B
0
1
15.41 (b)
15.42 (a)
S3
S2
S1
S1, S5
S1, S3
S2, S4
S1, S6
S2, S7
S3, S5
S3, S6
S4, S7
S5, S6
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
S0
S1
S2
0
0
S
1
S
3
S
4
0
0
—
0
—
S
S
S
0
0
0
0
S6
S0
S0
1
0
0
1
S
C
E
D
0
1
S
D
C
D
1
0
S
S
S
E
A
B
0
1
15.42 (b)
S5
S4
S3
S1, S6
S2, S7
S1, S7
S2, S6
S1, S7
S3, S6
S4, S7
S3, S7
S4, S6
S3, S7
S5, S6
S5, S7
S5, S7
S6, S7
S6, S7
√
15.43 (b)
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
S0 S1 S3 S6
A
A
B
1
0
S
0
S
2
S
4
S
5
S
7
B
C
D
0
1
Unit 15 Solutions
200
15.44 (a)
Maximal Compatibles: (S0 S1 S3 S6), (S0 S1 S4 S5),
(S0 S2 S3 S6), (S0 S2 S4 S5)
S0 S2 S3 S6
C
D
C
1
0
S0 S1 S4 S5
D
A
B
0
1
S2
S1
S1, S3
S2, S4
S1, S5
S2, S6
S3, S5
S4, S6
Present
Next
State
Output
State
X = 0
X = 1
X = 0
X = 1
S0 S1 S3 S6
A
A
B
1
0
S0 S2 S4 S5
B
D
C
0
1
15.44 (b)
15.45 (a)
S
S
C
D
A
0
1
S
S
D
E
F
—
—
S
S
E
A
D
0
1
S2 S5
F
D
A
1
0
S3
S2
S1
S1, S3
S2, S4
S1, S4
S2, S3
S1, S5
S2, S6
S3, S4
S3, S5
S4, S6
S4, S5
S3, S6
Present
Next
State
Output
State
X = 0
X = 1
X = 0
X = 1
S0 S3
A
B
C
—
—
S
1
S
5
B
A
D
1
0
15.45 (b)
15.45 (c)
Starting with any maximal compatible requires all
other maximal compatibles. Eight states would be
required.