Radix 4 booth

Radix 2 and 4 booth algorithm with example

1. PRESENTED BY DAVIS OOMMEN ABRAHAM RICHU JOSE CYRIAC BINARY MULTIPLICATION USING BOOTH’S RADIX-4 ALGORITHM MICROELECTRONICS & VLSI DESIGN NIT CALICUT WINTER 2012

2. WHY BOOTH’S ALGORITHM? In ALU, only add/subtract/shift operations are possible. Multiplication involves 2 basic operations - generation of partial products + their accumulation 2 ways to speed up - reducing number of partial products and/or accelerating accumulation Fewer partial products generated for groups of consecutive 0’s and 1’s in Booth's algorithm

3. RADIX-2 : AN OVERVIEW ---------------------------------------------------------------------- X i X i –1 Y i Explanation ---------------------------------------------------------------------- 0 0 0 No string of 1s in sight 0 1 1 End of string of 1s in x 1 0 - 1 Beginning of string of 1s in x 1 1 0 Continuation of string of 1s in x ------------------------------------------------------------------------ EXAMPLE 1 1 0 1 0 1 1 1 0 Operand x - 1 1 - 1 1 0 0 - 1 0 Recoded version y (0) TIP: Y i=Xi-1 -X i

4. RADIX-2 : AN EXAMPLE M 0110 +6 X Y 0010(0) +2 Z 0 1 -1 0 RECODED MULTIPLIER ACCUMULATOR Y Y n-1 Z OPERATIONS 0000 0010 0000 0001 -1 SHIFT 1010 1101 0001 0000 1 1 A<-A-M SHIFT 0011 0001 0000 1000 1 A<-A+M SHIFT 0000 1100

5. DRAWBACKS OF RADIX-2 ALGORITHM Algorithm inefficient with isolated 1's e.g. 001010101(0) recoded as 0 1-1 1-1 1-1 1 -1, requiring 8 instead of 4 operations

6. RADIX-4 : CODING TECHNIQUE –––––––––––––––––––––––––––––––––––––––––––––––––––– x i +1 x i x i –1 z i /2 Explanation –––––––––––––––––––––––––––––––––––––––––––––––––––– 0 0 0 0 No string of 1s in sight 0 1 1 End of string of 1s 1 0 1 Isolated 1 1 1 2 End of string of 1s 1 0 0 - 2 Beginning of string of 1s 1 0 1 - 1 End a string, begin new one 1 1 - 1 Beginning of string of 1s 1 1 1 0 Continuation of string of 1s –––––––––––––––––––––––––––––––––––––––––––––––––––– Example 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 0 (0) Operand x - 2 2 - 1 2 - 1 - 1 - 2 Radix-4 version z

7. RADIX 4 : AN EXAMPLE

8. VHDL SIMULATION VHDL code simulation for the multiplication of two binary numbers A=00010001(17) B=11110111(-9)

9. CONCLUSION In radix-4 algorithm , n/2=3 steps are used ie . 2 multiplier bits in each step All shift operations are 2 bit position shifts Compared to radix-2 Booth's algorithm - less patterns with more partial products; Smaller increase in number of operations Algorithms can be extended for higher radices also

10. Thank you

11. APPENDIX