EECE 320 Exam, Fall 2004

A. CHEHAB DEPARTMENT OF ELECTRICAL AND COMPUTER EGINEERING M. MANSOUR AMERICAN UNIVERSITY OF BEIRUT FALL TERM 2004-2005 MIDTERM EE/CCE 2007 EECE320 - DIGITAL SYTEMS DESIGN NOVEMBER 23, 2003 UNAMEU: _____________________ ID: _____________________ UCOURSE SECTIONU: SECTION 1 (PROF. CHEHAB) SECTION 2 (PROF. MANSOUR) INSTRUCTIONS: o BE AS NEAT AND CLEAR AS POSSIBLE. o THE SCRATCH BOOKLET UWILL NOTU BE CONSIDERED IN GRADING. o PROVIDE YOUR ANSWERS IN THE SPACE PROVIDED ON THE QUESTION SHEET. o INDICATE THE SECTION YOU ARE REGISTERED IN. o WRITE YOUR NAME AND ID NUMBER IN THE SPACE PROVIDED ABOVE. o CALCULATORS ARE NOT ALLOWED. o THE EXAM IS CLOSED BOOK/CLOSED NOTES. THE DURATION IS UTWO HOURSU. Problem Total Points Earned Points 1 20 2 8 3 6 4 10 5 10 6 10 7 8 8 10 9 8 10 16 11 16 Total 122 Page 1 of 13 UProblem 1U: Short questions [20 points] Answer the following questions: (CORRECT answer = +1point, NO answer = 0 point, WRONG answer = -1 point) 1. The acronym VHDL stands for ____________________________________________________ ________________________________________________________________________________. 2. In logic minimization, a minimal sum can be the canonical sum. True / False (Circle one). 3. Any Boolean function can be built using NAND gates. True / False (Circle one). 4. State the consensus theorem: _______________________________________________________. 5. Consider the binary number 1010111 represented in signed-magnitude notation. The corresponding 2’s complement representation is _____________________________________. 6. The sum of AB.CB16 B and 56.7B8 B in base 4 is ____________________________________________. 7. The decimal value of the smallest n-bit signed-magnitude integer is smaller than the decimal value of the smallest n-bit 2’s complement integer. True / False (Circle one). 8. Consider the unsigned n-bit integer X. Let Y be the unsigned integer obtained by shifting X p positions to the left and inserting ones on the right. Determine Y in terms of X and p. Answer; Y = ____________________________________________. 9. In Boolean algebra, if X = X + Y, then Y = 0. True / False (Circle one). 10. Within a process in VHDL, statements execute sequentially. True / False (Circle one). 11. A with-select construct can be used within a process statement in VHDL. True / False (Circle one). 12. How many pairs of Boolean functions F(a,b,c,d) and G(a,b,c,d) are there that are complements of each other? (Don’t count a pair more than once.) Answer: _________________________________. 13. Write the entity declaration of a 2-to-4 decoder with input a and output b assuming standard logic vectors. Page 2 of 13 14. Complete the following architecture definition for the prime-number detector using select signal assignment, where N is a 4-bit input and F is the output that is asserted if N is prime: ARCHITECTURE prime4_arch OF prime IS BEGIN END prime4 arch; 15. Co 6. What is the dual of F=ΣBX,Y,Z B(1,3,5,7)? Answer: ______________________________________. _______________________________________________________________________________. 8. A function of n variables that includes all the 2Pn P minterms is equal to ______________________. 9. State the Prime-Implicant theorem: ___________________________________________________. ___________________________________________________________________________________. mplete the following architecture definition for decoder with output Y: ARCHITECTURE V2to4dec_b OF V2to4dec IS SIGNAL Y_s : STD_LOGIC_VECTOR(0 TO 3) ; BEGIN PROCESS(IN, EN) BEGIN CASE IN IS WHEN “00” => Y_s <= “1000” ; _______________________________; _______________________________; _______________________________; _______________________________; END CASE ; IF EN = ‘1’ THEN _____________; ELSE _____________; END IF ; END PROCESS; END V2to4dec_b; 1 17. Define a static 1 hazard: Answer: _________________________________________________ _ 1 1 20. What property does a Gray code have? ________________________________________________ Page 3 of 13 UProblem 2 [8 points] Consider the function: F = ΣBA,B,C,D B(1, 3, 4, 5, 10, 11, 12, 13, 14, 15) a) What are the prime implicants of F? CD AB 00 01 11 10 00 01 11 10 _______________________________________________ b) What are the essential prime implicants of F? _______________________________________________ c) What is a minimum SOP expression for F? _______________________________________________ d) What is a minimum POS expression for F? _________________________________________________ UProblem 3 [6 points] Draw the gate implementation of the expression F = (XB1 B+XB2 B’)(XB2 B+XB3 B) a) What type of hazard is possible with this implementation? ________________________________ b) Indicate which transition causes such hazard _________________________________ c) How do you modify the implementation to obtain a hazard-free circuit? Page 4 of 13 UProblem 4U: Boolean Function Implementations [10 points] a) Implement the Boolean function F = A XOR B using NAND gates. You should use the minimum number of NAND gates in your implementation. Label all inputs and outputs. First use the scratch booklet, and then write your final answer clearly below. b) Consider the 1-bit full adder gate (FA) shown below. It takes as inputs A and B and a carry input Cin, and generates the sum S of A, B, and Cin, and a carry output Cout. Implement each of the following functions Uusing one FA gateU. Label all your inputs and outputs clearly according to the function to be implemented. Any unused outputs should be connected to ground. FA A B Cin Cout S FB1 B = X.Y FB2 B = X + Y FB3 B = X XORY FB4 B = X XNOR Y FB5 B = X’ FB6 B = X XNOR Y XNOR Z Page 5 of 13 UProblem 5U: Shannon’s Theorem [10 points] Consider the Boolean function F(a,b,c,d,e,f,g,h) = a’b’c’d + ag’h+ ag + a’b’ce + a’bf’’. Using Boolean algebra, show that F can be implemented with 2-to-1 multiplexers only (no other gates or inverters). Inputs to the circuit are the variables a, b, c ,... and the constants 0 and 1. Draw the resulting logic circuit. Page 6 of 13 UProblem 6U: Majority Function [10 points] An n-bit majority function generates a 1 if more than half the input bits are one (i.e., n/2 or more bits are one assuming n even). Design a 4-bit majority function F using a single 4-to-1 multiplexer and minimal extra gates. Page 7 of 13 UProblem 7U: Look-Up Tables [8 points] A look-up table (LUT) implements a Boolean function by memorizing its truth table. For a given input, a LUT simply ‘looks up’ the corresponding output. A 3-input LUT with enable is shown below. For example, a LUT that implements the function F(a,b,c)=a+bc produces F(0,1,1)=1 when a=0, b=1,c=1. LUT EN F(a,b,c) a b c a) Show how to implement a Boolean function G(a,b,c,d,e) of five variables using 3-input LUTs with enable and a multiplexer. Label all inputs and outputs. b) Repeat part a) but now using 3-input LUTs with enable and a decoder (with minimal extra gates). Page 8 of 13 UProblem 8U: Absolute Value Computer [10 points] In this problem, we are interested in designing a logic circuit that determines the absolute value of an n- bit 2’s complement number ABn-1 PB… PAB2 BAB1 BAB0 B. Since n can be large, it is not practical to implement the circuit by first constructing a truth table. Hence, we’ll build the circuit using identical simple blocks that connect to each other as shown below. Design the simple block ABS so that the circuit computes the absolute value of its input. Try to use as few logic gates as possible in your design. Clearly label all inputs and outputs. Write down Boolean equations for all outputs of the block ABS. ABS ABS ABS ABS . . . Page 9 of 13 UProblem 9U: Algebraic Manipulations [8 points] Prove the identity of the following Boolean equation Uusing algebraic manipulationsU. Justify each simplifying step you make by stating the corresponding theorem or axiom you use. WY + W’YZ’ + WXZ + W’XY’ = WY + W’XZ’ + X’YZ’ + XY’Z Proof: Page 10 of 13 UProblem 10U: Dual Priority Encoder [16 points] In this problem, you are asked to design an 8-to-3 priority encoder that identifies the inputs with highest and second highest priorities using regular 4-to-2 priority encoders with enable. The inputs of the 4-to-2 encoder are defined as follows: EN: When asserted, block functions as an encoder; otherwise, outputs are zero. AB3 B,AB2 B,AB1 B,AB0 B: Data inputs where AB3 Bhas highest priority. BB1 B,BB0 B: Outputs identifying highest priority input. EO: Asserted if EN=1 and at least one is ABi Bone. The output signals BB2 B, BB1 B, BB0 Bof the 8-to-3 dual priority encoder identify the inputs with highest priority respectively. The output signals CB2 B, C1, C0B B identify the inputs with second highest priority. The signal EOB is asserted if a highest priority input is detected, and EOC is asserted if a second-highest priority input is detected. In your design, you can use standard logic gates (AND, OR, NOT) as well as 2-to-4 decoders with enable. EN AB3 B AB2 B AB1 B AB0 B BB1 B BB0 B EO 4-to-2 Priority Encoder EN AB7 B AB6 B AB5 B AB4 B BB1 B BB0 B EOB 8-to-3 Dual Priority Encoder AB3 B AB2 B AB1 B AB0 B BB2 B CB1 B CB0 B CB2 B EOC Page 11 of 13 UProblem 11U: VHDL [16 points] We would like to design a comparator that compares two 8-bit inputs and produces one output that is set to one if the numbers are equal and 0 otherwise. The design is to be iterative. So, first design a 1-bit comparator that takes two input data bits and one cascaded input, and produces one cascaded output. Find the expression of the output in terms of the inputs. Write a VHDL entity and architecture that implements the 1-bit comparator. Then, write a VHDL entity and architecture that implements the 8-bit comparator by cascading 1-bit comparators. Finally, write a testbench that tests the implementation with the following inputs: A = 0x23 and B = 0x32 A = 0x34 and B = 0x34 A = 0xFF and B = 0x00 Page 12 of 13 Page 13 of 13