Solution manual Digital Design and

Citation preview

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

SOLUTIONS

© Elsevier 2015

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CHAPTER 1

Exercise 1.1

(a) Biologists study cells at many levels. The cells are built from organelles such as the mitochondria, ribosomes, and chloroplasts. Organelles are built of macromolecules such as proteins, lipids, nucleic acids, and carbohydrates. These biochemical macromolecules are built simpler molecules such as carbon chains and amino acids. When studying at one of these levels of abstraction, biologists are usually interested in the levels above and below: what the structures at that level are used to build, and how the structures themselves are built. (b) The fundamental building blocks of chemistry are electrons, protons, and neutrons (physicists are interested in how the protons and neutrons are built). These blocks combine to form atoms. Atoms combine to form molecules. For example, when chemists study molecules, they can abstract away the lower levels of detail so that they can describe the general properties of a molecule such as benzene without having to calculate the motion of the individual electrons in the molecule. Exercise 1.2

(a) Automobile designers use hierarchy to construct a car from major assemblies such as the engine, body, and suspension. The assemblies are constructed from subassemblies; for example, the engine contains cylinders, fuel injectors, the ignition system, and the drive shaft. Modularity allows components to be swapped without redesigning the rest of the car; for example, the seats can be cloth, leather, or leather with a built in heater depending on the model of the vehicle, so long as they all mount to the body in the same place. Regularity involves the use of interchangeable parts and the sharing of parts between different vehicles; a 65R14 tire can be used on many different cars.

1

© 2015 Elsevier, Inc.

2

SOLUTIONS

chapter 1

(b) Businesses use hierarchy in their organization chart. An employee reports to a manager, who reports to a general manager who reports to a vice president who reports to the president. Modularity includes well-defined interfaces between divisions. The salesperson who spills a coke in his laptop calls a single number for technical support and does not need to know the detailed organization of the information systems department. Regularity includes the use of standard procedures. Accountants follow a well-defined set of rules to calculate profit and loss so that the finances of each division can be combined to determine the finances of the company and so that the finances of the company can be reported to investors who can make a straightforward comparison with other companies. Exercise 1.3

Ben can use a hierarchy to design the house. First, he can decide how many bedrooms, bathrooms, kitchens, and other rooms he would like. He can then jump up a level of hierarchy to decide the overall layout and dimensions of the house. At the top-level of the hierarchy, he material he would like to use, what kind of roof, etc. He can then jump to an even lower level of hierarchy to decide the specific layout of each room, where he would like to place the doors, windows, etc. He can use the principle of regularity in planning the framing of the house. By using the same type of material, he can scale the framing depending on the dimensions of each room. He can also use regularity to choose the same (or a small set of) doors and windows for each room. That way, when he places a new door or window he need not redesign the size, material, layout specifications from scratch. This is also an example of modularity: once he has designed the specifications for the windows in one room, for example, he need not respecify them when he uses the same windows in another room. This will save him both design time and, thus, money. He could also save by buying some items (like windows) in bulk. Exercise 1.4

An accuracy of +/- 50 mV indicates that the signal can be resolved to 100 mV intervals. There are 50 such intervals in the range of 0-5 volts, so the signal represents log250 = 5.64 bits of information. Exercise 1.5

(a) The hour hand can be resolved to 12 * 4 = 48 positions, which represents log248 = 5.58 bits of information. (b) Knowing whether it is before or after noon adds one more bit.

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 1.6

Each digit conveys log260 = 5.91 bits of information. 400010 = 1 6 4060 (1 in the 3600 column, 6 in the 60’s column, and 40 in the 1’s column). Exercise 1.7

216 = 65,536 numbers. Exercise 1.8

232-1 = 4,294,967,295 Exercise 1.9

(a) 216-1 = 65535; (b) 215-1 = 32767; (c) 215-1 = 32767 Exercise 1.10

(a) 232-1 = 4,294,967,295; (b) 231-1 = 2,147,483,647; (c) 231-1 = 2,147,483,647 Exercise 1.11

(a) 0; (b) -215 = -32768; (c) -(215-1) = -32767 Exercise 1.12

(a) 0; (b) -231 = -2,147,483,648; (c) -(231-1) = -2,147,483,647; Exercise 1.13

(a) 10; (b) 54; (c) 240; (d) 2215 Exercise 1.14

(a) 14; (b) 36; (c) 215; (d) 15,012 Exercise 1.15

(a) A; (b) 36; (c) F0; (d) 8A7

3

© 2015 Elsevier, Inc.

4

SOLUTIONS

chapter 1

Exercise 1.16

(a) E; (b) 24; (c) D7; (d) 3AA4 Exercise 1.17

(a) 165; (b) 59; (c) 65535; (d) 3489660928 Exercise 1.18

(a) 78; (b) 124; (c) 60,730; (d) 1,077,915, 649 Exercise 1.19

(a) 10100101; (b) 00111011; (c) 1111111111111111; (d) 11010000000000000000000000000000 Exercise 1.20

(a) 1001110; (b) 1111100; (c) 1110110100111010; (d) 100 0000 0011 1111 1011 0000 0000 0001 Exercise 1.21

(a) -6; (b) -10; (c) 112; (d) -97 Exercise 1.22

(a) -2 (-8+4+2 = -2 or magnitude = 0001+1 = 0010: thus, -2); (b) -29 (-32 + 2 + 1 = -29 or magnitude = 011100+1 = 011101: thus, -29); (c) 78; (d) -75 Exercise 1.23

(a) -2; (b) -22; (c) 112; (d) -31 Exercise 1.24

(a) -6; (b) -3; (c) 78; (d) -53 Exercise 1.25

(a) 101010; (b) 111111; (c) 11100101; (d) 1101001101

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 1.26

(a) 1110; (b) 110100; (c) 101010011; (d) 1011000111 Exercise 1.27

(a) 2A; (b) 3F; (c) E5; (d) 34D Exercise 1.28

(a) E; (b) 34; (c) 153; (d) 2C7; Exercise 1.29

(a) 00101010; (b) 11000001; (c) 01111100; (d) 10000000; (e) overflow Exercise 1.30

(a) 00011000; (b) 11000101; (c) overflow; (d) overflow; (e) 01111111 Exercise 1.31

00101010; (b) 10111111; (c) 01111100; (d) overflow; (e) overflow Exercise 1.32

(a) 00011000; (b) 10111011; (c) overflow; (d) overflow; (e) 01111111 Exercise 1.33

(a) 00000101; (b) 11111010 Exercise 1.34

(a) 00000111; (b) 11111001 Exercise 1.35

(a) 00000101; (b) 00001010 Exercise 1.36

(a) 00000111; (b) 00001001 Exercise 1.37

5

© 2015 Elsevier, Inc.

6

SOLUTIONS

chapter 1

(a) 52; (b) 77; (c) 345; (d) 1515 Exercise 1.38

(a) 0o16; (b) 0o64; (c) 0o339; (d) 0o1307 Exercise 1.39

(a) 1000102, 2216, 3410; (b) 1100112, 3316, 5110; (c) 0101011012, AD16, 17310; (d) 0110001001112, 62716, 157510 Exercise 1.40

(a) 0b10011; 0x13; 19; (b) 0b100101; 0x25; 37; (c) 0b11111001; 0xF9; 249; (d) 0b10101110000; 0x570; 1392 Exercise 1.41

15 greater than 0, 16 less than 0; 15 greater and 15 less for sign/magnitude Exercise 1.42

(26-1) are greater than 0; 26 are less than 0. For sign/magnitude numbers, (26-1) are still greater than 0, but (26-1) are less than 0. Exercise 1.43

4, 8 Exercise 1.44

8 Exercise 1.45

5,760,000 Exercise 1.46

(5 × 109 bits/second)(60 seconds/minute)(1 byte/8 bits) = 3.75 × 1010 bytes Exercise 1.47

46.566 gigabytes

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 1.48

2 billion Exercise 1.49

128 kbits Exercise 1.50

-4

-3

-2

-1

Unsigned

100

101

110

111

111

110

101

0

1

2

3

4

5

6

7

000

001

010

011

100

101

110

111

000

001

010

011

Two’s Complement

001

010

011

Sign/Magnitude

000 100

Exercise 1.51

-2

-1

0

1

2

3

00

01

10

11

11

00

01

Two’s Complement

11

00 10

01

Sign/Magnitude

Unsigned

10

Exercise 1.52

(a) 1101; (b) 11000 (overflows) Exercise 1.53

7

© 2015 Elsevier, Inc.

8

SOLUTIONS

chapter 1

(a) 11011101; (b) 110001000 (overflows) Exercise 1.54

(a) 11012, no overflow; (b) 10002, no overflow Exercise 1.55

(a) 11011101; (b) 110001000 Exercise 1.56

(a) 010000 + 001001 = 011001; (b) 011011 + 011111 = 111010 (overflow); (c) 111100 + 010011 = 001111; (d) 000011 + 100000 = 100011; (e) 110000 + 110111 = 100111; (f) 100101 + 100001 = 000110 (overflow) Exercise 1.57

(a) 000111 + 001101 = 010100 (b) 010001 + 011001 = 101010, overflow (c) 100110 + 001000 = 101110 (d) 011111 + 110010 = 010001 (e) 101101 + 101010 = 010111, overflow (f) 111110 + 100011 = 100001 Exercise 1.58

(a) 10; (b) 3B; (c) E9; (d) 13C (overflow) Exercise 1.59

(a) 0x2A; (b) 0x9F; (c) 0xFE; (d) 0x66, overflow Exercise 1.60

(a) 01001 – 00111 = 00010; (b) 01100 – 01111 = 11101; (c) 11010 – 01011 = 01111; (d) 00100 – 11000 = 01100 Exercise 1.61

(a) 010010 + 110100 = 000110; (b) 011110 + 110111 = 010101; (c) 100100 + 111101 = 100001; (d) 110000 + 101011 = 011011, overflow

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 1.62

(a) 3; (b) 01111111; (c) 000000002 = -12710; 111111112 = 12810 Exercise 1.63

-3

-2

-1

0

1

2

3

4

000

001

010

011

100

101

110

111

Biased

Exercise 1.64

(a) 001010001001; (b) 951; (c) 1000101; (d) each 4-bit group represents one decimal digit, so conversion between binary and decimal is easy. BCD can also be used to represent decimal fractions exactly. Exercise 1.65

(a) 0011 0111 0001 (b) 187 (c) 95 = 1011111 (d) Addition of BCD numbers doesn’t work directly. Also, the representation doesn’t maximize the amount of information that can be stored; for example 2 BCD digits requires 8 bits and can store up to 100 values (0-99) – unsigned 8bit binary can store 28 (256) values. Exercise 1.66

Three on each hand, so that they count in base six. Exercise 1.67

Both of them are full of it. 4210 = 1010102, which has 3 1’s in its representation. Exercise 1.68

Both are right. Exercise 1.69 #include

9

© 2015 Elsevier, Inc.

10

SOLUTIONS

chapter 1

void main(void) { char bin[80]; int i = 0, dec = 0; printf(“Enter binary number: “); scanf(“%s”, bin);

}

while (bin[i] != 0) { if (bin[i] == ‘0’) dec = dec * 2; else if (bin[i] == ‘1’) dec = dec * 2 + 1; else printf(“Bad character %c in the number.n”, bin[i]); i = i + 1; } printf(“The decimal equivalent is %dn”, dec);

Exercise 1.70 /* This program works for numbers that don’t overflow the range of an integer. */ #include void main(void) { int b1, b2, digits1 = 0, digits2 = 0; char num1[80], num2[80], tmp, c; int digit, num = 0, j; printf (“Enter base #1: “); scanf(“%d”, &b1); printf (“Enter base #2: “); scanf(“%d”, &b2); printf (“Enter number in base %d “, b1); scanf(“%s”, num1); while (num1[digits1] != 0) { c = num1[digits1++]; if (c >= ‘a’ && c = ‘0’ && c = ‘A’ && c = b1) printf(“Illegal digit %cn”, c); num = num * b1 + digit; } while (num > 0) { digit = num % b2; num = num / b2; num2[digits2++] = digit < 10 ? digit + ‘0’ : digit + ‘A’ 10; } num2[digits2] = 0; for (j = 0; j < digits2/2; j++) { // reverse order of digits tmp = num2[j]; num2[j] = num2[digits2-j-1]; num2[digits2-j-1] = tmp; } }

Exercise 1.71

printf(“The base %d equivalent is %sn”, b2, num2);

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

OR3 A B C

XOR3 A B C

Y Y = A+B+C

(a)

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 0 1 1 1 1 1 1 1

A B C D

Y

Y=A+B+C

(b)

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 0 1 1 0 1 0 0 1

XNOR4 Y

Y=A+B+C+D A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 (c) 1

C 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Y 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

11

© 2015 Elsevier, Inc.

12

SOLUTIONS

chapter 1

Exercise 1.72

A B C D

OR4

XNOR3 A B C

Y

Y = A+B+C+D A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 (a) 1

C 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

Exercise 1.73

B 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Y 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

NAND5 A B C D E

Y

Y=A+B+C A 0 0 0 0 1 1 1 1 (b)

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 1 0 0 1 0 1 1 0

Y

Y = ABCDE A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (c) 1

B 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

C 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

D 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

E 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 0 0 0 1 0 1 1 1

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 0 1 0 1 0 1 1 1

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 1 1 1 0 1 0 1 0

Exercise 1.74

Exercise 1.75

Exercise 1.76

13

© 2015 Elsevier, Inc.

14

SOLUTIONS

chapter 1

A 0 0 1 1

B 0 1 0 1

Y 0 0 0 0

Zero A 0 0 1 1

B 0 1 0 1

A 0 0 1 1

B 0 1 0 1

Y 0 0 1 0

A 0 0 1 1

B 0 1 0 1

A

A 0 0 1 1

B 0 1 0 1

Y 1 0 1 0

Y 0 0 0 1

A 0 0 1 1

B 0 1 0 1

A 0 0 1 1

A 0 0 1 1

B 0 1 0 1

A+B

Y 0 1 0 0

A 0 0 1 1

B 0 1 0 1

Y 1 0 0 1

A 0 0 1 1

B 0 1 0 1

Y 0 1 1 0

A 0 0 1 1

A 0 0 1 1

B 0 1 0 1

OR

Y 1 1 0 0

B 0 1 0 1

Y 1 1 1 0

NAND Y 0 1 0 1

A 0 0 1 1

B Y 1 0 1 1

B 0 1 0 1

NOT A

XOR

XNOR Y 0 0 1 1

B 0 1 0 1

AB

NOT B

AND A 0 0 1 1

Y 1 0 0 0

A NOR B

AB A 0 0 1 1

B 0 1 0 1

B 0 1 0 1

Y 1 1 0 1

A+B Y 0 1 1 1

A 0 0 1 1

B 0 1 0 1

Y 1 1 1 1

One

Exercise 1.77

2

2

N

Exercise 1.78

VIL = 2.5; VIH = 3; VOL = 1.5; VOH = 4; NML = 1; NMH = 1 Exercise 1.79

No, there is no legal set of logic levels. The slope of the transfer characteristic never is better than -1, so the system never has any gain to compensate for noise. Exercise 1.80

VIL = 2; VIH = 4; VOL = 1; VOH = 4.5; NML = 1; NMH = 0.5

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 1.81

The circuit functions as a buffer with logic levels VIL = 1.5; VIH = 1.8; VOL = 1.2; VOH = 3.0. It can receive inputs from LVCMOS and LVTTL gates because their output logic levels are compatible with this gate’s input levels. However, it cannot drive LVCMOS or LVTTL gates because the 1.2 VOL exceeds the VIL of LVCMOS and LVTTL. Exercise 1.82

(a) AND gate; (b) VIL = 1.5; VIH = 2.25; VOL = 0; VOH = 3 Exercise 1.83

(a) XOR gate; (b) VIL = 1.25; VIH = 2; VOL = 0; VOH = 3 Exercise 1.84

Y A

B

A

A

B

C

B C

Y

Y

C

C A

D

A B

B

(b)

(a)

C

(c)

Exercise 1.85

Y

A C

A

B Y

Y A

C

B (a)

Exercise 1.86

B

A

B

(b)

(c)

15

© 2015 Elsevier, Inc.

16

SOLUTIONS

chapter 1

A

B

B

C

A

C

A

Y A

B

B

Exercise 1.87

See also  xcode duplicate symbols for architecture error after updating cocoa pods

XOR A 0 0 1 1

B 0 1 0 1

Y 0 1 1 0

Exercise 1.88

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 1 0 1 0 1 0 0 0

Exercise 1.89

weak weak

Y

Y A

weak

Y A

B (a)

Exercise 1.90

C

A

B

B

C (b)

C (c)

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Question 1.1

Question 1.2

4 times. Place 22 coins on one side and 22 on the other. If one side rises, the fake is on that side. Otherwise, the fake is among the 20 remaining. From the group containing the fake, place 8 on one side and 8 on the other. Again, identify which group contains the fake. From that group, place 3 on one side and 3 on the other. Again, identify which group contains the fake. Finally, place 1 coin on each side. Now the fake coin is apparent. Question 1.3

17 minutes: (1) designer and freshman cross (2 minutes); (2) freshman returns (1 minute); (3) professor and TA cross (10 minutes); (4) designer returns (2 minutes); (5) designer and freshman cross (2 minutes).

17

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CHAPTER 2

Exercise 2.1

(a) Y = AB + AB + AB (b) Y = ABC + ABC (c) Y = ABC + ABC + ABC + ABC + ABC (d) Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD (e) Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD Exercise 2.2

(a) Y = AB + AB + AB (b) Y = ABC + ABC + ABC + ABC + ABC (c) Y = ABC + ABC + ABC (d) Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD (e) Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD Exercise 2.3

(a) Y =  A + B 

11

© 2015 Elsevier, Inc.

12

SOLUTIONS

chapter 2

(b) Y =  A + B + C  A + B + C  A + B + C  A + B + C  A + B + C A + B + C  (c) Y =  A + B + C   A + B + C   A + B + C  (d) Y =  A + B + C + DA + B + C + DA + B + C + DA + B + C + DA + B + C + D A + B + C + D A + B + C + D A + B + C + DA + B + C + D (e) Y =  A + B + C + DA + B + C + DA + B + C + DA + B + C + DA + B + C + D  A + B + C + D A + B + C + DA + B + C + D  Exercise 2.4

(a) Y = A + B (b) Y =  A + B + C   A + B + C   A + B + C  (c) Y =  A + B + C   A + B + C   A + B + C   A + B + C   A + B + C  (d) Y =  A + B + C + DA + B + C + DA + B + C + D A + B + C + D  A + B + C + DA + B + C + D A + B + C + D A + B + C + D A + B + C + D (e) Y =  A + B + C + DA + B + C + DA + B + C + D A + B + C + D  A + B + C + DA + B + C + D A + B + C + D A + B + C + D A + B + C + D Exercise 2.5

(a) Y = A + B (b) Y = ABC + ABC (c) Y = AC + AB + AC (d) Y = AB + BD + ACD (e) Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD This can also be expressed as: Y = A  BC  D + A  BC  D Exercise 2.6

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

(a) Y = A + B (b) Y = AC + AC + BC

or Y = AC + AC + AB

(c) Y = AB + ABC (d) Y = BC + BD (e) Y = AB + ABC + ACD or Y = AB + ABC + BCD Exercise 2.7

(a) A

Y

B

(b) A B C

Y

(c) A C

Y

B

(d) A

B C D

Y

13

© 2015 Elsevier, Inc.

14

SOLUTIONS

chapter 2

(e) A B Y

C D

Exercise 2.8

A B

Y

(a)

C

A Y (b)

or

C B

Y A B

A Y (c)

B C C Y

(d)

B D ABCD

ABCD

Y

Y or

(e)

Exercise 2.9

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

(a) Same as 2.7(a) (b) A B C

Y

(c) A

B C

Y

(d) A

B C D

Y

15

© 2015 Elsevier, Inc.

16

SOLUTIONS

chapter 2

(e) A

B

C

D

Y

Exercise 2.10

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A B

Y

(a) A

B

C

A

Y

or

(b) A

B

C

Y (c) C Y (d)

B D ABCD

Y

(e)

Exercise 2.11

(a) A B

Y

B

C

Y

17

© 2015 Elsevier, Inc.

18

SOLUTIONS

chapter 2

(b) A B

Y

C

(c) A C

Y

B

(d) A B

Y

D C

(e) A B Y C D

Exercise 2.12

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A B

Y

(a) A

B

C

Y

(b) A

B

C

Y (c) C Y (d)

B D ABCD

Y

(e)

Exercise 2.13

(a) Y = AC + BC (b) Y = A (c) Y = A + B C + B D + BD Exercise 2.14

(a) Y = AB (b) Y = A + B + C = ABC

19

© 2015 Elsevier, Inc.

20

SOLUTIONS

chapter 2

(c) Y = A  B + C + D  + BCD = ABCD + BCD Exercise 2.15

(a) A B C

Y

(b) A

Y

(c) A B D

Y

C

Exercise 2.16

A B

Y

A B C

Y

(a)

(b)

ABCD Y

(c)

Exercise 2.17

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

(a) Y = B + AC B A C

Y

(b) Y = AB A B

Y

(c) Y = A + BC + DE A B CD E Y

Exercise 2.18

(a) Y = B + C (b) Y =  A + C D + B (c) Y = BDE + BD  A  C  Exercise 2.19

4 gigarows = 4 x 230 rows = 232 rows, so the truth table has 32 inputs. Exercise 2.20

21

© 2015 Elsevier, Inc.

22

chapter 2

SOLUTIONS

A Y B Y=A

Exercise 2.21

Ben is correct. For example, the following function, shown as a K-map, has two possible minimal sum-of-products expressions. Thus, although ACD and BCD are both prime implicants, the minimal sum-of-products expression does not have both of them. Y

AB

Y 00

01

11

10

00

1

0

1

1

01

0

0

1

0

CD

ACD

AB

00

01

11

10

00

1

0

1

1

01

0

0

1

0

CD

BCD

ABD

ABD

ABC

ABC 11

0

0

0

0

11

0

0

0

0

10

1

0

0

0

10

1

0

0

0

Y = ABD + ABC + ACD

Y = ABD + ABC + BCD

Exercise 2.22

(a) B 0 1

B B 0 1

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

(b) B 0 0 0 0 1 1 1 1

C 0 0 1 1 0 0 1 1

D 0 1 0 1 0 1 0 1

(B C) + (B D) B (C + D) 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1

(c) B 0 0 1 1

C 0 1 0 1

(B C) + (B C) 0 0 1 1

Exercise 2.23

B2 0 0 0 0 1 1 1 1

B1 0 0 1 1 0 0 1 1

B0 0 1 0 1 0 1 0 1

B2 B1 B0 1 1 1 1 1 1 1 0

Exercise 2.24

Y = AD + ABC + ACD + ABCD Z = ACD + BD Exercise 2.25

B2 + B1 + B0 1 1 1 1 1 1 1 0

23

© 2015 Elsevier, Inc.

24

chapter 2

SOLUTIONS

Y CD

AB

00

Z

00

01

11

10

0

0

0

0

CD

AB

00

00

01

11

10

0

0

1

0 ACD

D

01

1

1

1

1

01

0

1

1

1

11

0

1

1

0

ABC

11

1

1

1

1

BD

10

0

0

0

1

10

0

Y = ABC + D

A B

0

0

0

Z = ACD + BD

C

D

Y

Z

Exercise 2.26

A B C D E

Y = (A + B)(C + D) + E

Y

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 2.27

A B C D

Y

E F G Y = ABC + D + (F + G)E = ABC + D + EF + EG

Exercise 2.28

Two possible options are shown below: Y

Y

01

11

10

00

X

0

1

1

0

01

X

X

1

0

1

1

11

0

X

1

1

X

X

10

X

0

X

X

01

11

10

00

X

0

1

1

01

X

X

1

11

0

X

10

X

0

(a)

AB

00

00

CD

Exercise 2.29

AB

Y = AD + AC + BD

CD

(b)

Y = A(B + C + D)

25

© 2015 Elsevier, Inc.

26

SOLUTIONS

chapter 2

Two possible options are shown below: C A Y

B

A B C D

(a)

(b)

D

Y

Exercise 2.30

Option (a) could have a glitch when A=1, B=1, C=0, and D transitions from 1 to 0. The glitch could be removed by instead using the circuit in option (b). Option (b) does not have a glitch. Only one path exists from any given input to the output. Exercise 2.31

Y = AD + ABCD + BD + CD = ABCD + D  A + B + C  Exercise 2.32

ABCD

Y

Exercise 2.33

The equation can be written directly from the description: E = SA + AL + H

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

27

SOLUTIONS

Exercise 2.34

(a) Sc

D3:2

D1:0

Sd

D3:2 00 D1:0

00

01

11

10

01

11

10

00

1

1

0

1

00

1

0

0

1

01

1

1

0

1

01

0

1

0

0

11

1

1

0

0

11

1

0

0

0

10

0

1

0

0

10

1

1

0

0

Sd = D3D1D0 + D3D2D1 +

Sc = D3D0 + D3D2 + D2D1 Se

D3:2 00 D1:0

D2D1D0 + D3D2D1D0

Sf 01

11

10

D3:2 00 D1:0

01

11

10

00

1

0

0

1

00

1

1

0

1

01

0

0

0

0

01

0

1

0

1

11

0

0

0

0

11

0

0

0

0

10

1

1

0

0

10

0

1

0

0

Se = D2D1D0 + D3D1D0

Sf = D3D1D0 + D3D2D1+ D3D2D0 + D3D2D1

© 2015 Elsevier, Inc.

28

SOLUTIONS

chapter 2

Sg

D3:2 00 D1:0

01

11

10

00

0

1

0

1

01

0

1

0

1

11

1

0

0

0

10

1

1

0

0

Sg = D3D2D1 + D3D1D0+ D3D2D1 + D3D2D1

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

29

SOLUTIONS

(b) Sa

D3:2

D1:0

Sc

Sb

D3:2 00 D1:0

00

01

11

10

00

1

0

X

1

00

01

0

1

X

1

11

1

1

X

10

0

1

X

01

11

10

1

1

X

1

01

1

0

X

1

X

11

1

1

X

X

X

10

1

0

X

X

Sa = D2D1D0 + D2D0 + D3 + D2D1 + D1D0

D3:2 00 D1:0

01 = D D 11 10 + D + D S D + D2D a 2 1 0 0 3 1

Sb = D1D0 + D1D0 + D2

Sd

D3:2 00 D1:0

01

11

10

00

1

1

X

1

00

1

0

X

1

01

1

1

X

1

01

0

1

X

0

11

1

1

X

X

11

1

0

X

X

10

0

1

X

X

10

1

1

X

X

Sc = D1 + D0 + D2

Sd = D2D1D0 + D2D0+ D2D1 + D1D0

© 2015 Elsevier, Inc.

30

chapter 2

SOLUTIONS

Se

D3:2

D1:0

Sf

D3:2 00 D1:0

00

01

11

10

01

11

10

00

1

0

X

1

00

1

1

X

1

01

0

0

X

0

01

0

1

X

1

11

0

0

X

X

11

0

0

X

X

10

1

1

X

X

10

0

1

X

X

Sf = D1D0 + D2D1+ D2D0 + D3

Se = D2D0 + D1D0

Sg

D3:2 00 D1:0

01

11

10

00

0

1

X

1

01

0

1

X

1

11

1

0

X

X

10

1

1

X

X

Sg = D2D1 + D2D0+ D2D1 + D3

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

(c) D3

D2

D1

D0

Sa

Exercise 2.35

Sb

Sc

Sd

Se

Sf

Sg

31

© 2015 Elsevier, Inc.

32

chapter 2

SOLUTIONS

Decimal Value 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

A3

A2

A1

A0

D

P

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1

0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0

P has two possible minimal solutions: D

A3:2

A1:0

P

A3:2 00 A1:0

00

01

11

10

01

11

10

00

0

0

1

0

00

0

0

0

0

01

0

0

0

1

01

0

1

1

0

11

1

0

1

0

11

1

1

0

1

10

0

1

0

0

10

1

0

0

0

D = A3A2A1A0 + A3A2A1A0 + A3A2A1A0 + A3A2A1A0 + A3A2A1A0

P = A3A2A0 + A3A1A0 + A3A2A1 + A2A1A0 P = A3A1A0 + A3A2A1 + A2A1A0 + A2A1A0

Hardware implementations are below (implementing the first minimal equation given for P).

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A3

A2

A1

A0

D

P

Exercise 2.36

A7

A6

A5

A4 A3

A2

A1

A0

Y2

Y1

Y0

NONE

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 1 X

0 0 0 0 0 0 1 X X

0 0 0 0 0 1 X X X

0 0 0 1 X X X X X

0 0 1 X X X X X X

0 1 X X X X X X X

0 0 0 0 0 1 1 1 1

0 0 0 1 1 0 0 1 1

0 0 1 0 1 0 1 0 1

1 0 0 0 0 0 0 0 0

0 0 0 0 1 X X X X

Y2 = A7 + A6 + A5 + A4 Y1 = A7 + A6 + A5 A4 A3 + A5 A4 A2 Y0 = A7 + A6 A5 + A6 A4 A3 + A6 A4 A 2 A1 NONE = A 7 A 6 A 5 A 4 A 3 A 2 A 1 A 0

33

© 2015 Elsevier, Inc.

34

SOLUTIONS

chapter 2

A7

A6

A5

A4

A3

A2

A1

A0

Y2 Y1

Y0

NONE

Exercise 2.37

The equations and circuit for Y2:0 is the same as in Exercise 2.25, repeated here for convenience. A7

A6

A5

A4 A3

A2

A1

A0

Y2

Y1

Y0

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 1 X

0 0 0 0 0 0 1 X X

0 0 0 0 0 1 X X X

0 0 0 1 X X X X X

0 0 1 X X X X X X

0 1 X X X X X X X

0 0 0 0 0 1 1 1 1

0 0 0 1 1 0 0 1 1

0 0 1 0 1 0 1 0 1

0 0 0 0 1 X X X X

Y2 = A7 + A6 + A5 + A4 Y1 = A7 + A6 + A5 A4 A3 + A5 A4 A2 Y0 = A7 + A6 A5 + A6 A4 A3 + A6 A4 A2 A1

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A7

A6

A5

A4

A3

A2

A1

A0

Y2 Y1

Y0

NONE

35

© 2015 Elsevier, Inc.

36

SOLUTIONS

chapter 2

The truth table, equations, and circuit for Z2:0 are as follows. A7

A6

A5

A4 A3

A2

A1

A0

Z2

Z1

Z0

0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1

0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1

0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 X

0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 X X X

0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 X X X X X X

0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 X X X X X X X X X X

1 0 0 0 0 0 0 1 1 1 1 1 1 X X X X X X X X X X X X X X X

1 1 1 1 1 1 1 X X X X X X X X X X X X X X X X X X X X X

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1

0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0

Z2 = A4  A5 + A6 + A7  + A5  A6 + A7  + A6 A7 Z1 = A2  A3 + A4 + A5 + A6 + A7  + A3  A4 + A5 + A6 + A7  + A6 A7 Z0 = A1  A2 + A3 + A4 + A5 + A6 + A7  + A3  A4 + A5 + A6 + A7  + A5  A6 + A7 

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

37

SOLUTIONS

A7

A6

A5

A4

A3

A2

A1

A0

Z2

Z1

Z0

Exercise 2.38

Y6 = A2 A1 A0 Y5 = A2 A1 Y4 = A2 A1 + A2 A0 Y3 = A2 Y2 = A2 + A1 A0 Y1 = A2 + A1 Y0 = A2 + A1 + A0

© 2015 Elsevier, Inc.

38

SOLUTIONS

chapter 2

A2 A1 A0 Y6 Y5

Y4 Y3 Y2 Y1 Y0

Exercise 2.39

Y = A + C  D = A + CD + CD Exercise 2.40

Y = CD  A  B  + AB = ACD + BCD + AB

Exercise 2.41

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

39

SOLUTIONS

A B C A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 1 0 0 0 0 0 0 1

000 001 010 011 100 101 110 111

A 0 0 1 1

B 0 1 0 1

Y

A 0 1

Y C 0 0 C AB

C

00 01 10

Y BC BC A

B C

0

Y

1

11

(b)

(a)

(c)

Exercise 2.42

A B C A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 1 0 1 1 0 0 1 1

(a)

000 001 010 011 100 101 110 111

A 0 0 1 1

Y

C 0 1 0 1

A 0 1

Y 1 B B B

A

AC

C B

00

B

(b)

Exercise 2.43

tpd = 3tpd_NAND2 = 60 ps tcd = tcd_NAND2 = 15 ps Exercise 2.44

tpd = tpd_AND2 + 2tpd_NOR2 + tpd_NAND2 = [30 + 2 (30) + 20] ps = 110 ps tcd = 2tcd_NAND2 + tcd_NOR2 = [2 (15) + 25] ps = 55 ps

01 10 11

Y B+C B

Y

0 1

(c)

Y

Y

Sarah L. Harris and David Money Harris Digital Design and Computer Architecture: ARM Edition 40 SOLUTIONS chapter 2

Exercise 2.45

tpd = tpd_NOT + tpd_AND3 = 15 ps + 40 ps = 55 ps tcd = tcd_AND3 = 30 ps A2

A1

A0

Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0

Exercise 2.46

© 2015 Elsevier, Inc.

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A3 A2 A1 A0

D

P

tpd = tpd_NOR2 + tpd_AND3 + tpd_NOR3 + tpd_NAND2 = [30 + 40 + 45 + 20] ps = 135 ps tcd = 2tcd_NAND2 + tcd_OR2 = [2 (15) + 30] ps = 60 ps Exercise 2.47

41

Sarah L. Harris and David Money Harris Digital Design and Computer Architecture: ARM Edition 42 SOLUTIONS chapter 2

© 2015 Elsevier, Inc.

A7 A6 A5 A4 A3 A2 A1 A0 Y2 Y1

Y0

NONE

tpd = tpd_INV + 3tpd_NAND2 + tpd_NAND3 = [15 + 3 (20) + 30] ps = 105 ps tcd = tcd_NOT + tcd_NAND2 = [10 + 15] ps = 25 ps Exercise 2.48

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

S2 S1 S0

D0

D1

D2

D3 Y D4

D5

D6

D7

tpd_dy = tpd_TRI_AY = 50 ps Note: the propagation delay from the control (select) input to the output is the circuit’s critical path: tpd_sy = tpd_NOT + tpd_AND3 + tpd_TRI_SY = [30 + 80 + 35] ps = 145 ps However, the problem specified to minimize the delay from data inputs to output, tpd_dy.

43

Sarah L. Harris and David Money Harris

44

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

chapter 2

SOLUTIONS

Question 2.1

A B

Y

Question 2.2

Y

Month

A3

A2

A1

A0

Y

Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec

0 0 0 0 0 0 0 1 1 1 1 1

0 0 0 1 1 1 1 0 0 0 0 1

0 1 1 0 0 1 1 0 0 1 1 0

1 0 1 0 1 0 1 0 1 0 1 0

1 0 1 0 1 0 1 1 0 1 0 1

A3:2 00 A1:0

01

11

10

00

X

0

1

1

01

1

1

X

0

11

1

1

X

0

10

0

0

X

1

A3 A0

Y

Y = A3A0 + A3A0 = A3 + A0

Question 2.3

A tristate buffer has two inputs and three possible outputs: 0, 1, and Z. One of the inputs is the data input and the other input is a control input, often called the enable input. When the enable input is 1, the tristate buffer transfers the data input to the output; otherwise, the output is high impedance, Z. Tristate buffers are used when multiple sources drive a single output at different times. One and only one tristate buffer is enabled at any given time.

See also  Plantation Life in the British West Indies, 1650–1850

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Question 2.4

(a) An AND gate is not universal, because it cannot perform inversion (NOT). (b) The set {OR, NOT} is universal. It can construct any Boolean function. For example, an OR gate with NOT gates on all of its inputs and output performs the AND operation. Thus, the set {OR, NOT} is equivalent to the set {AND, OR, NOT} and is universal. (c) The NAND gate by itself is universal. A NAND gate with its inputs tied together performs the NOT operation. A NAND gate with a NOT gate on its output performs AND. And a NAND gate with NOT gates on its inputs performs OR. Thus, a NAND gate is equivalent to the set {AND, OR, NOT} and is universal. Question 2.5

A circuit’s contamination delay might be less than its propagation delay because the circuit may operate over a range of temperatures and supply voltages, for example, 3-3.6 V for LVCMOS (low voltage CMOS) chips. As temperature increases and voltage decreases, circuit delay increases. Also, the circuit may have different paths (critical and short paths) from the input to the output. A gate itself may have varying delays between different inputs and the output, affecting the gate’s critical and short paths. For example, for a two-input NAND gate, a HIGH to LOW transition requires two nMOS transistor delays, whereas a LOW to HIGH transition requires a single pMOS transistor delay.

45

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CHAPTER 3

Exercise 3.1

S R Q

Exercise 3.2

S R Q

Exercise 3.3

41

Sarah L. Harris and David Money Harris SOLUTIONS chapter 3

42

clk D Q

Exercise 3.4

CLK D Q

Exercise 3.5

clk D Q

Exercise 3.6

CLK D Q

Digital Design and Coputer Architecture: ARM Edition

© 2015 Elsevier, Inc.

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 3.7

The circuit is sequential because it involves feedback and the output depends on previous values of the inputs. This is a SR latch. When S = 0 and R = 1, the circuit sets Q to 1. When S = 1 and R = 0, the circuit resets Q to 0. When both S and R are 1, the circuit remembers the old value. And when both S and R are 0, the circuit drives both outputs to 1. Exercise 3.8

Sequential logic. This is a D flip-flop with active low asynchronous set and reset inputs. If S and R are both 1, the circuit behaves as an ordinary D flip-flop. If S = 0, Q is immediately set to 0. If R = 0, Q is immediately reset to 1. (This circuit is used in the commercial 7474 flip-flop.) Exercise 3.9

clk Q

Exercise 3.10

J K

clk Q clk

clk (a)

(b)

D

J K

Q

(c)

Q

Exercise 3.11

If A and B have the same value, C takes on that value. Otherwise, C retains its old value.

43

© 2015 Elsevier, Inc.

44

SOLUTIONS

chapter 3

Exercise 3.12

Make sure these next ones are correct too. R clk

D

N1

Q

N2

Q

Exercise 3.13

Q

R clk R R D

Exercise 3.14

Q

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CLK D Set

D

Q Q

CLK

Q

Q

D Set

Exercise 3.15

CLK Set

Set Q

D

Q Set

Exercise 3.16

1 1 From ————– to ————– . 2Nt pd 2Nt cd Exercise 3.17

If N is even, the circuit is stable and will not oscillate. Exercise 3.18

Set

45

© 2015 Elsevier, Inc.

46

SOLUTIONS

chapter 3

(a) No: no register. (b) No: feedback without passing through a register. (c) Yes. Satisfies the definition. (d) Yes. Satisfies the definition. Exercise 3.19

The system has at least five bits of state to represent the 24 floors that the elevator might be on. Exercise 3.20

The FSM has 54 = 625 states. This requires at least 10 bits to represent all the states. Exercise 3.21

The FSM could be factored into four independent state machines, one for each student. Each of these machines has five states and requires 3 bits, so at least 12 bits of state are required for the factored design. Exercise 3.22

This finite state machine asserts the output Q for one clock cycle if A is TRUE followed by B being TRUE.

state

encoding s1:0

S0

00

S1

01

S2

10

TABLE 3.1 State encoding for Exercise 3.22

. current state

inputs

next state

s1

s0

a

b

s’1

s’0

0

0

0

X

0

0

0

0

1

X

0

1

TABLE 3.2 State transition table with binary encodings for Exercise 3.22

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

current state

inputs

next state

s1

s0

a

b

s’1

s’0

0

1

X

0

0

0

0

1

X

1

1

0

1

0

X

X

0

0

TABLE 3.2 State transition table with binary encodings for Exercise 3.22

. current state

output

s1

s0

q

0

0

0

0

1

0

1

0

1

TABLE 3.3 Output table with binary encodings for Exercise 3.22

S’ 1 = S 0 B S’ 0 = S 1 S 0 A Q = S1

CLK

B

S’1

S1

S’0

A

S0 r Reset

S1

S0

Q

47

Sarah L. Harris and David Money Harris Digital Design and Computer Architecture: ARM Edition 48 SOLUTIONS chapter 3

© 2015 Elsevier, Inc.

Exercise 3.23

This finite state machine asserts the output Q when A AND B is TRUE.

state

encoding s1:0

S0

00

S1

01

S2

10

TABLE 3.4 State encoding for Exercise 3.23

current state

inputs

next state

output

s1

s0

a

b

s’1

s’0

q

0

0

0

X

0

0

0

0

0

1

X

0

1

0

0

1

X

0

0

0

0

0

1

X

1

1

0

0

1

0

1

1

1

0

1

1

0

0

0

0

0

0

1

0

0

1

0

0

0

1

0

1

0

0

0

0

TABLE 3.5 Combined state transition and output table with binary encodings for Exercise 3.23

S’ 1 = S 1 S 0 B + S 1 AB S’ 0 = S 1 S 0 A Q’ = S 1 AB

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A

B

CLK S’1

S1

S’0

Q

S0 r Reset

S1

S0

Exercise 3.24

TA

Reset S0 LA: green LB: red

TA

S5 LA: red LB: red

S1 LA: yellow LB: red

S2 LA: red LB: red

S4 LA: red LB: yellow

S3 LA: red LB: green

TB TB

state

encoding s1:0

S0

000

S1

001

S2

010

TABLE 3.6 State encoding for Exercise 3.24

49

Sarah L. Harris and David Money Harris Digital Design and Computer Architecture: ARM Edition 50 SOLUTIONS chapter 3

state

encoding s1:0

S3

100

S4

101

S5

110

© 2015 Elsevier, Inc.

TABLE 3.6 State encoding for Exercise 3.24

current state

inputs

next state

s2

s1

s0

ta

tb

s’2

s’1

s’0

0

0

0

0

X

0

0

1

0

0

0

1

X

0

0

0

0

0

1

X

X

0

1

0

0

1

0

X

X

1

0

0

1

0

0

X

0

1

0

1

1

0

0

X

1

1

0

0

1

0

1

X

X

1

1

0

1

1

0

X

X

0

0

0

TABLE 3.7 State transition table with binary encodings for Exercise 3.24

S’ 2 = S 2  S 1 S’ 1 = S 1 S 0 S’ 0 = S 1 S 0  S 2 t a + S 2 t b 

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

51

SOLUTIONS

current state

outputs

s2

s1

s0

la1

la0

lb1

lb0

0

0

0

0

0

1

0

0

0

1

0

1

1

0

0

1

0

1

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

0

1

1

1

0

1

0

1

0

TABLE 3.8 Output table for Exercise 3.24

L A1 = S 1 S 0 + S 2 S 1 L A0 = S 2 S 0

(3.1)

L B1 = S 2 S 1 + S 1 S 0 L B0 = S 2 S 1 S 0

Ta Tb S2 S1 S0

CLK S’2

S2

S’1

S1

S’0

S0 r Reset

FIGURE 3.1 State machine circuit for traffic light controller for Exercise 3.21

Sarah L. Harris and David Money Harris Digital Design and Computer Architecture: ARM Edition 52 SOLUTIONS chapter 3

© 2015 Elsevier, Inc.

Exercise 3.25

0/0 1/1 reset

1/0

S0

1/0

0/0

S1

0/0

S2

S3 0/1

0/0 1/0 S4 1/0

state

encoding s1:0

S0

000

S1

001

S2

010

S3

100

S4

101

TABLE 3.9 State encoding for Exercise 3.25

current state

input

next state

output

s2

s1

s0

a

s’2

s’1

s’0

q

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

0

TABLE 3.10 Combined state transition and output table with binary encodings for Exercise 3.25

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

53

SOLUTIONS

current state

input

next state

output

s2

s1

s0

a

s’2

s’1

s’0

q

0

0

1

0

0

0

0

0

0

0

1

1

0

1

0

0

0

1

0

0

1

0

0

0

0

1

0

1

1

0

1

0

1

0

0

0

0

0

0

0

1

0

0

1

0

0

1

1

1

0

1

0

1

0

0

1

1

0

1

1

1

0

1

0

TABLE 3.10 Combined state transition and output table with binary encodings for Exercise 3.25

S’ 2 = S 2 S 1 S 0 + S 2 S 1 S 0 S’ 1 = S 2 S 1 S 0 A S’ 0 = A  S 2 S 0 + S 2 S 1  Q = S2 S1 S0 A + S2 S1 S0 A

A CLK S2 S1 S0

S’2

S2

S’1

S1

S’0

S0 r Reset

© 2015 Elsevier, Inc. chapter 3

Exercise 3.26

N

Reset

D Q

N D Q

S0 Nickel

Quarter

D

N

Q

Dime

N

S10

S25 Dispense

Dime

Nickel

Quarter

N

Q

Dime

Q

Quarter

D

Nickel

S5

D

SOLUTIONS

Nickel

S20

Q

S15

D

S30 Dispense ReturnNickel

N

54

S35 Dispense ReturnDime

Dime Dime Quarter

Nickel Quarter

S40

S45

Dispense ReturnDime ReturnNickel

Dispense ReturnTwoDimes

Note: N D Q = Nickel Dime Quarter

FIGURE 3.2 State transition diagram for soda machine dispense of Exercise 3.23

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

state

encoding s9:0

S0

0000000001

S5

0000000010

S10

0000000100

S25

0000001000

S30

0000010000

S15

0000100000

S20

0001000000

S35

0010000000

S40

0100000000

S45

1000000000

FIGURE 3.3 State Encodings for Exercise 3.26

current state s

nickel

dime

quarter

next state s’

S0

0

0

0

S0

S0

0

0

1

S25

S0

0

1

0

S10

S0

1

0

0

S5

S5

0

0

0

S5

S5

0

0

1

S30

S5

0

1

0

S15

S5

1

0

0

S10

S10

0

0

0

S10

inputs

TABLE 3.11 State transition table for Exercise 3.26

55

Sarah L. Harris and David Money Harris Digital Design and Computer Architecture: ARM Edition 56 SOLUTIONS chapter 3

© 2015 Elsevier, Inc.

current state s

nickel

dime

quarter

next state s’

S10

0

0

1

S35

S10

0

1

0

S20

S10

1

0

0

S15

S25

X

X

X

S0

S30

X

X

X

S0

S15

0

0

0

S15

S15

0

0

1

S40

S15

0

1

0

S25

S15

1

0

0

S20

S20

0

0

0

S20

S20

0

0

1

S45

S20

0

1

0

S30

S20

1

0

0

S25

S35

X

X

X

S0

S40

X

X

X

S0

S45

X

X

X

S0

inputs

TABLE 3.11 State transition table for Exercise 3.26

current state s

nickel

dime

quarter

0000000001

0

0

0

0000000001

0000000001

0

0

1

0000001000

0000000001

0

1

0

0000000100

0000000001

1

0

0

0000000010

inputs

TABLE 3.12 State transition table for Exercise 3.26

next state s’

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

current state s

nickel

dime

quarter

0000000010

0

0

0

0000000010

0000000010

0

0

1

0000010000

0000000010

0

1

0

0000100000

0000000010

1

0

0

0000000100

0000000100

0

0

0

0000000100

0000000100

0

0

1

0010000000

0000000100

0

1

0

0001000000

0000000100

1

0

0

0000100000

0000001000

X

X

X

0000000001

0000010000

X

X

X

0000000001

0000100000

0

0

0

0000100000

0000100000

0

0

1

0100000000

0000100000

0

1

0

0000001000

0000100000

1

0

0

0001000000

0001000000

0

0

0

0001000000

0001000000

0

0

1

1000000000

0001000000

0

1

0

0000010000

0001000000

1

0

0

0000001000

0010000000

X

X

X

0000000001

0100000000

X

X

X

0000000001

1000000000

X

X

X

0000000001

inputs

TABLE 3.12 State transition table for Exercise 3.26

S’ 9 = S 6 Q S’ 8 = S 5 Q

next state s’

57

© 2015 Elsevier, Inc.

58

SOLUTIONS

chapter 3

S’ 7 = S 2 Q S’ 6 = S 2 D + S 5 N + S 6 NDQ S’ 5 = S 1 D + S 2 N + S 5 NDQ S’ 4 = S 1 Q + S 6 D S’ 3 = S 0 Q + S 5 D + S 6 N S’ 2 = S 0 D + S 1 N + S 2 NDQ S’ 1 = S 0 N + S 1 NDQ S’ 0 = S 0 NDQ + S 3 + S 4 + S 7 + S 8 + S 9 Dispense = S 3 + S 4 + S 7 + S 8 + S 9 ReturnNickel = S 4 + S 8 ReturnDime = S 7 + S 8 ReturnTwoDimes = S 9

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

59

© 2015 Elsevier, Inc.

60

chapter 3

Quarter Dime Nickel

SOLUTIONS

CLK S’9

S9

S’8

S8

S’7

S7

S’6

S6

S’5

S5

S’4

S4

S’3

S3

S’2

S2

S’1

S1

ReturnTwoDimes

r CLK S’0 Reset

S0

s

ReturnDime ReturnNickel Dispense

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 3.27

Reset

S000

S001

S011

S010

S110

S111

S101

S100

FIGURE 3.4 State transition diagram for Exercise 3.27

61

© 2015 Elsevier, Inc.

62

SOLUTIONS

chapter 3

current state s2:0

next state s’2:0

000

001

001

011

011

010

010

110

110

111

111

101

101

100

100

000

TABLE 3.13 State transition table for Exercise 3.27

S’ 2 = S 1 S 0 + S 2 S 0 S’ 1 = S 2 S 0 + S 1 S 0 S’ 0 = S 2  S 1 Q2 = S2 Q1 = S1 Q0 = S0

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CLK S ‘2

S2

S ‘1

S1

S ‘0

S0

r S2 S1 S0

Q2

Q1

Q0

Reset

FIGURE 3.5 Hardware for Gray code counter FSM for Exercise 3.27

Exercise 3.28

63

© 2015 Elsevier, Inc.

64

SOLUTIONS

chapter 3

Reset

S000

UP

UP S001

UP

UP S011

UP

UP S010

UP UP

UP UP

S110

UP

UP S111

UP

UP S101

UP

UP S100

FIGURE 3.6 State transition diagram for Exercise 3.28

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

current state s2:0

input up

next state s’2:0

000

1

001

001

1

011

011

1

010

010

1

110

110

1

111

111

1

101

101

1

100

100

1

000

000

0

100

001

0

000

011

0

001

010

0

011

110

0

010

111

0

110

101

0

111

100

0

101

TABLE 3.14 State transition table for Exercise 3.28

S’ 2 = UPS 1 S 0 + UPS 1 S 0 + S 2 S 0 S’ 1 = S 1 S 0 + UPS 2 S 0 + UPS 2 S 1 S’ 0 = UP  S 2  S 1 Q2 = S2 Q1 = S1 Q0 = S0

65

© 2015 Elsevier, Inc.

66

SOLUTIONS

chapter 3

UP

CLK S ‘2

S2

S ‘1

S1

S ‘0 S2 S1 S0

S0

r

Q2

Q1

Q0

Reset

FIGURE 3.7 Finite state machine hardware for Exercise 3.28

Exercise 3.29

(a) CLK A B Z

FIGURE 3.8 Waveform showing Z output for Exercise 3.29

(b) This FSM is a Mealy FSM because the output depends on the current value of the input as well as the current state.

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

(c) Reset A/0 S0 BA/0

BA/0 BA/1 BA/0 BA/1

BA/0

S3

S1

BA/1

BA/1

BA/1 BA/1

BA/1

BA/1 BA/0

S2 BA/0 FIGURE 3.9 State transition diagram for Exercise 3.29

(Note: another viable solution would be to allow the state to transition from S0 to S1 on BA  0 . The arrow from S0 to S0 would then be BA  0 .)

current state s1:0

inputs

next state s’1:0

output

b

a

00

X

0

00

0

00

0

1

11

0

00

1

1

01

1

01

0

0

00

0

01

0

1

11

1

01

1

0

10

1

01

1

1

01

1

10

0

X

00

0

10

1

0

10

0

z

TABLE 3.15 State transition table for Exercise 3.29

67

© 2015 Elsevier, Inc.

68

SOLUTIONS

chapter 3

current state s1:0

inputs

next state s’1:0

output

b

a

10

1

1

01

1

11

0

0

00

0

11

0

1

11

1

11

1

0

10

1

11

1

1

01

1

z

TABLE 3.15 State transition table for Exercise 3.29

S’ 1 = BA  S 1 + S 0  + BA  S 1 + S 0  S’ 0 = A  S 1 + S 0 + B  Z = BA + S 0  A + B 

See also  Complexity and Contradiction in Architecture

B A CLK S’1

S1

Z S’0

S0 r Reset

FIGURE 3.10 Hardware for FSM of Exercise 3.26

Note: One could also build this functionality by registering input A, producing both the logical AND and OR of input A and its previous (registered)

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

value, and then muxing the two operations using B. The output of the mux is Z: Z = AAprev (if B = 0); Z = A + Aprev (if B = 1). Exercise 3.30

reset

reset

S0 A

A

SZero A A

S1

A

SOne

A

A

S11 Y

A

STwo A

A SThree X

FIGURE 3.11 Factored state transition diagram for Exercise 3.30

current state s1:0

input a

next state s’1:0

00

0

00

00

1

01

01

0

00

TABLE 3.16 State transition table for output Y for Exercise 3.30

69

© 2015 Elsevier, Inc.

70

SOLUTIONS

chapter 3

current state s1:0

input a

next state s’1:0

01

1

11

11

X

11

TABLE 3.16 State transition table for output Y for Exercise 3.30

current state t 1:0

input a

next state t’1:0

00

0

00

00

1

01

01

0

01

01

1

10

10

0

10

10

1

11

11

X

11

TABLE 3.17 State transition table for output X for Exercise 3.30

S’ 1 = S 0  S 1 + A  S’ 0 = S 1 A + S 0  S 1 + A  Y = S1 T’ 1 = T 1 + T 0 A T’ 0 = A  T 1 + T 0  + AT 0 + T 1 T 0 X = T1 T0

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

A CLK S’1

S1

S’0

S0

Y

r Reset

S1 S0

CLK T’1

T1

T’0

T0 X r Reset

T1 T0

FIGURE 3.12 Finite state machine hardware for Exercise 3.30

Exercise 3.31

This finite state machine is a divide-by-two counter (see Section 3.4.2) when X = 0. When X = 1, the output, Q, is HIGH.

current state

input

next state

s1

s0

x

s’1

s’0

0

0

0

0

1

0

0

1

1

1

0

1

0

0

0

TABLE 3.18 State transition table with binary encodings for Exercise 3.31

71

© 2015 Elsevier, Inc.

72

chapter 3

SOLUTIONS

current state

input

next state

s1

s0

x

s’1

s’0

0

1

1

1

0

1

X

X

0

1

TABLE 3.18 State transition table with binary encodings for Exercise 3.31

current state

output

s1

s0

q

0

0

0

0

1

1

1

X

1

TABLE 3.19 Output table for Exercise 3.31

1 1

0 S00 0

S01 1

S10 1

S11 1

0

Exercise 3.32

current state

input

next state

s2

s1

s0

a

s’2

s’1

s’0

0

0

1

0

0

0

1

0

0

1

1

0

1

0

1

0

0

0

0

1

0

TABLE 3.20 State transition table with binary encodings for Exercise 3.32

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc.

73

SOLUTIONS

current state

input

next state

s2

s1

s0

a

s’2

s’1

s’0

0

1

0

1

1

0

0

1

0

0

0

0

0

1

1

0

0

1

1

0

0

TABLE 3.20 State transition table with binary encodings for Exercise 3.32

S0 0

S1 0 A

A

A

A

S2 1 A

A FIGURE 3.13 State transition diagram for Exercise 3.32

Q asserts whenever A is HIGH for two or more consecutive cycles. Exercise 3.33

(a) First, we calculate the propagation delay through the combinational logic:

tpd = 3tpd_XOR = 3 × 100 ps = 300 ps Next, we calculate the cycle time: Tc  tpcq + tpd + tsetup

 [70 + 300 + 60] ps = 430 ps f = 1 / 430 ps = 2.33 GHz

(b) Tc  tpcq + tpd + tsetup + tskew Thus, tskew  Tc (tpcq + tpd + tsetup), where Tc = 1 / 2 GHz = 500 ps

 [500430] ps = 70 ps

(c)

© 2015 Elsevier, Inc.

74

SOLUTIONS

chapter 3

First, we calculate the contamination delay through the combinational logic:

tcd = tcd_XOR = 55 ps tccq + tcd > thold + tskew Thus, tskew < (tccq + tcd) – thold < (50 + 55) – 20 < 85 ps (d) clk

clk

FIGURE 3.14 Alyssa’s improved circuit for Exercise 3.33

First, we calculate the propagation and contamination delays through the combinational logic: tpd = 2tpd_XOR = 2 × 100 ps = 200 ps tcd = 2tcd_XOR = 2 × 55 ps = 110 ps Next, we calculate the cycle time: Tc  tpcq + tpd + tsetup

 [70 + 200 + 60] ps

f

= 330 ps = 1 / 330 ps = 3.03 GHz

tskew < (tccq + tcd) – thold < (50 + 110) – 20 < 140 ps

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Exercise 3.34

(a) 9.09 GHz (b) 15 ps (c) 26 ps Exercise 3.35

(a) Tc = 1 / 40 MHz = 25 ns

Tc  tpcq + NtCLB + tsetup

25 ns  [0.72 + N(0.61) + 0.53] ps Thus, N < 38.9 N = 38 (b) tskew < (tccq + tcd_CLB) – thold < [(0.5 + 0.3) – 0] ns < 0.8 ns = 800 ps

Exercise 3.36

1.138 ns Exercise 3.37

P(failure)/sec = 1/MTBF = 1/(50 years * 3.15 x 107 sec/year) = 6.34 x 10-10 (EQ 3.26) P(failure)/sec waiting for one clock cycle: N*(T0/Tc)*e-(Tc-tsetup)/Tau = 0.5 * (110/1000) * e-(1000-70)/100 = 5.0 x 10-6 P(failure)/sec waiting for two clock cycles: N*(T0/Tc)*[e-(Tc-tsetup)/Tau]2 = 0.5 * (110/1000) * [e-(1000-70)/100]2 = 4.6 x 10-10 This is just less than the required probability of failure (6.34 x 10-10). Thus, 2 cycles of waiting is just adequate to meet the MTBF.

75

© 2015 Elsevier, Inc.

76

SOLUTIONS

chapter 3

Exercise 3.38

(a) You know you’ve already entered metastability, so the probability that the sampled signal is metastable is 1. Thus, t – -

P  failure  = 1  e Solving for the probability of still being metastable (failing) to be 0.01: t – -

P  failure  = e = 0.01 Thus, t = –   ln  P  failure   = – 20  ln   0.01   = 92 seconds (b) The probability of death is the chance of still being metastable after 3 minutes P(failure) = 1 × e -(3 min × 60 sec) / 20 sec = 0.000123

Exercise 3.39

We assume a two flip-flop synchronizer. The most significant impact on the probability of failure comes from the exponential component. If we ignore the T0/Tc term in the probability of failure equation, assuming it changes little with increases in cycle time, we get: P  failure  = e

t – -

1 MTBF = ————————— = e P  failure 

T c – t setup ———————–

T c2 – T c1

———————MTBF 2 30ps ——————- = 10 = e MTBF 1

Solving for Tc2 – Tc1, we get: T c2 – T c1 = 69ps

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Thus, the clock cycle time must increase by 69 ps. This holds true for cycle times much larger than T0 (20 ps) and the increased time (69 ps). Exercise 3.40

Alyssa is correct. Ben’s circuit does not eliminate metastability. After the first transition on D, D2 is always 0 because as D2 transitions from 0 to 1 or 1 to 0, it enters the forbidden region and Ben’s “metastability detector” resets the first flip-flop to 0. Even if Ben’s circuit could correctly detect a metastable output, it would asynchronously reset the flip-flop which, if the reset occurred around the clock edge, this could cause the second flip-flop to sample a transitioning signal and become metastable. Question 3.1

77

© 2015 Elsevier, Inc.

78

SOLUTIONS

chapter 3

reset

Sreset A A

S0 A

A

S01

A

A A

S010 A

S0101

A

A

A

S01010 Q=1

A

FIGURE 3.15 State transition diagram for Question 3.1

current state s5:0

input

000001

0

000010

000001

1

000001

a

next state s’5:0

TABLE 3.21 State transition table for Question 3.1

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

current state s5:0

input

000010

0

000010

000010

1

000100

000100

0

001000

000100

1

000001

001000

0

000010

001000

1

010000

010000

0

100000

010000

1

000001

100000

0

000010

100000

1

000001

a

next state s’5:0

TABLE 3.21 State transition table for Question 3.1

S’ 5 = S 4 A S’ 4 = S 3 A S’ 3 = S 2 A S’ 2 = S 1 A S’ 1 = A  S 1 + S 3 + S 5  S’ 0 = A  S 0 + S 2 + S 4 + S 5  Q = S5

79

© 2015 Elsevier, Inc.

80

SOLUTIONS

chapter 3

CLK S ‘5

S5

S ‘4

S4

S ‘3

S3

S ‘2

S2

S ‘1

S1

S ‘0

S0

Q

r Reset

FIGURE 3.16 Finite state machine hardware for Question 3.1

Question 3.2

The FSM should output the value of A until after the first 1 is received. It then should output the inverse of A. For example, the 8-bit two’s complement of the number 6 (00000110) is (11111010). Starting from the least significant bit on the far right, the two’s complement is created by outputting the same value of the input until the first 1 is reached. Thus, the two least significant bits of the two’s complement number are “10”. Then the remaining bits are inverted, making the complete number 11111010.

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

Start

S0 Q=0 A A S1 Q=1 A

A A

S2 Q=0

A

S3 Q=1

A

A

FIGURE 3.17 State transition diagram for Question 3.2

current state s1:0

input

00

0

00

00

1

01

01

0

11

01

1

10

10

0

11

10

1

10

11

0

11

11

1

10

a

next state s’1:0

TABLE 3.22 State transition table for Question 3.2

S’ 1 = S 1 + S 0 S’ 0 = A   S 1 + S 0  Q = S0

81

© 2015 Elsevier, Inc.

82

SOLUTIONS

chapter 3

CLK

A

S ‘1

S1

S ‘0

S0

Q

r Start

FIGURE 3.18 Finite state machine hardware for Question 3.2

Question 3.3

A latch allows input D to flow through to the output Q when the clock is HIGH. A flip-flop allows input D to flow through to the output Q at the clock edge. A flip-flop is preferable in systems with a single clock. Latches are preferable in two-phase clocking systems, with two clocks. The two clocks are used to eliminate system failure due to hold time violations. Both the phase and frequency of each clock can be modified independently.

Question 3.4

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

reset

S00000

S00001

S00010

S00011

S11110

S11111

FIGURE 3.19 State transition diagram for Question 3.4

current state s4:0

next state s’4:0

00000

00001

00001

00010

TABLE 3.23 State transition table for Question 3.4

83

© 2015 Elsevier, Inc.

84

SOLUTIONS

chapter 3

current state s4:0

next state s’4:0

00010

00011

00011

00100

00100

00101

11110

11111

11111

00000

TABLE 3.23 State transition table for Question 3.4

S’ 4 = S 4  S 3 S 2 S 1 S 0 S’ 3 = S 3  S 2 S 1 S 0 S’ 2 = S 2  S 1 S 0 S’ 1 = S 1  S 0 S’ 0 = S 0 Q 4:0 = S 4:0

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CLK S ‘4

S4

S ‘3

S3

S ‘2

S2

S ‘1

S1

S ‘0

S0

Q4 Q3 Q2 Q1 Q0

r Reset

FIGURE 3.20 Finite state machine hardware for Question 3.4

Question 3.5

Reset

S0 Q=0 A A

A

A

S1 Q=1 A S2 Q=0 A

FIGURE 3.21 State transition diagram for edge detector circuit of Question 3.5

85

© 2015 Elsevier, Inc.

86

SOLUTIONS

chapter 3

current state s1:0

input

00

0

00

00

1

01

01

0

00

01

1

10

10

0

00

10

1

10

next state s’1:0

a

TABLE 3.24 State transition table for Question 3.5

S’ 1 = AS 1 S’ 0 = AS 1 S 0 Q = S1 A

CLK S ‘1

S1

S ‘0

S0

Q

r Reset

FIGURE 3.22 Finite state machine hardware for Question 3.5

Question 3.6

Pipelining divides a block of combinational logic into N stages, with a register between each stage. Pipelining increases throughput, the number of tasks that can be completed in a given amount of time. Ideally, pipelining increases throughput by a factor of N. But because of the following three reasons, the

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

speedup is usually less than N: (1) The combinational logic usually cannot be divided into N equal stages. (2) Adding registers between stages adds delay called the sequencing overhead, the time it takes to get the signal into and out of the register, tsetup + tpcq. (3) The pipeline is not always operating at full capacity: at the beginning of execution, it takes time to fill up the pipeline, and at the end it takes time to drain the pipeline. However, pipelining offers significant speedup at the cost of little extra hardware.

Question 3.7

A flip-flop with a negative hold time allows D to start changing before the clock edge arrives.

Question 3.8

We use a divide-by-three counter (see Example 3.6 on page 155 of the textbook) with A as the clock input followed by a negative edge-triggered flip-flop, which samples the input, D, on the negative or falling edge of the clock, or in this case, A. The output is the output of the divide-by-three counter, S0, OR the output of the negative edge-triggered flip-flop, N1. Figure 3.24 shows the waveforms of the internal signals, S0 and N1. A S2 Reset

r

S1 r

S0 s

N1 r

FIGURE 3.23 Hardware for Question 3.8

A B S1 N1 FIGURE 3.24 Waveforms for Question 3.8

B

87

© 2015 Elsevier, Inc.

88

SOLUTIONS

chapter 3

Question 3.9

Without the added buffer, the propagation delay through the logic, tpd, must be less than or equal to Tc – (tpcq + tsetup). However, if you add a buffer to the clock input of the receiver, the clock arrives at the receiver later. The earliest that the clock edge arrives at the receiver is tcd_BUF after the actual clock edge. Thus, the propagation delay through the logic is now given an extra tcd_BUF. So, tpd now must be less than Tc + tcd_BUF – (tpcq + tsetup).

Sarah L. Harris and David Money Harris

Digital Design and Computer Architecture: ARM Edition

© 2015 Elsevier, Inc. SOLUTIONS

CHAPTER 4

Note: the HDL files given in the following solutions are available on the textbook’s companion website at: http://textbooks.elsevier.com/9780123704979 Exercise 4.1

a b c

y

z

Exercise 4.2

a2 a1 a0 y1 y0

85

© 2015 Elsevier, Inc.

86

SOLUTIONS

chapter 4

Exercise 4.3

SystemVerilog

VHDL

module xor_4(input logic [3:0] a, output logic y);

library IEEE; use IEEE.STD_LOGIC_1164.all; entity xor_4 is port(a: in STD_LOGIC_VECTOR(3 downto 0); y: out STD_LOGIC); end;

assign y = ^a; endmodule

architecture synth of xor_4 is begin y

Video tutorials: Solution manual Digital Design and

Articles in category: architecture

Leave a Reply

Back to top button