text: Like this presentation? Why not share!
  
  # Booths Multiplication Algorithm
  
  ## by knightnick on Feb 29, 2008
  
  • 37,989 views
  
  Booth's multiplication algorithm
  
  Booth's multiplication algorithm
  
  ### Views
  
  Total Views
  37,989
  Views on SlideShare
  37,859
  Embed Views
  130
  
  Likes
  3
  720
  3
  
  ### 4 Embeds130
  
   http://www.slideshare.net 111 http://4thsemesterallsolutions.blogspot.com 9 http://4thsemesterallsolutions.blogspot.in 6 http://www.4thsemesterallsolutions.blogspot.com 4
  
  ### Categories
  
  Uploaded via SlideShare as Microsoft PowerPoint
  
  ### Report content
  
  • prasantalgt goodd 8 months ago
  Are you sure you want to
  • intr199 Thats why I always recommend slideshare 1 year ago
  Are you sure you want to
  • avinash.bhagat It is really helpful 2 years ago
  Are you sure you want to
  
  ## Booths Multiplication AlgorithmPresentation Transcript
  
  • BOOTH'S MULTIPLICATION ALGORITHM
  • INTRODUCTION
  • History
  • Procedure
  • Example
  • HISTORY
  • 在 1951 年時， Andrew D. Booth 在倫敦的 Bloomsbury 區的 Birkbeck 學院研究結晶學的時候發明的。
  • Booth 創造了這個運算法增加計算機運算加法位移的速度。
  • 這個算法對電腦運算結構有很大的幫助。
  • PROCEDURE
  • If x is the count of bits of the multiplicand, and y is the count of bits of the multiplier :
  • Draw a grid of three rows, each with columns for x + y + 1 bits. Label the lines respectively A (add), S (subtract), and P (product).
  • In two’s complement notation, fill the first x bits of each line with :
  • A: the multiplicand
  • S: the negative of the multiplicand
  • (in 2's complement format)
  • P: zeroes
  • Fill the next y bits of each line with :
  • A: zeroes
  • S: zeroes
  • P: the multiplier
  • Fill the last bit of each line with a zero.
  • Find 3 × -4, with x = 4 and y = 4: A = 0011 0000 0 S = 1101 0000 0 P = 0000 1100 0 x y 1 A multiplicand zeroes 0 S negative of the multiplicand zeroes 0 P zeroes multiplier 0
  • Do both of these steps y times :
  • 1. If the last two bits in the product are...
  • 00 or 11: do nothing.
  • 01: P = P + A. Ignore any overflow.
  • 10: P = P + S. Ignore any overflow.
  • 2. Arithmetically shift the product right one position.
  • Drop the first (we count from right to left when dealing with bits) bit from the product for the final result.
  • The last two bits do 00 do nothing 01 P = P + A. Ignore any overflow 10 P = P + S. Ignore any overflow. 11 do nothing
  • EXAMPLE 1
  • Find 3 × -4, with x = 4 and y = 4:
  • A = 0011 0000 0
  • S = 1101 0000 0
  • P = 0000 1100 0
  • Perform the loop four times :
  • P = 0000 110 0 0 . The last two bits are 00.
  • P = 0000 0110 0. A right shift.
  • P = 0000 011 0 0 . The last two bits are 00.
  • P = 0000 0011 0. A right shift.
  • P = 0000 001 1 0 . The last two bits are 10 .
  • P = 1101 0011 0 . P = P + S .
  • P = 1 110 1001 1. A right shift.
  • P = 1110 100 1 1 . The last two bits are 11.
  • P = 1111 0100 1. A right shift.
  • The product is 1111 0100, which is -12.
  • EXAMPLE 2
  • A = 1 1000 0000 0
  • S = 0 1000 0000 0
  • P = 0 0000 0010 0
  • Perform the loop four times :
  • P = 0 0000 0010 0. The last two bits are 00.
  • P = 0 0000 0001 0. Right shift.
  we demonstrate the improved technique by multiplying -8 by 2 using 4 bits for the multiplicand and the multiplier:
  • P = 0 0000 000 1 0 . The last two bits are 10 .
  • P = 0 1000 000 1 0 . P = P + S .
  • P = 0 0100 0000 1. Right shift.
  • P = 0 0100 000 0 1 . The last two bits are 01 .
  • P = 1 1100 000 0 1 . P = P + A .
  • P = 1 1110 0000 0. Right shift.
  • P = 1 1110 0000 0 . The last two bits are 00.
  • P = 1 1111 0000 0. Right shift.
  • The product is 11110000 (after discarding the first and the last bit) which is -16.
  • EXAMPLE 3
  • Find -11 × -4, with x = 4 and y = 4:
  • A = 1 0101 0000 0
  • S = 0 1011 0000 0
  • P = 0 0000 1100 0
  • Perform the loop four times :
  • P = 0 0000 1100 0 The last two bits are 00.
  • P = 0 0000 0110 0 Right shift.
  • P = 0 0000 0110 0. The last two bits are 00.
  • P = 0 0000 0011 0 Right shift.
  • P = 0 0000 001 1 0 The last two bits are 10 .
  • P = P + S
  • 0 0000 0011 0 (P)
  • + 0 1011 0000 0 (S)
  • = 0 1011 0011 0 (P+S)
  • P = 0 0101 1001 1. Right shift.
  • P = 0 0101 1001 1 The last two bits are 11.
  • P = 0 0010 1100 1 Right shift.
  • The product is 0010 1100 (after discarding the first and the last bit) which is 44.
  • ORIGINAL INFORMATION
  • http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm