Booth's Multiplication Algorithm in Computer Organization
Reading Time: 6 minutes
Published: 29 October 2025
Table of Contents
Key Takeaways From The Blog
- Booth's Algorithm is a fast and efficient binary multiplication algorithm used to multiply signed numbers in 2's complement representation.
- Proposed by Andrew Donald Booth in 1951, it simplifies binary multiplication by minimizing the number of arithmetic operations.
- It is widely implemented in computer architecture, processors, and digital signal processors (DSPs) for efficient signed multiplication.
- The algorithm scans pairs of the multiplier and performs arithmetic operations based on patterns, reducing redundant additions and subtractions.
- Key advantages include reduced computational complexity and improved hardware efficiency; limitations include higher latency in some cases and increased implementation complexity.
Introduction
In computer architecture, the rapid and efficient multiplication of binary numbers is a critical factor that significantly influences the overall performance of digital systems. Essentially, a simple multiplication algorithm involves a series of addition and shifting operations, which can be costly in terms of computation time if there are many of them. Hence, a solution in the form of an optimization technique called Booth's Algorithm has been found to minimize the interaction of the algorithm with memory and therefore speed up multiplication and allow for the use of less hardware.
Historical Background and Significance
The Booth Algorithm was created by Andrew Donald Booth in 1951 when he was looking for fast ways of multiplication for digital computers. In those days, computers had minimal hardware capabilities, and it was necessary to optimise arithmetic operations.
The Booth multiplication algorithm in computer architecture is a technique that helps the computer multiply signed binary numbers more efficiently by examining the bit patterns of the multiplier. This change significantly improved computational performance, especially in systems where multiplication is performed very often, for example, in signal processing and embedded hardware.
What is Booth Algorithm in Computer Architecture?
Booth's multiplication is an algorithm for binary multiplication. It reduces the number of operations required for multiplication by expressing the multiplier in a unique form. It treats positive and negative numbers the same as in other forms of multiplication, so it is highly efficient to implement in computer programs that manipulate signed numbers extensively.
The following is how multiplication is carried out in Booth's Algorithm:
- Taking two adjacent bits of the multiplier step by step.
- Adding to or subtracting from, or leaving the current product unchanged, depending on these bits.
- Shifting the product rightward, step by step, builds the resulting value.
How the Booth's Algorithm Works?
The Booth algorithm scans successive pairs of bits in the multiplier and performs arithmetic based on the pairs. It uses 2's complement representation to support both positive and negative numbers.
Understanding Booth's Algorithm is easier when its sequential steps are clearly mentioned. This section breaks down the algorithm's working, introduces the key registers and terms, and the process to help you follow each stage of the multiplication.
Hardware Implementation of Booth's Algorithm
Booth's Algorithm implemented in hardware is very effective as it regularly accesses the content of several registers and does only some arithmetic operations of a very simple kind each time. The knowledge of the hardware organization is a must to understand the algorithm's efficiency in performing binary multiplication.
Key Registers and Their Roles
- AC (Accumulator Register): For one time, it holds temporary both intermediate and the final multiplication result.
- QR (Q Register or Multiplier Register): Contains the multiplier and is also involved in the shifting part of the operation.
- Qn and Qn+1: Qn stands for the least significant bit of QR and Qn+1 is an additional bit that is attached to QR to keep the record of the previous value of Qn. The pair is very important in deciding whether to add, subtract, or change the partial product.
- BR (B Register or Multiplicand Register): The register that contains the value of the multiplicand.
- SC (Sequence Counter): A device that monitors the number of steps or iterations, usually set equal to the number of bits in a multiplier.
Step-by-Step Procedure of Booth's Algorithm
The Booth multiplication algorithm in computer architecture follows a sequence of logical steps to perform signed multiplication efficiently.
Algorithm Steps
Initialize Registers:
- AC (Accumulator Register) ← 0
- QR (Multiplier Register) ← Multiplier
- BR (Multiplicand Register) ← Multiplicand
- Qn+1 ← 0
- SC (Sequence Counter) ← Number of bits in multiplier
Check Bit Pair (Qn, Qn+1):
- If (Qn, Qn+1) = (0, 1) → AC = AC + BR
- If (Qn, Qn+1) = (1, 0) → AC = AC – BR
- Else → No arithmetic operation
Perform Arithmetic Right Shift:
- Combine AC, QR, and Qn+1, then shift right by 1 bit.
Decrement SC:
- Reduce sequence counter by 1.
Repeat Steps 2–4:
Combine Results:
- The final product is found in the concatenated AC and QR registers.
Booth's Algorithm Flowchart in Hardware
The hardware flow typically follows these steps:
- Initialize AC, QR, Qn+1, and SC.
- Inspect the pair (Qn, Qn+1) and perform the required operation (add, subtract, or no change).
- Perform an arithmetic right shift on AC and QR together, shifting Qn+1 as well.
- Decrement SC and repeat until SC reaches zero.
- The final product is contained in the combined AC and QR registers.
This arrangement allows Booth's Algorithm to be efficiently executed in digital systems, such as processors and digital signal processors (DSPs), where speed and resource optimization are critical.
Registers Used in Booth's Algorithm
In Booth's multiplication algorithm, several registers play specific roles to store intermediate and final results.
| Register |
Full Name |
Purpose |
| AC |
Accumulator Register |
Temporarily holds the intermediate and final results of multiplication |
| BR |
B Register (Multiplicand Register) |
Holds the multiplicand |
| QR |
Q Register (Multiplier Register) |
Holds the multiplier and participates in shifting |
| Qn and Qn+1 |
Least Significant Bits |
The least significant bits of QR, used to determine operations |
| SC |
Sequence Counter |
Tracks how many iterations remain |
This hardware design makes Booth's algorithm in computer architecture efficient and modular for integration in Arithmetic Logic Units (ALUs).
Practical Example and Algorithm Steps
It is really effective to understand Booth's Algorithm when you go through a practical example and list the step-by-step process. Such a demonstration shows the algorithm working in a computer and makes easier to follow the functions of the different registers and control logic.
Example: Multiplying 5 × (−3)
Step 1: Initialize the Registers
We first convert both numbers to their binary forms.
Now, m = 5 (binary: 0101), r = −3 (binary: 1101) in 4-bit 2's complement representation, as we are working with 4-bit registers. We will assume we are using 4 bits for the multiplicand and multiplier.
- Multiplicand M = 0101
- Multiplier Q = 1101
Now we initialize the following registers:
- AC (Accumulator) = 0000 (4-bit register)
- QR (Multiplier Register) = Q = 1101
- Qn+1 = 0 (additional bit, initialized to 0)
- SC (Sequence Counter) = 4 (since the multiplier has 4 bits)
Step 2: Start the Algorithm
We have to verify the least significant two bits of multipliers Qn and Qn+1 and adhere to Booth's algorithm rules:
First Iteration (SC = 4):
- Qn = 1 (from QR), Qn+1 = 0 (initialized to 0)
- The last two bits are 10, so we perform a subtraction of the multiplicand from AC:
- AC = AC − M
- AC = 0000 − 0101 = 1011 (in 2's complement representation of 4 bits)
- Now perform the arithmetic right shift operation on AC and QR:
- Before shift: AC = 1011, QR = 1101, Qn+1 = 0
- After the right shift: AC = 1101, QR = 1110, Qn+1 = 1
- Decrement the sequence counter SC = 3.
Second Iteration (SC = 3):
- Qn = 0, Qn+1 = 1
- The last two bits are 01, so we perform an addition of the multiplicand to AC:
- AC = AC + M
- AC = 1101 + 0101 = 0010 (in 4-bit 2's complement representation)
- Perform the arithmetic right shift operation on AC and QR:
- Before shift: AC = 0010, QR = 1110, Qn+1 = 1
- After right shift: AC = 0001, QR = 1111, Qn+1 = 0
- Decrement the sequence counter SC = 2.
Third Iteration (SC = 2):
- Qn = 1, Qn+1 = 0
- The last two bits are 10, so we perform a subtraction of the multiplicand from AC:
- AC = AC − M
- AC = 0001 − 0101 = 1011 (in 2's complement)
- Perform the arithmetic right shift operation on AC and QR:
- Before shift: AC = 1011, QR = 1111, Qn+1 = 0
- After right shift: AC = 1101, QR = 1111, Qn+1 = 1
- Decrement the sequence counter SC = 1.
Fourth Iteration (SC = 1):
- Qn = 1, Qn+1 = 1
- The last two bits are 11, so we do not perform any addition or subtraction. We just perform the arithmetic right shift:
- Before shift: AC = 1101, QR = 1111, Qn+1 = 1
- After right shift: AC = 1110, QR = 1111, Qn+1 = 1
- Decrement the sequence counter SC = 0.
Step 3: Result
At the end of the algorithm, the result of the multiplication will be stored in the AC and QR registers.
To interpret this result:
- The AC and QR together form the final product in 8-bit 2's complement representation: 11101111.
- This is the 8-bit 2's complement representation of -15, which is the product of 5 × (−3) = −15
Final Answer: The product of 5 × (−3) using Booth's algorithm is -15.
What We've Learned So Far
- Booth's Algorithm simplifies multiplication by encoding patterns of bits.
- It uses add, subtract, and shift operations to handle signed numbers.
- The algorithm minimizes arithmetic complexity and improves hardware performance.
What are the Advantages of Booth's Multiplication Algorithm?
The benefits of Booth's multiplication algorithm are:
- The algorithm is utilized to multiply signed binary numbers and it is effective for negative and positive numbers both without the requirement of individual logic for negative numbers.
- The algorithm reduces the number of additions and subtractions to be performed in multiplication and therefore the algorithm is efficient compared to other algorithms.
- Booth's algorithm is also highly hardware-friendly as it can reduce the arithmetic complexity of the operations significantly, which is invaluable when dealing with low-resource systems like embedded systems.
- The algorithm is efficient in dealing with strings of 0's or 1's in the multiplier by reducing shifting and operation to a minimum.
- It is mostly used in processors, digital signal processors (DSPs), and other hardware accelerators in an effort to maximize the acceleration of multiplication operations.
What are the Disadvantages of Booth's Multiplication Algorithm?
The disadvantages of Booth's Multiplication Algorithm are:
- It may be more challenging to obtain and execute than the usual multiplication techniques. It is more conservative when dealing with sign bits and conditional add or subtract.
- It is mostly for signed binary numbers. To be used with unsigned numbers, adjustments must be done, so it is less general to the multiplication of all types of binary numbers.
- The algorithm involves multiple iterations of addition, subtraction, and shifting, which may lead to higher latency compared to simpler multiplication methods.
- Although it reduces the number of operations, the algorithm may still consume more power due to the multiple cycles involved in shifting and adding or subtracting the multiplicand.
Applications of Booth's Multiplication Algorithm
The applications of Booths' Multiplication Algorithm:
- This algorithm is often integrated into the Arithmetic Logic Unit (ALU) of microprocessors to perform efficient binary multiplication.
- In DSP applications, where the algorithm helps to reduce computation time for multiplication operations such as filtering and convolution.
- The systems often require efficient exponentiation and multiplication of large numbers.
- This is utilized in dedicated hardware accelerators to accelerate specific tasks, such as image processing or machine learning, where big multiplications are generally executed.
Key Takeaways
- Booth's Algorithm is efficient for signed multiplication in 2's complement form.
- It significantly reduces the number of arithmetic operations compared to conventional methods.
- Widely used in computer organization, DSPs, and embedded processors.
Radix-4 and Radix-8 Booth Multipliers
Advanced versions of Booth's algorithm improve performance by processing multiple bits per iteration.
Radix-4 Booth Multiplier
- Only two bits of the multiplier are processed at one time.
- The number of cycles is reduced by half compared to the standard Booth algorithm.
- Hardware implementations that require faster multiplication can use it as a power source.
Radix-8 Booth Multiplier
- Three bits of the multiplier are processed simultaneously.
- It further reduces the number of cycles and increases the throughput for large data operations.
- Now, this technique is mainly found in high-performance processors and digital signal systems.
Conclusion
Booth's Algorithm is one of the core methods in computer architecture to multiply signed binary numbers efficiently. It achieves this by minimising the number of additions and subtractions and by utilising bit-level operations. Thus, the method it yields is not only faster but also more hardware-friendly. Consequently, it is a key concept in the study of digital systems when one wants to understand how computation is optimised, with the algorithm serving as the foundation of many processors, DSPs, and hardware accelerators.
Why It Matters?
Booth's Algorithm enables efficient signed binary multiplication, forms the basis for hardware multipliers in processors and DSPs, and illustrates how logical optimization can improve computational performance.
Practice Advice for Learners
- Begin by using minimal examples (4-bit or 8-bit) to figure out the shifting and addition/subtraction steps.
- Practice converting numbers to 2's complement to use signed values properly.
- Follow each loop closely to understand how AC, QR, and Qn+1 change.
- Check the results against regular multiplication to confirm that they are correct.
- Gradually move to Radix-4 or Radix-8 variations for faster implementations.
Frequently Asked Questions
1. What is the importance of Booth's Multiplication Algorithm?
The algorithm of the booth is essential as it optimizes the multiplication of the signed binary numbers, reducing the number of required additions and subtractions. It is necessary in hardware implementation, especially in processors and digital signal processors, where speed and hardware efficiency are crucial.
2. How many bits are in the Booth Algorithm?
The multiplier's bit width determines the number of bits in the Booth Algorithm. If the multiplier is n bits, the algorithm operates with n bits for both the multiplicand and the multiplier, and an additional bit (Qn+1) is used for the least significant bit of the multiplier.
3. What are the two attractive features of Booth's algorithm?
The two attractive features of Booth's algorithm are:
- Reduced the number of additions/subtractions for multiplication.
- Efficient handling of signed binary numbers, making it ideal for computing in digital systems.
4. What is the time complexity of Booth's algorithm?
The time complexity of Booth's algorithm is O(n), where n is the number of bits in the multiplier. This is because the algorithm requires a constant number of operations (add, subtract, shift) per bit in the multiplier.
5. What is the Radix 4 and Radix 8 Booth's Multiplier?
- Radix-4 Booth Multiplier: It consumes two bits of the multiplier in each iteration, effectively decreasing the number of cycles from the standard Booth algorithm. This results in faster multiplication and fewer operations.
- Radix-8 Booth Multiplier: The multiplication takes optimization even further by processing three bits of the multiplier at a time. This can significantly speed up the multiplication process, especially in hardware implementations for large numbers.
6. What are Radix-4 and Radix-8 Booth Multipliers?
These are optimized versions of the standard Booth Algorithm. Radix-4 processes two bits of the multiplier at a time, and Radix-8 processes three bits, reducing the number of cycles and further speeding up multiplication operations.
7. What are common misconceptions about Booth's Algorithm?
- It is only for positive numbers: Booth's Algorithm is designed explicitly for signed numbers.
- It always reduces operations: While it often reduces the number of operations, in some cases—such as alternating 0s and 1s—it may not provide significant gains.
- It is complex to implement: While conceptually more involved than basic multiplication, it is widely used in hardware due to its efficiency.
Related Articles
Source: NxtWave - CCBP Blog
Original URL: https://www.ccbp.in/blog/articles/booth-multiplication-algorithm-in-computer-organization