A High-Speed Realization of Chinese Remainder Theorem
Shuangching Chen, Shugang Wei · 2007
This paper proposes a novel technique for the Chinese remainder theorem (CRT) with the moduli (2 n i 1,2 n ,2 n +1). Hardware implementation of the proposed CRT algorithm utilizes two kinds of parallel adders. One is referred to as modulo signed-digit m adder (MSDA) which performs a fast propagation-free addition and allows for the annihilation of carry or borrow chains using redundant binary number representation. Another implements parallel prefix adder which is the evolution of carry-lookahead adder (CLA). Compared to 16-digit Piestrak's high- speed converter , the computation time is shorten by 34%.