Digital Design and oly oliccwetea ira aeic: RU s\@eava se lie(ey a) Sarah L Harris David Money Harris9s Exercises Exercises Exercise 2.1 Write a Boolean equation in sum-of-products canonical form for 2.80. each of the truth tables in Figui @ Cy ae _cly asec ply aec oly (C) Figure 2,80 Truth tales for Exercises 2,1, 2.3, and 2.41 Exercise 2.2 Write a Boolean equation in sum-of-products canonical form for cach of the teuth tables in Figure 2.81 > 5 | > 5 o| cS = | cS e* > | cy s* > | Figure 2.81 Truth tables for Exercises 2.2 and 2.496 Combinational Logic Design Exercise 2.3 Write a Boolean equation in product-of-sums canonical form for the truth tables in Figure 2.80. Exercise 2.4 Write a Boolean equation in product-of-sums canonical form for the truth tables in Figuee 2.81 Exercise 2.5 Minimize each of the Boolean equations from Exercise 2.1 Exercise 2.6 Minimize each of the Boolean equations from Exercise 2.2. Exercise 2.7 Sketch a reasonably simple combinational circuit implementing cach of the functions from Exercise 2.5. Reasonably simple means that you are not wasteful of gates, but you don’t waste vast amounts of time checking every possible implementation of the circuit either. Exercise 2.8 Sketch a reasonably simple combinational circuit implementing each of the functions from Exercise 2.6 Exercise 2.9 Repeat Exercise 2.7 using only NOT gates and AND and OR gates. Exercise 2.10 Repeat Exercise 2.8 using only NOT gates and AND and OR gates. Exercise 2,11 Repeat Exercise 2.7 using only NOT gates and NAND and NOR gates. Exercise 2.12 Repeat Exercise 2.8 using only NOT gates and NAND and NOR gates. Exercise 2.13 Simplify the following Boolean equations using Boolean theorems. Check for correctness using a truth table or K-map. (a) Y= Ac 4 ABe (b) ¥ = AB + ABT + (A+ OQ) () Y= ABCD + ABC + ABCD + aBp + ABCD + BCD + A Exercise 2.14 Simplify the following Boolean equations using Boolean theorems. Check for correctness using a truth table or Kemap. (a) ¥ = Ac + ABt (b) Y = ABC + AB (). ¥ = ABCD + ABCD + (AF BF CHD)Exercises 97 Exercise 2.15 Sketch a reasonably simple combinational circuit implementing each of the functions from Exercise 2.13 Exercise 2.16 Sketch a reasonably simple combinational circuit implementing each of the functions from Exercise 2.14 Exercise 2.17 Simplify each of the following Boolean equations. Sketch a reasonably simple combinational circuit implementing the simplified equation, (a) ¥ = BC+ ABT + BT (b) Y= A+AB+AB + A+B (]_ ¥ = ABC + ABD + ABE + ACD + ACE + (A¥ D+ £) + BCD + BCE + BDE ~CDE Exercise 2.18 Simplify each of the following Boolean equations. Sketch a reasonably simple combinational circuit implementing the simplified equation. (a) Y = ABC + BC + BC (b) ¥ i ¥ AFEFOD + AD+B ABCD ~ ABCD ~ (B+ D)E Exercise 2.19 Give an example of a truth table requiring between 3 billion and 5 billion rows that can be constructed using fewer than 40 (but at least 1) two- input gates Exercise 2.20 Give an example of a circuit with a cyclic path that is nevertheless combinational, Exercise 2.21 Alyssa P. Hacker says that any Boolean function can be written in minimal sum-of-products form as the sum of all of the prime implicants of the function. Ben Bitdiddle says that there are some functions whose minimal equation does not involve all of the prime implicants. Explain why Alyssa is right or provide a counterexample demonstrating Ben’s point. Exercise 2.22 Prove that the following theorems are true using perfect induction. You need not prove their duals. (a) The idempotency theorem (T3) (b). The distributivity theorem (T8) (c]_ The combining theorem (T10)8 ‘Combinational Logic Design Exercise 2.23 Prove De Morgan's Theorem (T12) for three variables, A, B, and C, using perfect induction. Exercise 2.24 Write Boolean equations for the circuit in Figure 2.82. You need not minimize the equations. ABCD U yo Figure 2.82 Circult schomatlc for Exercise 2.24 Exercise 2.25 Minimize the Boolean equations from Exercise 2.24 and sketch an improved circuit with the same function. Exercise 2,26 Using De Morgan equivalent gates and bubble pushing methods, redraw the circuit in Figure 2.83 so that you can find the Boolean equation by inspection, Write the Boolean equation. af» y 1, Figure 2.83 Circuit schematic for Exercises 2.26.Exercises Exercise 2.27 Repeat Exercise 2.26 for the circuit in Figure 2.84 ()) Figure 2.84 Circuit schematic for Exercises 2.27 and 2.44 Exercise 2.28 Find a minimal Boolean equation for the function in Figure 2.85. Remember to take advantage of the don’t care entries. 8 o ° 1 1 1 1 ° ° ° ° 1 1 1 1 Figure 2.85 Truth table for Exercise 2.28 Exercise 2.29 Sketch a circuit for the function from Exercise 2.28. Exercise 2.30 Does your circuit from Exercise 2.29 have any potential glitches when one of the inputs changes? If not, explain why not. If s0, show how to modify the circuit to eliminate the glitches Exercise 2.31 Find a minimal Boolean equation for the funetion in Figure 2.86, Remember to take advantage of the don’t care entries. 99100 CHAPTER TWO Combinational Logic Design Figure 2.86 Truth ta for Exercise 2.31 Exercise 2.32 Sketch a circuit for the function from Exercise 2.31. Exercise 2.33 Ben Bitdidadle will enjoy his picnic on sunny days that have no ants. He will also enjoy his picnic any day he sees a hummingbird, as well as on days where there are ants and ladybugs. Write a Boolean equation for his enjoyment (E) in terms of sun (S), ants (A), hummingbirds (H), and ladybugs (L) Exercise 2.34 Complete the design of the seven-segment decoder segments S, through 5, (see Example 2.10) (a) Derive Boolean equations for the outputs 5. through S, assuming that inputs greater than 9 must produce blank (0) outputs. (b) Derive Boolean equations for the outputs 5. through S, assuming that inputs greater than 9 are don't cares. (c)_ Sketch a reasonably simple gate-level implementation of part (b). Multiple outputs can share gates where appropriate. Exercise 2.35 A circuit has four inputs and two outputs. The inputs As. represent a number from 0 to 15, Output P should be TRUE if the number is prime (0 and are not prime, but 2, 3, 5, and so on, are prime). Output D should be TRUE if the number is divisible by 3. Give simplified Boolean equations for each output and sketch a circuit. Exercise 2.36 A priority encoder has 2" inputs. It produces an N-bit binary coutpat indicating the most significant bit of the input that is TRUE or 0 if noneExercises of the inputs are TRUE, It also produces an output NONE that is TRUE if none of the inputs are TRUE, Design an eight-input priority encoder with inputs Aro and outputs Yoo and NONE. For example, if the input is 00100000, the output Y should be 101 and NONE should be 0. Give a simplified Boolean equation for each output, and sketch a schematic Exercise 2.37 Design a modified priority encoder (see Exercise 2,36) that receives an 8-bit input, Avo, and produces two 3-bit outputs, Yo. and Zao. Yindicates the most significant bit of the input that is TRUE. Z indicates the second most significant bit of the input that is TRUE. Y should be 0 if none of the inputs are TRUE. Z should be 0 if no more than one of the inputs is TRUE. Give a simplified Boolean equation for each output and sketch a schematic Exercise 2.38 An Mcbit thermometer code for the number k consists of k 1's in the least significant bie positions and M ~ k 0's in all the more significant bit positions. A binary-to-thermometer code converter has N inputs and 28-1 outputs, It produces a 2%-1 bit thermometer code for the number specified by the input. For example, if the input is 110, the output should be 0111111 Design a 3:7 binary-to-thermometer code converter, Give a simplified Boolean equation for each output and sketch a schematic. Exercise 2.39 Write a minimized Boolean equation for the function performed by the circuit in Figure 2.87. oo —[e" A on : y ti, Figure 2.87 Multiplexer circuit for Exercise 2.39 Exercise 2.40 Write a minimized Boolean equation for the function performed by the circuit in Figure 2.88 Figure 2.88 Multiplexer circuit for Exercise 2.40 101102 ‘CHAPTER TWO Combinational Logic Design Exercise 2.41 Implement the function from Figure 2.80(b) using. (a) an 8:1 multiplexer (b)_ 24:1 multiplexer and one inverter (c)_ 2:1 multiplexer and two other logic gates Exercise 2.42 Implement the function from Exercise 2.17(a) using. (a) an 8:1 multiplexer (b)_ 24:1 multiplexer and no other gates (c) 22:1 multiplexer, one OR gate, and an inverter Exercise 2.43 Determine the propagation delay and contamination delay of the circuit in Figure 2.83. Use the gate delays given in Table 2.8. Exercise 2.44 Determine the propagation delay and contamination delay of the circuit in Figure 2.84. Use the gate delays given in Table 2.8. Table 2.8 Gate delays for Exercises 2.43-2.45 and 2.47-2.48 ate E J NOT as 10 2-input NAND 20 15 3-input NAND 30 25 2input NOR 25 3-input NOR 45 35 2input AND. 30 2s 3-input AND. 40 30 2input OR 40 30 J+input OR 5S 45 input XOR 60 40 Exercise 2.45 Sketch a schematic for a fast 3:8 decoder. Suppose gate delays are given in Table 2.8 (and only the gates in that table are available). Design your decoder to have the shortest possible critical path and indicate what that path is. ‘What are its propagation delay and contamination delay?Exercises Exercise 2.46 Design an 8:1 multiplexer with the shortest possible delay from the data inputs to the output. You may use any of the gates from Table 2.7 on page 90. Sketch a schematic. Using the gate delays from the table, determine this delay. Exercise 2.47 Redesign the circuit from Exercise 2.35 to be as fast as possible. Use only the gates from Table 2.8. Sketch the new circuit and indicate the critical path, What are its propagation delay and contamination delay? Exercise 2.48 Redesign the priority encoder from Exercise 2.36 to be as fas possible. You may use any of the gates from Table 2.8, Sketch the new circuit and indicate the critical path, What are its propagation delay and contamination delay? Exercise 2.49 Another way to think about transistor-level design (see Section 1.7) isto use De Morgan's theorem to consider the pull-up and pull-down networks. Design the pull-down network of a transistor-level gate directly from the equations below. Then, apply De Morgan's theorem to the equations and draw the pull-up network using that rewritten equation. Also, state the numbers of transistors used, Do not forget to draw (and count) the inverters needed to complement the inputs, if needed. + BC+ oD (b) X = ABTC+D) + AD (ce) Y = AIBC + BC) + ABC a) Ww Exercise 2.50 Repeat Exercise 2.49 for the equations below. (a) W=AFRIC+D (b)_X = ABIE+D)+ AD (c) ¥ = A[By CD) + ABCD 103