Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding
Author:
- 1 July 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (7) , 646-651
Abstract
Two conversion techniques based on the Chinese remainder theorem are developed for use in residue number systems. The new implementations are fast and simple mainly because adders modulo a large and arbitrary integer M are effectively replaced by binary adders and possibly a lookup table of small address space. Although different in form, both techniques share the same principle that an appropriate representation of the summands must be employed in order to evaluate a sum modulo M efficiently. The first technique reduces the sum modulo M in the conversion formula to a sum modulo 2 through the use of fractional representation, which also exposes the sign bit of numbers. Thus, this technique is particularly useful for sign detection and for any operation requiring a comparison with a binary fraction of M. The other technique is preferable for the full conversion from residues to unsigned or 2's complement integers. By expressing the summands in terms of quotients and remainders with respect to a properly chosen divisor, the second technique systematically replaces the sum modulo M by two binary sums, one accumulating the quotients modulo a power of 2 and the other accumulating the remainders the ordinary way. A final recombination step is required but is easily implemented with a small lookup table and binary adders.Keywords
This publication has 13 references indexed in Scilit:
- Residue Arithmetic A Tutorial with ExamplesComputer, 1984
- A technique for the efficient generation of projections for error correcting residue codesIEEE Transactions on Circuits and Systems, 1984
- An improved residue number system digital-to-analog converterIEEE Transactions on Circuits and Systems, 1983
- A Fully Parallel Mixed-Radix Conversion Algorithm for Residue Number ApplicationsIEEE Transactions on Computers, 1983
- Time-Component Complexity of Two Approaches to Multioperand Binary AdditionIEEE Transactions on Computers, 1979
- On decoding techniques for residue number system realizations of digital signal processing hardwareIEEE Transactions on Circuits and Systems, 1978
- Techniques for residue-to-analog conversion for residue-encoded digital filtersIEEE Transactions on Circuits and Systems, 1978
- The use of residue number systems in the design of finite impulse response digital filtersIEEE Transactions on Circuits and Systems, 1977
- Multiple Addition by Residue Threshold Functions and Their Representation by Array LogicIEEE Transactions on Computers, 1973
- Error Correcting Properties of Redundant Residue Number SystemsIEEE Transactions on Computers, 1973