An Efficient Parallel Reverse Conversion of Residue Code to Mixed-Radix Representation Based on the Chinese Remainder Theorem - Mikhail Selianinau; Yuriy Povstenko (Entropy, 2022)
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 <semantics>O<mfenced separators="" open="(" close=")">k2/2</mfenced></semantics>, where k equals the number of used moduli. The time complexity is <semantics>O<mfenced separators="" open="(" close=")"><mfenced separators="" open="⌈" close="⌉">log2k</mfenced></mfenced></semantics> modular clock cycles. In pipeline mode, the throughput rate of the proposed algorithm is one reverse conversion in one modular clock cycle.