US 5,633,819 AGranted

Inexact leading-one/leading-zero prediction integrated with a floating-point adder

AssigneeExponential Technology, Inc.

InventorsCheryl S. Brashears, James S. Blomgren, Earl T. Cohen

Life of this patent

Estimating the term…

Loading patent…

Abstract

The sum from a floating point adder is normalized by an initial shift based on a prediction for the position of the leading one or zero in the sum. This leading-one/zero prediction is based not on the operands input to the adder, nor the result from the adder, but on the intermediate generate and propagate signals within the adder. The adder has a first stage that reduces each bit-position to a generate and a propagate signal. The adder's second stage propagates the carries in the adder using these generate and propagate signals to generate the sum. Thus the adder's first-stage logic is also used for the leading one/zero prediction, reducing cost and complexity. An ECL half-adder cell is preferably used for the adder's first stage. A zero output is added to the ECL half-adder cell at minimal cost. The shift for the leading one/zero prediction is accomplished in two stages, with a selective complement of negative sums between the two-stage shift. This allows more time for a more exact prediction after the first coarse shift. The final exact detection of the leading one is pipelined to detect the sum after the complementor but before the second stage of the shifter. This allows the final exact detection of the leading one to occur in parallel with the second stage of the shifter, reducing the delay for generating the final normalized sum by a final shifter.

Claims19

Dependent claims

A floating point adder for generating a normalized sum of a plurality of input operands, the floating point adder comprising:

a plurality of half-adder cells, each half-adder cell in the plurality of half-adder cells receiving a bit-position of each operand in the plurality of operands, each half-adder cell outputting a generate signal when at least two of the plurality of operands have a binary one for the bit-position, each half-adder cell outputting a propagate signal when at least one of the plurality of operands have a binary one for the bit-position;
carry-propagate means, receiving the generate and propagate signals from the plurality of half-adder cells, for outputting a sum of the plurality of operands, the carry-propagate means including means for propagating a carry input from adjacent lower-significance bit-positions to adjacent higher-significance bit-positions when the propagate signal is active, but not propagating the carry input when none of the generate and propagate signals input to the carry-propagate means is active;
a leading significant-bit predictor, receiving the generate and propagate signals from the plurality of half-adder cells, for generating a first prediction signal indicating a predicted position of the most-significant bit in the sum;
a first shifter, receiving the sum from the carry-propagate means, for shifting the sum and outputting a shifted sum in response to the first prediction signal so that the most-significant bit in the sum is shifted to a more significant bit-position in the shifted sum;
a leading significant-bit detector, receiving the shifted sum, for determining the bit-position of a leading significant bit and outputting a final shift amount signal;
and
final shift means, responsive the final shift amount signal, for shifting the shifted sum such that the leading significant bit is shifted to a most significant bit-position in the normalized sum,
whereby the leading significant-bit predictor predicts the bit-position of the leading significant bit from the generate and propagate signals.

5 more elements

A floating point unit for generating a normalized sum of a plurality of input operands, the floating point unit comprising:

a plurality of half-adder cells, each half-adder cell in the plurality of half-adder cells receiving a bit-position of each operand in the plurality of operands, each half-adder cell outputting a generate signal when at least two of the plurality of operands have a binary one for the bit-position, each half-adder cell outputting a propagate signal when an odd number of the plurality of operands have a binary one for the bit-position;
group-propagate cells, receiving the generate and propagate signals from the plurality of half-adder cells, for outputting group propagate and group generate signals;
propagate means for propagating the group propagate and the group generate signals from the group-propagate cells, the propagate means outputting a sum of the plurality of operands;
a leading significant-bit predictor, receiving the generate and propagate signals from the plurality of half-adder cells, for generating a first prediction signal indicating the predicted position of a leading group of bit-positions containing the most-significant bit in the sum, the leading significant-bit predictor also outputting a second prediction signal indicating a relative position within the leading group of the most-significant bit in the sum;
a first shifter, receiving the sum from the propagate means, for shifting the sum and outputting a shifted sum in response to the first prediction signal so that the most-significant bit in the sum is shifted to a more significant bit-position in the shifted sum;
a complementor, receiving the shifted sum, for selectively complementing the shifted sum when the shifted sum represents a negative number, the complementor outputting a selectively complemented sum;
a second shifter, receiving the selectively complemented sum from the complementor, for shifting the selectively complemented sum and outputting a twice shifted sum in response to the second prediction signal so that the most-significant bit in the selectively complemented sum is shifted to a more significant bit-position in the twice shifted sum;
a leading significant-bit detector, receiving the selectively complemented sum and the second prediction signal, for determining the bit-position of a leading significant bit in the twice shifted sum and outputting a final shift amount signal;
and
final shift means, responsive the final shift amount signal, for shifting the twice shifted sum such that the leading significant bit is shifted to the most significant bit-position in the normalized sum,
whereby the leading significant-bit predictor predicts the bit-position of the leading significant bit from the generate and propagate signals.

8 more elements

A computer-implemented method for normalizing a sum from an adder, the method comprising the computer-implemented steps of:

applying electrical signals representing the value of a first operand and the value of a second operand to inputs to the adder;
generating propagate and generate signals for a plurality of bit-positions in the adder, a generate signal for a bit-position being activated when an electrical signals representing the first operand and the second operand are both activated for the bit-position, a propagate signal for the bit-position being activated when exactly one but not both of the electrical signals representing the first operand and the second operand are activated for the bit-position;
applying the propagate and generate signals to a leading-significant-bit predictor;
generating a predicted shift amount based on the propagate and generate signals applied to the leading-significant-bit predictor, the predicted shift amount being approximately a number of leading bit-positions not having a significant bit;
outputting a sum from the adder by propagating carries between bit-positions, a carry being generated by the generate signals, the carry being propagated by the propagate signal, the carry not propagated to another bit-position when the bit position has neither the propagate nor the generate signal activated;
shifting the sum from the adder by a number of bit-positions equal to the predicted shift amount and outputting a shifted sum;
detecting a leading significant bit-position in the shifted sum and outputting a final shift amount;
and
shifting the shifted sum by the final shift amount to produce a final sum having a leading significant bit in a most-significant bit-position in the final sum,
whereby the sum is first shifted by the predicted shift amount that is generated from the propagate and generate signals from the adder.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/547,396Filed 24 Oct 1995
Granted: 27 May 1997
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 7/74
Methods or arrangements for processing data by operating upon the order or content of the data handled: selecting or encoding within a word the…
G06F 5/012
For shifting, e.g. justifying, scaling, normalising: in floating-point computations
G06F 7/485
Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or…:…
G06F 7/503
Half or full adders, i.e. basic adder cells for one denomination: using carry switching, i.e. the incoming carry being connected directly, or only…