15.5 Multipliers: Partial Products, Array Multiplication, and Signed Multiplication
Explain how binary multiplication is built from partial products, contrast shift-and-add and array multiplier architectures, and explain why signed multiplication needs careful sign handling.
Multiplication is significantly more hardware-intensive than addition or bitwise logic, which is why it is treated as its own dedicated ALU-adjacent building block rather than folded into the basic ALU operation set covered in Section 15.1. Binary multiplication follows the exact same long-multiplication procedure taught for decimal numbers in grade school — generate a partial product for each digit of the multiplier, shift each one into its correct position, and sum them all together — but implementing that procedure efficiently in hardware, and correctly for both unsigned and signed operands, is a rich design problem with several standard solutions.
Partial Products: The Core Idea
To multiply an N-bit multiplicand A by an N-bit multiplier B, binary long multiplication generates one partial product per bit of B: for each bit position i of B, the partial product is A ANDed bit-by-bit with that single bit of B (which simply produces either all-zero, if bit i of B is 0, or a copy of A, if bit i of B is 1), and that partial product is shifted left by i positions before being added into a running total. This is exactly the schoolbook long-multiplication algorithm, just using base 2 instead of base 10 — and it's simpler in binary because each 'digit' of the multiplier is only 0 or 1, so each partial product is either all-zero or a shifted copy of A, with no digit-by-digit multiplication table needed at all.
Summing N partial products (for an N-bit by N-bit multiply) requires N−1 additions, and the full result can require up to 2N bits to represent without overflow, since the product of two N-bit numbers can be as large as (2^N − 1)^2, which needs 2N bits to hold.
• Each partial product = A AND (single bit of B), shifted left by that bit's position. • A partial product is either all-zero (if the corresponding B bit is 0) or a shifted copy of A (if it's 1). • N partial products are summed to produce the final product. • The full product of two N-bit numbers needs up to 2N bits to represent without overflow.
Shift-and-Add vs Array Multiplier Architectures
A shift-and-add multiplier implements this process sequentially, using one adder reused across multiple clock cycles: on each cycle, it examines one bit of the multiplier, conditionally adds the (appropriately shifted) multiplicand into an accumulating sum register if that bit is 1, and shifts either the multiplicand or the accumulator to align the next partial product — repeating N times for an N-bit multiplier. This trades speed for hardware economy: it reuses the same small adder N times rather than building N separate adders, closely mirroring how a SAR ADC (Section 14.6) trades speed for hardware reuse compared to a flash ADC.
An array multiplier instead lays out all N partial products' generation and summation in a two-dimensional grid of AND gates and full adders, computed in parallel (or in a tightly pipelined fashion) rather than sequentially over N cycles. Every partial product bit is generated by its own AND gate, and a systolic array of full adders (arranged in rows and columns, each summing a partial product row into a running total that cascades down to the next row) computes the entire sum in a bounded, fixed amount of propagation delay rather than N sequential clock cycles. This is the same fundamental speed/hardware trade-off seen throughout this module: an array multiplier is much faster than a shift-and-add multiplier for the same bit width, at the cost of needing roughly N² AND gates and N full adders arranged in a grid, rather than one small adder reused N times.
• Shift-and-add multiplier: one adder reused over N cycles — smaller hardware, slower (sequential). • Array multiplier: a 2D grid of AND gates and full adders computing all partial products and sums in parallel — larger hardware, much faster. • This mirrors the same speed-vs-hardware trade-off seen between SAR and flash ADCs (Sections 14.6–14.7).
Signed Multiplication Requires Correct Sign Handling
Signed multiplication requires correct sign handling; simply multiplying bit patterns as unsigned values can produce the wrong interpretation. If two two's-complement operands are simply fed through an unsigned partial-product multiplier without any special handling, a negative operand's high-order bits (which represent negative positional weight in two's complement, not the huge positive weight an unsigned interpretation would assume) get multiplied as if they were large positive magnitudes, producing an incorrect result. The straightforward but wasteful fix is to convert each negative operand to its magnitude (negating it), perform an ordinary unsigned multiplication, and then correct the sign of the final product afterward based on whether an odd or even number of the original operands were negative.
A more elegant and hardware-efficient approach, widely used in real multiplier circuits, is Booth's algorithm, which directly handles two's-complement operands without ever needing a separate sign-correction step — it examines pairs of adjacent multiplier bits and, based on the transition between them, decides whether to add, subtract, or do nothing at each step, naturally producing the correct signed result and often reducing the number of required additions along the way (particularly for multiplier values with long runs of consecutive 1s or 0s).
• Naively multiplying two's-complement bit patterns as if unsigned produces an incorrect result. • Simple fix: negate any negative operand to get its magnitude, multiply unsigned, then correct the sign of the product afterward. • Booth's algorithm handles signed (two's-complement) operands directly, without a separate sign-correction step, and can also reduce the number of additions needed.
Code Examples
Each bit of B that is 1 contributes a copy of A shifted left by that bit's position; each bit that is 0 contributes nothing. Summing the nonzero partial products (A itself, and A shifted left by 2, since bits 0 and 2 of B are the 1s) gives 6 + 24 = 30, matching 6 × 5 = 30 exactly. Expected result: 0001_1110 (30)
6 × 5 = 30, built from partial products at bit positions 0 and 2 of the multiplier (the two 1-bits of 0101).
If the multiplier hardware simply treats A's bit pattern as an unsigned magnitude, it multiplies 254 × 3 instead of recognizing that A actually represents −2 in two's complement — the result is nowhere close to the correct signed answer. Correct signed multiplication either converts A to its magnitude (2) first and negates the final product afterward, or uses an algorithm like Booth's that handles two's-complement operands directly. Expected result: Naive (wrong): 762. Correct: -6
Treating a negative two's-complement bit pattern as an unsigned magnitude during multiplication gives a completely wrong result.
Common mistake: Feeding two's-complement operands directly into an unsigned multiplier without any sign handling — this is exactly the mistake the spec warns against.
A (multiplicand) = 0110 (6)
B (multiplier) = 0101 (5)
Bit 0 of B = 1: partial product = A << 0 = 0000_0110
Bit 1 of B = 0: partial product = 0000_0000
Bit 2 of B = 1: partial product = A << 2 = 0001_1000
Bit 3 of B = 0: partial product = 0000_0000
Sum = 0000_0110 + 0000_0000 + 0001_1000 + 0000_0000 = 0001_1110 (30)A = 1111_1110 (8-bit two's complement, = -2)
B = 0000_0011 (= 3, positive)
Unsigned bit-pattern multiplication treats A as 254 (unsigned), giving:
254 × 3 = 762 (WRONG for the intended signed multiplication)
Correct signed result: -2 × 3 = -64×4 partial product generation
Each row is either all-zero or a shifted copy of A, depending on the corresponding bit of B — exactly like decimal long multiplication, just in base 2.
A3 A2 A1 A0 (multiplicand A)
× B3 B2 B1 B0 (multiplier B)
─────────────────
A3B0 A2B0 A1B0 A0B0 <- partial product 0 (B0 · A), no shift
A3B1 A2B1 A1B1 A0B1 <- partial product 1 (B1 · A), shifted left 1
A3B2 A2B2 A1B2 A0B2 <- partial product 2 (B2 · A), shifted left 2
... (partial product 3, shifted left 3)
───────────────── (sum all partial products)
Product (up to 8 bits)Important Rules
Each partial product = multiplicand AND (single bit of multiplier), shifted left by that bit's position.
N partial products are summed to compute the full product of two N-bit numbers, which can require up to 2N bits.
Shift-and-add multiplication reuses one adder over N cycles (small, slow); an array multiplier computes all partial products/sums in parallel (large, fast).
Signed multiplication requires correct sign handling — naively multiplying two's-complement bit patterns as unsigned values gives the wrong result.
Booth's algorithm handles two's-complement operands directly and can also reduce the number of additions needed.
Where multipliers show up
CPU integer multiply instructions, digital signal processing (DSP) multiply-accumulate units used in audio/video/radio filtering, graphics pipeline arithmetic, and cryptographic algorithms all depend on dedicated multiplier hardware, with the shift-and-add vs array (or further pipelined) trade-off chosen based on how much silicon area and power a given chip can dedicate to multiplication speed.
Feeding two negative two's-complement operands (or one negative, one positive) directly into an unsigned partial-product multiplier and trusting the raw bit-pattern result.
Either convert negative operands to their magnitude before multiplying and correct the sign of the product afterward, or use a signed-aware algorithm like Booth's algorithm that handles two's-complement operands directly.
Signed multiplication requires correct sign handling; simply multiplying bit patterns as unsigned values can produce the wrong interpretation, since a negative two's-complement operand's high bits represent negative positional weight, not a huge unsigned magnitude.
What is a partial product in binary multiplication? A. The final product before rounding B. The multiplicand ANDed with a single bit of the multiplier, shifted into that bit's position C. The carry-out of the final addition D. A random intermediate value with no defined meaning
B. The multiplicand ANDed with a single bit of the multiplier, shifted into that bit's position — Each partial product is formed by ANDing the multiplicand with one bit of the multiplier (giving either all-zero or a copy of the multiplicand) and shifting it left by that bit's position — exactly mirroring how a single digit's product is shifted into position in decimal long multiplication.
What goes wrong if two's-complement (signed) operands are multiplied using a plain unsigned partial-product multiplier with no special handling? A. Nothing — unsigned and signed multiplication always produce identical bit patterns B. Signed multiplication requires correct sign handling; naively multiplying bit patterns as unsigned values can produce the wrong interpretation, especially when an operand is negative C. The multiplier hardware physically cannot accept negative numbers D. The result will always be exactly double the correct answer
B. Signed multiplication requires correct sign handling; naively multiplying bit patterns as unsigned values can produce the wrong interpretation, especially when an operand is negative — A negative two's-complement operand's high-order bits represent negative positional weight, not a large positive unsigned magnitude — feeding it directly into an unsigned multiplier misinterprets those bits, producing an incorrect result unless the operands are pre-converted to magnitude form (with a sign correction afterward) or a signed-aware algorithm like Booth's is used.
Using the shift-and-add partial-product method, compute 1011 (11) × 0110 (6) as unsigned 4-bit binary numbers, and verify against 11 × 6 = 66.
Multiplier 0110 has 1-bits at position 1 and position 2. Partial product at position 1: 1011 << 1 = 1_0110 (22). Partial product at position 2: 1011 << 2 = 10_1100 (44). Sum = 22 + 44 = 66, matching 11 × 6 = 66.
Generate a partial product for each 1-bit of the multiplier (0110 has 1-bits at positions 1 and 2), shift each into position, and sum.