Booth Multiplication Algorithm

Efficient Binary Multiplication for Signed Numbers

📚 Overview

The Booth Multiplication Algorithm is a powerful technique for multiplying binary numbers, particularly efficient for signed binary multiplication. Developed by Andrew Donald Booth in 1950, it reduces the number of additions required in the multiplication process by examining consecutive bits and performing intelligent operations.

⚡ Efficient

Reduces the number of arithmetic operations compared to traditional methods

🔢 Handles Signed Numbers

Works seamlessly with both positive and negative binary numbers

🎯 Hardware Implementation

Easily implemented in digital circuits and processors

🎛️ Navigation

Algorithm Steps

Step 1: Initialize AC (Accumulator) = 0, SC (Sequence Counter) = n (number of bits), and QR (Multiplier Register) with the multiplier. Add an extra bit Q-1 = 0.
Step 2: Examine Qn and Qn+1 (the rightmost bit of QR and Q-1):
  • If QnQn+1 = 01: AC ← AC + BR (Add multiplicand to AC)
  • If QnQn+1 = 10: AC ← AC - BR (Subtract multiplicand from AC)
  • If QnQn+1 = 00 or 11: Do nothing
Step 3: Perform arithmetic right shift (ashr) on the combined AC and QR register (maintaining sign bit).
Step 4: Decrement SC by 1.
Step 5: If SC ≠ 0, repeat from Step 2. Otherwise, the product is in AC and QR combined.

Worked Example: B = 10111 (Multiplicand)

This example demonstrates the complete multiplication process using Booth's Algorithm:

Operation E A Q SC
Multiplier in Q 0 00000 10011 101
Qn = 1; add B 10111
First partial product 0 10111
Shift right EAQ 0 01011 11001 100
Qn = 1; add B 10111
Second partial product 1 00010
Shift right EAQ 0 10001 01100 011
Qn = 0; shift right EAQ 0 01000 10110 010
Qn = 0; shift right EAQ 0 00100 01011 001
Qn = 1; add B 10111
Fifth partial product 0 11011
Shift right EAQ 0 01101 10101 000
Final product in AQ = 0110110101

Hardware Architecture

Block Diagram of Booth Multiplication Hardware
BR register Complementer and parallel adder AC register QR register Qn Qn+1 Sequence counter (SC) Data flow and control paths

Component Description:

  • BR (B Register): Holds the multiplicand
  • AC (Accumulator): Stores partial products during computation
  • QR (Q Register): Holds the multiplier and evolving product
  • SC (Sequence Counter): Tracks the number of iterations remaining
  • Complementer & Adder: Performs addition/subtraction operations

Algorithm Flowchart

Booth's Algorithm Control Flow
Booth Flowchart

Flowchart Key Points:

  • Initialization: Sets up registers and counters for the algorithm
  • Bit Pair Examination: Checks QₙQₙ₊₁ to determine the operation
  • Conditional Operations: Add, subtract, or do nothing based on bit pattern
  • Arithmetic Shift: Right-shifts the result while preserving the sign
  • Loop Control: Continues until all bits are processed (SC = 0)

Interactive Booth Multiplication Calculator

Enter binary numbers to see Booth's algorithm in action! (Use 5-bit signed binary numbers)

🎯 Advantages of Booth's Algorithm

✓ Efficiency

Reduces the number of additions needed, especially when multiplying numbers with consecutive 1s or 0s

✓ Signed Arithmetic

Naturally handles two's complement signed numbers without additional conversion

✓ Hardware Friendly

Simple to implement in digital circuits with standard components

🔍 Why Booth's Algorithm Works

The algorithm exploits the mathematical property that a string of 1s in binary can be represented as a subtraction. For example:

Binary: 0111 = 8 - 1 = 7

This means: 0111 = 1000 - 0001

By recognizing bit patterns (01 and 10 transitions), Booth's algorithm minimizes operations by treating consecutive 1s as a single subtract-add pair rather than multiple additions.

Array Multiplier