6 Fixed Point Arithmetic Unit II

 

The objectives of this module are to discuss Booth’s multiplication technique, fast multiplication techniques and binary division techniques.

 

Booth’s Multiplier

 

The major advantage of the Booth’s technique as proposed by Andrew D. Booth is that it handles both positive and negative numbers. It may also have an added advantage of reducing the number of operations depending on the multiplier. The principle behind this is given below.

 

Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by :

 

M x 00111110 = M x (2⁵ + 2⁴+ 2³ + 2² + 2¹) = M x 62, where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as

 

M x 01000010 = M x (2⁶ – 2¹) = M x 62

 

In fact, it can be shown that any sequence of 1’s in a binary number can be broken into the difference of two binary numbers:

 

Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 − 1 while multiplying by 99.

 

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,

Booth’s algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth’s algorithm performs fewer additions and subtractions than the normal multiplication algorithm.

 

As a ready reference, use the table below: 

 

Fast multiplication

 

We saw the binary multiplication techniques in the previous section. This section will introduce you to two ways of speeding up the multiplication process. The first method is a further modification to the Booth’s technique that helps reduce the number of summands to n / 2 for n-bit operands. The second techinque reduces the time taken to add the summands.

 

Bit – pair recoding of multiplier

 

This is derived from the Booth’s algorithm. It pairs the multiplier bits and gives one multiplier bit per pair, thus reducing the number of summands by half. This is shown below.

 

 

 

Multiplication requiring only n/2

summands Carry-save addition of summands

 

 

As the figure above shows, one CSA block is used for every bit. This circuit adds 3 8-bit numbers into two numbers.

 

The important point is that c and s can be computed independently and each ci and si can be computed independent of all other ci’s and si’s. An example is given below.

 

 

The multiplication process carried out using CSA is illustrated below.

 

 

Thus, in order to speed up the multiplication process, bit-pair recoding of the multiplier is used to reduce the summands. These summands are then reduced to 2 using a few CSA steps. The final product is generated by an addition operation that uses CLA. All these three techniques help in reducing the time taken for multiplication.

 

Binary division

 

An example of binary division is shown below. We first examine the divisor and the dividend, decide that only if we consider the first three bits of the dividend the divisor will go and then proceed. The first two bits, though not shown, will have to be 0’s. We then get a quotient bit of 1, do the subtraction, get the partial remainder and do the trial subtraction (mentally) and accordingly generate the quotient bit. This process is repeated till we exhaust all the dividend bits. This is illustrated below.

 

 

Now, the same logic has to be adopted for machine implementation too. Only thing is that, it has to be done systematically, and to decide whether the divisor is less than or equal to the dividend, we have to do a trial comparison / subtraction. There are basically two types of division algorithms:

 

• Restoring division
• Non-restoring division

 

Both these are for positive numbers. Negative numbers are handled the same way with the sign bits processed separately.

 

Restoring division

 

Take the first bit of the dividend and do a trial subtraction. If the subtraction produces a negative result, we generate a quotient bit of zero, restore, bring the next bit of dividend and continue. Otherwise, we simply continue with a quotient bit of 1. The algorithm, register organization and example are given below.

 

where N=Numerator, D=Denominator, n=#bits, P=Partial remainder, q(i)=bit #i of quotient

 

Non-restoring division

 

This is a modification of the restoring algorithm. It combines the restore / no restore and shift left steps of two successive cycles and reduces the number of operations. The algorithm is given below.

• Do the first shift and subtraction
• Check sign of the partial remainder
• If it is negative, shift and add
• If it is positive, shift and subtract
• Fix the quotient bit appropriately
• If the final remainder is negative, add the divisor.

An example is discussed below.