6 December 2002 Application of symmetric redundant residues for fast and reliable arithmetic
Author Affiliations +
Despite difficulties in general division, magnitude comparison, and sign detection, residue number system arithmetic has been used for many special-purpose systems in light of its parallelism and modularity for the most common arithmetic operations of addition/subtraction and multiplication. Computation in RNS requires modular reduction, both for the initial conversion from binary to RNS and after each operation to bring the result back to within a valid residue range. Use of redundant residues simplifies this critical operation, leading to even faster arithmetic. One type of redundant mod-m residue, that keeps the representational redundancy to the minimum of 1 bit per residue, has the nearly symmetric range (-m,m) and allows two values for each pseudoresidue: ⟨xm or ⟨xm - m. We study the extent of simplification and speed-up in the modular reduction process afforded by such redundant residues and discuss its potential implications to the design of RNS arithmetic circuits. In particular, we show that besides cost and performance benefits, introduction of error checking and fault tolerance in arithmetic computations is facilitated when such redundant residues are used.
© (2002) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Behrooz Parhami, Behrooz Parhami, } "Application of symmetric redundant residues for fast and reliable arithmetic", Proc. SPIE 4791, Advanced Signal Processing Algorithms, Architectures, and Implementations XII, (6 December 2002); doi: 10.1117/12.452058; https://doi.org/10.1117/12.452058


RNS bases and conversions
Proceedings of SPIE (October 26 2004)
Compressive computation and Moore’s Law
Proceedings of SPIE (January 30 2003)
Redundant finite rings for fault-tolerant signal processors
Proceedings of SPIE (October 28 1994)
Parity-preserving transformations in computer arithmetic
Proceedings of SPIE (December 06 2002)
Recent advances in algorithm-based fault tolerance
Proceedings of SPIE (October 28 1994)

Back to Top