Booth's multiplication algorithm

The Booth algorithm is an algorithm for multiplication of two numbers in two's complement representation. It was developed in 1951 by Andrew Donald Booth at work on crystallography at Birkbeck College.

  • 3.1 Encoding of a factor according to Booth
  • 3.2 multiplication

Method

  • Let x be the number of bits of the multiplicand and y is the number of bits of the multiplier.
  • Draw a three-row grid with columns. Denote the rows of A ( addition), S ( subtraction) and P ( product).
  • Note the first x bits of each line as follows: A: multiplicand
  • S: negated multiplicand ( in two's complement)
  • P: zeros
  • A: zeros
  • S: zeros
  • P: multiplier
  • 00 or 11: Do nothing
  • 01. Ignore any overflow.
  • 10th Ignore any overflow.

Idea

It makes use of the fact that each number can b as the difference of two numbers c and d:

Then you can choose any arbitrary multiplication of b by a factor a transform as follows:

Advantages over the " paper and pencil " method, this method in numbers that have long strings of bits in the binary equivalent. These are " skipped " at the Booth method. Based on this method also allows the Booth - efficient multiplication of binary numbers in two, ie the algorithm has the advantage that one need not observe the signs of the two factors.

Example

If you want to multiply by a number X, you needed with the traditional method three additions. The Booth's method, however, required only one.

The subtraction can be expected as an addition in the two's complement multiplication by a multiple of 2 only corresponds to a shift in the positions to the left ( shift operation ). Thus, the method of efficient multiplication in computers used.

The Booth algorithm provides an efficient way to identify a number of the according -to-use coding. One starts from right to left by the binary number. Changes the binary digit from the last to the current position from 0 to 1, then -1 is a 1 and none change a 0 is set when changing from 1 to 0. The first step is to think of the number to the right a 0 to it.

Examples

Multiply and

Coding of a factor according to Booth

Formal: The operand to be encoded by Booth to add another " site", which is set to zero. The other points of the new can be calculated as follows:.

Multiplication

Instead 0100000, 0001000 and 0000100 to multiply and add the results, so now is with 1000000, 0100000, 0010000 and 0000100 multiplied and accordingly the results are added or subtracted.

As you can see by the example, the number of additions can also increase (in the example from 3 to 4 ), which is, yes, but not desired. On a statistical average, as many additions as needed without Booth's method in the Booth method. The advantage lies in the fact that in the computer science there is no uniform distribution of numbers. Rather, there are often numbers with many zeros and the two's complement for negative numbers often many ones at the beginning. Only by this fact, the method of Booth's advantages over a normal multiplication.

The extension of the Booth's method, the bit -pair method in which always two points are summarized.

Shift register
138641
de