Saturday, 1 June 2013

Program for Signed Multiplication using Booth's Algorithm

Booth's algorithm is a multiplication algorithm which worked for two's complement numbers. It is similar to our paper-pencil method, except that it looks for the current as well as previous bit in order to decided what to do. Here are steps

  • If the current multiplier digit is 1 and earlier digit is 0 (i.e. a 10 pair) shift and sign extend the multiplicand, subtract with previous result.
  • If it is a 01 pair, add to the previous result.
  • If it is a 00 pair, or 11 pair, do nothing.
Let's look at few examples.
           4 bits
            0110   <- 6
        x   0010   <- 2
   -------------
        00000000
     -     0110
  --------------
        11110100
     +    0110
  --------------
    (1) 00001100  <- 12     (overflow bit ignored)
         8 bits
In Booth's algorithm, if the multiplicand and multiplier are n-bit two's complement numbers, the result is considered as 2n-bit two's complement value. The overflow bit (outside 2n bits) is ignored.
The reason that the above computation works is because
      0110 x 0010 = 0110 x (-0010 + 0100) = -01100 + 011000 = 1100.
Example 2:
            0010
         x  0110
     ------------
        00000000
    -      0010
    -------------
        11111100
    +    0010
    -------------
    (1) 00001100
In this we have computed
    0010 x 0110 = 0010 x ( -0010 + 1000) = - 00100 + 0010000 = 1100

Download With OUTPUT


EmoticonEmoticon

:)
:(
hihi
:-)
:D
=D
:-d
;(
;-(
@-)
:o
:>)
(o)
:p
:-?
(p)
:-s
8-)
:-t
:-b
b-(
(y)
x-)
(h)