Moduli Selection in Robust Chinese Remainder Theorem: Closed-Form Solutions and Layered Design

Abstract

We study the fundamental problem of moduli selection in the Robust Chinese Remainder Theorem (RCRT), where each residue may be perturbed by a bounded error. Consider L moduli of the form m<inf>i</inf> = Γ<inf>i</inf>m (1 ≤ i ≤ L), where Γ<inf>i</inf> are pairwise coprime integers and m ∈ R⁺ is a common scaling factor. For small L (L = 2, 3, 4), we obtain exact solutions that maximise the robustness margin under dynamic-range and modulus-bound constraints. We also introduce a Fibonacci-inspired layered construction (for L = 2) that produces exactly K robust decoding layers, enabling predictable trade-offs between error tolerance and dynamic range. We further analyse how robustness and range evolve across layers and provide a closed-form expression to estimate the success probability under common data and noise models. The results are promising for various applications, such as sub-Nyquist sampling, phase unwrapping, range estimation, modulo analog-to-digital converters (ADCs), and robust residue-number-system (RNS)-based accelerators for deep learning. Our framework thus establishes a general theory of moduli design for RCRT, complementing prior algorithmic work and underscoring the broad relevance of robust moduli design across diverse information-processing domains.