A systematic approach for selecting practical moduli sets for residue number systems

Abstract

The residue number system (RNS) is a useful tool for digital signal processing (DSP) since it can support parallel, carry free, high speed arithmetic. An RNS is defined by a set of relatively prime integers called the moduli set. The most important consideration when designing RNS systems is the choice of the moduli set. In order to maintain simple arithmetic, several example cases of moduli sets containing numbers of the forms 2(/sup k/1)+1, 2(/sup k/2)-1 and 2(/sup k/3) have been considered and studied by RNS researchers in the past. However, there is a lack of a comprehensive theory of properties of numbers of the forms 2(/sup k/1)+1 and 2(/sup k/2)-1 and of how these numbers can be used as moduli choices for RNS systems. A detailed and comprehensive theoretical study of properties of numbers of the forms 2(/sup k/1)+1 and 2(/sup k/2)-1 is presented. This study will enable RNS researchers and engineers to make the very best moduli selections for RNS systems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>