DocumentCode :
1407349
Title :
On the binary quadratic residue system with noncoprime moduli
Author :
Abdallah, Mohammad ; Skavantzos, Alexander
Author_Institution :
Intel Corp., Folsom, CA, USA
Volume :
45
Issue :
8
fYear :
1997
fDate :
8/1/1997 12:00:00 AM
Firstpage :
2085
Lastpage :
2091
Abstract :
The residue number system (RNS) appropriate for implementing fast digital signal processors since it can support parallel, carry-free, high-speed arithmetic. A development in residue arithmetic is the quadratic residue number system (QRNS), which can perform complex multiplications with only two integer multiplications instead of four. An RNS/QRNS is defined by a set of relatively prime integers, called the moduli set, where the choice of this set is one of the most important design considerations for RNS/QRNS systems. In order to maintain simple QRNS arithmetic, moduli sets with numbers of forms 2n+1 (n is even) have been considered. An efficient such set is the three-moduli set (22k-2+1.22k+1.22k+2+1) for odd k. However, if large dynamic ranges are desirable, QRNS systems with more than three relatively prime moduli must be considered. It is shown that if a QRNS set consists of more than four relatively prime moduli of forms 2n+1, the moduli selection process becomes inflexible and the arithmetic gets very unbalanced. The above problem can be solved if nonrelatively prime moduli are used. New multimoduli QRNS systems are presented that are based on nonrelatively prime moduli of forms 2n +1 (n even). The new systems allow flexible moduli selection process, very balanced arithmetic, and are appropriate for large dynamic ranges. For a given dynamic range, these new systems exhibit better speed performance than that of the three-moduli QRNS system
Keywords :
computational complexity; parallel processing; residue number systems; signal processing; QRNS arithmetic; RNS/QRNS; balanced arithmetic; binary quadratic residue system; carry free arithmetic; complex multiplications; fast digital signal processors; high speed arithmetic; integer multiplications; large dynamic ranges; moduli selection process; moduli set; multimoduli QRNS systems; noncoprime moduli; nonrelatively prime moduli; parallel arithmetic; quadratic residue number system; relatively prime integers; residue number system; speed performance; three-moduli set; Cathode ray tubes; Convolution; Digital arithmetic; Digital signal processing; Digital signal processors; Dynamic range; Equations; Hardware; Signal mapping;
fLanguage :
English
Journal_Title :
Signal Processing, IEEE Transactions on
Publisher :
ieee
ISSN :
1053-587X
Type :
jour
DOI :
10.1109/78.611213
Filename :
611213
Link To Document :
بازگشت