New algorithms for hardware-efficient implementation of sign detection and magnitude comparison in residue number systems

Residue Number System (RNS), being a non-positional number system, is emerging as a promising data representation to substitute the accustomed two’s complement number system for low-power and high-speed digital signal processing. Due to its carry free property at sub-word level, arithmetic operations such as addition, subtraction and multiplication can be performed at higher speed than any weighted number system. Nonetheless, the arithmetic operations such as sign detection, signed integer magnitude comparison are found to be more difficult to implement in RNS. This thesis aims to develop new algorithms for hardware-efficient implementation of these difficult operations in RNS. Specifically, the following new findings and results are reported in this thesis. First and foremost, a new fast and area-efficient adder-based sign detector for RNS {2n−1, 2n, 2n+1} has been proposed. The circuit is greatly simplified by shrinking the dynamic range to eliminate large modulo operations with the help of the new Chinese remainder theorem (CRT)-I. Synthesis results based on 65nm CMOS standard cell library show that the proposed design outperforms all existing adder-based sign detectors reported for this moduli set in area and speed for n ranges from 5 to 25 in step of 5. Following which, a radically different quantization approach for comparing signed integers in the four-moduli supersets, S1 ≡ {2n+k, 2n−1, 2n+1, 2n+1−1} and S2 ≡ {2n+k, 2n−1, 2n+1, 2n−1−1}, is proposed. The dynamic range of the target moduli set is quantized into equal divisions, and the ranks of the divisions resided by the residue representations of the integers in comparison are identified and compared. This approach allows the sign of a residue representation to be directly extracted from the most significant bit of its rank, or with some simple additional logic function if it resides in the middle rank. Comparing with the best existing signed magnitude comparator applicable to these two moduli sets, the synthesis results based on 65 nm CMOS technology show that the proposed design is at least 22.48% smaller, 19.08% faster and 27.66% more energy-efficient for S1 and 18.75% smaller, 16.41% faster and 23.30% more energy-efficient for S2. Last but not least, a scaling-assisted sign integer comparator for the balanced five-moduli set {2n−1, 2n, 2n+1, 2n+1−1, 2n−1−1} has been proposed. The signs of the operands in comparison, as well as their difference are detected after scaling them 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 to reduce 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 inferred with a small fraction of logic gates. 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 CRT-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.Doctor of Philosophy (EEE