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 4x3 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 8x8 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.