US 5,957,999 A · Booth multiplier with squaring operation accelerator

Abstract

A multiplier which uses Booth recoding to multiply large word length operands. A first operand is fully loaded into a shift register. The loading of the second operand is then begun, with the recoding operation beginning after the loading of the minimum number of bits of the second operand required for the first stage of the recoding. The recoded portions of the second operand are used to select what factor of the first operand to use in forming the partial product terms. The partial product terms are added using carry save addition, with the least significant bits being used to form the least significant bits of the final product. The most significant bits of the final product are then formed by adding the carry save data from the partial product summations. The present invention performs squaring operations used in exponentiation functions by shifting the first operand value (A) by one bit to form twice that value (2*A) prior to multiplying by the second operand (B) to form the 2*(A*B) term needed in such calculations. This shifting is performed in the multiplexer used to select the appropriate factor of the first operand for each partial product term, rather than after the accumulation of the final product term.

Claims4

Dependent claims

A method of computing the square of the sum of a first operand and a second operand utilizing an integrated circuit, the method comprising:

loading the first operand into a first operand data storage means formed as part of the integrated circuit;
loading the second operand into a second operand data storage means formed as part of the integrated circuit;
recoding the second operand utilizing recoding circuitry formed as part of the integrated circuit, thereby determining the factors of the first operand to use in forming Booth partial products of the first and second operands;
forming the factor 2*A utilizing factoring circuitry formed as part of the integrated circuit, where A is the first operand, for use in computing the square of the sum of the first and second operands;
forming the Booth partial products of the factor 2*A and the second operand utilizing partial products circuitry formed as part of the integrated circuit, including partial products of 2*A*B, where B is the second operand, for use in computing the square of the sum of the first and second operands;
accumulating the Booth partial products utilizing accumulator circuitry formed as part of the integrated circuit;
and
forming the square of the sum of the first and second operands from the accumulated Booth partial products by performing add and shift operations utilizing add/shift circuitry formed as part of the integrated claims.

5 more elements

Dependencies are inferred from the claim text.

Booth multiplier with squaring operation accelerator

Life of this patent

Booth multiplier with squaring operation accelerator

Life of this patent

Abstract

Claims4