Booth multiplier - Computer Arithmetic -

💡 What’s the Problem with Simple Multiplication?

Before we jump into Booth’s method, let’s recall what happens in Shift-and-Add multiplication.

That method works fine — but when the numbers are negative or have long sequences of 1s, it becomes slow and repetitive.
The computer ends up doing unnecessary additions, which wastes time.

Booth’s algorithm fixes this! 🙌

It’s a clever shortcut that makes multiplication faster — especially for signed numbers (numbers that can be positive or negative).

⚙️ What is the Booth Multiplier?

Booth’s multiplier is a method used by computers to multiply binary numbers, including negative ones, using 2’s complement representation.

It was invented by Andrew Donald Booth in 1951 — so you can think of it as an early form of “smart multiplication” for binary systems.

🧠 The Big Idea (in Simple Words)

Instead of adding the multiplicand again and again for each ‘1’ in the multiplier,
Booth’s algorithm looks at patterns in the multiplier to decide whether to:

Add the multiplicand
Subtract the multiplicand
or Do nothing

This means fewer additions and subtractions — and faster results! ⚡

🔍 The Trick Behind It

Booth’s method checks two bits at a time — the current bit and the bit just before it.

Let’s call:

The multiplier bits → Q
An extra bit (initialized as 0) → Q₋₁

Then, at each step, Booth looks at the pair (Q₀, Q₋₁) — that is, the current LSB and the previous bit — and decides what to do.

Here’s the simple rule table:

Pair (Q₀, Q₋₁)	Action
00	Do nothing
11	Do nothing
01	Add multiplicand to accumulator
10	Subtract multiplicand from accumulator

After performing the action, the algorithm arithmetic shifts right (ASR) — this moves all bits one position to the right while keeping the sign bit safe.

🧩 Step-by-Step Process (Easy Version)

Let’s multiply –5 (in binary) and 3 (in binary) using Booth’s algorithm.

Step 1: Represent Numbers in 2’s Complement Form

We’ll use 4-bit representation.

Multiplicand (M) = -5 = 1011
Multiplier (Q)   = 3  = 0011
Q₋₁              = 0
Accumulator (A)  = 0000

Step 2: Repeat for the number of bits (4 times here)

Step	(Q₀, Q₋₁)	Action	A (Accumulator)	Q (Multiplier)	Q₋₁	Operation
1	1,0	A = A – M	0101	0011	0	Subtract
		→ ASR	1010	1001	1	Shift right
2	1,1	Do nothing	1010	1001	1
		→ ASR	1101	0100	1	Shift right
3	0,1	A = A + M	1000	0100	1	Add
		→ ASR	1100	0010	0	Shift right
4	0,0	Do nothing	1100	0010	0
		→ ASR	1110	0001	0	Final shift

Now, the result in (A, Q) = 11100001, which is the 8-bit result.

Convert it back → –15 in decimal ✅
And indeed, (–5 × 3 = –15). Perfect!

🎯 Why Booth’s Algorithm is Smart

Booth noticed that instead of adding the same number repeatedly (like in the shift-and-add method),
we could look for runs of 1s and replace them with fewer operations.

For example:
If your multiplier is 011110, it has a long group of 1s.
Instead of adding 4 times, Booth’s method says — “just subtract once at the start and add once at the end.”
That’s much faster!

⚙️ Hardware Components (Concept Diagram)

Here’s a simple diagram to help visualize how Booth’s multiplier works:

          +----------------------+
          |      CONTROL UNIT    |
          +----------------------+
                   |     ^
                   v     |
  +----------+   +-------------+   +-----------+
  |  ACC (A) |<->|   ADDER/SUB |<->|  M (Multiplicand) |
  +----------+   +-------------+   +-----------+
        |                 |
        v                 |
  +----------+             |
  |   Q (Multiplier) <----+
  +----------+
        |
        v
  +----------+
  |  Q₋₁ Bit |
  +----------+

  (ASR → Arithmetic Shift Right after each step)

This setup lets the hardware:

Check (Q₀, Q₋₁)
Add/Subtract as needed
Shift all bits right for the next step

⚖️ Advantages of Booth’s Algorithm

Advantage	Explanation
✅ Handles signed numbers easily	Works with 2’s complement — no separate logic needed
⚡ Faster than shift-and-add	Reduces unnecessary additions
🧠 Efficient with consecutive 1s	Converts repeated adds into one subtract and one add
🔩 Simple hardware design	Needs only adder, subtractor, and shifter

⚠️ Limitations

Limitation	Description
🐢 Complex for random patterns	Doesn’t always save time if bits alternate frequently
🧮 Needs extra control logic	Slightly more complex than simple multipliers
💡 Better methods exist	Modern processors use improved versions like Modified Booth’s algorithm

💬 Everyday Analogy

Think of it like counting apples:
If you need 5 apples and someone gives you 4 in a bunch,
you don’t say “Give me one apple five times.”
You take 4 in one go and then one more.

That’s what Booth’s algorithm does — it groups operations smartly instead of repeating them!