Multiplication: shift-add and Booth

Why it exists

Multiplying two $n$-bit numbers by the school method gives $n$ partial products, each a shifted copy of the multiplicand or zero, which are added together. Hardware does exactly this, but reuses one adder: in each of $n$ steps it adds the multiplicand if the current multiplier bit is 1 and shifts. For signed numbers a direct approach needs sign handling; Booth's algorithm treats a run of 1s in the multiplier as one subtraction and one addition, works directly on two's complement numbers, and is faster for multipliers with long runs. GATE asks for the register contents after some steps, the number of additions, the final product, and the number of steps or partial products.

Prerequisites

You need the ALU and adder of ALU design, and two's complement and arithmetic shifts from fixed-point arithmetic and signed number representation.

Precise definitions

Product size. Multiplying an $m$-bit number by an $n$-bit number gives a result of up to $m + n$ bits. For two $n$-bit numbers the product fits in $2n$ bits (unsigned: at most $(2^n - 1)^2 < 2^{2n}$; signed: the extreme case $(-2^{n-1})^2 = 2^{2n-2}$ also fits).

Sequential shift-and-add multiplier (unsigned). Registers: $M$ (the multiplicand, $n$ bits), $Q$ (the multiplier, $n$ bits, later the low half of the product), $A$ (the accumulator, $n$ bits, the high half) and a carry bit $C$. $A$ starts at 0. Repeat $n$ times:

1. If $Q_0 = 1$ then $A \leftarrow A + M$ (the carry goes to $C$).
2. Shift $C, A, Q$ one place right (with a 0 entering at the top).

After $n$ repetitions $A{:}Q$ holds the $2n$-bit product. Time: $n$ steps, each an addition and a shift. The number of additions equals the number of 1s in the multiplier.

Booth's algorithm (two's complement). Registers $M$, $A$ (starts 0), $Q$ (the multiplier) and one extra bit $Q_{-1}$ (starts 0) to the right of $Q$. Repeat $n$ times, looking at the pair $(Q_0, Q_{-1})$:

then do an arithmetic shift right of $A, Q, Q_{-1}$ as one register (the sign bit of $A$ is copied). After $n$ repetitions $A{:}Q$ is the $2n$-bit two's complement product.

Why it works. A two's complement multiplier is $q = -q_{n-1}2^{n-1} + \sum_{i<n-1} q_i 2^i = \sum_{i=0}^{n-1} (q_{i-1} - q_i)\,2^i$ with $q_{-1} = 0$. So each bit position contributes a digit $q_{i-1} - q_i \in \{-1, 0, +1\}$, which is exactly the table above: the pair 10 gives $-1$ (subtract), 01 gives $+1$ (add), 00 and 11 give 0. A run of 1s such as $0111 = 2^3 - 2^0$ needs just one subtraction and one addition, however long the run.

Number of operations. The number of adds and subtracts equals the number of places where neighbouring bits of the multiplier (with the extra bit $Q_{-1} = 0$ to the right) differ. Best case: all 0s or all 1s (0 or 1 operations); worst case: alternating bits 0101... (about $n$ operations). The shift-and-add method needs as many additions as the multiplier has 1s.

A caveat. If the multiplicand is the most negative number $-2^{n-1}$, then $A - M = A + 2^{n-1}$ may not fit in $n$ bits. The adder must keep an extra bit (or the $A$ register needs one more bit) for the result to be right.

Radix-4 Booth (bit-pair recoding). Examine three bits $(q_{2i+1}, q_{2i}, q_{2i-1})$ at a time and produce one digit in $\{-2, -1, 0, +1, +2\}$:

The multiplier then has only $n/2$ digits, so there are only $n/2$ partial products ($0$, $\pm M$, $\pm 2M$; $2M$ is just a shift) and the multiplication takes $n/2$ steps instead of $n$.

Array multiplier. A combinational multiplier for a $j$-bit by $k$-bit product: $j \cdot k$ AND gates form all the partial-product bits and $j - 1$ rows of $k$-bit adders add them; the product has $j + k$ bits. It is fast (delay about proportional to $j + k$) but large.

How it works

First the unsigned shift-and-add multiplier for $13 \times 11$. Watch $A{:}Q$: the multiplier bits leave from the right of $Q$ while the product grows from the left.

M = 1101 (13), Q = 1011 (11), A = 0000, C = 0
4 repetitions

Now Booth's algorithm for $7 \times (-3)$ with 4-bit registers. The multiplier $-3 = 1101$ has bit changes at three places (reading with $Q_{-1} = 0$ on the right: 1 1 0 1 0 gives changes at the 1-0, 0-1 and 1-0 boundaries), so there are three operations: subtract, add, subtract.

M = 0111 (7), Q = 1101 (-3), A = 0000, Q-1 = 0
4 repetitions

Worked examples

#include <stdio.h>
 
/* unsigned shift-and-add: A:Q holds the product after n repetitions */
static unsigned shift_add(unsigned m, unsigned q, int n, int *adds) {
    unsigned a = 0, c = 0, mask = (1u << n) - 1;
    *adds = 0;
    for (int i = 0; i < n; i++) {
        if (q & 1) { unsigned t = a + m; c = t >> n; a = t & mask; (*adds)++; }
        unsigned full = ((c << (2 * n)) | (a << n) | q) >> 1;
        c = 0; a = (full >> n) & mask; q = full & mask;
    }
    return (a << n) | q;
}
 
/* Booth: A is kept as a signed int so that A - M cannot overflow even for the most negative M */
static int booth(int m, int q, int n, int *ops) {
    int a = 0, qm1 = 0;
    unsigned qq = (unsigned)q & ((1u << n) - 1);
    *ops = 0;
    for (int i = 0; i < n; i++) {
        int pair = (int)(qq & 1) * 2 + qm1;
        if (pair == 2) { a -= m; (*ops)++; }
        else if (pair == 1) { a += m; (*ops)++; }
        int newqm1 = (int)(qq & 1);
        qq = (qq >> 1) | ((unsigned)(a & 1) << (n - 1));
        a >>= 1;                                   /* arithmetic shift right */
        qm1 = newqm1;
    }
    int low = (int)qq;
    return a * (1 << n) + low;                     /* A:Q as a signed 2n-bit number */
}
 
/* radix-4 recoding of an n-bit two's complement multiplier into n/2 digits from -2 to 2 */
static void radix4(int q, int n, int *digits) {
    static const int table[8] = { 0, 1, 1, 2, -2, -1, -1, 0 };
    unsigned u = (unsigned)q & ((1u << n) - 1);
    int prev = 0;                                  /* the bit below the pair: q[i-1], 0 for the first pair */
    for (int i = 0; i < n; i += 2) {
        int triple = (int)(((u >> i) & 3) << 1) | prev;   /* (q[i+1], q[i], q[i-1]) */
        digits[i / 2] = table[triple];
        prev = (int)((u >> (i + 1)) & 1);
    }
}
 
int main(void) {
    int adds, ops;
    unsigned p1 = shift_add(13, 11, 4, &adds);
    printf("13 x 11 (unsigned) = %u with %d additions (11 = 1011 has three 1s)\n", p1, adds);
    int p2 = booth(7, -3, 4, &ops);
    printf("7 x -3 (Booth) = %d with %d add/subtract operations\n", p2, ops);
    int p3 = booth(5, 7, 4, &ops);
    printf("5 x 7 (Booth) = %d with %d operations (7 = 0111: one subtract, one add)\n", p3, ops);
    int p4 = booth(-8, -8, 4, &ops);
    printf("-8 x -8 (Booth, most negative multiplicand) = %d\n", p4);
    int bad_u = 0, bad_b = 0;
    for (unsigned m = 0; m < 64; m++)
        for (unsigned q = 0; q < 64; q++) {
            int a;
            bad_u += shift_add(m, q, 6, &a) != m * q;
        }
    for (int m = -32; m < 32; m++)
        for (int q = -32; q < 32; q++) bad_b += booth(m, q, 6, &ops) != m * q;
    printf("6-bit operands: shift-and-add wrong on %d of 4096 pairs, Booth wrong on %d of 4096 pairs\n", bad_u, bad_b);
    int d[2];
    radix4(-3, 4, d);
    printf("radix-4 digits of -3 (1101): %d %d (value %d x 1 + %d x 4)\n", d[0], d[1], d[0], d[1]);
    return 0;
}

13 x 11 (unsigned) = 143 with 3 additions (11 = 1011 has three 1s)
7 x -3 (Booth) = -21 with 3 add/subtract operations
5 x 7 (Booth) = 35 with 2 operations (7 = 0111: one subtract, one add)
-8 x -8 (Booth, most negative multiplicand) = 64
6-bit operands: shift-and-add wrong on 0 of 4096 pairs, Booth wrong on 0 of 4096 pairs
radix-4 digits of -3 (1101): 1 -1 (value 1 x 1 + -1 x 4)

Cheat box

Traps and GATE patterns

Connections

Everything here uses the adder of the ALU and the flags of fixed-point arithmetic. The same shift-and-subtract idea with the roles reversed gives division. In the datapath the multiplier is a state machine (counter plus control) around the ALU. Multiplication time is one of the terms in the performance equations.

PYQs

The following two signed 2's complement numbers
(multiplicand M and multiplier Q) are being
multiplied using Booth's algorithm:

M: 1100110111101101

Q: 1010010010101010

The total number of addition and subtraction
operations to be performed is __________.

DIGITAL LOGIC

The two numbers given below are multiplied
using the Booth's algorithm.

Multiplicand: 0101 1010 1110 1110

Multiplier: 0111 0111 1011 1101

How many additions/Subtractions are required for
the multiplication of the above two numbers?

When multiplicand Y is multiplied by multiplier X =
xn-1 xn-2 ... x0 using bit-pair recoding in Booth's
algorithm, partial products are generated according to
the following table.

DIGITAL LOGIC

The partial products for rows 5 and 8 are?

Using Booth's Algorithm for multiplication, the
multiplier -57 will be recoded as

Self-check

Revision card

References