29-06-2012, 01:05 PM
Booth’s Algorithm
Booth’s Algorithm.pdf (Size: 98.47 KB / Downloads: 197)
Notice the following equality (Booth did)
• 2J + 2J–1 + 2J–2 + … + 2K = 2J+1 – 2K
• Example: 0111 = 1000 - 0001
• We can exploit this to create a faster multiplier
• How?
• Sequence of N 1s in the multiplier yields sequence of N additions
• Replace with one addition and one subtraction
Booth Hardware
Control algorithm: repeat 16 times
• Multiplier LSBs == 10? Subtract multiplicand from product
• Multiplier LSBs == 01? Add multiplicand to product
• Shift product/multiplier right by 1 (not by 2!)
Booth in Summary
Performance/efficiency
+ Good for sequences of 3 or more 1s
• Replaces 3 (or more) adds with 1 add and 1 subtract
• Doesn’t matter for sequences of 2 1s
• Replaces 2 adds with 1 add and 1 subtract (add = subtract)
– Actually bad for singleton 1s
• Replaces 1 add with 1 add and 1 subtract
• Bottom line
• Worst case multiplier (101010) requires N/2 adds + N/2 subs
• What is the worst case multiplier for straight multiplication?
• How is this better than normal multiplication?
Carry Save Addition (CSA)
Carry save addition (CSA): d(N adds) < N*d(1 add)
• Enabling observation: unconventional view of full adder
• 3 inputs (A,B,Cin) ® 2 outputs (S,Cout)
• If adding two numbers, only thing to do is chain Cout to Cin+1
• But what if we are adding three numbers (A+B+D)?
• One option: back-to-back conventional adders
• Add A + B = temp
• Add temp + D = Sum
• Better option: instead of rippling carries in first addition (A+B),
feed the D bits in as the carry bits (treat D bits as C bits)
• Assume A+B+D = temp2
• Then do traditional addition (not CSA) of temp2 and C bits
generated during addition of A+B+D