An efficient reverse converter for the 4-moduli set {2^n -1, 2^n, 2^n + 1, 2^2n + 1} based on the new Chinese remainder theorem

Abstract

The inherent properties of carry-free operations, parallelism and fault-tolerance have made the residue number system a promising candidate for high-speed arithmetic and specialized high-precision digital signal-processing applications. However, the reverse conversion from the residues to the weighted binary number has long been the performance bottleneck, particularly when the number of moduli set increases beyond 3. In

this paper, we present an elegant residue-to-binary conversion algorithm for a new 4-moduli set 2^n- 1, 2^n, 2^n +1, 2^2n +1. The new Chinese remainder theorem introduced recently has

been employed to exploit the special properties of the proposed moduli set where modulo corrections are done without resorting to the costly and time consuming modulo operations. The resulting architecture is notably simple and can be realized in hardware with only bit reorientation and one multioperand modular adder. The new reverse converter has superior area-time complexity in comparison with the reverse converters for several other 4-moduli sets.