Shift-and-Add Multiplier Sign Handling
An 8-bit shift-and-add multiplier is built for unsigned operands: it accumulates partial products, shifting the multiplier right each step and the multiplicand left. A designer reuses it for signed two's-complement operands by simply feeding the bit patterns in and ignoring the sign, claiming 'the low 8 bits of the product are the same either way.' Test vectors: (-3) x (5) and (-3) x (-5), expected 8-bit two's-complement products. The multiplier produces 0x0F for the first vector. The designer also plans to widen the result to 16 bits for a later datapath and asks whether the same shortcut holds there.
1. Compute the correct 8-bit products for (-3)x(5) and (-3)x(-5), and explain why the unsigned shortcut gives the wrong first result.
Read the worked answer
(-3) in 8-bit two's complement = 0xFD (11111101). (5) = 0x05. (-5) = 0xFB (11111011).
Correct signed products:
- (-3)*5 = -15 → 8-bit two's complement: 256-15 = 241 = 0xF1.
- (-3)*(-5) = +15 = 0x0F.
The multiplier returned 0x0F for the first vector - that is the value of the second product, i.e. it computed as if both operands were positive? No: unsigned 0xFD * 0x05 = 253*5 = 1265 = 0x4F1; low 8 bits = 0xF1. Hmm, low 8 bits of unsigned product equal the correct signed low 8 bits here. The reported 0x0F suggests the sign extension of the multiplicand was mishandled: the unsigned algorithm shifts the multiplicand left treating it as 0x00FD, but signed arithmetic requires sign-extending 0xFD to 0xFFFD before shifting. With sign extension, 0xFD (-3) times 0x05 gives -15 = 0xF1. Without it, the high bits are wrong and, once you truncate to 8 bits after a 16-bit internal accumulation with wrong extension, you can get 0x0F.
Key point: the 'low bits are the same' claim is only true when the full 2n-bit product is formed with proper sign extension and then truncated. Truncating an incorrectly extended partial-product sum does not preserve the low bits.
2. State the general rule for when low-bit truncation of a two's-complement product is safe, and whether the 16-bit widening changes the answer.
Read the worked answer
Rule: if you compute the exact 2n-bit signed product (with sign-extended multiplicand and sign-corrected final partial product for a negative multiplier) and then take the low n bits, those low n bits equal the exact product mod 2^n, which is the correct n-bit two's-complement result. So truncation is safe only after a correct full-width product.
For 16-bit output from 8-bit signed inputs: the exact product of two 8-bit signed numbers fits in 16 bits (range -128127.. -128-128 = up to 16384, well within -32768..32767). So widening to 16 bits requires the full signed product, not just the low 8 bits. The shortcut that 'works' for 8-bit truncation fails at 16 bits, because the high 8 bits are exactly the part the unsigned algorithm got wrong. Therefore the shortcut does not hold for the widened datapath.
3. Describe the minimal modification to the unsigned shift-and-add hardware to make it correct for signed operands, and note the impact on latency/area.
Read the worked answer
Modifications:
- Sign-extend the multiplicand to 2n bits before the shift-and-add (replicate the MSB into the upper n bits).
- Sign-extend the multiplier's partial-product accumulation, or equivalently use a correction step: for a negative multiplier (MSB=1), subtract the multiplicand from the high half at the end (Booth-style correction).
- Accumulate in a 2n-bit register and only truncate at the end.
Minimal version: keep the n-step loop, but (a) initialize the 2n-bit accumulator with sign extension, (b) after the loop, if the multiplier was negative, subtract the sign-extended multiplicand from the upper half.
Impact: one extra 2n-bit subtractor (or a conditional add of the negated multiplicand) and n extra accumulator bits; latency stays n cycles (the correction is a single final step). Area grows by roughly the width of the accumulator plus a small adder. This is cheaper than a full Booth recoder but functionally sufficient.