Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 57 ยท Combinational Building Blocks

Binary Multipliers: Shift-and-Add, Array and Booth

Build binary multipliers from AND gates and adders: partial products, the combinational array multiplier, the sequential shift-and-add unit and Booth's signed algorithm.

Comparing two numbers was the last arithmetic circuit in subtractors and comparators. The next arithmetic operation is multiplication, and in binary it is surprisingly friendly. Each digit of a binary number is 0 or 1, so multiplying by one digit is either "write the number" or "write zero". There is no times table to learn. The whole job is to line up shifted copies of the multiplicand and add them, exactly like long multiplication on paper.

This lesson shows three ways to turn that idea into hardware: a purely combinational array multiplier, a tiny sequential shift-and-add unit that uses one adder over many clock cycles, and Booth's algorithm for signed numbers. You will model each one in Python and check it against the * operator.

Partial products

Multiply 1101 (13) by 1011 (11). For each bit of the multiplier, write a row: the multiplicand if the bit is 1, zeros if it is 0, shifted left by the bit's position.

TEXT
        1101      multiplicand (13)
      x 1011      multiplier   (11)
      ------
        1101      bit 0 = 1: copy
       1101       bit 1 = 1: copy, shifted by 1
      0000        bit 2 = 0: zeros, shifted by 2
     1101         bit 3 = 1: copy, shifted by 3
   ---------
   10001111       = 143

Each row is a partial product. Bit j of the multiplicand times bit i of the multiplier is just x[j] AND y[i], so all the partial products of an n by n multiplication come from n squared AND gates. The remaining task is to sum n rows. The result of multiplying two n-bit numbers needs 2n bits, because the largest product, (2^n - 1)^2, is just below 2^(2n).

The array multiplier

An array multiplier puts all the AND gates in a grid and adds the rows with a grid of full adders (the adder lesson shows the cell). Row 0 passes through. Each further row is added to the running sum, shifted one place to the left. A carry travels along its row, and the sum bits move down to the next row. The structure is regular, which makes it easy to lay out on a chip, and the pattern of repeated cells is why it is called an array.

flowchart TB
    PP["n x n AND gates: partial products x_j AND y_i"] --> R1["Adder row 1: row 0 + row 1"]
    R1 --> R2["Adder row 2: previous sum + row 2"]
    R2 --> R3["Adder row n-1: previous sum + last row"]
    R3 --> OUT["2n-bit product"]

Each adder row adds one more shifted partial product to the running sum.

For n bits you need about n^2 AND gates and n(n-1) full adders. The delay is the price: the slowest path crosses roughly 2n adder cells, so the multiplier is much slower than an adder of the same width. Faster designs reduce the number of rows with a Wallace tree (a tree of carry-save adders that compresses many rows into two, so only the last addition needs a fast carry) and halve them with Booth recoding, described below.

Python A 4-bit array multiplier built from gates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shift-and-add multiplier

A full grid of adders is expensive. If time is cheaper than hardware, use one adder and several clock cycles. The sequential shift-and-add multiplier needs three registers:

  • M holds the multiplicand and never changes.
  • Q holds the multiplier.
  • A is the accumulator, starting at 0. Together, A and Q form a double-width register that ends up holding the product.

On each of n clock cycles, look at the lowest bit of Q. If it is 1, add M into A. Then shift the combined register A:Q one place to the right. The shift does two jobs at once: it moves the next multiplier bit into position 0, and it moves the partial sum right relative to M, which is the same as shifting M left. The bits of the product also slide into Q as the multiplier bits slide out, so no extra register is needed. After n cycles the product is in A:Q.

The control unit is a counter that counts to n plus a few gates. This is a compact multiplier, but a 32-bit one takes 32 cycles. That tradeoff, hardware against time, is a recurring theme in digital design. See shift registers for the register that does the shifting.

Python Shift-and-add with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Signed numbers and Booth's algorithm

Shift-and-add treats the numbers as unsigned. With two's complement operands, the top bit of the multiplier has a negative weight, so the last step should subtract instead of add, and negative multiplicands need sign extension. A cleaner solution is Booth's algorithm, invented by Andrew Booth, which handles signed numbers with no special cases and also skips work on runs of ones.

The idea starts from a fact about runs: a run of ones such as 0111100 equals 10000000 - 100, that is 128 - 4 = 124. Instead of adding four shifted copies, you can subtract once at the start of the run and add once after its end. Booth's algorithm looks at the current multiplier bit together with the bit to its right (starting with an imaginary 0 to the right of bit 0):

Bit pair (Qi, Qi-1) Meaning Action
0 0 middle of a run of zeros nothing
1 1 middle of a run of ones nothing
1 0 start of a run of ones subtract M
0 1 end of a run of ones add M

After the action, shift right arithmetically, keeping the sign bit of A, so negative partial sums stay correct. A multiplier with long runs of ones needs few additions. In the worst case, such as 0101, there is an action on every bit, but the result is still correct. Modern multipliers use radix-4 Booth recoding, which examines three bits at a time and cuts the number of partial products in half.

Python Booth multiplication of signed numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The guard bit matters. The most negative 4-bit number is -8, and -(-8) = +8 does not fit in four bits. With only n bits for A, the subtraction step for a multiplicand of -8 can overflow; the extra bit in the working width avoids that. Real hardware designs carry that extra bit too, or handle the corner case in the control logic.

Choosing a multiplier

Design Hardware Time Signed numbers Where used
Shift-and-add 1 adder, 3 registers, counter n cycles Needs a fix Small microcontrollers, teaching
Array n^2 ANDs, n(n-1) adders One long combinational delay Needs a fix (Baugh-Wooley) Regular layouts
Booth (radix-4) with a tree About half the rows, plus recoders Short Built in CPU and DSP multipliers

Processors choose by budget: a tiny 8-bit microcontroller might multiply in software or with a multi-cycle unit, while a desktop CPU contains a Booth-recoded Wallace-tree multiplier that finishes in a few clock cycles.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many bits does the product of two 8-bit unsigned numbers need?

    The largest product is 255 x 255 = 65025, which needs 16 bits. In general n-bit by n-bit gives 2n bits.
  2. 2. How are the partial products of an array multiplier generated?

    Multiplying two single bits is the AND function, so n x n AND gates produce all partial products in parallel.
  3. 3. In the shift-and-add multiplier, what happens on each clock cycle?

    The conditional add handles the current multiplier bit, and the right shift both exposes the next bit in Q0 and aligns the partial sum.
  4. 4. Booth's algorithm sees the bit pair (Qi, Qi-1) = (1, 0). What does it do?

    The pair (1, 0) marks the start of a run of ones. A run equals 'subtract at the start, add after the end', so M is subtracted.

Summary

  • Binary multiplication is a sum of shifted partial products. Each partial-product bit is one AND gate, and an n by n product has 2n bits.
  • An array multiplier adds the rows with a grid of full adders: about n^2 ANDs and n(n-1) adders, regular and parallel but slow because carries cross the whole grid.
  • A shift-and-add multiplier uses one adder, a conditional add and a right shift of A:Q on each of n cycles, trading time for hardware.
  • Booth's algorithm treats runs of ones as "subtract at the start, add after the end", multiplies two's complement numbers with no special cases, and radix-4 Booth halves the number of partial products.
  • Fast multipliers combine Booth recoding with carry-save (Wallace) trees.

Next, learn how circuits choose between signals with multiplexers.