157
Unit 14 Solutions
Unit 14 Problem Solutions
14.4 Typical input and output sequences:
X = 0 1 0 0 0 0 0 1 0 1 0 1 1 …
Z = (0) 0 0 0 0 0 0 0 1 1 1 … (output remains 1)
X = 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 …
Z = (0) 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 … (output remains 1)
X = 0 1 0 1 0 1 …
The state meanings are given in the following table:
State Meaning
S0Reset
S1One 0, no 1’s
S2≥ Two 0’s, no 1’s
S8One 0 and one 1
14.5 Typical input and output sequence:
X = 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 …
Z1 = 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 … (output remains 0 after 100 received)
Z2 = 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 … (at this point, the sequence 01 has occurred, so Z1 = 0 from now on)
The graph needs two distinct parts. The first checks for 010 and 100. If 100 is received, we proceed to the second
The state meanings are given in the following table:
State Meaning
S0Reset
S1Last input was 0, 100 has never occurred
Unit 14 Solutions
14.6 This should be solved in the same way as Example 3 on FLD p. 471-472. Assign a state to each possible input (00,
01, 11, 10) with an output of 0, and another state to each input with an output of 1. This gives eight states.
See FLD p. 762 for the state table.
State Z = 0
S0Last input was 00
to the three input sequences.
Alternate Solution: Notice that when Z = 0, “causes the output to become 0” is the same as remaining constant, and
“causes the output to become 1” is the same as toggling the output. The situation is similar when Z = 1. So we can
use only four states, as follows:
State Meaning
S0Z= 0 and last input was either 00 or 01
Note: The state table with 8 states reduces to this 4-state table using methods in Unit 15.
State
Next State
X1X2 = 00 01 10 11
Z
00,01
S0
0
S1
0
10,11
10,11
01
14.7 (a) Typical input and output sequence:
State Z = 1
S4Last input was 00
State Meaning
S0Number of 1’s is divisible by three
14.7 (b) Typical input and output sequence:
X = 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 1 …
159
Unit 14 Solutions
14.7 (b)
(cont.)
State Meaning
S0Number of 1’s is divisible by three, no 0’s
S1Number of 1’s is one more than divisible by 3, no 0’s
S2Number of 1’s is two more than divisible by 3, no 0’s
14.8 (a) Typical input and output sequence:
X1 = 1 0 0 1 0 0 1 1 1 0 …
See FLD p. 762 for state table.
State Meaning
S0Reset
S1Previous input was 00
S1S2S3S4
S0
00
00
11
00
01
10
01
01
11
10
00
01
11
10
10
10
01
01
14.8 (b) Similar to part (a), but we need a separate state for each
possible output and previous input.
See FLD p. 763 for state table.
State Meaning
S0Reset state / current output is = 00
S1Previous input was 00 / current output is = 00
S2Previous input was 00 / current output is = 01
14.9 (a) 11
0001
State Meaning
S0Previous output bit was 0
See FLD p. 763 for state table.
160
Unit 14 Solutions
14.10
1
14.9 (b) State Meaning
A false output occurs in NRZI just before the input
NRZ goes from 1 to 0.
14.9 (c) Notice that the Moore output is delayed to the next
clock cycle.
14.9 (d)
See FLD p. 763 for solution. See FLD p. 764 for state graph.
State Meaning
S0Reset
14.11
See FLD p. 763 for state table.
State
Next State
x = 0 x = 1
z
A B A 0
14.12 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
A B A 0 0
14.12 (b)
14.13 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 2 3 0 0 Initial State
2 4 4 0 0 1st bit was 0
State
Next State
x = 0 x = 1
z
State
Meaning
1 2 3 0 Initial State, Valid BCD digit
2 4 4 0 1st bit was 0
9 2 3 1 Invalid BCD digit
14.13 (b)
14.13 (c) The ‘Mealy’ circuit of Part (a) is such a Moore
circuit. This is possible since the output does not
depend upon the fourth (least significant) bit.
161
Unit 14 Solutions
14.14 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 1 2 0 0 Previous 3 bits were -00
2 3 4 0 0 Previous 3 bits were 001
State
Next State
x = 0 x = 1
z
State
Meaning
1 1 2 0 Previous 4 bits: -000, 0-00
2 3 4 0 Previous 4 bits:-001
8 1 5 1 Previous 4 bits: 1010
9 6 7 1 Previous 4 bits: 1011
10 1 2 1 Previous 4 bits: 1100
11 8 9 1 Previous 4 bits: 1101
14.14 (b)
14.15 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 2 2 0 0 Initial State
2 3 4 0 0 1st bit was –
State
Next State
x = 0 x = 1
z
State
Meaning
1 2 2 0 Valid digit
2 3 4 0 1st bit was –
14.15 (b)
14.15 (c) It is not possible in this case since the output does
depend upon the fourth (most significant) bit.
14.16 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 1 2 0 0 Previous 3 bits were -00
State
Next State
x = 0 x = 1
z
State
Meaning
1 1 2 0 Previous 4 bits were –00
14.16 (b)
162
Unit 14 Solutions
14.17 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 2 3 0 0 Initial State
2 4 5 0 0 1st bit was 0
3 5 6 0 0 1st bit was 1
State
Next State
x = 0 x = 1
z
State
Meaning
1 2 3 0 Valid digit
2 4 5 0 1st bit was 0
3 5 6 0 1st bit was 1
14.17 (b)
14.17 (c) It is not possible because the output depends on the
value of the fourth bit, e.g., see state 8 in Part (a).
14.18 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 1 2 1 1 Previous 3 bits were 000
2 3 4 1 0 Previous 3 bits were 001
3 5 6 0 0 Previous 3 bits were 010
State
Next State
x = 0 x = 1
z
State
Meaning
1 1 2 1 Previous 4 bits were 0000
2 3 4 1 Previous 4 bits were 0001
3 5 6 1 Previous 4 bits were 0010
13 5 12 1 Previous 4 bits were 1110
14 13 14 1 Previous 4 bits were 1111
14.18 (b)
14.18 (c) It is not possible because the output depends on the
value of the fourth bit, e.g., see state 2 in Part (a).
163
Unit 14 Solutions
14.19 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 2 3 0 0 Initial State
2 4 5 0 0 1st bit was 0
3 5 6 0 0 1st bit was 1
State
Next State
x = 0 x = 1
z
State
Meaning
1 2 3 0 Initial State, Valid digit
2 4 5 0 1st bit was 0
3 5 6 0 1st bit was 1
14.19 (b)
14.19 (c) It is not possible because the output depends on the
value of the fourth bit, e.g., see state 7 in Part (a).
14.20 (a)
State
Next State
x = 0 x = 1
z
x = 0 x = 1
State
Meaning
1 1 2 1 0 Previous 3 bits were -00
2 3 4 0 0 Previous 3 bits were 001
State
Next State
x = 0 x = 1
z
State
Meaning
1 7 2 0 Previous 4 bits:1100
2 3 4 0 Previous 4 bits: -001
14.20 (b)
14.21 Plot 0’s horizontally. Plot 1’s vertically. Receiving
a 0 takes us one state to the right. Receiving a 1
takes us one state down. The output is a 1 only in
the “three 0’s or more, one 1 or more” state:
164
Unit 14 Solutions
14.22
State Meaning
S0Reset
S1Previous input was 0 / 011 has not occurred
S2Previous input was 01 / 011 has not occurred
State
Next State
X = 0 X = 1
Z1Z2
X = 0 X = 1
S0 S1 S600 00
S1 S1 S200 00
0
00
S0
S6S1
0
00
1
00
1
00
S3
1
00
0
00
* When this point in the graph is reached,
011 has been received, and we are only
looking for 011 to occur again.
14.23
0
S2
S3
1
S0
0
10,11
11
10
01
10
01,11
State Meaning
S0Z = 0, last input was 10 or 11
State
Next State
X1X2 = 00 01 10 11
Z
S0 S1 S1 S0 S00
Alternate solution has 8 states, similar to problem 14.6:
State
Next State
X1X2 = 00 01 10 11
Z
S0 S1 S2 S0 S30
State Meaning
S0Z = 0, last input was 10 (reset)
S1Z = 0, last input was 00
165
Unit 14 Solutions
14.24 (a) We need four states to describe the
1’s received, as there are four possible
01000000
14.24 (b) Now, expand the state graph into two dimensions: one for 1’s and the other for 0’s. We need two states to describe
the zeros, odd and even.
S1S0
01
00
00
1010
Left column: odd zeros
14.25 (a) We need four states, one for each of the possible past inputs. The next state is just the one that describes that input.
The output Z1 is formed by adding the value of the present state to the present input. Z2 is found in a similar way:
State
Next State
00 01 10 11
Z1Z2
00 01 10 11
S0 S0 S1 S2 S3 00 00 00 10
State Meaning
S0Previous input was 00 (0)
14.25 (b) The Moore version is less intuitive. Again, we need
a state for each past input. We do not, however, need
a state for every possible output (this would give 4 ×
4 = 16 states) since some outputs never occur. For
Previous
Input
State
X1X2
00 01 10 11
Z1Z2
00 S0 S0 S2 S5 S800
166
Unit 14 Solutions
14.26 There are two identical parts: one with an output of
0 and one with an output of 1.
State Meaning
S1, S4Previous input was 0
S1
S5
S0
0
0
0
1
1
0
1
S0
0
S2
0
S1
0
0
1 0
14.27 There are two identical parts: one with an output of 0 and one
with an output of 1.
State Meaning
S0Reset
S1Previous input was 1
14.28 This is another problem similar to 14.10. Plot the
number of 0’s horizontally and the number of pairs
vertically:
S0
no pairs
no 0’s one zero two zeros three zeros four zeros
000
010100
110
167
Unit 14 Solutions
14.29 0’s are plotted horizontally. 1’s are plotted
vertically.
State
Next State
X = 0 X = 1
Z
0
even 1’s
S0
0
S2
0
S4
0
0
0
Pairs
0’s
Present
State
Next State
00 01 10 11
Z1Z2
00 01 10 11
0 0 S0 S3 S2 S2 S1 0 0 0 0
1 0 S1 S6 S5 S5 S4 0 0 0 0
14.28
(cont.)
14.30
State
Next State
X = 0 X = 1
Z1Z2
X = 0 X = 1
S0 S1 S0 00 00
S1S2
S0
0
00 S3
0
00
0
00
1
10
1
State Meaning
S0Reset, 0111
S10
168
Unit 14 Solutions
14.32
State
Next State
X = 0 X = 1
Z
X = 0 X = 1
S0 S1 S0 0 1
S1 S2 S0 0 1
State Meaning
Example: X = 0 0 1 1 0 0 1 1 0 1 0 1
Z = 0 0 1 1 1 0 1 1 1 1 0 1
Note: Overlapping sequences are allowed.
14.31
State
X1X2
00 01 10 11
Z
State Meaning
S0Reset
S0
S1
00
01
00
S0
0
S3
0
S6
0
0
0
1
1
0
0,
1
14.33
State
Next State
X = 0 X = 1
Z
S0 S0 S10
S1 S6 S20
State Meaning
S0No 1’s
S1One 1 in first group
169
Unit 14 Solutions
14.34 To delay by two clock periods, we need to
remember the previous two inputs. So we have
four states, one for each combination of two inputs:
State
Next State
X = 0 X = 1
Z
X = 0 X = 1
S0 S0 S1 0 0
State Meaning
S0Previous two inputs were 00
Note: Just go to the state that represents the last
two inputs.
S0S1
11
00
10
00
01
10
14.35 This is the same as 14.34, except that we need to
remember the last three inputs. So we have eight
states:
State
Next State
X = 0 X = 1
Z
X = 0 X = 1
S0 S0 S1 0 0
S1 S2 S3 0 0
00S0S1S3S7
S6
S5
S2
S4
10
10101
1
01
01
110011
0001
00
10
01
11
State
Next State
X = 0 X = 1
Z
S0 S0 S10
S1 S2 S30
S2 S4 S50
14.36 (a) 16 states are required since the last four inputs must
be remembered.
14.36 (b)
Note: The state
number expressed in
binary gives the last
3 inputs.
170
Unit 14 Solutions
14.37
State
Next State
X = 0 X = 1
SV
X = 0 X = 1
S0 S1 S1 00 10
S1 S2 S4 10 00
State Meaning
S0No bits received
S1One bit received
S2Two bits received; Carry-in = 0
S2
S3
S3
00, 10
0 1
10, 01
0 1
010
00, 10
0 1
14.38
State
Next State
X = 0 X = 1
DB
X = 0 X = 1
S0 S1 S1 00 10
S1 S2 S3 10 00
State Meaning
S0No bits received
S1One bit received
S2Two bits received; Borrow-in = 1
S2
S3
S4
11, 00
0 1
00, 10
0 1
010
10
0
171
Unit 14 Solutions
14.39 This is similar to 14-15, and should be answered in
the same way. See the solution to 14-15 for more
information.
Horizontally: Number of 1’s modulo 3
Vertically: Number of 0’s modulo 3.
State
Next State
X = 0 X = 1
YZ
S0 S3 S100
S1 S4 S201
S2 S5 S010
S3 S6 S400
S6
00
S3
00
S0
00
S4
01
S1
01
S7
01
S5
10
S2
10
S8
10
1
1
1
1 1
1 1
1 1
0
0
0
0
0
0
0
0
0
0 1 2
0
1
2
This problem is essentially a circular counting
exercise. Pairs of 1’s take you further around the
state graph. Pairs can overlap, so if the last input
was a 1, and the present input is a 1, you move on.
If the sequence is interrupted, you branch off while
you wait for the next 1. Then, you go back to the
cycle of counting.
State
Next State
X = 0 X = 1
YZ
S0 S0 S100
S1 S0 S200
S2 S3 S401
S0
00
S6
11
S4
10
S2
01
S1
00
S7
11
S5
S3
11
1 1
1
1
1
1
00
0
0
0
0
1’s take you
around
14.40
172
Unit 14 Solutions
14.43 (a) Look at Figure 14-19, FLD p. 473, to see that
Manchester 01 gives NRZ 00
Manchester 10 gives NRZ 11
Other Manchester inputs are presumed not to occur.
State
Next State
X = 0 X = 1
Z
X = 0 X = 1
S0 S1 S2 0 1
S0
S1S2
1
0
1
1
0
0
0
1
We notice that input ABXX becomes output AABB.
It can be seen that it is not necessary to remember
S5
S1
S0
00
11
1001
14.41
14.42 This problem is simply addition. We need a state
to describe every possible sum of money entered,
i.e., 0¢ to 45¢ in 5¢ intervals.
Just go to the state with the correct sum. The 25¢
State
Next State
Z
S2 S4 S4 0 0
S3 S6 S6 1 1
S4 S0 S0 0 0
S5 S2 S3 1 1
State Meaning
S2, S4B = 0
S3, S6B = 1
$
Present
State
NDQ
000 100 010 001
RC
.00 S0 S0 S1 S2 S500
.05 S1 S1 S2 S3 S600
.30 S6 S5 – – –01
.35 S7 S6 – – –01
.40 S8 S7 – – –01
.45 S9 S8 – – –01
173
Unit 14 Solutions
14.43 (b) This is the same as the Mealy, except that we need
two reset states, one with an output of zero, the
1
0
S0
0
S2
1
0
1
14.43
(c), (d) CLOCK2
Manchester
NRZ (Mealy)
State
Next State
14.44 State Meaning
S0Reset
S1One ring, waiting for two (or answer)
S3, S4, S5One, two, or three rings, respectively;
waiting for four (or answer)
S0
0
S3
S5
0
Z
S1
R’
RS’
AR’
RS
AR’
R
A’R’
A’R’
A’R’
Present
State
Next State
00 01 10 11
Z1Z2
00 01 10 11
S0 S1 S0 S2 S2 01 10 01 01
14.45
In state S0 there is no specification for X1X2‘. This
can be corrected by adding an arc for X1X2‘ or
changing X1X2 to X1 or changing X1‘ X2‘ to X2‘.
14.46
S0
Z1
X2‘*
14.44
cont.
174
Unit 14 Solutions
14.47
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
S0
S1
S2
0
0
0
S
1
S
3
S
4
0
0
1
S
2
S
5
S
6
0
0
00
S3
S7
S8
0
0
10
0
0
14.48
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
S0
S1
S2
0
0
0
S
1
S
3
S
4
0
0
1
S2
S4
S5
0
0
00
S3
S6
—
0
10, 01
S4
S7
S8
0
0
11
S5
S9
—
0
0
001
S6
S0
—
1
100, 010
S
S
S
0
1
101, 011
S
S
S
1
0
110
S
S
—
1
—
14.49
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
S0
S1
S2
0
0
0
S
1
S
3
S
4
0
0
1
S
00
0
0
01
—
0
10
S5
S8
S7
0
0
11
—
0
000, 101
1
0
001, 100
S
S
S
0
1
111
S10
S0
—
0
—
S
S
0
0
Noting that the six illegal sequences only need to
be distinguished by their parity produces this table.
This table can be reduced using techniques of Unit
15. Alternatively, it can be reduced by noting that
all sequences of length 2 and all of length 3 only
need to be distinguished by their parity.
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
S0
S1
S2
0
0
Distinguishing between legal and illegal sequences
and combining sequences with the same parity
produces the table below.
This table can be reduced using techniques of Unit
15. Alternatively, it can be reduced by noting that
all sequences of length 2 and all of length 3 only
need to be distinguished by their parity.
Present
State
Next
X = 0
State
X = 1
Output
X =0
(Z)
X = 1
Distinguishing between legal and illegal sequences
and combining sequences with the same parity
produces the table below.
This table can be reduced using techniques of Unit
15. Alternatively, it can be reduced by noting that
all sequences of length 2 and all of length 3 only
need to be distinguished by their parity.
Present
Next
State
Output
(Z)
175
Unit 14 Solutions
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
S0
S1
S2
—
—
State
14.50
14.51
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
S0
S1
S2
—
—
0
S
1
S
3
S
4
—
—
00
S
S
S
1
0
01,10
S
S
S
0
1
Distinguishing legal and illegal sequences
produces the following table.
This table can be reduced using techniques of Unit
15. Alternatively, it can be reduced by combining
the sequences of length 2 that have the same parity.
Present
Next
State
Output
176
Unit 14 Solutions