Arithmetic and Logic in Computer Systems

4

Sequential Multiplication

Multiplication is an important task in computer arithmetic operations. Efficient algorithms and high-speed hardware should be developed to complete the multiplication. The sequential multiplication algorithms we introduce in this chapter are based on an add-shift approach. Detailed design of different types of multipliers will be given. Signed numbers multiplication will be discussed based on the indirect schemes and Robertson's approach. In addition, recoding techniques and Booth's algorithm, which speed up the multiplication by multiple-bit scanning, will be explained.

First we define some notation used in this chapter.

←	replacement operator
	concatenation or cascading operator
(R)	content of register R
∨	logic OR operation
∧	logic AND operation
+, −, ×, /	arithmetic operations of addition, subtraction, multiplication and division.

Let the multiplicand A and the multiplier B be two n-bit unsigned numbers. The multiplication

P = A × B

will create a 2n-bit product P. For the case that A and B are signed numbers, n − 1 bits are in each number excluding the sign bit. Hence 2(n − 1) + 1 = 2n − 1 bits will be in the product including the sign bit. To obtain a uniform representation, we add a dummy bit between the sign bit and the most significant bit, making a total of 2n bits. The dummy bit can be either 0 or the replication of the sign bit ...