Robustness in Chinese Remainder Theorem for Multiple Numbers and Remainder Coding
Hanshen Xiao, Yufeng Huang, Yu Ye, Guoqiang Xiao · IEEE Transactions on Signal Processing · 2018
Chinese remainder theorem (CRT) has been widely studied with its applications in frequency estimation, phase unwrapping, coding theory, and distributed data storage. Since traditional CRT is greatly sensitive to the errors in residues due to noises, the problem of robustly reconstructing integers via the erroneous residues has been intensively studied in the literature. In order to robustly reconstruct integers, there are basically two approaches: one is to introduce common divisors in the moduli and the other is to directly decrease the dynamic range. In this paper, we take further insight into the geometry property of the linear space associated with CRT. Echoing both ways to introduce redundancy, we propose a pseudometric as a uniform framework to analyze the tradeoff between the error bound and the dynamic range for robust CRT. Furthermore, we present the first robust CRT for multiple numbers to solve the problem raised by CRT-based undersampling frequency estimation in general. Based on symmetric polynomials proposed, we proved that in most cases, the problem can be solved efficiently in the polynomial time.