A hardware multiplier needs to compute 1011 × 01110000 (a multiplicand ANDed with a multiplier that contains a long run of 1s). Why does Booth's algorithm reduce the number of additions required?
AIt skips multiplier bits that are 0, generating fewer partial products
BIt replaces runs of consecutive 1s with a subtraction at the start and an addition at the end of the run
CIt converts the operands to two's complement before multiplication
DIt generates partial products in parallel rather than sequentially
A run of 1s like 01110 represents 8 − 2 = 6. Instead of generating three separate additions (one per 1-bit), Booth's algorithm subtracts the partial product at the run's start and adds it at the run's end — two operations instead of three. The key insight is that consecutive 1s in binary can always be expressed as a difference of two powers of 2, reducing the addition count. Option A describes why multiplication by 0-bits is cheap (trivially true, but not Booth's contribution); options C and D describe unrelated techniques.
Question 2 Multiple Choice
In the shift-and-add multiplication algorithm, what hardware element performs the 'multiply the multiplicand by a single multiplier bit' step?
AA full adder, which sums the bit with a carry
BA shift register, which moves the partial product into position
CAn AND gate applied to each bit of the multiplicand
DA comparator, which selects between the multiplicand and zero
Multiplying any number by a single binary digit is trivial: if the bit is 1, the result is the multiplicand; if 0, the result is 0. This is exactly what an AND gate does — it outputs 1 only when both inputs are 1, so ANDing each bit of the multiplicand with a single multiplier bit either passes the bit through unchanged (multiplier bit = 1) or zeros it out (multiplier bit = 0). The shift register (option B) positions the partial product but doesn't generate it. The full adder (option A) accumulates the partial products but doesn't create them.
Question 3 True / False
A Wallace tree multiplier is faster than a sequential shift-and-add multiplier because it generates all partial products simultaneously and reduces them in logarithmic time using parallel carry-save adders.
TTrue
FFalse
Answer: True
This is the core architectural tradeoff in hardware multiplication. A sequential shift-and-add approach takes O(n) cycles — one addition per multiplier bit. A Wallace tree generates all n partial products in parallel, then arranges carry-save adders in a tree that reduces them to two numbers in O(log n) depth, before a final fast adder produces the result. The cost is enormous chip area — a tradeoff that makes sense in performance-critical CPU cores where multiplication latency matters.
Question 4 True / False
Booth's algorithm increases the number of partial products compared to naive shift-and-add, which is why it requires a more complex adder tree.
TTrue
FFalse
Answer: False
This is backwards. Booth's algorithm *reduces* the number of partial products by recoding runs of 1s in the multiplier. Each run of k consecutive 1s normally produces k partial products; Booth's encoding produces at most 2 (a subtraction and an addition), regardless of run length. This is the entire motivation for Booth encoding — fewer partial products means fewer additions, which means faster multiplication.
Question 5 Short Answer
Why is binary multiplication fundamentally simpler than decimal multiplication, and how does this simplicity enable an efficient hardware implementation?
Think about your answer, then reveal below.
Model answer: In binary, each multiplier digit is either 0 or 1 — there are no intermediate cases like 7 × multiplicand that require a separate multiplication table lookup. Multiplying the entire multiplicand by a single binary bit is just an AND gate: bit = 1 passes the multiplicand unchanged, bit = 0 produces all zeros. This means generating each partial product requires only n AND gates (for an n-bit multiplicand), not a lookup table. The full multiplication then reduces to shift-and-add: generate n partial products using AND gates, shift each left by the appropriate position, and sum them with adder circuits.
The reduction from general multiplication to AND-plus-addition is what makes hardware multiplication tractable. Decimal multiplication requires remembering (or computing) products of single digits 0–9, which are complex to implement in hardware. Binary multiplication replaces this with a trivial operation — an AND gate — and delegates all the real work to the adder circuits that already exist in every processor.