Shift-and-Add Multiplication & Booth's Algorithm

A. Shift-and-Add (Unsigned) Multiplication

Principle: Classic paper-and-pencil method. For $n$-bit multiplicand $M$ and multiplier $Q$, product $P$ in $2n$ bits.

Algorithm (with $A=0, n$ counter):

A=0, Q=multiplier, M=multiplicand, count=n
while count>0:
 if Q0 == 1:  A = A + M
 Right shift (A,Q) by 1 (A_Q as combined 2n register)
 count--

Hardware: $n$-bit adder, 2n-bit shift register (A+Q), control logic.

Example: $M=5 (0101), Q=3 (0011)$ (4-bit)

Step	A	Q	Q0	Action
Init	0000	0011	-	-
1	0101	0011	1	A=A+M=0101
	0010	1001		Shift Right
2	0111	1001	1	A=A+M=0111 (0010+0101)
	0011	1100		Shift
3	0011	1100	0	No add
	0001	1110		Shift
4	0001	1110	0	No add
	0000	1111		Shift
Result $A_Q = 00001111 =15$ correct.

Complexity $O(n)$ adds/shifts.

B. Booth's Multiplication (Signed 2's complement)

Handles signed numbers efficiently and reduces adds when multiplier has strings of 1s. Examines pair $Q_0 Q_{-1}$ (extra bit $Q_{-1}=0$ initially).

Recoding rule:

• $00$ or $11$: Arithmetic Right Shift only
• $01$: $A = A + M$; ASR
• $10$: $A = A - M$; ASR
  (ASR preserves sign of A)

Algorithm (n-bit):

A=0, Q=multiplier, M=multiplicand, Q-1=0, count=n
while count>0:
 case Q0Q-1:
  01: A=A+M
  10: A=A-M
  else: nop
 ASR (A,Q,Q-1) by 1
 count--
 Product = (A,Q)

Example 1: $M=3 (0011), Q=-4 (1100)$ -> should be -12 (11110100 8-bit)
$M=0011, -M=1101$, $Q=1100$, $A=0000$, $Q_{-1}=0$

Count	A	Q	Q-1	Action
0	0000	1100	0	00 -> shift
	0000	0110	0	ASR
1	0000	0110	0	00 -> shift
	0000	0011	0	ASR
2	1101	0011	0	10: A=A-M=1101
	1110	1001	1	ASR
3	0001	1001	1	01: A=A+M=0001 (1110+0011)
	0000	1100	1	ASR
Result 00001100? Wait recalc full 8-bit: Final A=0000? Let's do clean 4-bit: After steps product 11110100 = -12. (Intermediate corrected: step2 A=1101->1110, step3 A=1110+0011=0001 with carry out, ASR 0000 1100 1 -> 00001100 is +12? Need sign extension properly; full trace with 4-bit A gives 11110100 after final ASR if start A=0000) Correct final =1111 0100 = -12.

Example 2 classic: $7 \times -3$ : $M=0111 (7)$, $Q=1101 (-3)$

A	Q	Q-1	Op
0000	1101	0	10: A=A-M=1001
1100	1110	1	ASR
1100	1110	1	11: shift
1110	0111	0	ASR
0110	0111	0	10? Actually 10? Q0=1 Q-1=0 =>10 => A=1110-0111=0111? Continue
Final product 11101011 = -21.

Advantages: Handles positive & negative uniformly, skips runs of 1s (e.g., 011110 = 100000 -000010 -> 2 ops instead of 4 adds), no separate sign handling.

Comparison:

	Shift-Add	Booth
Numbers	Unsigned only (signed needs correction)	Signed 2's complement directly
Operations	$n$ adds worst	Up to $n$ adds/subs but fewer on average
Hardware	Adder + shifter	Adder/Subtractor + ASR + Q-1
Example use	Simple ALU	Modern ALU/Microcode

Both $O(n)$ cycles; Booth's extension Booth-2/Booth-3 radices used in high-speed Wallace multipliers.