- September 5, 2020

Homework 1 for the ECE 545 students only due Sunday, September 13, 11:59pm (submission using Blackboard) Note: In all of the problems below assume that signed integers use a two’s complement representation Problem 1 Using a simple block diagram, show how to implement: A. one’s complement of a 4-bit number A using XNOR gates. B. 4-bit comparator, A≠B, returning 1, when A is different than B, and 0 otherwise, using only XNOR gates and one additional type of gate. C. circuit calculating parity of an 8-bit vector A, returning 1 if the parity is even, and 0 otherwise, using only 2-input logic gates. Make sure that your circuit has the smallest delay assuming that delays of all 2-input logic gates are the same. Problem 2 Are the following sets of gates complete sets? Are they minimal complete sets? Give separate answers for each set A.-C. Justify your answers to the former question by demonstrating how gates from each of the given below sets can be used to implement all gates belonging to the set {AND, OR, NOT}. A. {XNOR} B. {XNOR, OR} C. {XNOR, OR, XOR} Problem 3 Define a 3-input Boolean function, which is different from the 3-input AND, OR, NAND, NOR, XOR, and XNOR gate. Then, demonstrate how this function can be implemented using a. ROM (draw a symbol of the ROM, and then describe the contents of the ROM using a separate diagram) b. NOT, AND, and OR gates c. NAND gates. Problem 4 Prove that the following circuit performs the same operation as a Full Adder. Problem 5 Draw a schematic of A. 8-to-1 multiplexer built of 2-to-1 multiplexers B. 4-to-16 decoder with enable built of 2-to-4 decoders with enable C. 16-to-4 priority encoder built of 4-to-2 priority encoders and 2-to-1 MUXes. Problem 6 Show how to implement an address decoder that recognizes the following four ranges of a 12-bit address A, and generates the corresponding enable signals e0, e1, e2, e3, indicating that the address is in the given range: Case A: Range 0: A00-A7F Range 1: A80-AFF Range 2: B00-B7F Range 3: B80-BFF Case B: Range 0: 800-AFF Range 1: B00-CFF Range 2: D00-EFF Range 3: F00-FFF All enable signals should be equal to 0, when the address A does not belong to any of the above ranges. Please do your best to use only decoders and a minimum number of logic gates. Problem 7 For what binary values of inputs to a 4×3 multiplier, the result will be the same (when expressed in the binary representation) for a signed and an unsigned multiplier. Mark all such values with X in the following 8×8 array: a b 000 001 010 011 100 101 110 111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 How would you describe all these combinations of inputs using a comprehensive rule, without listing all of them? Problem 8 A. Determine the a. minimum value (in binary and decimal) b. maximum value (in binary and decimal) c. range (in decimal) d. minimum number of bits required to represent all numbers in this range for the following products: 1) 5-bit unsigned integer multiplied by a 4-bit unsigned integer 2) 5-bit signed integer multiplied by a 4-bit signed integer 3) 5-bit unsigned integer multiplied by a 4-bit signed integer 4) 5-bit signed integer multiplied by a 4-bit unsigned integer B. Prove rigorously, using mathematical derivations, that a product of an n-bit unsigned integer and an m-bit unsigned integer can be always represented using n+m bits, and that n+m-1 bits are not sufficient. Assume n ³ 2 and m ³ 2. C. Prove rigorously, using mathematical derivations, that a product of an n-bit signed integer and an m-bit signed integer can be always represented using n+m bits, and that n+m-1 bits are not sufficient. Assume n ³ 2 and m ³ 2. Problem 9 A. Determine the a. minimum value (in decimal and binary) b. maximum value (in decimal and binary) c. range (in decimal) d. minimum number of bits required to represent all numbers in this range for the following sums: 1) Sum of 16 5-bit unsigned numbers 2) Sum of 16 5-bit signed numbers 3) Sum of 12 5-bit unsigned numbers 4) Sum of 12 5-bit signed numbers B. Prove rigorously, using mathematical derivations, that the sum of m n-bit unsigned integers can be always represented using n+ceil(log2(m)) bits, where ceil(x) is the ceiling function, rounding x up to the nearest integer. Assume n ³ 1 and m ³ 1. C. Prove rigorously, using mathematical derivations, that the sum of m n-bit signed integers can be always represented using n+ceil(log2(m)) bits, where ceil(x) is the ceiling function, rounding x up to the nearest integer. Assume n ³ 2 and m ³ 1.