Binary Multiplication by Hand

Section 2.2 finished the ALU. This section adds the two operations that do not fit inside it: multiplication and shifting by a variable amount. Before building a multiplier I want to be clear about the algorithm, because the hardware is a direct translation of it, and the algorithm is the long multiplication you learned at school.

Multipliers matter more than they used to. A neural network inference is billions of multiply-accumulate operations, and the area and power of the multiplier decides whether an accelerator fits in a phone. The circuits in this section are the ones that get scaled up for that.

Long multiplication in decimal

$23 \times 47$: multiply 23 by 7 to get 161; multiply 23 by 4 to get 92, shifted one place left because it is really 40, giving 920; add 161 and 920 to get 1081. Each digit of the multiplier produces a partial product, the multiplicand times that digit, shifted by the digit’s position. The result is the sum of the partial products.

Binary has the same structure with a much simpler step: since each multiplier bit is 0 or 1, each partial product is either zero or the multiplicand shifted left. No digit multiplication at all, just AND gates.

0110 × 0101

$6 \times 5 = 30$. Multiplicand $A = 0110$, multiplier $B = 0101$. Take each bit of $B$ from the least significant:

        0110    (A = 6)
      x 0101    (B = 5)
      --------
        0110    A x B[0], shift 0   PP0
       0000     A x B[1], shift 1   PP1
      0110      A x B[2], shift 2   PP2
     0000       A x B[3], shift 3   PP3
     --------
     00011110   = 30

$00000110 + 00011000 = 00011110 = 16 + 8 + 4 + 2 = 30$.

The equation

For an $N$-bit multiplicand $A$ and $N$-bit multiplier $B$,

$$A \times B = \sum_{i=0}^{N-1} B_i \cdot (A \ll i)$$

This equation is the multiplier. Each term $B_i \cdot (A \ll i)$ is a row of AND gates gating the multiplicand with one multiplier bit. The sum is an adder tree. Everything in the next two articles is about doing that sum quickly.

The result is 2N bits wide

An $N$-bit unsigned number goes up to $2^N - 1$, and $(2^N - 1)^2 = 2^{2N} - 2^{N+1} + 1$ needs $2N$ bits. For 4 bits, $15 \times 15 = 225 = 11100001$, eight bits.

This is not optional. A 4×4 multiplier has an 8-bit output. If you declare the product 4 bits wide in Verilog you throw away the top half of every result, and the bug is hard to find because small products still look right. Always declare the product as [2*N-1:0].

How many partial products

An $N \times N$ multiplication has $N$ partial products, one per multiplier bit, each up to $N$ bits wide and starting anywhere from bit 0 to bit $N-1$. The hardware problem is adding $N$ things together efficiently, and the answers are the subject of this section: the array multiplier adds them one row at a time, simple and slow; the Wallace tree reduces them in parallel with carry-save adders; Booth encoding halves the number of partial products before the addition starts.

One thing people get wrong: multiplier bit $i$ shifts the multiplicand left by $i$, because bit $i$ has weight $2^i$. Shifting right would divide.

Signed multiplication

Everything above is for unsigned numbers. For two’s complement, sign-extending both operands to $2N$ bits and multiplying as unsigned gives the right answer but wastes hardware. The standard method is Booth’s algorithm from 1951, which recodes the multiplier so that runs of 1s produce fewer partial products; the radix-4 version halves the partial product count and is what production multipliers use. We stay with unsigned multiplication here. The point to take away is that signed multiplication is an extension of the same algorithm, not a different one.

Practice Exercise

Problem 1. Compute $1011 \times 0110$ ($11 \times 6 = 66$) by binary long multiplication, showing the partial products aligned for addition.

Problem 2. What is the largest product of two 6-bit unsigned numbers, and how many bits does it need?

In the next article we build the simplest hardware that implements the equation, the array multiplier.