Fast Multiplication - Bit Pair Recoding

Fast Multiplication – Bit Pair Recoding

• To speed–up the multiplication process in the Booth's algorithm a technique called bit–pair recoding is used. It is also called modified Booth's algorithm. It halves the maximum number of summands.

• In this technique, the Booth–recoded multiplier bits are grouped in pairs. Then each pair is represented by its equivalent single bit multiplier reducing total number of multiplier bits to half.

• For example pair (+ 1 −1) is equivalent to the pair (0 +1). That is, instead of adding −1 times multiplicand at shifted position i to +1 times the multiplicand at position i + 1, the same result is obtained by adding +1 times multiplicand at position i. Similarly, (+1 0) is equivalent to (0 +2), (−1 +1) is equivalent to (0-1) and so on.

• By replacing pairs with their equivalents we can get bit-pair multiplier. But instead of deriving bit-pair recoded multiplier from Booth recoded multiplier one can directly derive it from original multiplier. The bit-pair recoding of multiplier can be directly derived from Table 4.12.2. Table 4.12.2 shows the bit-pair code for all possible multiplier bit options.

Example 1 Find the bit-pair code for multiplier.

1 1 0 1 0.

Solution

By referring table we can derive bit-pair code as follows:

Example 2 Multiply given signed 2's complement numbers using bit-pair recoding

A=110101 multiplicand (−11)

B=011011 multiplier (+27)

Solution: Let us find the bit-pair code for multiplier.

Multiplication: Multiplicand X + 2 = Left shift multiplicand by 1 bit = 1101010.

Example: 3

Give the Booth's recoding and bit–pair recoding of the number.

1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1.

Solution : Booth's recoding

Example: 4

Multiply the following pair of signed 2's complement numbers using bit–pair recoding of the multipliers : A = 010111, B = 101100.

Solution :

A = 0 1 0 1 1 1                       Multiplicand (+ 23)

B = 1 0 1 1 0 0                       Multiplier (– 20)

Let us find the bit–pair code for multiplier

Multiplication :

Example: 5

Explain Booth's algorithm to multiply the following pair of signed two's complement numbers :

A = 110011 multiplicand

B = 101100 multiplier

Also, implement the above using bit–pair Recoding and explain how it achieves faster multiplication.

Solution :

Multiplication :

Note : Shaded portion indicates sign extensions

Implementation with Bit–Pair recoding

Bit–pair recoding for multiplier :

Multiplication :

The Booth's algorithm may need the summation at each step and number of steps required in Booth's algorithm are equal to length of multiplier in bits. The bit–pair recoding halves the maximum number of summations. Hence it achieves faster multiplication.

Example: 6

Solve the following using bit–pair recoding method.

Multiplicand = 01111 (15)      Multiplier 10110 (–10)

Solution :

Bit–pair recoding of multiplier :

Multiplicand × (+2) = Shift left multiplicand by 1 bit = 011110

Multiplicand × (–2) = Shift left 2's complement multiplicand by 1 bit = 100010

Multiplication :

Example: 7

Solve the following multiplication using bit pair recoding technique

Multiplicand = 11011       Multiplier = 0011

Solution :

Bit–pair recoding :

Multiplication :

Example: 8

Bit pair recode multipliers : (110110101111001)₂ and (0101101010010101)₂

Solution :

Bit pair recoding of (110110101111001)₂

Bit pair recoding of (0101101010010101)₂

Example: 9

Solve the following using bit–pair recoding method :

Multiplicand = 110101 and Multiplier = 011011

Solution:

Bit–pair recoding of multiplier :

Multiplicand × (+2) = Shift left multiplicand by 1–bit = 1101010

Multiplication :

Review Question

1. Illustrate multiplication of signed 2's complement numbers 01101 and 11010 using bit–pairing of the multipliers.