A Scaling-Assisted Signed Integer Comparator for the Balanced Five-Moduli Set RNS $\{2^{n}-1, 2^{n}, 2^{n}+ 1, 2^{n+1}- 1, 2^{n-1}- 1\}$
Sachin Kumar, Chip-Hong Chang · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · 2017
Signed integer comparison occurs prevalently in process control, sorting, address decoding, and conditional branching. Existing algorithms for magnitude comparison in RNS are based either on parity check or partial reverse conversion. With separately designed RNS sign detectors, they can also be used to compare residue representations of signed integers. In this paper, a radically different approach to this problem is proposed for the five-moduli set {2n- 1, 2n, 2n+1, 2n+1- 1, 2n-1- 1}. The signs of the operands in comparison, as well as their difference are detected after scaling by a factor of (22n-1)(2n-1-1). The resulting finite series in the composite modulus channel is further factored into parallel carry-saved additions in the existing mod 2n and mod 2n+1- 1 modulus channels, thus reducing the sizes of modulo adders from 5n bits to n and n+1 bits. Upon detecting the signs of the operands and their difference, the relation is inference with a small fraction of logic gates. Our synthesis results in 65-nm CMOS technology show that the proposed design is 36.9% smaller, 7.6% faster, and 45.5% more energy efficient than the best Chinese remainder theorem-II-based magnitude comparator and at least 12.9% smaller, 7.3% faster, and 20.8% more energy efficient than the best reverse-conversion-based implementation of signed integer comparator for the same five-moduli set.