Multiplication of Signed and Unsigned Numbers

Multiplication of Signed and Unsigned Numbers

 

1. Sequential Multiplication of Positive Numbers

• The multiplication is a complex operation than addition and subtraction. It can be performed in hardware or software.

• Fig. 4.11.1 shows the usual algorithm for multiplying positive numbers by hand.

• Looking at this algorithms we can note following points :

■ Multiplication process involves generation of partial products, one for each digit in the multiplier. These partial products are then summed to produce the final product.

■ In the binary system the partial products are easily defined. When the multiplier bit is 0, the partial product is 0, and when the multiplier is 1, the partial product is the multiplicand.

■ The final product is produced by summing the partial products. Before summing operation each successive partial product is shifted one position to the left relative to the preceding partial product, as shown in Fig. 4.11.1.

■ The product of two n–digit numbers can be accommodated in 2n digits, so the product of the two 4–bit numbers in fits into 8–bits.

• Fig. 4.11.2 shows the implementation of manual multiplication approach. It consists of n–bit binary adder, shift and add control logic and four registers, A, B, C and Q.

Note : Dotted lines indicate control signals

• As shown in Fig. 4.11.2 multiplier and multiplicand are loaded into register Q and register B, respectively and C are initially set to 0.

Multiplication operation steps

1. Bit 0 of multiplier operand (Q₀ of Q register) is checked.

2. If bit 0 (Q₀) is one then multiplicand and partial product are added and all bits of C, A and Q registers are shifted to the right one bit, so that the C bit goes into A_n–1, A₀ goes into Q_n–1, and Q₀ is lost. If bit 0 (Q₀) is 0, then no addition is performed, only shift operation is carried out.

3. Steps 1 and 2 are repeated n times to get the desired result in the A and Q registers.

• A flowchart for multiplication operation is shown in Fig. 4.11.3.

• Let us see one example.

Consider 4–bit multiplier and multiplier and Multiplicand:

Multiplicand = 1 1 0 1 and

Multiplier = 1 0 1 1

Fig. 4.11.4 shows operations involved and their results in the process.

 

Review Questions

1. Explain an algorithm to multiply two positive numbers. Also discuss the realization of a multiplier to implement the same.

2. Design a multiplier that multiplies two 4–bit numbers.

3. Explain with an example how to multiply two unsigned binary numbers.

4. Explain the sequential version of multiplication algorithm and its hardware.

5. Demonstrate multiplication of two binary numbers with an example. Design an arithmatic element to perform this multiplication.

 

2. Sign Multiplication–Booth's Algorithm

• A powerful algorithm for signed–number multiplication is a Booth's algorithm, which generates a 2n–bit product and treats both positive and negative numbers uniformly.

• This algorithm suggest that we can reduce the number of operations required for multiplication by representing multiplier difference between numbers. For example, multiplier 0 0 1 1 1 0 (14) can be represented as follows.

• Therefore, the product can be computed by adding 2⁴ times the multiplicand to the 2's complement of 2¹ times the multiplicand. In simple notations, we can describe the sequence of required operations by recoding the preceding multiplier as

0 + 1 0 0 – 1 0

• In general, for Booth's algorithm recoding scheme can be given as :

–1 times the shifted multiplicand is selected when moving from 0 to 1, +1 times the shifted multiplicand is selected when moving from 1 to 0, and 0 times the shifted multiplicand is selected for none of the above case, as multiplier is scanned from right to left.

• We have to assume an implied 0 to right of the multiplier LSB. This is illustrated in the following examples.

Example: 1

Recode the multiplier 1 0 1 1 0 0 for Booth's multiplication.

Solution :

Example: 2

Recode the multiplier 0 1 1 0 0 1 for Booth's multiplication.

Solution :

• Fig. 4.11.5 shows the Booth's multiplication. As shown in Fig. 4.11.5, whenever multiplicand is multiplied by –1, its 2's complement is taken as a partial result.

Multiplier : 0 0 1 1 0 0

Multiplicand : 0 1 0 0 1 1

Recoded multiplier : 0 + 1 0 – 1 0 0

Note : Shaded portion indicates sign extensions

• The same algorithm can be used for negative multiplier. This is illustrated in the following example.

Example: 3

Multiply 0 1 1 1 0 (+14) and 1 1 0 1 1 (–5).

Solution :

Multiplication :

Note : Shaded portion indicates sign extensions

• The same algorithm also can be used for negative multiplier and negative multiplicand. This is illustrated in the following example.

Example: 4

Explain the following pair of signed 2's complement numbers.

Multiplicand : 1 1 0 0 11 (–13)

Multiplier : 1 0 1 1 0 0 (–20)

Solution :

Multiplication :

Note : Shaded portion indicates sign extensions

Example: 5

Multiply –9 × 7 using Booth's algorithm.

Solution :

Multiplication

Example: 6

Multiply –7 × 14 using Booth's algorithm.

Solution :

Multiplication

Example: 7

Explain multiplication of signed numbers (–13) × (–5) using Booth's algorithm.

Solution :

Multiplication

Example: 8

Multiply the following signed numbers using Booth algorithm. A = (–34)₁₀ = (1011110)₂ and B = (22)₁₀ = (0010110)₂ where B is multiplicand and A is multiplier.

Solution :

Example: 9

Calculate the following problems using BOOTH'S ALGORITHM.

i) (+13) × (–6)

ii) (+13) × (+6)

iii) (−13) × (−6)

iv)(−13) × (+6)

Solution :

 (+13) = (01101)₂

(+6) = (0110)₂

i) (+13) × (–6)

ii) (+13) × (+6)

iii) (−13) × (–6)

iv) (–13) × (+6)

Example: 10

Calculate 10011 (–13) × 01011 (+11) using Signed–Operand Multiplication.

Solution :

1. Hardware Implementation of Booth's Algorithm

• The Booth's algorithm can be implemented as shown in Fig. 4.11.6.

• It consists of n–bit adder, shift, add subtract control logic and four registers, A, B, Q and Q_–1.

• As shown in Fig. 4.11.6 multiplier and multiplicand are loaded into register Q and register B, respectively, and register A and Q_–1 are initially set to 0. The sequence counter, SC is set to a number n equal to the number of bits in the multiplier.

• The n–bit adder performs addition of two inputs. One input is the A register and other input is multiplicand. In case of addition,  line is 0, therefore C_in= 0 and multiplicand is directly applied as a second input to the n–bit adder.

• In case of subtraction,  line is 1, therefore C_in= 1 and multiplicand is complemented and then applied to the n–bit adder. As a result, the 2's complement of multiplicand is added in the A register.

• The shift, add and subtract control logic scans bits Q₀ and Q_–1 one at a time and generates the control signals as shown in Table 4.11.1.

• If the two bits are same (1 – 1 or 0 – 0), then all of the bits of the A, Q, and Q_{– 1} registers are shifted to right 1–bit without addition or subtraction (Add/subtract Enable = 0).

• If the two bits are differ, then the multiplicand (B–register) is added to or subtracted from the A register, depending on the status of bits.

• If bits are Q₀ = 0 and Q_–1 = 1 then multiplicand is added and if bits are Q₀ = 1 and Q_–1  = 0 then multiplicand is subtracted.

• After addition or subtraction right shift occurs such that the leftmost bit of A (A_n–1) is not only shifted into A_n–2, but also remains in A_n–1. This is required to preserve the sign of the number in A and Q. It is known as an arithmetic shift, since it preserves the sign bit.

• After arithmetic shift, the sequence counter is decremented by 1 and if it is not zero, computational loop is repeated. That is, in all computational loop is repeated n–times.

2. Flowchart of Booth's Multiplication Algorithm

• The sequence of events in Booth's algorithm can be explained with the help of flowchart and algorithm shown in Fig. 4.11.7.

Flowchart

Algorithm

Step 1: Load A = 0, Q_–1 = 0

B = Multiplicand

Q = Multiplier

SC = n

Step 2 : Check the status of Q₀Q_–1

if Q₀Q_–1 = 10 perform A ← A–B

if QoQ_–1 = 01 perform A ← A+B

Step 3 : Arithmetic shift right : A, Q, Q_–1

Step 4 :  Decrement sequence counter

if not zero, repeat step 2 through 4

Step 5 :  Stop

Example: 11

Multiply (–7) and (3) by using Booth's multiplication, Give the flow table of multiplication.

Solution :

 

Review Questions

1. Discuss the principle behind the Booth's multiplier.

2. Illustrate Booth's algorithm with an example.

3. Explain in detail about the multiplication algorithm with suitable example and diagram.

4. Define Booth Multiplication algorithm with suitable example.

5. Explain Booth's Algorithm for the multiplication of signed two's complement numbers.