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

Area of Science:

• Computer Science
• Number Theory
• Digital Arithmetic

Background:

• Residue arithmetic is crucial for efficient computation.
• Reverse conversion from Residue Number System (RNS) to positional notation is a key non-modular operation.
• Existing methods face challenges in computational efficiency.

Purpose of the Study:

• To present a novel approach for parallel reverse conversion from RNS to Mixed-Radix System (MRS).
• To reduce the computational complexity of RNS to MRS conversion.
• To enhance the efficiency of non-modular operations in residue arithmetic.

Main Methods:

• Developed a parallel reverse conversion algorithm from RNS to MRS.
• Reduced mixed-radix digit calculation to parallel summation of small word-length residues.
• Utilized independent modular channels corresponding to primary RNS moduli.

Main Results:

• Achieved computational complexity of O(k^2)/2 for modular additions and lookup tables, where k is the number of moduli.
• Established a time complexity of O(log2k) modular clock cycles.
• Demonstrated a throughput rate of one reverse conversion per modular clock cycle in pipeline mode.

Conclusions:

• The proposed method offers a significant improvement in parallel reverse conversion efficiency for RNS.
• This novel approach contributes to faster implementation of computational algorithms relying on residue arithmetic.
• The algorithm's parallel nature and reduced complexity make it suitable for high-performance computing applications.