Booth's Multiplication Algorithm

One commonly discussed type of binary multiplier is the Booth multiplier; a hardware multiplier based on Booth’s multiplication algorithm. This algorithm was invented by Andrew Donald Booth in 1950 and aims to simplify the multiplication of two, signed $n$ bit numbers. The sign of these numbers being represented by the two’s complement notation.

Booth multipliers have the advantage of potentially reducing the amount of additions / subtractions needed to perform a multiplication. If we take the advanced form of the algorithm which is known as modified Booth algorithm, then we can even reduce the amount of partial products that must be added together. Both of these benefits help us speed up the process of multiplication by reducing the propagation delay of our calculating circuit.

In order to understand the Booth algorithm, you should already be familiar with regular binary multiplication also known as long multiplication. You should also have an understanding of basic binary arithmetic in the form of addition and subtraction with two’s complement.

Multiplication Basics

Let us start by defining some terminology. We define a multiplication of two $n$ bit numbers as:

Both numbers $a,b$ are known as factors inside a multiplication. The multiplication of numbers is communicative which is why we usually make no distinction between the two factors. For the Booth algorithm, however, we want to distinguish the two numbers. We call $a$ the multiplicand and $b$ the multiplicator.

The result $P$ is known as the product. When we do long multiplication we will generally have partial results that we need to add together in the final step to receive the product. We call these partial results partial products and we will denote them as $pp$.

Booth Algorithm (Booth-1 / Radix-2)

Booth’s algorithm works by re-encoding the partial multiplication steps we do as part of normal long multiplication. This re-encoding will result in simplified partial products which, when added together, will produce a final product that is already in two’s complement notation.

The re-encoding is determined by the bits that make up the multiplicator $b$. The Booth algorithm always looks at every pair of two bits ($y_i$, $y_{i-1}$) in the multiplicator $b$ starting from the right-most place, the LSB, and moving toward the left.

To start, we write out our binary number $b$. Let us take $b = 6_{10} = 0110_{2}$ as an example:

For Booth’s algorithm to work, we must append an additional bit before the LSB. This is because we start by defining our LSB as our first $y_i$. Therefore, we must add an implicit $0$ bit before the LSB to act as our first $y_{i-1}$.

We can now start encoding by looking at ever pair ($y_i$, $y_{i-1}$) and defining an operation that will be performed on our multiplicand $a$ from earlier. The encoding table looks as follows:

We do not have to understand yet how to apply these operations. Let us first take our example multiplicator $b$ and re-encode it according to the table.

Encoding the multiplicator

We start by looking at the first pair ($y_1$, $y_0$):

This pair is ($00$) so it encodes to "$0x$" according to the table.
Next up is the pair ($y_2$, $y_1$):

Here we have the pair ($10$) which encodes to "$-x$".
The pattern should be obvious by now. Here we have the last two encodings:

The pairs are ($11$) and ($01$) which map to "$0x$" and "$+x$" respectively.

Inserting the encoded operations

Our encoding of the multiplicator $b$ has given us four operations that we will perform on the multiplicand $a$. We will perform these operations just as we would in normal long multiplication, so writing our multiplication and partial results out in columns.

Lets write out the multiplication vertically like a long multiplication. For our example we will set $a = -7_{10} = 1001$

Notice how our place values (the $2^i$s) are in binary and accordingly aligned with our multiplicand $a$. Also notice that below every place value, we have inserted the corresponding “operation” that we derived from encoding the multiplicator $b$.

For example, the first operation we encoded from the pair ($y_1$, $y_0$) was ($00$). We therefore put the corresponding operation "$0x$" into the first column from the right. The next pair ($y_2$, $y_1$) was ($10$) and so we put into the second column from the right the operation "$-x$".

With all that set up, we are ready to calculate our partial products.

Performing the multiplication

We will now multiply the entire multiplicand $a$ with whatever operation is written in the column we are currently looking at. Fortunately, all our “multiplying” is actually just multiplying by $0$, $1$ or $-1$. That means we must only insert zeros, insert $a$ or insert the two’s complement of $a$ respectively.

Let start calculating our first partial product $pp_1$:

Any number multiplied by $0$ is trivially $0$ as well. Thus, we have already calculated our first partial product: $pp_1 = 00000000$. Notice that we are now using twice the bits we did to display the result. This is because when multiplying $n$ bits, we can receive an output that requires $2n$ bits.

Let us look at our next partial product $pp_2$:

Here we multiply $a$ by -1, which yields us $0111_2 = 7_{10}$. Multiplying any number by $-1$ flips the sign of that number. In this case, we simply take the two’s complement of $a$.

Note that just like in decimal long multiplication, we fill all columns to the right of the column we are looking at with zeros. In this case, we put a zero into the $2^0$ column for our $pp_2$ row (notice the gray color).

We continue with $pp_3$:

Just like $pp_1$, the result is all zero.

Let us calculate the final partial product $pp_4$:

Here we simply multiplied $a$ by $1$, yielding us $a$ again. However, notice that we also filled the $2^7$ column with a $1$ as well.

This is because our number $-7$ is in two’s complement form. When we expand our 4 bit number into an 8-bit number, all new leading bits must take over the same value as the MSB of our original 4 bit number.

Negative two’s complement numbers always have $1$ as their MSB, therefore we copy that value into all leading bits as well, meaning column $2^7$ is filled with $1$ too.

Adding the partial products

All that is left to do is to add together our partial products and arrive at the final result:

Our binary addition yields us $11010110_2 = -42_{10} = -7 \times 6$. Booth’s algorithm has correctly produced a final product that is also in two’s complement form.

Note how two of our partial products ($pp_1$, $pp_3$) were just all zero, meaning we did not need to account for them while doing our addition. This is an example of how the Booth algorithm can potentially reduce the amount of additions we need to make.

However, there remains one major issue we have not yet encountered nor addressed: multiplying with the most negative number our $n$ bits can present.

Multiplying with the most negative number

The most negative number is special because multiplying it by $1$ or $-1$ yields the same result when we are confined to our original $n$ bits. Let us take $-8_{10} = 1000_2$ as an example and apply the two’s complement to it, i.e. multiplying by $-1$:

This circumstance causes Booth algorithm to not produce correct results when utilizing the most negative number. Luckily, we can fix this.

In order to use the most negative number, we must expand our multiplicand $a$ by one leading bit. Just like we added leading bits to our partial product, we simply copy the MSB of $a$ and append it to the left of $a$ again:

From now on, we always use $a'$ for every time we perform the Booth algorithm. Let us see this change in action.

We will calculate $-8 \times -8$. Encoding $b = 1000\color{red}{0}$ will yield us the following operations, right to left: $0x$, $0x$, $0x$, $-x$

Let us draw our multiplication table but this time insert $a'$.

Note how in column $2^4$, the bit of $a'$ is now an explicit $1$, giving us more “space”. This causes the two’s complement produce the value of $01000$: the additional bit we added allows us to represent $+8$.

Let us now look at the final result:

As expected we get the correct answer $01000000_2 = 64_{10} = -8 \times -8$.

Can you see that we would have gotten a wrong answer of $-64$ if we had used the old $a$ instead of $a'$?

Summary

We can summarize Booth’s algorithm as a five-step process:

1. Add a $0$ as a trailing bit before the LSB of the multiplicator $b$
2. Pairwise encode all bits of $b$ according to the encoding table
3. Add a leading bit after the MSB of the multiplicand $a$. This bit has the same value as the MSB of $a$.
4. Calculate the partial products. Multiply $a$ by the respective numbers that were derived from encoding $b$ in step 2.
5. Add all partial products together.

It is also important to remember:

• The partial products should be $2n$ bits long. When adding leading bits, remember that they take the same value as the MSB of the $n$ bit long number.
• Fill the columns to the right of the currently processed column with zeros. Like in ordinary, decimal long multiplication

Modified Booth Algorithm (Booth-2 / Radix-4)

The “normal” Booth algorithm has the potential to reduce the amount of partial products we need to add together. However, this is only the case if one or more partial products ends up being zero.

In terms of a hardware implementation, this is of little use to us. The propagation delay is determined by the critical path in our circuit. That is the path which is the longest and takes the most amount of time. For the Booth algorithm, the longest path would be if all partial products are non-zero. We always have to take the worst case scenario as the basis for our circuit. This means that we have no significant speed benefit from utilizing a Booth multiplier when compared to a regular multiplier.¹

The modified Booth algorithm is an advanced version of Booth’s algorithm and fixes this speed issue by consistently reducing the amount partial products. It does so by encoding the multiplicator three bits at a time.

While the modified Booth algorithm is slightly more complicated, it is often the preferred algorithm for signed multiplication due to its significant speed benefit.

Radix-4 encoding

The modified Booth algorithm uses a radix-4 encoding, meaning we now encode triplets of the multipliator $b$. We define each triplet of bits as ($y_{i+1}$, $y_{i}$, $y_{i-1}$).

With three bits, we now have eight encoding possibilities. The encoding table for radix-4 looks as follows:

The important additions are "$2x$" and "$-2x$". They demand that we multiply our multiplicand by $a$ by $2$ or $-2$ respectively.

Multiplying and diving by powers of two is very easy with binary numbers. To multiply by two, all bits must only be shifted once to the left.

Example

Let us look at a 4 bit example to see how the modified Booth algorithm works.

We will be calculating $a\times b$ with $a = 5_{10} = 00101$ and $b = 6_{10} = 0110$. Note that we have already added a leading bit to our number $a$.

We start by encoding $b$. Remember to append a trailing $0$ to it for the encoding process.

With the modified algorithm, we only encode two operations from our 4 bit multiplicator: "$-2x$" and "$+2x$".

Let us draw the multiplication table.

Note how we only have two operations and that these two operations are at different place values. Our first operation is still placed in the $2^0$ column. The second operation is placed in the $2^2$ column. This is because we utilize a radix-4 encoding: our operations are written in the columns which are powers of four. If we had a third operation we would write it in the $2^4$ column, a fourth into the $2^6$ column and so on.

Let us now calculate our partial products:

Notice that per new row, we add two zeros to the right. Because we are in radix-4, we automatically skip every second column.

For the multiplication by $2$ we simply shift our result one column to the left. These shifts are highlighted in red ($\color{red}{0}$).

Our final result is $00011110_2 = 30_{10} = 5 \times 6$ which is correct.

The modified Booth algorithm has halved the amount of partial products compared to the normal Booth algorithm. This gives us a significant speed benefit because we only need to do one addition instead of three additions.

Reducing partial products

The amount of partial products created by a given Booth algorithm can be calculated like so:

$n$ is the amount of bits the factors use. $N_b$ is the number denoting the different types of Booth’s algorithm (Booth-1, Booth-2, Booth-3…).

We multiplied 4 bit numbers with Booth-1 (normal) and Booth-2 (modified). Let us verify the formula gives us the same partial products we saw during our examples:

We can see that the normal Booth algorithm never reduces the amount of partial products when compared to conventional multiplication. The amount of partial products is equal to the amount of bits used.

The modified Booth algorithm halves the amount of partial products which is why it is the preferred algorithm for hardware implementations.

Booth-3 / Radix-8

Given the significant reduction of partial products with the modified Booth algorithm, we might consider to look at the next level and encode four bits at a time. This algorithm is called Booth Radix-8 or Booth-3 and would result in only a third of the usual partial products.

The radix-8 algorithm looks at quadruples of bits: ($y_{i+2}$,$y_{i+1}$, $y_{i}$, $y_{i-1}$).
The table has 16 different encodings:

Unfortunately this encoding has a huge problem: the odd multiples "$3x$" and "$-3x$". Unlike powers of two ($2x$, $4x$) which we can easily realize in binary by left-shifting, multiplying by $3$ or any odd number is not so simple.

Because of the odd multiples, the radix-8 algorithm is not often considered for hardware implementations. However, if the odd multiples can be overcome, there is a benefit in further reducing the amount of partial products.

The practical use and calculation of radix-8 and beyond is left up to the reader from this point.

Bibliography

• Booth, Andrew Donald, 1951, “A Signed Binary Multiplication Technique”
• Brown University, 2010, “Booth’s Algorithm for Multiplication”