National Institute of Electronics and Information Technology

(Deemed to be University)

Computer Organization and Architecture: Assignment 3

1. (a) Derive the boolean formulas for sum and carry of half adder using truth table.
(b) Draw a circuit diagram for half adder using XOR gate and AND gate.
(c) Derive the boolean formulas for sum and carry bits of a full adder using truth
table, and simply them using Karnaugh map.
(d) Prove that the boolean equations AB + C(A + B) and AB + C(A ⊕ B) are
logically equivalent. Demostrate their equivalence either by using truth table,
or by reducing one equation to the other using laws of boolean algebra.
(e) Based on the above equivalence, design a block diagram for full adder using
two half adders and a 2-input OR gate.
Note: Do not assume how the half adder circuit is internally implemented.
Consider it a black box with two input and two output bits (sum and carry).

2. (a) Design a block diagram for a 4-bit ripple-carry adder.

(b) Consider a ripple-carry adder circuit for two n-bit non-negative integers.
i. What is the minimum number of full adders required?
ii. If each full adder is implemented with two half adders and an OR gate,
how many half adders are required in total?

3. (a) Modify the previous block diagram to design a 4-bit ripple-carry adder/subtractor
circuit based on two’s complement representation of negative integers.
(b) Consider a ripple-carry adder/subtractor circuit for two n-bit integers.
i. What is the minimum number of full adders required?
ii. If each full adder is implemented with two half adders and an OR gate,
how many half adders are required in total?
iii. If each half adder requires one XOR gate (for sum) and one AND gate
(for carry), how many XOR, AND, and OR gates are required in total?
iv. If each AND gate has delay a, each OR gate has delay o, and each XOR gate
has delay x, what will be the overall delay for the circuit? Simply the
expression assuming all gates have same delay d, such that a = o = x = d.

4. (a) Write the carry generate (G) and propagate (P ) functions for a full adder.
 (b) For each output carry bit of a 4-bit carry-lookahead adder, express the
carry function in terms of generate (Gi ) and propagate (Pi ) functions.
(c) Design the circuit diagram of a 4-bit carry-lookahead adder by first computing
all the generate (Gi ) and propagate (Pi ) values (in parallel), then use them to
compute all the carry bits (using AND and OR gates with fan-in more than 2),
and finally use these carry bits to generate the sum bits (also in parallel).
(d) An n-bit carry-lookahead adder is implemented using 2-input XOR gates and
multi-input AND and OR gates. What is the minimum quantity required for
each of these logic gates? Note: Write each quantity in terms of n.
(e) Consider a carry-lookahead adder implemented using AND, OR, and XOR gates,
and assume that each logic gate has the same delay d (irrespective of fan-in).
i. In the first stage, what is the total delay for computing the generate (Gi )
and propagate (Pi ) values?
ii. In the second stage, what is the total delay for computing all the carry
bits using Gi and Pi values?
iii. In the third stage, what is the total delay for computing the sum bits
using the carry bits?
5. (a) Design a block diagram for the first stage of a carry-save adder to add three
4-bit integers.
(b) Group all the carry bits as C = c4 c3 c2 c1 and all the sum bits as S = s3 s2 s1 s0 .
Write the expression for the final sum in terms of C and S.
(c) Each full adder is constructed using two half adders and an OR gate. Each
half adder is constructed using one XOR gate (for sum) and one AND gate (for
carry). Assuming each gate has the same delay d, what is the total delay in
the first stage of a carry-save adder for adding three n-bit integers?
(d) Consider the following two approaches for adding three integers A, B, D,
where each integer is represented using n-bits.
ˆ First approach: Compute partial sum E = A + B using n-bit ripple-carry
adder, and then add D with E using (n + 1)-bit ripple-carry adder.
ˆ Second approach: Use a carry-save adder for reducing A+B +D to 2C +S,
where 2C + S is computed using (n + 1)-bit ripple-carry adder.
Justify which approach is faster by comparing their overall delays.
6. (a) What is meant by partial product in the binary multiplication of two integers?
(b) Assuming a register shift operation can be completed in one clock cycle, and
n registers, each 2n-bits wide, are available for storing partial products, what
is the maximum number of clock cycles required to compute all the partial
products in a Wallace tree multiplier for multiplying two n-bit integers?
 7. (a) What is the primary motivation for using Booth encoding scheme?
(b) Write your roll number in 7-bit format, and re-write it using Booth encoding.
Comment on the number of bits set to 1 before and after Booth encoding.
(c) Give an example of a 7-bit integer for which the total number of bits set to 1
increases after Booth encoding.
(d) Draw a flowchart to represent Booth multiplication algorithm.
(e) Write DD (day of month) and M M (month) from your date of birth as two 7-
bit integers. Encode one of them using Booth scheme and write all the partial
products generated in Booth multiplication algorithm without adding them.

8. (a) Draw a flowchart to represent restoring division algorithm. As per the flowchart,
what would be the maximum number of subtraction and addition operations
incurred in the worst-case for restoring division of two n-bit integers?
(b) What is meant by “restore” in the restoring division algorithm?

9. (a) Draw a flowchart to show non-restoring division algorithm. As per the flowchart,
what would be the maximum number of subtraction and addition operations
incurred in the worst-case for non-restoring division of two n-bit integers?
(b) Explain how the non-restoring division algorithm postpones the restoring step
to the next iteration, and why it makes the algorithm slightly more efficient.

10. (a) What is the difference between accuracy and precision?

(b) Give an example using decimal fractions to demonstrate how rounding-off the
operands before an operation can produce less accurate results as compared
to rounding-off the result after the operation.
(c) What are the different rounding-off modes used for floating-point arithmetic?