The Residue Number System (RNS) has attracted many researchers as basis for the computational hardware in the last 60 years with an increasing interest in the last decade, in particular for applications like Digital Signal Processing (DSP) and Fast Fourier Transform (FFT). This system has a very big advantage in the modular arithmetic operations like addition, subtraction and multiplication since this system provides the ability to add, subtract or multiply without the need to wait for the carry propagation as required by the weighted number systems. The non modular operation such as sign detection, division, conversion to weighted number system, and overflow detection presented a challenge to researchers. A lot of research has been done to address these issues.
In this dissertation, we present an efficient and simplified algorithm for the RNS conversion to weighted number system. The algorithm is based on the Mixed Radix conversion (MRC). The new algorithm simplifies the hardware implementation and improves the speed of conversion by replacing a number of multiplication operations with small look-up tables. The algorithm requires less ROM size compared to those required by existing algorithms. Also, we present a generic sign detection algorithm based on Mixed Radix Conversion algorithm MRC-II and an optimum algorithm for sign detection based on a special moduli set. Finally, we present two new algorithms. One for RNS Scaling and the other is for RNS division. The new scaling algorithm is based on Mixed Radix Conversion MRC-II. The algorithm utilizes a simplified base extension process that works on smaller moduli set utilizing look-up tables. The algorithm works with a single moduli or a product of moduli as divisors or scaling factors. The new division algorithm presented in this paper addresses the long standing problem of RNS division by breaking the process into division remainder zero and a small correction process.
