Booth’s Multiplication Algorithm in Computer Organization

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. 

The Booth multiplication algorithm in computer architecture follows a sequence of logical steps to perform signed multiplication efficiently.

Algorithm Steps

1. 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
2. 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
3. Perform Arithmetic Right Shift:
   
   • Combine AC, QR, and Qn+1, then shift right by 1 bit.
4. Decrement SC:
   
   • Reduce sequence counter by 1.
5. Repeat Steps 2–4:
   
   • Continue until SC = 0.
6. 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:

1. Initialize AC, QR, Qn+1, and SC.
2. Inspect the pair (Qn, Qn+1) and perform the required operation (add, subtract, or no change).
3. Perform an arithmetic right shift on AC and QR together, shifting Qn+1 as well.
4. Decrement SC and repeat until SC reaches zero.
5. 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.

In Booth’s multiplication algorithm, several registers play specific roles to store intermediate and final results.

• AC (Accumulator): Temporarily holds the intermediate and final results of multiplication.
• BR (B Register): Holds the multiplicand.
• QR (Multiplier Register): Holds the multiplier and participates in shifting.
• Qn and Qn+1: 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).

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.

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 = 101, 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 = 1The 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 = 0The 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 = 1The 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. Where, AC = 1110, QR = 1111To 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.

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.

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.

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.

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.

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.

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.