Booth's Multiplication Algorithm

Booth's multiplication algorithm is an algorithm used to multiply two signed binary numbers using shifts and additions. It is particularly efficient when one of the numbers is negative. The algorithm reduces the number of additions needed to perform the multiplication.

The steps involved in Booth's multiplication algorithm are as follows:

1. Initialize the variables:
- Let A be the multiplicand (14 in this case) and Q be the multiplier (11 in this case).
- Let M be the number of bits in the binary representation of the multiplier (4 in this case).
- Let Q(-1) be initialized as 0, which represents the extra bit for the sign extension.
- Let Q(0) be initialized as the least significant bit of Q (1 in this case).

2. Perform the multiplication:
- Repeat the following steps M times:
- If the least significant bit of Q and Q(-1) are both 1 or both 0, perform an arithmetic right shift on AQ and assign the value of Q(0) to Q(-1).
- If the least significant bit of Q is 1 and Q(-1) is 0, perform an addition of A to AQ and assign the value of Q(0) to Q(-1).
- If the least significant bit of Q is 0 and Q(-1) is 1, perform a subtraction of A from AQ and assign the value of Q(0) to Q(-1).

3. Obtain the result:
- After M iterations, the product AQ represents the result of the multiplication.

Applying Booth's Multiplication Algorithm to (14) x (11):

Step 1: Initialize the variables
- A = 14 (multiplicand)
- Q = 11 (multiplier)
- M = 4 (number of bits in the binary representation of the multiplier)
- Q(-1) = 0
- Q(0) = 1

Step 2: Perform the multiplication
- Iteration 1:
- Q(0) = 1, Q(-1) = 0
- Since the least significant bit of Q and Q(-1) are both 1, perform an arithmetic right shift on AQ and assign the value of Q(0) to Q(-1).
- AQ = 0000 1110
- Q(0) = 0

- Iteration 2:
- Q(0) = 0, Q(-1) = 1
- Since the least significant bit of Q is 0 and Q(-1) is 1, perform a subtraction of A from AQ and assign the value of Q(0) to Q(-1).
- AQ = 1111 0000 (AQ - A = 14 - 14 = 0)
- Q(0) = 0

- Iteration 3:
- Q(0) = 0, Q(-1) = 0
- Since the least significant bit of Q and Q(-1) are both 0, perform an arithmetic right shift on AQ and assign the value of Q(0) to Q(-1).
- AQ = 0111 1000
- Q