Booth's multiplication algorithm

Booth's multiplication algorithm

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.

Procedure

Booth's algorithm involves repeatedly adding one of two predetermined values "A" and "S" to a product "P", then performing a rightward arithmetic shift on "P". Let x and y be the multiplicand and multiplier, respectively; and let "x" and "y" represent the number of bits in x and y.

# Determine the values of "A" and "S", and the initial value of "P". All of these numbers should have a length equal to ("x" + "y" + 1).
## A: Fill the most significant (leftmost) bits with the value of x. Fill the remaining ("y" + 1) bits with zeros.
## S: Fill the most significant bits with the value of (−x) in two's complement notation. Fill the remaining ("y" + 1) bits with zeros.
## P: Fill the most significant "x" bits with zeros. To the right of this, append the value of y. Fill the least significant (rightmost) bit with a zero.
# Determine the two least significant (rightmost) bits of "P".
## If they are 01, find the value of "P" + "A". Ignore any overflow.
## If they are 10, find the value of "P" + "S". Ignore any overflow.
## If they are 00 or 11, do nothing. Use "P" directly in the next step.
# Calculate the bit which gets shifted-in using the formula Sin = msb("Q") ^ msb("P") ^ carry_out_of("P" + "Q"), where "Q" represents "A", "S", or zero depending on what was added to "P".
# Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let "P" now equal this new value. The value Sin calculated from the previous step is shifted in leftmost bit.
# Repeat steps 2 to 4 until they have been done "y" times.
# Drop the least significant (rightmost) bit from "P". This is the product of x and y.

Example

Find 3 × −4, with x = 3 and y = −4, and "x" = 4 and "y" = 4:

* A = 0011 0000 0
* S = 1101 0000 0
* P = 0000 1100 0

* Perform the loop four times :
*# P = 0000 1100 0. The last two bits are 00.
*#* P = 0000 0110 0. Arithmetic right shift.
*# P = 0000 0110 0. The last two bits are 00.
*#* P = 0000 0011 0. Arithmetic right shift.
*# P = 0000 0011 0. The last two bits are 10.
*#* P = 1101 0011 0. P = P + S.
*#* P = 1110 1001 1. Arithmetic right shift.
*# P = 1110 1001 1. The last two bits are 11.
*#* P = 1111 0100 1. Arithmetic right shift.

* The product is 1111 0100, which is −12.

The above mentioned technique is inadequate when the multiplicand is the largest negative number that can be represented (i.e. if the multiplicand has 8 bits then this value is −128). One possible correction to this problem is to add one more bit to the left of A, S and P. Below, we demonstrate the improved technique by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
* A = 1 1000 0000 0
* S = 0 1000 0000 0
* P = 0 0000 0010 0

* Perform the loop four times :
*# P = 0 0000 0010 0. The last two bits are 00.
*#* P = 0 0000 0001 0. Right shift.
*# P = 0 0000 0001 0. The last two bits are 10.
*#* P = 0 1000 0001 0. P = P + S.
*#* P = 0 0100 0000 1. Right shift.
*# P = 0 0100 0000 1. The last two bits are 01.
*#* P = 1 1100 0000 1. P = P + A.
*#* P = 1 1110 0000 0. Right shift.
*# P = 1 1110 0000 0. The last two bits are 00.
*#* P = 0 1111 0000 0. Right shift.

* The product is 11110000 (after discarding the first and the last bit) which is −16.

How it works

Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by : : M imes ,^{primeprime} 0 ; 0 ; 1 ; 1 ; 1 ; 1 ; 1 ; 0 ,^{primeprime} = M imes (2^5 + 2^4 + 2^3 + 2^2 + 2^1) = M imes 62 where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as : M imes ,^{primeprime} 0 ; 1 ; 0 ; 0 ; 0 ; 0 mbox{-1} ; 0 ,^{primeprime} = M imes (2^6 - 2^1) = M imes 62.

In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:

: (ldots 0 overbrace{1 ldots 1}^{n} 0 ldots)_{2} equiv (ldots 1 overbrace{0 ldots 0}^{n} 0 ldots)_{2} - (ldots 0 overbrace{0 ldots 1}^{n} 0 ldots)_2.

Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 − 1 while multiplying by 99.

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,

: M imes ,^{primeprime} 0 ; 0 ; 1 ; 1 ; 1 ; 0 ; 1 ; 0 ,^{primeprime} = M imes (2^5 + 2^4 + 2^3 + 2^1) = M imes 58 : M imes ,^{primeprime} 0 ; 1 ; 0 ; 0 mbox{-1} ; 1 mbox{-1} ; 0 ,^{primeprime} = M imes (2^6 - 2^3 + 2^2 - 2^1) = M imes 58.

Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.

History

The algorithm was invented by Andrew D. Booth in 1951 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.

See also

* Multiplication ALU

External links

* [http://www.geoffknagge.com/fyp/booth.shtml Radix-4 Booth Encoding]
* [http://www.russinoff.com/libman/text/node38.html Radix-8 Booth Encoding] in [http://www.russinoff.com/libman/ A Formal Theory of RTL and Computer Arithmetic]

References

# Collin, Andrew. [http://www.cs.man.ac.uk./CCS/res/res05.htm#e Andrew Booth's Computers at Birkbeck College] . "Resurrection", Issue 5, Spring 1993. London: Computer Conservation Society.
# Patterson, David and John Hennessy. "Computer Organization and Design: The Hardware/Software Interface, Second Edition". ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
# Stallings, William. "Computer Organization and Architecture: Designing for performance, Fifth Edition". ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Booth — may refer to:In architecture:*Isolation booth, device used to prevent a person or people from seeing or hearing certain events *Photo booth, vending machine or modern kiosk which contains an automated, usually coin operated, camera and film… …   Wikipedia

  • Multiplication — Multiply redirects here. For other uses, see Multiplication (disambiguation). For methods of computing products, including those of very large numbers, see Multiplication algorithm. Four bags of three marbles gives twelve marbles. There are also… …   Wikipedia

  • Multiplication ALU — In digital design, a multiplier or multiplication ALU is a hardware circuit dedicated to multiplying two binary values. A variety of techniques can be used to implement a digital multiplier. Most techniques involve computing a set of partial… …   Wikipedia

  • Andrew Donald Booth — (born 1918) was a British engineer, physicist and computer scientist who led the invention of the magnetic drum memory for computers and invented Booth s multiplication algorithm.From 1943 to 1945 Booth worked as a mathematical physicist in the X …   Wikipedia

  • Алгоритм Бута — Алгоритм умножения Бута это алгоритм умножения, который позволяет перемножить два двоичных числа в дополнительном коде. Алгоритм был разработан Эндрю Дональдом Бутом в 1951 при проведении исследований в области кристаллографии в колледже им. Дж.… …   Википедия

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Binary multiplier — A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders. A variety of computer arithmetic techniques can be used to implement a digital… …   Wikipedia

  • Binary numeral system — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Two's complement — The two s complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2 N for an N bit two s complement).A two s complement system or two s complement arithmetic is a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”