Magnitude Comparison and Sign Detection in Residue Number System

Abstract

The Residue Number System (RNS) is a non-positional number system that represent number in the form of residues modulo a set of coprime moduli. This nature of RNS makes it advantageous in achieving carry-free arithmetic. However, due to the non-positional nature of RNS, direct number comparisons to determine the magnitude of RNS numbers is nearly impossible. In this paper, a magnitude comparison scheme is proposed and is theoretically proven and evaluated. The proposed scheme compares the relative magnitude of any two RNS numbers via sign detection. It first computes the modular differences of the residues of the two RNS numbers,  and , and then computes the sum of the results, ,which is then proven to be equal to zero. The final implementation of the technique requires the reverse conversion of . Then sign detection is performed on  and the results determine whether  or . Further analysis proves that the proposed scheme accurately compares the magnitude of any two RNS numbers, whether a signed or unsigned number. The proposed scheme was evaluated and compared with another state-of-the-art scheme based on three key matrices, Area, Delay and Area-Delay product. The proposed scheme outperformed the state-of-the-art scheme in all three-matrix evaluations.