Overflow Detection in Residue Number System, Moduli Set {2n-1,2n,2n+1}

Abstract

Residue Number System (RNS) is a non-weighted number system for integer number arithmetic, which is based on the residues of a number to a certain set of numbers called module set. The main characteristics and advantage of residue number system is reducing carry propagation in calculations. The elimination of carry propagation leads to the possibility of maximizing parallel processing and reducing the delay. Residue number system is mostly fitted for calculations involving addition and multiplication. But some calculations and operations such as division, comparison between numbers, sign determination and overflow detection is complicated. In this paper a method for overflow detection is proposed for the special moduli set {2n-1,2n,2n+1} . This moduli set is favorable because of the ease of calculations in forward and reverse conversions. The proposed method is based on grouping the dynamic range into groups by using the New Chinese Theorem and exploiting the properties of residue differences. Each operand of addition is mapped into a group, then the sum of these groups is compared with the indicator and the overflow is detected. The proposed method can detect overflow with less delay comparing to previous methods.

Keywords

• Computer Arithmetic
• Overflow Detection
• Residue Number System