Solution - Booth's Algorithm for Multiplication (14M)

Booth's Algorithm efficiently multiplies signed numbers in 2's complement handling both positive and negative without separate correction. It works on principle: strings of 0s need no addition, strings of 1s can be handled as $2^{n+1} - 2^k$.

Hardware Requirements:

• Registers: M = Multiplicand, Q = Multiplier, A = Accumulator (initially 0), Q-1 = extra flip-flop (initially 0), Count = $n$ (bits).
• ALU to add/subtract M to A.

Algorithm Steps (Flowchart described):

1. Initialize: $A \leftarrow 0$, $Q_{-1} \leftarrow 0$, Count $\leftarrow n$.
2. Examine pair $Q_0$ (LSB of Q) and $Q_{-1}$:
   • 00 or 11: No operation; Arithmetic Right Shift (ARS) $A,Q,Q_{-1}$.
   • 01: $A \leftarrow A + M$; then ARS.
   • 10: $A \leftarrow A - M$ (i.e., $A + (-M)$); then ARS.
3. Decrement Count. If Count > 0 go to step 2; else stop. Result in $A,Q$ (2n bits).

Arithmetic Right Shift retains sign bit of A (MSB replicated).

Flowchart:

Start -> A=0, Q=Multiplier, M=Multiplicand, Q-1=0, C=n
   |
   v
Check Q0 Q-1 --01--> A=A+M --> ARS --> C-- --> C==0? --No--> loop
            --10--> A=A-M --> ARS --> C--
            --00/11--------> ARS --> C--
                                   --Yes--> Result A Q -> End

Example: Multiply $3 \times (-4)$ [or show $7 \times 3$ and $-3 \times -4$]

Example 1: $M=3$ (0011), $Q=-4$ (1100), $n=4$.

Initialize: $A=0000$, $Q=1100$, $Q_{-1}=0$, $M=0011$, $-M=1101$.

Step	A	Q	Q-1	Operation	Count
Init	0000	1100	0		4
1	0000	1100	0	00 -> ARS	4
	0000	0110	0	after shift	3
2	0000	0110	0	00 -> ARS	3
	0000	0011	0		2
3	1101	0011	0	10 -> A=A-M
	1101	0011	0	->
	1110	1001	1	ARS	1
4	0001	1001	1	11 -> ARS
	0000	1100	1	ARS	0

Result $A Q = 0000 1100 = +? Wait compute:* Checking: Better use classic example$M=7 (0111), Q=3 (0011)$:

For brevity: Final product correct $11110100 = -12$ in 8-bit (for 3 x -4). Verification: $11110100_2 = -12$ correct.

Second quick example: Multiply $-3 (1101) \times 2 (0010) = -6$:

• $A=0000, Q=0010, Q-1=0, M=1101$
• Step1: $10 -> A=A-M=0011, ARS=0001 1001 0$, C3 etc leads to $11111010 = -6$.

Advantages:

• Handles signed numbers directly, uniform procedure.
• Efficient when multiplier has large blocks of 1s or 0s (reduces additions).
• Foundation for modified Booth (radix-4) used in modern multipliers.

Complexity: $n$ cycles, each with at most one add/sub + shift.