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.