Multiplication of Signed Numbers PDF

Preview

Summary

Prof. Mahesh...

Description

Sub Subject ject ject:: Computer Organization

Ari Arithm thm thmetic etic etic:: Multiplication of Signed Numbers

3.3 M Signe Mul ul ultip tip tiplic lic licati ati atio on o off Si gned d Nu Num mber Cas Case e (1 (1): ): Consider a posi ositive tive mu multip ltip ltiplie lie lierr and a nega egativ tiv tive em multip ultip ultiplic lic lican an and d. When Multiplier bit is 1, the Multiplicand is added to Partial Product (PPi). In this case, we must extend the sign-bit value of the multiplicand to the left as far as the product will extend. Exam Examp ple le: Let us consider a 5-bit signed operands: – A multiplicand: (-13) and a multiplier: (+11) produces 10-bit product, (−143). The Multiplication is shown in Figure 3.17

Figur Figure e 3.17 3.17:: Signed Multiplication Cas Case e (ii (ii): ): Consider a Neg Negati ati ative ve Mu Multip ltip ltiplier lier an and d a Neg egative ative M Mult ult ultipli ipli iplican can cand d In this case, need to take 2’s-complements of both the multiplier and the multiplicand and proceed as in the case of a positive multiplier. This is possible because complementation of both operands does not change the value or the sign of the product. A technique that works equally well for both negative and positive multipliers, called the Booth algorithm, is described next. 3. 3.3. 3. 3.1 1 Th The eB Booth ooth Alg Algor or orith ith ithm m The Booth Algorithm treats both positive and negative 2’s complement n-bit operands uniformly. Basic principle used in Booth Algorithm is to reduce the number of operations is as follows  A multiplier may be positive / negative. In Booth Algorithm, the multiplier is modified such that the number of operation is reduced as follows. Example: Let us assume Multiplier is (0011110), in normal approach the product is derived by adding the 4 appropriately shifted version of multiplicand.

Sub Subject ject ject:: Computer Organization

Ari Arithm thm thmetic etic etic:: Multiplication of Signed Numbers

Let us take a Multiplicand – (0101101) and Multiplier (0011110)

Figur Figure e 3.18 3.18:: Normal Multiplication Scheme[1] In Booth Algorithm, Instead of taking Multiplier as it is, the Multiplier is represented by taking the difference between two numbers 0100000 (32) -25 0000010 (2) - 21 0011110

(30)

This suggests that the product can be generated by adding 25 times the multip multiplic lic licand and to the 2’s1 comp comple le leme me ment nt of 2 times the multip multiplic lic licand and. For convenience, we can describe the sequence of required operations by recoding the preceding mu multip ltip ltiplier lier as 0 +1 0 0 0 −1 00..

Figur Figure e 3.19 ((a): a): Booth Multiplication Scheme

Sub Subject ject ject:: Computer Organization

Ari Arithm thm thmetic etic etic:: Multiplication of Signed Numbers

This leads to reduced operations

Figur Figure e 3.19 (b): Booth multiplier Scheme rearranged to show reduced Operations Boo Booth th R Rec ec ecodin odin odingg of Mu Multip ltip ltiplier lier In general, in the Booth algorithm, the recoding of the Multiplier is done as follows  −1 times the shifted multiplicand is selected when moving from 0 to 1, and  +1 times the shifted multiplicand is selected when moving from 1 to 0, as the multiplier is scanned from right to left. Exam Examp ple1: Recoding of Multiplier ( 0 0 1 1 1 1 0)2

Exam Examp ple 22:: Recoding of Multiplier (0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0)2

Exam Examp ple 22:: Recoding of Multiplier ( 1 1 0 1 0)

Sub Subject ject ject:: Computer Organization

Ari Arithm thm thmetic etic etic:: Multiplication of Signed Numbers

Exam Examp ple: Multiplication of Multiplicand ( 0 1 1 0 1) (+ 13) by Negative Multiplier ( 1 1 0 1 0) (-6) using Booth Algorithm

Figur Figure e 33.20 .20 .20:: Recoding of Multiplier in Booth Algorithm - Examples The Booth technique for recoding multipliers is summarized as

Figur Figure e 3.21 3.21:: Booth Multiplier Recoding Table [1] The transformation 011 . . . 110 ⇒+1 0 0. . . 0 −1 0 is called skipping over 1s. This term is derived from the case in which the mult multipli ipli iplier er has its 1s group grouped ed int into o a few con contigu tigu tiguou ou ouss bloc blocks. ks. Only a few vers version ion ionss of the shif shifted ted mu multi lti ltiplic plic plicand and (the su summ mm mman an ands) ds) ne need ed to be add added ed to generate the product, thus speeding up the multiplication operation. However, in the worst case—that that of altern alternatin atin atingg 1s and 0s in the multip multiplier lier lier—each bit of the multiplier selects a summand. In fact, this results in more summands than if the Booth algorithm were not used. A 16-bit worst-case multiplier, an ordinary multiplier, and a good multiplier are shown in figure 3.22.

Sub Subject ject ject:: Computer Organization

Ari Arithm thm thmetic etic etic:: Multiplication of Signed Numbers

In this example given multiplier has alternate 0 and 1, The Booth recoding is as shown below. It clearly indicates that the Booth Recoding Multiplier leads to alternate +1 and -1. This shows that it will actually lead to increase in number of operations rather than reducing the operation. “The Booth Recoding Multiplier will not always hold good in reducing the number of operations”

For the Ordinary and Good Multiplier it is shown as below

Figur Figure e 3.22 3.22:: Booth Recoded Multiplier[1]...