Wide word multiplier using booth encoding

Details Wide word multiplier using booth encoding Wide word multiplier using booth encoding

2001-01-02

2004-04-27

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S627000

Reexamination Certificate

active

06728744

ABSTRACT:

The present invention relates to the field of arithmetic processors and more particularly to a method and circuit for multiplying large numbers using a booth encoder with iterative addition.
BACKGROUND OF THE INVENTION
As is well known multiplication of two numbers can be performed by a series of repeated additions, where the number to be added is the multiplicand and the number of times that it is added is the multiplier, the result is the product. Each step in the series of repeated additions generates a partial product. As it may be well appreciated, this process may be extremely slow when performed in a general-purpose processor, taking many clock cycles. In general terms multiplication of an M-bit number by an N-bit number will result in a product which is M+N bits long.
The increased need for high speed processing of large numbers has been precipitated by, for example, various cryptographic applications that use large numbers as encryption keys. These keys are at least 1024-bits long. Accordingly, multiplication using the repeated addition method that is suggested by the arithmetic definition above is often replaced by more efficient algorithms that make use of positional number representation. In general, the execution speed of an arithmetic operation is a function of two factors. One is a circuit technology and the other is the algorithm used.
The multiplication operation may be thought of as having two parts. The first part is dedicated to the generation of partial products and the second one collects and sums the partial products to obtain the final result. The booth algorithm is often used in the generation part because it reduces the number of partial products. The collection of the partial products can then be made using a regular array, a Wallace tree or a binary tree.
For an N-bit multiplier, no more than N/2 partial products are created. However, when the partial products from one multiplier operation are first added, the result is initially in a redundant format, such as carry-sum. That it, the result takes the form of two rows of binary information, a carry row and a sum row. But before this result may be used again, it must first be processed by an adder to put it into binary format. In other words, the carry row and the sum row must be added first. As mentioned earlier a Wallace tree compression unit also known in the art may be used to take the partial products and using rows of carry-save adders compress the partial products into two rows, a sum row and a carry row. A conventional N-bit full adder may then be used to add the sum row and the carry row.
However this full adder is slow since a carry generated in the low order bits may ripple all the way through to the high order bits. Thus the high order must wait for the carry to ripple through all N-bits. This problem is exacerbated when large width operands are used. Alternatively, carry look-ahead and carry select adders may be used to avoid large propagation delays, but are still slow. The complexity of such adder circuits is directly related to the width of the adder. A 32-bit adder is reasonable to implement using most technologies. A 64-bit adder is extremely large, extremely slow or both.
U.S. Pat. No. 5,944,776 describes one possible approach to eliminating the need for a full adder; by using a multiplicity of interconnected logic cells that produces a Booth output that is the Booth encoded form of the sum of a sum row and a carry row. This technique is not easily adaptable to wide width operands. Furthermore the technique described by this patent is more applicable to iterative multiplication algorithms used in a multiplicative divider.
In U.S. Pat. No. 5,724,280 a Booth multiplier using carry look ahead adders performs a multiplication operation in three stages: First the operands are loaded from a data bus, which takes a minimum of 8 clock cycles for a 256 -bit operand and a 32 bit bus; second while loading the second operand, Booth encoding is begun 4-bits at a time and encoded values are accumulated, which takes 64 clock cycles; and third performing a final addition on 32-bit segments while outputting a result to the data bus, which requires 8 further clock cycles when using a 32-bit adder and a 32-bit data bus. Hence, a total number of 80 clock cycles are needed with a 32-bit data bus and a 32-bit adder. This circuit would thus be unacceptably slow when used with wider width operands.
It is possible to implement a high speed wide-width multiplier (256-bit by 256-bit) by using a number of 256-by-256 Booth multipliers which are pipelined to obtain the desired speed. But, such a circuit would be impractically large, particularly for implementation in an ASIC.
Furthermore, wide-width numbers can be processed by segmenting the operands and processing each of the segmented operands in a multiplier. The results from the processed segments are combined to obtain a final result. A problem associated with this technique is that carries generated while processing each segment have to be properly processed in order to obtain the correct final result, thus placing a constraint on the adder circuit, used to combine the results.
It is thus desirable to have a multiplier circuit using Booth encoding that performs wide width number multiplication in relatively few clock cycles and which occupies minimal chip area. Furthermore it is also desirable to have a more efficient adder circuit for processing the final result from the Booth encoder and which manages the carries generated in the Booth multiplier.
SUMMARY OF THE INVENTION
In accordance with this invention there is described a multiplier for computing a final product of a first operand and a second operand comprising:
(a) a multiplier array for forming a product of the first operand and second operand in carry-save form;
(b) a carry-save adder for adding said carry-save partial products and an accumulatd sum to produce a carry and save values;
(c) a carry-lookahead adder for adding said carry and save values to produce a product value and a carry-out value;
(d) a general purpose adder for adding said carry-out and said product value to produce said final product.


REFERENCES:
patent: 4228520 (1980-10-01), Letteney et al.
patent: 5675527 (1997-10-01), Yano
patent: 5724280 (1998-03-01), Davis
patent: 5944776 (1999-08-01), Zhang et al.
patent: 5957999 (1999-09-01), Davis

Affiliated with

Also associated with

Rating

Wide word multiplier using booth encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Wide word multiplier using booth encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wide word multiplier using booth encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3266849