An Efficient Parallel Reverse Conversion of Residue Code to Mixed-Radix Representation Based on the Chinese Remainder Theorem

In this paper, we deal with the critical problems in residue arithmetic. The reverse conversion from a Residue Number System (RNS) to positional notation is a main non-modular operation, and it constitutes a basis of other non-modular procedures used to implement various computational algorithms. We present a novel approach to the parallel reverse conversion from the residue code into a weighted number representation in the Mixed-Radix System (MRS). In our proposed method, the calculation of mixed-radix digits reduces to a parallel summation of the small word-length residues in the independent modular channels corresponding to the primary RNS moduli. The computational complexity of the developed method concerning both required modular addition operations and one-input lookup tables is estimated as O (k(2)/2), where k equals the number of used moduli. The time complexity is O(inverted right perpendicularlog(2)kinverted left perpendicular) modular clock cycles. In pipeline mode, the throughput rate of the proposed algorithm is one reverse conversion in one modular clock cycle.

Automated summary

This paper focuses on critical problems in residue arithmetic and proposes a novel approach for parallel reverse conversion. By parallel summation of small word-length residues in independent modular channels, the calculation complexity of mixed-radix digits is reduced, improving computational efficiency.