A new algorithm for RNS decoding
Yuke Wang, Mostafa Abd‐El‐Barr · IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications · 1996
In this brief, a divide-and-conquer based RNS (residue number system) decoding algorithm is proposed. The basic idea of this algorithm is to decompose a set of moduli into groups each of size two moduli and to decode a given number in a two moduli representation. The time complexity of the algorithm used is O(log n), where n is the size of the moduli set. There is no assumption made on the elements of the module set. In addition, the algorithm requires less ROM size and smaller size module adders compared to those required by existing approaches.