Booth's Algorithm

Introduction

• Booth's Algorithm is used for multiplying two signed binary numbers.
• The algorithm involves a series of arithmetic operations and bit manipulations.

Flowchart Overview

• Start: Initialize variables.
  • A (Accumulator) = 0
  • Q-1 = 0 (previous bit of Q)
  • M = Multiplicand
  • Q = Multiplier
  • n = Number of bits

Key Conditions

• If Q0 and Q-1 are:

  • 00 or 11: Perform arithmetic right shift and decrement n.
  • 01: Add A and M, then right shift.
  • 10: Subtract M from A, then right shift.

• When n = 0, end the program and store the result in A.

Example Calculation

• Multiplicand (M) = 7 (binary 0111)
• Multiplier (Q) = 3 (binary 0011)
• Result: 7 x 3 = 21
  • Binary result of 21 = 10101

Step-by-Step Operations

1. Initialization:

   • A = 0000 (4 bits)
   • Q = 0011 (3)
   • Q-1 = 0
   • n = 4

2. First Check (Q0=1, Q-1=0):

   • Perform A = A - M (A = A + 2's complement of M)
   • 2's complement of M (0111) = 1001
   • New A = 1001
   • Perform right shift: A = 1100, Q = 0011, Q-1 = 0

3. Second Check (Q0=1, Q-1=1):

   • Arithmetic right shift:
   • New A = 1110, Q = 0011, Q-1 = 1

4. Third Check (Q0=0, Q-1=1):

   • Perform A = A + M
   • New A = 0101
   • Perform right shift: A = 1010, Q = 0011, Q-1 = 1

5. Fourth Check (Q0=0, Q-1=1):

   • Perform A = A + M
   • New A = 1110
   • Perform right shift: A = 0111, Q = 0100, Q-1 = 0

6. Final Check (Q0=0, Q-1=0):

   • Arithmetic right shift:
   • Final values: A = 0001, Q = 0101
   • Result = 21 (in binary: 0001 0101)

Summary

• The Booth's algorithm effectively multiplies two signed binary numbers through a series of checks and operations based on the states of Q0 and Q-1.
• The final output is obtained after a specified number of shifts and operations, showcasing the binary multiplication process.