An Efficient CRT-Base Power-of-Two Scaling in Minimally Redundant Residue Number System.

Area of Science:

• Modular Arithmetic
• Computer Arithmetic

Background:

• Scaling in residue number systems (RNS) is computationally intensive and requires significant hardware.
• Existing methods for RNS scaling are complex, time-consuming, and inefficient.

Purpose of the Study:

• To develop a novel, efficient method for power-of-two scaling in RNS.
• To simplify and accelerate the scaling process in modular arithmetic.

Main Methods:

• Utilizing the Chinese Remainder Theorem (CRT) and the rank form of number representation in RNS.
• Employing minimal redundancy in residue codes to optimize rank calculation and parity determination.
• Implementing power-of-two scaling with optimized iterative steps.

Main Results:

• The proposed method significantly simplifies and speeds up power-of-two scaling compared to existing techniques.
• Each modular scaling iteration by two is achieved in a single modular clock cycle after initial rank calculation.
• Computational complexity is estimated at *k* for modular additions and 2*k*+1 for lookup tables, where *k* is the number of RNS moduli.
• Time complexity is reduced to log2(*k*)+*l* modular clock cycles.

Conclusions:

• The novel CRT-based approach offers a substantial improvement in the efficiency of power-of-two scaling in RNS.
• This method reduces computational complexity and hardware requirements, making RNS more practical for high-speed applications.