Towards Robustness in Residue Number Systems

Abstract

The problem of robustly reconstructing a large number from its erroneous remainders with respect to several moduli, namely the robust remaindering problem, may occur in many applications including phase unwrapping, frequency detection from several undersampled waveforms, wireless sensor networks, etc. Assuming that the dynamic range of the large number is the maximal possible one, i.e., the least common multiple (lcm) of all the moduli, a method called robust Chinese remainder theorem (CRT) for solving the robust remaindering problem has been recently proposed. In this paper, by relaxing the assumption that the dynamic range is fixed to be the lcm of all the moduli, a trade-off between the dynamic range and the robustness bound for two-modular systems is studied. It basically says that a decrease in the dynamic range may lead to an increase of the robustness bound. We first obtain a general condition on the remainder errors and derive the exact dynamic range with a closed-form formula for the robustness to hold. We then propose simple closed-form reconstruction algorithms. Furthermore, the newly obtained two-modular results are applied to the robust reconstruction for multi-modular systems and generalized to real numbers. Finally, some simulations are carried out to verify our proposed theoretical results.

32 pages, 5 figures

References in corpus (4)

• Multi-Stage Robust Chinese Remainder Theorem
• Basis construction for range estimation by phase unwrapping
• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• A binary Hopfield network with $1/\log (n)$ information rate and applications to grid cell decoding

Cited by in corpus (7)

• Exact and Robust Reconstructions of Integer Vectors Based on Multidimensional Chinese Remainder Theorem (MD-CRT)
• Robustness in Chinese Remainder Theorem
• Robust Polynomial Reconstruction via Chinese Remainder Theorem in the Presence of Small Degree Residue Errors
• Statistical Robust Chinese Remainder Theorem for Multiple Numbers
• On Solving Ambiguity Resolution with Robust Chinese Remainder Theorem for Multiple Numbers
• On the Foundation of Sparse Sensing (Part II): Diophantine Sampling and Array Configuration
• On the Foundation of Sparse Sensing (Part I): Necessary and Sufficient Sampling Theory and Robust Remaindering Problem