Browse Prior Art Database

Novel Scheme for "Hot One" Additions in Array Multipliers

IP.com Disclosure Number: IPCOM000114247D
Original Publication Date: 1994-Nov-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 6 page(s) / 200K

Publishing Venue

IBM

Related People

Bhatia, R: AUTHOR [+2]

Abstract

An extremely low cost mechanism for adding the two's complement carry in's (hot ones) required for Booth multiplication.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 44% of the total text.

Novel Scheme for "Hot One" Additions in Array Multipliers

      An extremely low cost mechanism for adding the two's complement
carry in's (hot ones) required for Booth multiplication.

      The simplest multiplication technique involves a shift and
conditional add of the multiplicand.  For every bit ON in the
multiplier, we add the appropriately shifted multiplicand into the
intermediate result.  For each bit more significant in the
multiplier, we shift the multiplicand another bit position left.
This technique suffers two problems:
  1.  One 'shifted multiplicand' (partial product) might be added for
       every bit in the multiplier.  In a 32 bit integer machine,
this
       will either involve massive parallel hardware or a large
number
       of clocks to complete the multiplication.
  2.  This technique cannot handle a 2's complement multiplier.  This
       implies that 2's complement multiplication could involve both
       preprocessing (2's complementing the negative multiplier) and
       postprocessing (2's complementing the final result).

      The modified Booth multiplication algorithm allows logic
designers to solve both of these problems.  Being a two bit step
algorithm, exactly half as many partial products must be added.
Booth
encoding actually assumes 2's complement operands.  Therefore, no
additional processing steps are required.  For unsigned
multiplication,
zero extending the operands transforms them into
positive "two's complement" operands.

      PROBLEM - As can be seen from the Table, we may have to add
negative partial products to the intermediate result.  Adding a '-1 *
M' involves complementing M and adding '1'.  From this point forward,
we will refer to the '1' as a 'hot one' for that partial product.  If
the performance requirements of the machine require only two bits of
the multiplication to be completed in each machine cycle, designing
the multiplier is relatively straight forward.  One such
implementation is shown in Fig. 1.  Adding the hot one for a negative
partial product is accomplished through the carry-in input of the CLA
as shown in Fig. 1.

      In the PowerPC 603 microprocessor, the integer multiplication
step is 8 bits per cycle.  In addition, it is possible to early exit
from the operation if the remaining multiplier bits will not add any
significance to the final product.  For a positive multiplier, this
implies that all remaining bits are zeros and for a negative
multiplier, the remaining bits are all ones.

      Fig. 2 shows the bit position alignment of the four partial
products and their corresponding hot ones, derived from eight
multiplier bits using Radix-4 Booth recoding, relative to the
intermediate result.  As you can see from Fig. 2, the hot ones for
partial products 0 through 2 can easily be hidden in the unused space
of the next most significant partial product.  However, the hot one
for PP3 remai...