Multi-Stage Robust Chinese Remainder Theorem

Abstract

It is well-known that the traditional Chinese remainder theorem (CRT) is not robust in the sense that a small error in a remainder may cause a large error in the reconstruction solution. A robust CRT was recently proposed for a special case when the greatest common divisor (gcd) of all the moduli is more than 1 and the remaining integers factorized by the gcd of all the moduli are co-prime. In this special case, a closed-form reconstruction from erroneous remainders was proposed and a necessary and sufficient condition on the remainder errors was obtained. It basically says that the reconstruction error is upper bounded by the remainder error level $\tau$ if $\tau$ is smaller than a quarter of the gcd of all the moduli. In this paper, we consider the robust reconstruction problem for a general set of moduli. We first present a necessary and sufficient condition for the remainder errors for a robust reconstruction from erroneous remainders with a general set of muduli and also a corresponding robust reconstruction method. This can be thought of as a single stage robust CRT. We then propose a two-stage robust CRT by grouping the moduli into several groups as follows. First, the single stage robust CRT is applied to each group. Then, with these robust reconstructions from all the groups, the single stage robust CRT is applied again across the groups. This is then easily generalized to multi-stage robust CRT. Interestingly, with this two-stage robust CRT, the robust reconstruction holds even when the remainder error level $\tau$ is above the quarter of the gcd of all the moduli. In this paper, we also propose an algorithm on how to group a set of moduli for a better reconstruction robustness of the two-stage robust CRT in some special cases.

26 pages, 2 figures

Cited by in corpus (11)

• Towards Robustness in Residue Number Systems
• Exact and Robust Reconstructions of Integer Vectors Based on Multidimensional Chinese Remainder Theorem (MD-CRT)
• Basis construction for range estimation by phase unwrapping
• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• Selecting wavelengths for least squares range estimation
• Robustness in Chinese Remainder Theorem
• On Solving Ambiguity Resolution with Robust Chinese Remainder Theorem for Multiple Numbers
• On the Foundation of Sparse Sensing (Part I): Necessary and Sufficient Sampling Theory and Robust Remaindering Problem
• Statistical Robust Chinese Remainder Theorem for Multiple Numbers
• Error Correction in Polynomial Remainder Codes with Non-Pairwise Coprime Moduli and Robust Chinese Remainder Theorem for Polynomials
• Radial Velocity Retrieval for Multichannel SAR Moving Targets with Time-Space Doppler De-ambiguity