Leading Guard Digits in Finite-Precision Redundant Representations

Abstract : Redundant number representations are generally used to allow constant time additions, based on the fact that only bounded carry-ripples take place. But, carries may ripple out into positions which may not be needed to represent the final value of the result and, thus, a certain amount of leading guard digits are needed to correctly determine the result. Also, when cancellation during subtractions occurs, there may be nonzero digits in positions not needed to represent the result of the calculation. It is shown here that, for normal redundant digit sets with radix greater than two, a single guard digit is sufficient to determine the value of such an arbitrary length prefix of leading nonzero digits. This is also the case for the unsigned carry-save representation, whereas two guard digits are sufficient, and may be necessary, for additions in the binary signed-digit and 2's complement carry-save representations. Thus, only the guard digits need to be retained during sequences of additions and subtractions. At suitable points, the guard digits may then be converted into a single digit, representing the complete prefix.
Type de document :
Article dans une revue
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2006, 55 (5), pp.541-548. 〈10.1109/TC.2006.79〉
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00000001
Contributeur : Jean-Michel Muller <>
Soumis le : lundi 27 mars 2006 - 16:35:53
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : samedi 3 avril 2010 - 22:06:45

Fichier

Identifiants

Collections

Citation

Jean-Michel Muller, Peter Kornerup. Leading Guard Digits in Finite-Precision Redundant Representations. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2006, 55 (5), pp.541-548. 〈10.1109/TC.2006.79〉. 〈ensl-00000001〉

Partager

Métriques

Consultations de la notice

192

Téléchargements de fichiers

127