Moduli Selection in Robust Chinese Remainder Theorem: Closed-Form Solutions and Layered Design
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908679820804096 |
|---|---|
| author | Yan, Wenyi Gan, Lu Liu, Hongqing Hu, Shaoqing |
| author_facet | Yan, Wenyi Gan, Lu Liu, Hongqing Hu, Shaoqing |
| contents | We study the fundamental problem of \emph{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_i = Γ_i m$ ($1 \le i \le L$), where $Γ_i$ are pairwise coprime integers and $m \in \mathbb{R}^+$ is a common scaling factor. For small $L$ ($L = 2, 3, 4$), we obtain exact solutions that maximize the robustness margin under dynamic-range and modulus-bound constraints. We also introduce a Fibonacci-inspired \emph{layered} construction (for $L = 2$) that produces exactly $K$ robust decoding layers, enabling predictable trade-offs between error tolerance and dynamic range. We further analyze 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22757 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Moduli Selection in Robust Chinese Remainder Theorem: Closed-Form Solutions and Layered Design Yan, Wenyi Gan, Lu Liu, Hongqing Hu, Shaoqing Signal Processing We study the fundamental problem of \emph{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_i = Γ_i m$ ($1 \le i \le L$), where $Γ_i$ are pairwise coprime integers and $m \in \mathbb{R}^+$ is a common scaling factor. For small $L$ ($L = 2, 3, 4$), we obtain exact solutions that maximize the robustness margin under dynamic-range and modulus-bound constraints. We also introduce a Fibonacci-inspired \emph{layered} construction (for $L = 2$) that produces exactly $K$ robust decoding layers, enabling predictable trade-offs between error tolerance and dynamic range. We further analyze 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. |
| title | Moduli Selection in Robust Chinese Remainder Theorem: Closed-Form Solutions and Layered Design |
| topic | Signal Processing |
| url | https://arxiv.org/abs/2511.22757 |