A High-Speed Realization of Chinese Remainder Theorem

摘要

This paper proposes a novel technique for the Chinese remainder theorem (CRT) with the moduli (2{sup}n-1, 2{sup}n, 2{sup}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%.