Booth Algorithm

with an example

3 min readJul 11, 2022

Multiplication in Computer Digital Logic is very intriguing since there exists myraid ways to implement it. You can simply create it in combinational style, or reluctantly compromise on speed for reducing the number of gates in the circuit by using sequential logic.

Naive Sequential Multiplication

Here is how to multiply 2 and 6 on binary representation.

note that 0110 can be decomposed to 0100 + 0010

The algorithm is very simple. Assume that your multiplicand and multiplier are n-bit binary number. First, intialize 2n bits with multiplier at nth least significant bits and zero at the remaining bits, and we will call it ‘product’. Iterating for n times, if current least significant bit of product is one, add multiplicand to nth most significant bits of product, which is the left half. Then shift right the product by one bit.

Table below represents steps to multiply 0010 and 0110.

Booth’s Algorithm

Booth has discovered that some addition steps can be reduced by decomposing consecutive ones as an example.

01101 x (10000 – 00001) requires only one addition and one subtraction while 01101 x 01111 requires four addition!

Here is a flowchart of Booth Algorithm.

Since the flowchart itself is not quite comprehensive, taking a look on an example might help you understand.

Example : 2 x 6

Initialize values (CNT stands for Count in the flowchart)

Q0 Q-1 = 00, then right shift and decrement CNT by 1

Q0 Q-1 = 10, then deduct A by M,

and right shift, then decrement CNT by 1

If you are confusing why the left bit become one after right shift, this is called arithmetic shift which preserves 2’s complements sign https://en.wikipedia.org/wiki/Arithmetic_shift

Q0 Q-1 = 11, then right shift and decrement CNT by 1