03-05-2017, 12:07 PM
The Booth multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in the notation of two complements. The algorithm was invented by Andrew Donald Booth in 1950 while conducting research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desktop calculators that were faster on change than adding and created the algorithm to increase their speed. The Booth algorithm is of interest in the study of computational architecture.
The Booth algorithm examines adjacent pairs of bits of the N-bit multiplier Y in a two-sign complement representation, including an implicit bit below the least significant bit, y-1 = 0. For each bit yi, for i that goes From 0 to N-1, bits yi and yi-1 are considered. When these two bits are equal, the product accumulator P is left unchanged. Where yi = 0 and yi-1 = 1, the multiplying times 2i is added to P; And where yi = 1 and yi-1 = 0, multiplying times 2i is subtracted from P. The final value of P is the signed product.
The multiplicand and product representations are not specified; Usually these are the two also in the complement representation of two, as the multiplier, but any number system that supports addition and subtraction will work as well. As indicated here, the order of the steps is not determined. Typically, it comes from LSB to MSB, starting at i = 0; The multiplication by 2i is then typically replaced by incremental displacement of the accumulator P to the right between steps; The low bits can be shifted out, and subsequent additions and subtractions can be made only in the higher N bits of P. There are many variations and optimizations in these details .....
The algorithm is often described as the conversion of 1s chains into the multiplier at a high +1 and a low -1 at the ends of the string. When a string is run through the MSB, there is no high order +1, and the net effect is interpretation as a negative value of the appropriate value.