Computer Arithmetic - Fundamentals of Computer Organization and Architecture - page 68

Multiplication In discussing multiplication, we shall assume that the two input

arguments are the multiplier Q given by Q ¼ q n 1 q n 2 q 1 q 0 and the multiplicand
M given by M ¼ m n 1 m m 2 m 1 m 0 . A number of methods exist for performing
multiplication. Some of these methods are discussed below.

The Paper and Pencil Method (for Unsigned Numbers)

This is the simplest
method for performing multiplication of two unsigned numbers. The method is illus-
trated through the example shown below.

Example Consider the multiplication of the two unsigned numbers 14 and 10.

The process is shown below using the binary representation of the two numbers.

1110 (14) Multiplicand( M)
1010 (10) Multiplier(Q)

0000 (Partial Product)

1110 (Partial Product)

0000 (Partial Product)

1110 (Partial Product)

¼¼¼¼¼¼
10001100 (140) Final Product(P)

The above multiplication can be performed using an array of cells each consisting
of an FA and an AND. Each cell computes a given partial product. Figure 4.6 shows
the basic cell and an example array for a 4 4 multiplier array.

What characterizes this method is the need for adding n partial products regard-
less of the values of the multiplier bits. It should be noted that if a given bit of the
multiplier is 0, then there should be no need for computing the corresponding partial
product. The following method makes use of this observation.

The Add-Shift Method In this case, multiplication is performed as a series of (n)
conditional addition and shift operations such that if the given bit of the multiplier is
0 then only a shift operation is performed, while if the given bit of the multiplier is 1
then addition of the partial products and a shift operation are performed. The follow-
ing example illustrates this method.

Example Consider multiplication of the two unsigned numbers 11 and 13. The

process is shown below in a tabular form. In this process, A is a 4-bit register and
is initialized to 0s and C is the carry bit from the most significant bit position.
The process is repeated n ¼

4 times (the number of bits in the multiplier Q). If
the bit of the multiplier is “1”, then A A þ M and the concatenation of AQ is
shifted one bit position to the right. If, on the other hand, the bit is “0”, then only
a shift operation is performed on AQ. The structure required to perform such an