Quadratic Residue Number Systems

Complex signal processing can be handled by RNS in a manner similar to standard complex number operations such as addition, subtraction, multiplication etc. However, under certain special cases of choice of moduli, the complete decoupling of computation of real and imaginary parts of the result is feasible. Nussbaumer [Nuss76] suggested that Fermat primes of the type 4k+l have this property. Later, this advantage has been extended to any primes of the type (4k+l) using the Quadratic Residue Number System (QRNS) [Jull87, Jenk87, Kris86a]. The QRNS also has been shown to be applicable for composite numbers which have (4k+l) as a factor and also to the case of composite numbers having (22n+l) as a prime factor. The primary disadvantage of the QRNS is the restriction on the type of moduli. Another technique which allows any modulus but with increase in number of multiplications has also been found known as Modified Quadratic Residue Number System (MQRNS) [Sode84b]. This will also be discussed in detail in this Chapter.