The Mixed-Radix Chinese Remainder Theorem and Its Applications to Residue Comparison

The Chinese remainder theorem (CRT) and the mixed-radix conversion (MRC) are two classic theorems used to convert a residue number to its binary correspondence for a given moduli set {P(n), ... P(2), P(1)}. The MRC is a weighted number system, and it requires operations modulo Pi only, and hence, magnitude comparison is easily performed. However, the calculation of the mixed-radix coefficients in the MRC is a strictly sequential process and involves complex divisions. Thus, the residue-to-binary (R/B) conversions and residue comparisons based on the MRC require a large delay. In contrast, the R/B conversion and residue comparison based on the CRT are fully parallel processes. However, the CRT requires large operations modulo M P(n), ..., P2P1. In this paper, a new mixed-radix CRT is proposed that possesses both the advantages of the CRT and the MRC, which are parallel processing, small operations modulo P(i) only, and the efficiency of making modulo comparison. Based on the proposed CRT, new residue comparators are developed for the three-moduli set {2(n) - 1,2(n), 2(n) + 1}. The FPGA implementation results show that the proposed modulo comparators are about 20 percent faster and smaller than one of the previous best designs.