Booth's Algorithm Booth's Algorithm for Two's Complement Multiplication


Booth's Algorithm

There is no need to take the sign if a number into consideration with unsigned multiplication. However, with signed multiplication the same process cannot be applied. The sign number is put in two's complement form which would cause an incorrect result if multiplied the same way as unsigned multiplication and this is where Booth's algorithm comes into play. Booth's algorithm keeps the sign of the result.


There are two methods used. These are:

  • Right Shift
  • Right Shift Arithmetic


    • Right Shift

    Right-shift is simply moving the A, Q and Q-1 registers 1 bit. After shifting, the least significant bit in A should be the first bit in Q and the least significant bit in Q should now be in Q-1.


    Right Shift Arithmetic

    Right-shift is simply moving the A, Q and Q-1 registers 1 bit. After shifting, the least significant bit in A should be the first bit in Q and the least significant bit in Q should now be in Q-1.

    Right-shift Arithmetic is adding or subtracting two (2) binary numbers together and shifting the result to the right one (1) bit position.

    Example for adding:    0110
                                       + 0110
        Result =                   1010

     Shift all the bits to the right and put the first (1st) bit at the beginning of the result.

    Result = 1010
    Shift = 11010

    Example for subtracting: 7 is 0111 in binary
                                              4 is 0100 in binary
    The second number is changed to one's complement first then add 1 to change to two's complement.

    0100 is 1011 in ones complement
    1011
    +  1
    1100
    Then add the two binary numbers.
    0111
    + 1100
      10011


    Steps for Booth's Algorithm
    You need 4 registers the first is the accumulator, A, the second is the multiplier, Q, the next is the Q-1 bit and the last is the multiplicand M.
    A <- 0
    Q <- multiplier
    Q -1 <- 0
    M <- multiplicand
    Count <- n

    Begin algorithm
    Step 1: Check LSB (least significant bit) and Q-1 if both are 00 or 11
    Step 2: Do a shift (explained above)
    End of algorithm
    Begin algorithm
    Step 1: If Q0 and Q-1 are 10 then subtract:
    Step 2: A <- A - M
    Step 3: Then do a shift
    End of algorithm
    Begin algorithm
    Step 1: If Q0 and Q-1 are 01 then add:
    Step 2: A <- A + M
    Step 3: then do a shift
    End of algorithm

    Example

     6 x 2
    We shall use 6 as the multiplicand which in binary is 0110
    We shall use 2 and the multiplier which in binary is 0010
    Initially A holds 0, A= 0000
    Q will hold the multiplier which is 0010
    Initially the Q-1 bit is 0
    M will hold the multiplicand which is 6, in binary 0110

    Step 1: Compare the Q0 and the Q-1 bit positions
    Q3    Q2    Q1    Q0
    0         0       1       0

     Both the Q0 and Q-1 positions are the same,00, whenever both are the same you simply shift the bits.(Arthimatic right shift)

    A QQ-1 M=0110
    0000 0010 0
    0000 0001 0


    Step 2: Again compare the Q0 and the Q-1 bit. This time it is 10. When it is 10 you subtract A<--A - M

    Therefore A - M =       0000
                                      - 0110
                          A <-       1010
     (This can be done using one's or the two's compliment)

    A becomes the outcome of subtracting A - M which is 1010 and the others are left as they are. The table should now look like:

    A QQ-1 M=0110
    0000 0010 0
    0000 0001 0
    1010 0001 0


    Another shift is then done below.

    A QQ-1 M=0110
    0000 0010 0
    0000 0001 0
    1010 0001 0
    1101 0000 1


    Step 3: Q0 and Q-1 are then compared again.This time it is 01, When it is 01 you add A <- A + M.

    Therefore A + M =       1101
                                      + 0110
                          A <-         0011
     (This can be done using one's or the two's compliment)

    A becomes the outcome of adding A + M which is 0011 and the others are left as they are. The table should now look like:

    A QQ-1 M=0110
    0000 0010 0
    0000 0001 0
    1010 0001 0
    1101 0000 1
    0011 0000 1


    Another shift is then done

    A QQ-1 M=0110
    0000 0010 0
    0000 0001 0
    1010 0001 0
    1101 0000 1
    0011 0000 1
    0001 1000 0


    Step 4: Q0 and Q-1 are then compared again. This time it is 00, when it is the bits are the same you simply perform a shift.

    A QQ-1 M=0110
    0000 0010 0
    0000 0001 0
    1010 0001 0
    1101 0000 1
    0011 0000 1
    0001 1000 0
    0000 1100 0


    The answer is now 0000 1100 = 12
    6 x 2 = 12
    Hence proven.

    NB: Keep in mind Q-1, the position to the right of the least significant bit. Unlike unsigned binary multiplication, there is no carry and if there is a carry then that is ignored.


    Think you understand? Take the Quiz!