Digit Set Conversion from Redundant Number System into Complement Representation

Abstract

Redundant number system was proposed in order to solve the carry-propagation problem. Although it provides a carry-free parallel addition, this representation requires a lot of space to store itself. Many conversions from the redundant number system into another number representation have been introduced to decrease the storage usage. This paper proposes a generic algorithm in order to convert the redundant number representation into the complement number representation. The proposed algorithm can perform the conversion of a number in any integer radix and eliminates the carry chain of the traditional method. The proofs of the proposed algorithm in term of correctness are also included in this paper.