### Unlock document.

**1 million**more documents.

This document is partially blurred.

Unlock all pages and **1 million** more documents.

Get Access
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

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

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

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

--

--

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

--

--

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

Students

Here are what students say about us.

Copyright ©2022 All rights reserved. | CoursePaper is not sponsored or endorsed by any college or university.