The field of the present invention is the field of Leading Zero Anticipators (LZA) that predict the number of leading zeros or leading ones in a sum of mantissas generated by an adding device used to add two floating point numbers.
Leading Zero Anticipators (“LZAs”) are typically used to predict the number of leading zeros in a sum of mantissas during floating point addition. Prediction of the number of leading zeroes is used to normalize the result of the addition and is performed at the same time as (in parallel with) mantissa addition, which increases the speed of the normalization process that is performed after mantissa addition has been completed.
In a traditional LZA design shown in FIG. 1, mantissaA and mantissaB (labeled as 10) both enter the adder 13 and the LZA 12 simultaneously. A normalization shift is performed by the shifter 15 after addition is performed. LZAs 12 are commonly used in devices performing fast addition that try to reduce the number and length of clock cycles required to do the addition and in devices that implement a single instruction which performs multiplication followed by addition. The use of redundant formats such as the carry-save format during addition does not require the use of the LZA during the addition. But the use of redundant formats does require placement of an LZA in parallel with a second adder which adds the sum and carry bit streams generated by the carry-save addition process. The sum and carry bit streams are added before the final normalization stage is completed. In such circuits, the carry and sum become the input operands (mantissaA and mantissaB) that are transmitted to the adder in FIG. 1. The nature of addition in redundant formats invalidates the use of several LZAs in the final add operation. For instance, in the carry-save format, the carry term is shifted left by 1 bit position (equivalent to multiplying the carry value by 2) before addition is performed. If there is a negative carry term and a positive sum term, the left shift that is performed after carry save addition might shift out the leading one of the carry term, making it a positive number (the leading bit indicates sign). The addition of two seemingly positive numbers (sum and carry) may then produce a valid negative number. This seemingly contradictory result is valid in carry-save addition but invalidates the assumptions made in the designs of many LZAs. For example, consider a carry (value −6) and a sum (value 7) with expected final result −6×2+7=−5. The corresponding 4 bit binary vectors in 2's complement are carry 1010 and sum 0111. When the carry is shifted left 1 bit, it becomes 0100. Adding 0100 (which is now seemingly a positive number) to 0111 (also a positive number) gives 1011 which is a negative number (−5) and is the correct expected final result.
Another drawback of conventional LZAs occurs if the operation is a subtraction. Traditional application of LZAs during subtraction requires that the mantissa of the smaller operand must be subtracted from the mantissa of the larger operand so that a positive result is generated. To insure that the operand of smaller magnitude is subtracted from the greater one, a comparator is used to determine which mantissa is larger. This is expensive because of the need to use extra logic gates. Another traditional method of leading zero anticipation does not require comparison but uses 2 LZAs together which are implemented so that they make opposite assumptions about the sign of the generated result when anticipating the number of leading zeroes or ones. The correct LZA output is then chosen depending on the sign of the result of the addition. This is also expensive.
Yet another conventional implementation of LZAs does not require comparison of mantissas and uses just one LZA. However logic designers implementing this form of LZA must assume that the “normal” rules of addition apply when the operands are added. Consequently, this implementation cannot be used when the input operands are expressed in redundant formats, such as the carry save format. This is the case because addition in redundant format does not follow all the conventions of normal addition as explained above.
Therefore, what is required is a novel LZA that may be implemented with a single LZA and that is implemented in a way that does not make assumptions regarding rules of addition that preclude the use of redundant formats such as the carry save format. Also, an LZA that does not require comparison of the magnitude of the input operands or knowledge of the sign of the result in order to anticipate the number of leading zeroes or leading ones is needed.