Week 10 – Assignment 10: Detailed Solutions

Course: Digital IC Design (NPTEL)

Topics: Two’s Complement Arithmetic · Sign Extension · Array Multiplier
· Carry-Save Multiplier · Signed Multiplication

Background Concepts
Two’s Complement Representation — For an n-bit number, the MSB (bit
n−1) carries weight −2^(n−1) instead of +2^(n−1). All other bit weights are
the usual positive powers of 2. This gives a range of −2^(n−1) to +2^(n−1)
− 1.
Sign Extension — To extend a 2’s complement number to more bits, replicate
the MSB into all new higher-order positions (e.g., −5 in 4 bits = 1011; in 8 bits
= 11111011).
Array Multiplier — Adds partial products row-by-row using a grid of full
adders. Simple but slow because the carry ripples both down through rows and
across columns.
Carry-Save Multiplier (CSM) — Uses Carry-Save Adders (CSA) to reduce
N partial-product rows to just 2 vectors without propagating carries between
stages. The final 2 vectors are then merged with a fast ripple or carry-lookahead
adder.

Question 1 — Properties of an 8-bit 2’s Complement Num-

ber (2 points)
Answer: Maximum value = 127; Minimum value = −128

Derivation
For an 8-bit 2’s complement number (n = 8):

Maximum = +2𝑛−1 − 1 = +27 − 1 = 128 − 1 = 127

This corresponds to the bit pattern 01111111.

Minimum = −2𝑛−1 = −27 = −128

This corresponds to the bit pattern 10000000.

The range is −128 to +127, giving 256 distinct values total. Note that 255
would be the maximum for an 8-bit unsigned number, not signed.

1
Question 2 — Compute 10000001 × 10000000 (2 points)
Answer: −16256 if signed 2’s complement; 16512 if unsigned
Wait — let us compute both interpretations carefully.

As Signed 2’s Complement (8-bit)

10000001 → MSB = 1 (negative). Value = −128 + 0 + 0 + 0 + 0 + 0 + 0 +
1 = −127
10000000 → MSB = 1 (negative). Value = −128

(−127) × (−128) = 16256

So the correct choice is: “16256 if both are signed 2’s complement num-
bers.”

As Unsigned (8-bit)
10000001 = 128 + 1 = 129
10000000 = 128

129 × 128 = 16512

So the correct choice is also: “16512 if both are unsigned numbers.”

Both of these statements are simultaneously true (they describe different inter-
pretations of the same bit patterns).

Question 3 — Smallest 6-bit 2’s Complement with MSB =

1 (2 points)
Answer: −32
For a 6-bit 2’s complement number, the bits have weights: −2�, 2�, 2³, 2², 2¹,
2� = −32, 16, 8, 4, 2, 1.
If the MSB (bit 5) is fixed to 1, the remaining 5 bits can range from 00000 to
11111. The smallest (most negative) value is obtained when all remaining bits
are 0:

Pattern: 100000 = −32 + 0 + 0 + 0 + 0 + 0 = −32

2
 If the course uses a 7-bit interpretation (sign bit + 6 magnitude
bits), the smallest value would be −2� = −64. The answer among
the given options would then be −64. Always confirm the bit-width
convention from your lecture notes.

Question 4 — Find Q given P = 1011 and P × Q = P² (2

points)
Answer: Q = 1111111111111011 (which is −5 in 16-bit 2’s comple-
ment)

Step 1: Find the value of P

1011 in 4-bit 2’s complement: −8 + 0 + 2 + 1 = −5

Step 2: Solve for Q

𝑃2
𝑃 × 𝑄 = 𝑃2 ⟹ 𝑄 = = 𝑃 = −5
𝑃

So Q = P = −5.

Step 3: Represent Q in 16-bit 2’s complement

Sign-extend −5 from 4 bits to 16 bits by replicating the MSB (1) twelve times:
1011 → 1111111111111011
Verify: −32768 + 16384 + 8192 + 4096 + 2048 + 1024 + 512 + 256 + 128 +
64 + 32 + 16 + 8 + 2 + 1 = … or simply: all ones in positions 15 down to 3
give −8 + 0 + 2 + 1 = −5 �

Question 5 — Sign Extension of 110010 (2 points)

Answer: Two statements are true — see below.

Step 1: Interpret 110010

As a 6-bit signed 2’s complement: MSB = 1 (negative).
Value = −32 + 16 + 0 + 0 + 1 + 0 = −14
As a 6-bit unsigned: Value = 32 + 16 + 2 = 50

3
Step 2: Extend each interpretation
Signed extension to 8 bits — replicate MSB (1) into positions 7 and 6:
11110010 → represents −128 + 64 + 32 + 16 + 2 = −14 �
Signed extension to 16 bits — replicate MSB (1) into the upper 10 positions:
1111111111110010 → still equals −14 �
Unsigned extension to 8 bits — pad with zeros (50 is still 50): 00110010 �
Unsigned extension to 16 bits — pad with zeros: 0000000000110010 �

Checking the options

Option Correct?
11110010 if signed 2’s complement � TRUE
extended to 8 bits
00110010 if signed 2’s complement � (wrong, that’s unsigned extension)
extended to 8 bits
1111111111110010 if signed extended � TRUE
to 16 bits
00110010 if unsigned extended to 8 � TRUE
bits
1111111111110010 if unsigned � (wrong, should be
extended to 16 bits 0000000000110010)

Question 6 — Full Adders in an 8×8 Array Multiplier (2

points)
Answer: (N−1)² = 49 full adders

Derivation
For an N×N array multiplier (N = 8) using full adder blocks only:
We have N = 8 partial product (PP) rows. We add them together row by row:
Stage 1 adds PP� + PP�: produces a (N+1)-bit result using approximately N
full adder cells. Stage 2 adds PP� to the stage-1 result, and so on through stage
N−1.
The total number of FA cells in the array (treating half-adders as FAs with one
input = 0) follows the formula:

Total FAs = 𝑁 ⋅ (𝑁 − 2) + 1 = (𝑁 − 1)2

4
For N = 8:
(8 − 1)2 = 72 = 49

You can verify this for N = 4: (4−1)² = 9 FAs, which matches the standard
4×4 array multiplier diagram from the lectures.

Question 7 — Critical Path Delay of 8×8 Array Multiplier

(2 points)
Given: t_AND = 1, t_CARRY = 1, t_SUM = 3
Answer: 17 units

Structure of the Critical Path

In an array multiplier, the worst-case path starts from an AND gate that pro-
duces a partial product bit at a mid-range bit position, then:
1. AND gate to produce one partial product bit: t_AND
2. N−2 FA carry stages propagating downward through intermediate rows
(carry path is used because it is faster than sum in each row): (N−2) ×
t_CARRY
3. N−1 FA carry stages in the final ripple adder row (horizontal carry
propagation across the last row): (N−1) × t_CARRY
4. Final FA sum to produce the MSB of the product: t_SUM

𝑇𝑎𝑟𝑟𝑎𝑦 = 𝑡𝐴𝑁𝐷 + (𝑁 − 2) ⋅ 𝑡𝐶𝐴𝑅𝑅𝑌 + (𝑁 − 1) ⋅ 𝑡𝐶𝐴𝑅𝑅𝑌 + 𝑡𝑆𝑈𝑀

= 𝑡𝐴𝑁𝐷 + (2𝑁 − 3) ⋅ 𝑡𝐶𝐴𝑅𝑅𝑌 + 𝑡𝑆𝑈𝑀

For N = 8, t_AND = 1, t_CARRY = 1, t_SUM = 3:

𝑇 = 1 + (16 − 3) × 1 + 3 = 1 + 13 + 3 = 17

Intuition: The array multiplier is slow because it suffers from carry rippling in
two dimensions — vertically through rows AND horizontally through the final
ripple row. This motivates the carry-save approach below.

5
Question 8 — Critical Path Delay of 8×8 Carry-Save Mul-
tiplier (2 points)
Given: t_AND = 3, t_CARRY = 1, t_SUM = 1
Answer: 17 units

How the CSM Differs

In the carry-save multiplier, the N−2 intermediate CSA stages each use the
SUM output of the full adder (not the carry output), because the carry is
“saved” and passed to the next stage offset by one position — no carry ripple
occurs between stages.

𝑇𝐶𝑆𝑀 = 𝑡𝐴𝑁𝐷 + (𝑁 − 2) ⋅ 𝑡𝑆𝑈𝑀𝐶𝑆𝐴 + (𝑁 − 1) ⋅ 𝑡𝐶𝐴𝑅𝑅𝑌𝑟𝑖𝑝𝑝𝑙𝑒 + 𝑡𝑆𝑈𝑀𝑟𝑖𝑝𝑝𝑙𝑒

For N = 8, t_AND = 3, t_CARRY = 1, t_SUM = 1:

𝑇 = 3 + (8 − 2) × 1 + (8 − 1) × 1 + 1 = 3 + 6 + 7 + 1 = 17

Why Both Give 17?

The parameters were chosen deliberately to produce equal results — the point
of the question is to highlight that the advantage of CSM depends on the
relative values of t_CARRY and t_SUM. In a technology where t_SUM
< t_CARRY (as is typical), the CSM stage costs less per level than the array
multiplier stage, making CSM faster overall.

Question 9 — FAs with Input Tied to Logic-1 in 8-bit

Signed CSM (2 points)
Answer: 4 full adders

Why Some FAs Have a Tied Input

In signed 2’s complement multiplication, the standard approach (Baugh-
Wooley or related correction) inverts certain partial product bits and adds cor-
rection terms. This correction is implemented by tying one input of specific full
adders to logic-1.
The hint states: for 4-bit signed multiplication using CSM, the answer is 2.
Observing that the count scales as N/2 for an N-bit operand:

6
 𝑁 8
FAs with input tied to 1 = = =4
2 2

Question 10 — Statements NOT TRUE: 8×8 Array vs

CSM (2 points)
Answer: Statements 1, 3, and 4 are NOT TRUE.

Analyzing Each Statement

Statement 1: “The carry-save multiplier is chosen for a lower area
implementation.” This is NOT TRUE. The CSM uses more hardware than
a standard array multiplier because each CSA stage requires an independent
set of adder cells (two copies for both carry and sum outputs). The CSM is
preferred for its speed, not area savings.
Statement 2: “The carry-save multiplier is chosen for a lower de-
lay implementation.” This IS TRUE. The CSM avoids intermediate carry
propagation between stages, dramatically reducing the critical path depth when
t_SUM < t_CARRY.
Statement 3: “The carry bit in one row is propagated to the follow-
ing row of adders in a carry-save multiplier.” This is NOT TRUE. The
defining feature of the CSM is precisely that the carry is saved (passed diago-
nally to the same stage in the next position), not propagated up the carry chain.
Propagating carry between rows is what array multipliers do — not CSMs.
Statement 4: “The carry-save multiplier is chosen for low area AND
low delay compared to array multiplier.” This is NOT TRUE. While
CSM offers lower delay, it does not offer lower area. Claiming both advantages
is incorrect.

Summary Table

Q Correct Answer Core Concept

1 Max = 127, Min = 2’s complement range:
−128 −2^(n−1) to 2^(n−1) −
1
2 16256 (signed); 16512 Interpret bits correctly
(unsigned) before multiplying
3 −32 (or −64 per MSB = 1 → most
convention) negative = all other bits
=0

7
Q Correct Answer Core Concept
4 Q = 1111 1111 1111 P×Q = P² → Q = P,
1011 then sign-extend to 16
bits
5 See options analysis Sign-extend with MSB
copy; zero-extend for
unsigned
6 49 FAs (N−1)² formula for
N×N array multiplier
7 17 units t_AND +
(2N−3)×t_CARRY +
t_SUM
8 17 units t_AND +
(N−2)×t_SUM +
(N−1)×t_CARRY +
t_SUM
9 4 FAs N/2 correction cells for
signed CSM
10 Statements 1, 3, 4 are CSM: faster but not
NOT TRUE smaller; carry is saved,
not propagated