Content deleted Content added
Removed spam point |
Matthiaspaul (talk | contribs) added and improved refs |
||
Line 1:
'''Booth's multiplication algorithm''' is a [[multiplication algorithm]] that multiplies two signed [[base 2|binary]] numbers in [[two's complement|two's complement notation]]. The [[algorithm]] was invented by [[Andrew Donald Booth]] in 1950 while doing research on [[crystallography]] at [[Birkbeck, University of London|Birkbeck College]] in [[Bloomsbury]], [[London]].
==The algorithm==
Booth's algorithm examines adjacent pairs of [[bit]]s of the 'N'-bit multiplier ''Y'' in signed [[two's complement]] representation, including an implicit bit below the [[least significant bit]], ''y''<sub>−1</sub> = 0. For each bit ''y''<sub>''i''</sub>, for ''i'' running from 0 to ''N'' − 1, the bits ''y''<sub>''i''</sub> and ''y''<sub>''i''−1</sub> are considered. Where these two bits are equal, the product accumulator ''P'' is left unchanged. Where ''y''<sub>''i''</sub> = 0 and ''y''<sub>''i''−1</sub> = 1, the multiplicand times 2<sup>''i''</sup> is added to ''P''; and where ''y''<sub>i</sub> = 1 and ''y''<sub>i−1</sub> = 0, the multiplicand times 2<sup>''i''</sup> is subtracted from ''P''. The final value of ''P'' is the signed product.
The representations of the multiplicand and product are not specified; typically, these are both also in two's complement representation, like the multiplier, but any number system that supports addition and subtraction will work as well. As stated here, the order of the steps is not determined. Typically, it proceeds from [[Least significant bit|LSB]] to [[Most significant bit|MSB]], starting at ''i'' = 0; the multiplication by 2<sup>''i''</sup> is then typically replaced by incremental shifting of the ''P'' accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest ''N'' bits of ''P''.<ref name="Chen_1992"/> There are many variations and optimizations on these details.....
The algorithm is often described as converting strings of 1s in the multiplier to a high-order +1 and a low-order −1 at the ends of the string. When a string runs through the MSB, there is no high-order +1, and the net effect is interpretation as a negative of the appropriate value.
Line 96 ⟶ 86:
==References==
{{reflist
<ref name="Chen_1992">{{cite book |title=Signal processing handbook |author-first=Chi-hau |author-last=Chen |publisher=[[CRC Press]] |date=1992 |isbn=978-0-8247-7956-6 |page=234 |url=https://books.google.com/books?id=10Pi0MRbaOYC&pg=PA234}}</ref>
}}
==Further reading==
* {{cite web |title=Advanced Arithmetic Techniques |author-first=John J. G. |author-last=Savard |date=2018 |orig-year=2006 |work=quadibloc |url=http://www.quadibloc.com/comp/cp0202.htm |access-date=2018-07-16 |dead-url=no |archive-url=https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm |archive-date=2018-07-03}}
==External links==
* [http://www.geoffknagge.com/fyp/booth.shtml Radix-4 Booth Encoding]
* [http://www.russinoff.com/libman/text/node65.html Radix-8 Booth Encoding] in [http://www.russinoff.com/libman/ A Formal Theory of RTL and Computer Arithmetic]
* [http://www.ecs.umass.edu/ece/koren/arith/simulator/Booth/ Booth's Algorithm JavaScript Simulator]
* [http://philosophyforprogrammers.blogspot.com/2011/05/booths-multiplication-algorithm-in.html Implementation in Python]
[[Category:1950 introductions]]
| |||