Residue number conversion
C. N. Zhang, Behrooz Shirazi, David Y. Y. Yun · Fall joint computer conference · 1987
This paper describes an algorithm for converting a number in Residue Number System (RNS) to its equivalent in Binary Weighted System using Chinese Remainder Theorem. The Proposed linear algorithm uses binary addition to compute a conversion from a residue representation with n moduli to a binary representation in (n) time steps. However, if the algorithm is to be implemented, we can take advantage of parallelism at the architecture level through a tree structured network of processing elements. Each processing element can perform one step of the algorithm to compute the conversion in (log n) time steps. Furthermore, we show that we can achieve parallelism at the computation level by using carry-save addition instead of binary addition. The advantages of this approach are twofold: (1) it simplifies the detection of overflow in our computations, and (2) it reduces the addition delay to a constant time, making the design highly suitable for very large integers.