An Efficient CRT Based Algorithm for Frequency Determination from Undersampled Real Waveform

Abstract

The Chinese Remainder Theorem (CRT) based frequency estimation has been widely studied during the past two decades. It enables one to estimate frequencies by sub-Nyquist sampling rates, which reduces the cost of hardware in a sensor network. Several studies have been done on the complex waveform; however, few works studied its applications in the real waveform case. Different from the complex waveform, existing CRT methods cannot be straightforwardly applied to handle a real waveform’s spectrum due to the spurious peaks. To tackle the ambiguity problem, in this paper, we propose the first polynomial-time closed-form Robust CRT (RCRT) for the single-tone real waveform, which can be considered as a special case of RCRT for arbitrary two numbers. The time complexity of the proposed algorithm is $O\left(L\right)$, where L is the number of samplers. Furthermore, our algorithm also matches the optimal error-tolerance bound.

1. Introduction

Chinese Remainder Theorem (CRT) is a fundamental number theory result, which shows the reconstruction of a single integer X from its residues modulo multiple co-prime moduli. It has been extensively used in various applications, such as wireless sensor networks [1,2], coding theory [3,4,5,6,7], phase unwrapping [8,9], and frequency estimation from undersampled waveforms [10,11,12,13,14,15,16,17]. In particular, the CRT-based method enables one to estimate frequencies with exponentially smaller sub-Nyquist rates in a distributed setup. This could significantly reduce hardware cost [18,19]. In practice, errors may occur in the spectrum measurement, while CRT is known highly sensitive to residue perturbation [20]. Moreover, in some applications of multiple parameter estimation, we may need to recover multiple real numbers simultaneously. To this end, many works have been proposed during the last two decades to solve the two issues, which can be summarized as follows.

• (i). Robustness: On the one hand, to make CRT robust against small errors in residues, Wang et al. introduced a common factor $\Gamma$ as redundancy to the co-prime moduli $\{M_1,M_2,$$\cdots ,M_L\}$ in a form $\{m_l=M_l\Gamma |l=1,2,\cdots ,L\}$. This forms the foundation of the first closed-form Robust CRT (RCRT) for a single real number [20]. RCRT can recover the folding number $\lfloor X/\Gamma \rfloor$ once the error in each residue is upper bounded by $\Gamma /4$. Hence, one can ensure the reconstruction error is upper bounded by $\Gamma /4$. The $\Gamma /4$ error tolerance bound is also proved to be tight in the follow-up works [21].

• (ii). Residue Ambiguity: On the other hand, since the observed residues are unordered, there is no clear correspondence between N numbers $\left\{X_i\right|i=1,2,\cdots N\}$ and residues in each residue set $R_l=\left\{r_{i,l}\right|i=1,2,\cdots ,N\}$, $l=1,2,\cdots ,L$. Here, $r_{i,l}$ denotes the residue of $X_i$ modulo $m_l$. Thus, the residue ambiguity makes reconstruction much more complicated for multiple numbers. When $N=2$, Xiao et al. proposed a robust generalized CRT, addressing the residue ambiguity by carefully-designed quadratic symmetric polynomials [22]. It is shown that the correspondence between these two numbers and residues can be uniquely determined while the error bound is sacrificed to $\Gamma /8$ [23]. As shown in recent works [24,25]; theoretically, one can approach the optimal error bound $\Gamma /4$ independent of N when the least common multiple of moduli is sufficiently large. However, to the best of our knowledge, no existing polynomial-time algorithm matches the optimal bound.

In this paper, we focus on CRT based algorithm for frequency determination from the undersampled real waveform. The proposed method can be applied in a sensor network with low power and low transmission rates sensors [26,27] or Synthetic Aperture Radar (SAR) imaging of moving targets [28]. However, in the real waveform scenario, the CRT-based method encounters both the above-mentioned challenges, robustness, and residue ambiguity, simultaneously.

Notably, the real waveform sampling needs less hardware, i.e., only one Analog-to-Digital Converter (ADC) per sampling frequency is required in real waveform sampling rather than two ADCs in complex waveform [29]. However, existing CRT methods for the complex waveform cannot be applied to the real waveform directly due to the existence of the spurious peak [24]. In this paper, we set out to solve these mentioned issues. Our main contributions can be concluded as follows.

• We present the first polynomial-time closed-form RCRT for frequency determination from undersampled single-tone real waveform, which provides a feasible and efficient solution. Moreover, the proposed method fixes the gap in the CRT-based method for frequency determination for the real waveform case.

• By fully utilizing the prior knowledge of the real waveform, we reach the optimal error tolerance bound, i.e., $\Gamma /4$, which is twice better than the best-known robust generalized CRT proposed in [23].

The remaining content is organized as follows. In Section 2, we give an overview of the problem formulation. Section 3 details our closed-form reconstruction for the real waveform. In Section 4, we present some simulation results to support the theory. In Section 5, we discuss and interpret the simulation results. The conclusion is drawn in Section 6.

2. Problem Formulation

We first describe the frequency estimation model from the undersampled real waveforms.

2.1. Signal Model and Sampling

A sinusoidal waveform is defined as

(1)$x\left(t\right)=Acos\left(2\pi Xt\right)=\frac{1}{2}(A{e}^{\left(2\pi jXt\right)}+A{e}^{(-2\pi jXt)}),$

where A denotes the amplitude, X represents the frequency. Sampling $x\left(t\right)$ with L ADCs at frequency rates of $\left\{m_l\right|l=1,2,\cdots ,L\}$ [24,30], where ${max}_l{m}_l<2X$, i.e., the sampling rates are below the Nyquist rate, we have

(2)$x_{m_l}\left[u\right]=\frac{1}{2}(A{e}^{\frac{2\pi jXu}{m_l}}+A{e}^{\frac{-2\pi jXu}{m_l}}),u\in \mathbb{Z}.$

Applying the $m_l$-point Discrete Fourier Transform (DFT) to $x_{m_l}\left[u\right]$ [31,32], we obtain

(3)$DF{T}_{x_{m_l}\left[u\right]}\left[k\right]=\frac{A}{2}\delta (k-{⟨X⟩}_{m_l})+\frac{A}{2}\delta (k-{⟨-X⟩}_{m_l}).$

Here, $\delta (*)$ is the the Kronecker delta function, i.e., $\delta (k-{⟨X⟩}_{m_l})$ equals 1 when $k={⟨X⟩}_{m_l}$ or 0 otherwise, where k represents a frequency bin and ${⟨X⟩}_{m_l}$ denote the residue of X modulo $m_l$. Clearly, the locations of the spectrum peaks correspond to the residues ${⟨X⟩}_{m_l}$ and ${⟨-X⟩}_{m_l}$, which leads to two symmetric peaks over the frequency spectrum domain in the noiseless case. Thus, one can recover the frequency X with sampling rates (moduli) $m_l$ and the locations of the spectrum peaks (residues) ${⟨X⟩}_{m_l}$ via CRT.

2.2. Noise Model and RCRT Procedure

In the following, we further consider the noisy case and review RCRT. Still, let $X_i\in \{X_1,X_2\}$ represent the real number to be recovered, where $X_1>0$ and $X_2=-X_1$. The moduli are in a form $\{m_l=M_l\Gamma |l=1,2,\cdots L\}$, where $\left\{M_l\right\}$ are pairwise co-prime. ${\tilde{r}}_{i,l}={⟨X_i+{\Delta }_{i,l}⟩}_{m_l}$ denotes the erroneous residue of $X_i$ modulo $m_l$, where ${\Delta }_{i,l}$ represents the underlying error such that $|{\Delta }_{i,l}|<\Gamma /4$. Moreover, $r_i^c={⟨X_i⟩}_{\Gamma }$ denotes the common residue of $X_i$. ${\tilde{r}}_{i,l}^c={⟨X_i+{\Delta }_{i,l}⟩}_{\Gamma }={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }$ denotes the erroneous common residue. In practical cases, ${\tilde{r}}_{i,l}^c$ is calculated from ${\tilde{r}}_{i,l}$ based on the number theory, i.e., ${\tilde{r}}_{i,l}^c={⟨X_i+{\Delta }_{i,l}⟩}_{\Gamma }={⟨{⟨X_i+{\Delta }_{i,l}⟩}_{M_l\Gamma }⟩}_{\Gamma }={⟨{\tilde{r}}_{i,l}⟩}_{\Gamma }$, which ensures that ${\tilde{r}}_{i,l}^c$ and ${\tilde{r}}_{i,l}$ share the same ${\Delta }_{i,l}$. For clarity, all the notations are listed in Table 1. In the following, we aim to estimate the real number $X_1$ with known erroneous residues ${\tilde{r}}_{i,l}$ and moduli $m_l$.

Since $X_i=\lfloor X_i/\Gamma \rfloor \Gamma +r_i^c$, we recover $X_i$ by estimating the folding number $\lfloor X_i/\Gamma \rfloor$ and common residue $r_i^c$ successively. We adopt the reconstruction framework proposed in [24], which consists of three steps:

• (i). Estimate the folding number: Based on the fact that $X_i=k_i{m}_l+r_{i,l}=k_i{M}_l\Gamma +r_{i,l}$, where $k_i\in \mathbb{Z}$, we have $\lfloor X_i/\Gamma \rfloor =k_i{M}_l+\lfloor r_{i,l}/\Gamma \rfloor =k_i{M}_l+(r_{i,l}-{⟨r_{i,l}⟩}_{\Gamma })/\Gamma$. Clearly, ${⟨r_{i,l}⟩}_{\Gamma }={⟨{⟨X_i⟩}_{M_l\Gamma }⟩}_{\Gamma }={⟨X_i⟩}_{\Gamma }=r_i^c$. Thus, we have $\lfloor X_i/\Gamma \rfloor =k_i{M}_l+(r_{i,l}-r_i^c)/\Gamma$. By taking the modulo arithmetic, one can obtain

  (4)$\lfloor \frac{X_i}{\Gamma }\rfloor \equiv \frac{r_{i,l}-r_i^c}{\Gamma }mod{M}_l,$

  From (4), the folding number $\lfloor X_i/\Gamma \rfloor$ is estimated by the equation below via CRT [24],

  (5)$q_i\equiv \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }mod{M}_l,$

  where $q_i$ denotes the estimation of $\lfloor X_i/\Gamma \rfloor$.

• (ii). Estimate the common residues: Calculate ${\sum }_{l=1}^L{\tilde{r}}_{i,l}^c/L$ as the estimation of the common residue $r_i^c$.

• (iii). Estimate the number: Based on $X_i=\lfloor X_i/\Gamma \rfloor \Gamma +r_i^c$, $X_i$ is reconstructed by

  (6)$\widehat{X_i}=q_i\Gamma +\frac{{\sum }_{l=1}^L{\tilde{r}}_{i,l}^c}{L},$

  where ${\widehat{X}}_i$ represents the estimation of $X_i$.

2.3. Key Issues in Real Waveform

• (i). Robustness: Trivially estimating the folding number by (5) may lead to large errors due to the ambiguity of $({\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c)/\Gamma$. In other words, since $r_i^c\in [0,\Gamma )$ and $|{\Delta }_{i,l}|<\Gamma /4$, $({\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c)/\Gamma$ must satisfy one of the three subcases below based on (4) [33],

  (7)$\begin{array}{c}\hfill \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }\equiv \left\{\begin{array}{c}\lfloor X_i/\Gamma \rfloor \mathrm{mod}{M}_l,\mathrm{if}{r}_i^c+{\Delta }_{i,l}\in [0,\Gamma )\hfill \\ \lfloor X_i/\Gamma \rfloor -1\mathrm{mod}{M}_l,\mathrm{if}{r}_i^c+{\Delta }_{i,l}\in (-\Gamma /4,0)\hfill \\ \lfloor X_i/\Gamma \rfloor +1\mathrm{mod}{M}_l,\mathrm{if}{r}_i^c+{\Delta }_{i,l}\in [\Gamma ,5\Gamma /4)\hfill \end{array}\right.\end{array}$

  If $r_i^c+{\Delta }_{i,l_1}$ and $r_i^c+{\Delta }_{i,l_2}$ fall into different subcases in (7), where $l_1,l_2\in \{1,2,\cdots ,L\}$, simply aggregating them via CRT will bring unpredictable reconstruction errors. Thus, we need to unify $({\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c)/\Gamma$ such that all of them fall into one subcase in (7) to ensure robustness. This can be achieved by sorting ${\tilde{r}}_{i,l}^c$, where ${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }$, in the order such that the corresponding ${\Delta }_{i,l}$ are in an ascending order for each i. However, the above operation is only implementable when $|{\Delta }_{i,l}|<\Gamma /8$ [34], while it still remains open in the generic setup $|{\Delta }_{i,l}|<\Gamma /4$.

• (ii). Residue Ambiguity: Due to the loss of the correspondence between $X_i$ and ${\tilde{r}}_{i,l}$, we cannot cluster ${\tilde{r}}_{i,l}$ corresponding to $X_i$ to calculate $q_i$ from (5) for each i.

3. Robust Reconstruction for Frequency Estimation of Single-Tone Real Waveform

This section presents the polynomial-time RCRT-based frequency estimation for a noisy single-tone real waveform. Before proceeding, the following notations are introduced.

We first define a metric to represent the minimum circular distance between ${\tilde{r}}_{i,l_1}^c$ and ${\tilde{r}}_{i,l_2}^c$ on the circle of length $\Gamma$, i.e.,

(8)$d({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)=\underset{z}{min}|{\tilde{r}}_{i,l_1}^c-{\tilde{r}}_{i,l_2}^c+z\Gamma |,z\in \{-1,0,1\}.$

For example, if $\Gamma =12$, $d(1,11)=2$. Let $I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ denote the interval between ${\tilde{r}}_{i,l_1}^c$ and ${\tilde{r}}_{i,l_2}^c$ on the circle (such as $I({\tilde{r}}_{1,1}^c,{\tilde{r}}_{1,3}^c)$ shown in Figure 1), whose length is $d({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$. ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ represents the interval whose length is maximal. As shown in Figure 1, when $i=1$, the maximum interval is $I({\tilde{r}}_{1,1}^c,{\tilde{r}}_{1,3}^c)$; when $i=2$, $I({\tilde{r}}_{2,1}^c,{\tilde{r}}_{2,3}^c)$ is the maximum one.

3.1. The Order of Residues

Now, we consider the first key issue stated in Section 2.3, i.e., sorting ${\tilde{r}}_{i,l}^c$ in the order such that the corresponding errors ${\Delta }_{i,l}$ are in ascending order for each i, where ${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }$. According to [21], sorting is equivalent to finding a cutting point $\xi$ on the circle of length $\Gamma$ and stretching it to a real axis. If $\xi \notin {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ for each i, the shifted common residues ${\widehat{r}}_{i,l}^c$ on the real axis are sorted in ascending order of ${\Delta }_{i,l}$.

For example, in Figure 1, $\Gamma /2$ is not in the maximum intervals, i.e., $I({\tilde{r}}_{1,1}^c,{\tilde{r}}_{1,3}^c)$ and $I({\tilde{r}}_{2,1}^c,{\tilde{r}}_{2,3}^c)$. Then, cutting the circle at $\Gamma /2$ leads to ${\widehat{r}}_{2,3}^c<{\widehat{r}}_{2,2}^c<{\widehat{r}}_{2,1}^c$ and ${\widehat{r}}_{1,1}^c<{\widehat{r}}_{1,2}^c<{\widehat{r}}_{1,3}^c$ sorted in ascending order of ${\Delta }_{i,l}$, i.e., ${\Delta }_{2,3}<{\Delta }_{2,2}<0<{\Delta }_{2,1}$ and ${\Delta }_{1,1}<{\Delta }_{1,2}<0<{\Delta }_{1,3}$ shown in Figure 2a. On the contrary, if we cut the circle at 0, where $0\in I({\tilde{r}}_{1,1}^c,{\tilde{r}}_{1,3}^c)$, ${\Delta }_{1,1}$ breaks the ascending order, as shown in Figure 2b. Here, ${\widehat{r}}_{1,2}^c<{\widehat{r}}_{1,3}^c<{\widehat{r}}_{1,1}^c$, but ${\Delta }_{1,2},{\Delta }_{1,3},{\Delta }_{1,1}$ are in non-ascending order.

However, the key remaining problem is how to find the proper cutting point without the correspondence between ${\tilde{r}}_{i,l}^c$ and $X_i$, i.e., ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ is unknown. To this end, ref. [21] sacrifices the error bound to $\Gamma /8$. Nonetheless, we reach the error bound $\Gamma /4$ by using the symmetry of residues, i.e.,

$r_2^c={⟨X_2⟩}_{\Gamma }={⟨-X_1⟩}_{\Gamma }=\Gamma -r_1^c.$

That is to say, $r_1^c$ and $r_2^c$ are axially symmetric about line $\alpha$ shown in Figure 1. Since $|{\Delta }_{i,l}|<\Gamma /4$, $d({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)<d(r_i^c-\Gamma /4,r_i^c+\Gamma /4)=\Gamma /2$, i.e., ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ cannot contain 0 and $\Gamma /2$ simultaneously. Based on the symmetry, ${max}_{l}I({\tilde{r}}_{1,l_1}^c,{\tilde{r}}_{1,l_2}^c)\cup {max}_{l}I({\tilde{r}}_{2,l_1}^c,{\tilde{r}}_{2,l_2}^c)$ cannot contain both 0 and $\Gamma /2$. Thus, either 0 or $\Gamma /2$ is the cutting point. To figure out the cutting point, we state Lemma 1, which is proved in Appendix A, that once $0\in {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$, ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<{min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)$ holds. Similarly, ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)>{min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)$ is true when ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ contains $\Gamma /2$. Thus, the unknown ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ problem is converted to distance comparison, i.e., ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)$ and ${min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)$.

Before giving Lemma 1, we define Operation 1 and 2 corresponding to the cutting point is 0 and $\Gamma /2$, respectively.

• Operations 1:

  (9)${\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c$

• Operation 2:

  (10)${\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c\mathrm{if}{\tilde{r}}_{i,l}^c\in [0,\frac{\Gamma }{2}),\mathrm{otherwise}{\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c-\Gamma$

 Lemma 1. 

If ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<{min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)$, where $1\le i\le 2$ and $1\le l\le L$, apply Operation 2 on ${\tilde{r}}_{i,l}^c$; otherwise, Operation 1. The resultant ${\widehat{r}}_{i,l}^c$ are sorted in ascending order of ${\Delta }_{i,l}$ for each i.

For example, as shown in Figure 1, ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)=d(0,{\tilde{r}}_{1,1}^c)<{min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)=d(\Gamma /2,{\tilde{r}}_{2,3}^c)$. Thus, Operation 2 is applied. The resultant ${\widehat{r}}_{i,l}^c$ are sorted in the order that the corresponding ${\Delta }_{i,l}$ are in ascending order for each i, shown in Figure 2a.

3.2. Residue Ambiguity

With ${\widehat{r}}_{i,l}^c$ sorted in ascending order of ${\Delta }_{i,l}$, $({\tilde{r}}_{i,l}-{\widehat{r}}_{i,l}^c)/\Gamma$ fall into one subcase in (7) [24]. Now, we discuss the second key issue, i.e., residue ambiguity. If we can divide ${\tilde{r}}_{i,l}$ into two sets corresponding to $X_1$ and $X_2$, respectively, the folding number $\lfloor X_i/\Gamma \rfloor$ can be estimated based on (5) [34]:

(11)$q_i\equiv \frac{{\tilde{r}}_{i,l}-{\widehat{r}}_{i,l}^c}{\Gamma }mod{M}_l.$

However, the correspondence between ${\tilde{r}}_{i,l}$ and $X_i$ is unknown. To determine the correspondence, Li et al. proposed a scheme for positive numbers, which cannot be directly applied to the real waveform since $X_2<0$ [23]. To solve this issue, we form a quadratic equation by the prior condition $X_2=-X_1$. First, we consider the two residues $\{({\tilde{r}}_{1,l}-{\widehat{r}}_{1,l}^c)/\Gamma ,({\tilde{r}}_{2,l}-{\widehat{r}}_{2,l}^c)/\Gamma \}$ as a pair for each l. By multiplying each pair, we can reconstruct $q_1{q}_2$ via CRT based on (11) [22], i.e.,

(12)$q_1{q}_2\equiv \frac{{\tilde{r}}_{1,l}-{\widehat{r}}_{1,l}^c}{\Gamma }\times \frac{{\tilde{r}}_{2,l}-{\widehat{r}}_{2,l}^c}{\Gamma }mod{M}_l.$

Then, with $X_2=-X_1$, it can be proved that either $q_2=-q_1$ or $q_2=-q_1-1$ holds, which is stated in Lemma 2 and proved in Appendix B. Hence, we can form a quadratic equation in one unknown by replacing $q_2$ with $-q_1$ or $-q_1-1$ in (12) based on Lemma 2. In a nutshell, the residue ambiguity is addressed by solving one of the two quadratic equations below via CRT, corresponding to $q_2=-q_1$ and $q_2=-q_1-1$, respectively.

(13)$q_1^2\equiv M_l-\frac{{\tilde{r}}_{1,l}-{\widehat{r}}_{1,l}^c}{\Gamma }\times \frac{{\tilde{r}}_{2,l}-{\widehat{r}}_{2,l}^c}{\Gamma }mod{M}_l$

(14)$q_1^2+q_1\equiv M_l-\frac{{\tilde{r}}_{1,l}-{\widehat{r}}_{1,l}^c}{\Gamma }\times \frac{{\tilde{r}}_{2,l}-{\widehat{r}}_{2,l}^c}{\Gamma }mod{M}_l$

 Lemma 2. 

If $|{\Delta }_{i,l}|<\Gamma /4$, $\{q_1,q_2\}$ must fall into one of the following two cases:

• $q_2=-q_1-1$, when Operation 1 is the appropriate operation and performed on ${\tilde{r}}_{i,l}^c$, where $q_1=\lfloor X_1/\Gamma \rfloor$.

• $q_2=-q_1$, when Operation 2 is the appropriate operation and performed on ${\tilde{r}}_{i,l}^c$. If $r_1^c\in [0,\Gamma /2)$, $q_1=\lfloor X_1/\Gamma \rfloor$. Otherwise, $q_1=\lfloor X_1/\Gamma \rfloor +1$.

3.3. Reconstruction Scheme

With identified $q_1$, we consider the last two steps mentioned in Section 2.2. Clearly, ${\widehat{r}}_{1,l}^c$ can be distinguished from (11) since $q_1$ is determined. Thus, $X_1$ is estimated based on Section 2.2:

(15)${\widehat{X}}_1=q_1\Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}.$

With the above understanding, we state the final conclusion, i.e., Theorem 1, that reconstruction error is bounded by $\Gamma /4$, where the proof is in Appendix C.

 Theorem 1. 

If $X_1\in [0,\lfloor \sqrt{M}\rfloor \Gamma -\Gamma /2)$ and $|{\Delta }_{i,l}|<\Gamma /4$, $|{\widehat{X}}_1-X_1|<\Gamma /4$ holds, where $M={\prod }_{l=1}^L{M}_l$.

For step 4 of Algorithm 1, the time complexity of solving the Equation (13) or (14) via CRT is $O\left(1\right)$. Since we need to process at most $2L$${\tilde{r}}_{i,l}^c$ or ${\widehat{r}}_{i,l}^c$ in each step, the time complexity of Algorithm 1 is $O\left(L\right)$.

Algorithm 1 Robust frequency estimation for the single-tone real waveform.

Input: Moduli: $\left\{m_l\right|m_l=M_l\Gamma ,l=1,2,\cdots ,L\}$.

Erroneous residue sets: $S_l=\{{\tilde{r}}_{1,l},{\tilde{r}}_{2,l}\}$, $l=1,2,\cdots ,L$.

1:. Calculate the erroneous common residues ${\tilde{r}}_{i,l}^c={⟨{\tilde{r}}_{i,l}⟩}_{\Gamma }$.    2:. Calculate ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)$ and ${min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)$ from (8).    3:. If ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<{min}_{il}d(\Gamma /2,{\tilde{r}}_{i,l}^c)$, perform (10) on ${\tilde{r}}_{i,l}^c$ to obtain ${\widehat{r}}_{i,l}^c$. Otherwise, perform (9).    4:. If (9) is applied, solve the Equation (14) via CRT to obtain $q_1$. Otherwise, solve the Equation (13).    5:. Cluster the shifted common residues ${\widehat{r}}_{i,l}^c$ satisfying $\left(11\right)$.    6:. Calculate ${\widehat{X}}_1$ according to (15).

Output: ${\widehat{X}}_1$

 Example 1. 

Operation 1 is applied. The moduli are $m_l=M_l\Gamma \in \{3\times 10,5\times 10,7\times 10\}$, where the greatest common divisor $\Gamma =10$ and $|{\Delta }_{i,l}|<\Gamma /4$. If $X_1=94$ and $X_2=-94$, we assume the erroneous residue sets are $S_1=\{2,25\}$, $S_2=\{44,7\}$, and $S_3=\{23,48\}$. Thus, the erroneous common residues are $\{{\tilde{r}}_{1,1}^c,{\tilde{r}}_{2,1}^c\}=\{2,5\}$, $\{{\tilde{r}}_{1,2}^c,{\tilde{r}}_{2,2}^c\}=\{4,7\}$, and $\{{\tilde{r}}_{1,3}^c,{\tilde{r}}_{2,3}^c\}=\{3,8\}$. Clearly, ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)=2>{min}_{il}d(5,{\tilde{r}}_{i,l}^c)=0$, so Operation 1 is performed, i.e., ${\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c$. According to (14), we obtain: (1). $q_1^2+q_1\equiv 0mod3$; (2). $q_1^2+q_1\equiv 0mod5$; (3). $q_1^2+q_1\equiv 6mod7$. One can obtain $q_1^2+q_1=90$ via CRT, which leads to $q_1=9$. From (11), the shifted common residues ${\widehat{r}}_{i,l}^c$ of $q_1$ are $\{2,4,3\}$. So ${\widehat{X}}_1=9\times 10+(2+4+3)/3=93$.

 Example 2. 

Operation 2 is applied. Likewise, the moduli are $m_l=M_l\Gamma \in \{3\times 10,5\times 10,7\times 10\}$. If $X_1=81$ and $X_2=-81$, the erroneous residue sets are assumed as $S_1=\{20,11\}$, $S_2=\{29,18\}$, and $S_3=\{12,57\}$. Correspondingly, the erroneous common residues are $\{{\tilde{r}}_{1,1}^c,{\tilde{r}}_{2,1}^c\}=\{0,1\}$, $\{{\tilde{r}}_{1,2}^c,{\tilde{r}}_{2,2}^c\}=\{9,8\}$, and $\{{\tilde{r}}_{1,3}^c,{\tilde{r}}_{2,3}^c\}=\{2,7\}$. Clearly, ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)=0<{min}_{il}d(5,{\tilde{r}}_{i,l}^c)=2$, so Operation 2 is applied on ${\tilde{r}}_{i,l}^c$. Thus, we obtain the shifted residues based on (10): $\{{\widehat{r}}_{1,1}^c,{\widehat{r}}_{2,1}^c\}=\{0,1\}$, $\{{\widehat{r}}_{1,2}^c,{\widehat{r}}_{2,2}^c\}=\{-1,-2\}$, and $\{{\widehat{r}}_{1,3}^c,{\widehat{r}}_{2,3}^c\}=\{2,-3\}$. According to (13), one can derive that: (1). $q_1^2\equiv 1mod3$; (2). $q_1^2\equiv 4mod5$; (3). $q_1^2\equiv 1mod7$. Based on CRT, we have $q_1^2=64$, resulting in $q_1=8$. With determined $q_1$, we continue to figure out the corresponding shifted common residues based on (11), i.e., $\{0,-1,2\}$. As a result, ${\widehat{X}}_1=8\times 10+(0-1+2)/3=80.33$.

4. Simulation Results

In this section, we first present some simulations to verify our proposed theory. Then the simulation results are shown to demonstrate the performance of the proposed method compared with that of the robust generalized CRT [23] and searching−based algorithm [29].

In the following, we first consider the estimation error versus the error upper bound for our proposed theory, i.e., Theorem 1. To begin with, the simulation setup is given as follows. The moduli are $m_l=\{11\times 80,13\times 80,17\times 80\}$, where the greatest common factor $\Gamma =80$ and the maximal error level $\tau \in \{1,2,\cdots ,25\}$. Based on Theorem 1, $\tau$ needs to be bounded by $\Gamma /4=20$ to ensure robustness.

For a trial, one unknown real number X is chosen randomly, which belongs to the dynamic range $[0,3880)$, where the negative duplicate is $-X$. Moreover, 10,000 trials are implemented for each $\tau$.

Figure 3 shows the mean absolute error $E_{\tau }$ between the estimate $\widehat{X}$ and the true number X for each error bound. The mean absolute error $E_{\tau }$ is defined as below,

(16)$E_{\tau }=E_{trials}\left(\right|\widehat{X}-X\left|\right),$

where $E_{trials}$ denotes the mean of all the trials, $\widehat{X}$ and X are the estimate and true number in a trial, respectively. Clearly, $E_{\tau }$ is less than $\tau$ when $\tau \le \Gamma /4=20$, which matches well with our conclusion. Once $\tau$ exceeds the error bound, the reconstruction error increases rapidly.

In Figure 4, we present the curve of the probability of failure $P_e$ versus the error bound $\tau$, where

(17)$P_e=P\left(\right|\widehat{X}-X|>\tau ).$

One can see that when $\tau \le \Gamma /4$, the probability of failure is zero while non−zero when $\tau$ exceeds the bound. In a word, if $\tau <\frac{\Gamma }{4}$, the reconstruction error is linearly bounded by $\tau$, the probability of which is 1.

Next, we compare the performance of the proposed algorithm with that of the robust generalized CRT for two numbers in [23] and the searching−based algorithm in [29]. We consider the real sinusoidal waveform case and select $L=3$ sampling rates (moduli) in a form $m[1:L]=\Gamma \times \{11,13,17\}$, which share a greatest common factor $\Gamma$. We test different sampling rates where $\Gamma =\{40,80\}$. The unknown frequency X is randomly selected from the range $[0,48.5\times \Gamma )$. Each noise ${\Delta }_{i,l}$ is assumed to be some independent uniform noise within $(-\tau ,\tau )$, where $\tau$ varies from 1 to 25.

We repeat 5000 trials for each selection of $\Gamma$ and $\tau$. On the on hand, the root mean square error (RMSE) is investigated, where

(18)$\mathrm{RMSE}={\{E{(\widehat{X}-X)}^2\}}^{1/2}.$

Figure 5a,c show that our method outperforms the best known robust generalized CRT, where the maximal error tolerance is improved from $\Gamma /8$ to $\Gamma /4$. Morever, our method performs as well as the best searching−based method when the maximal error level is less than $\Gamma /4$.

On the other hand, we compare the test fail rate (TFR). We say that the test fails when

(19)$\mathrm{TFR}=P(|\widehat{X}-X|>\Gamma /4).$

As shown in Figure 5b,d, if $\tau \le \Gamma /4$, the estimation error is bounded by $\Gamma /4$, the probability of which is one. Once the maximal error level exceeds $\Gamma /4$, the reconstruction error is almost unpredictable. In a word, our method outperforms the robust generalized CRT while slightly worse than the searching−based algorithm when $\tau >\Gamma /4$. However, it’s worth pointing out that our method provides a closed−form solution that cannot be realized by the searching−based method. Then, we consider the real running time consumption, where the computing equipment is Lenovo xiaoxin Pro 13. The real running time of our method that runs for 125,000 times is about 7.96 s, while the robust generalized CRT proposed in [23] requires about 86.05 s since the algorithm involves a lot of loops. The searching-based method proposed in [29] sightly outperforms our method, which only needs about 5.75 s.

5. Discussion

The experiment results in Figure 5 suggest a clear improvement in the error bound from $\Gamma /8$ to $\Gamma /4$ compared with the method proposed in [23]. The reason why we can improve the error bound is that we fully utilized the prior knowledge of the real waveform, i.e., symmetry. For the real waveform, the real peak and the corresponding spurious peak are symmetric at about 0 points in the spectrum. Thus, the frequency determination from undersampled single-tone real waveform can be formulated as RCRT for two numbers $\{X_1,X_2\}$, where these two numbers are in a form $X_1=-X_2$. Based on this symmetry, the corresponding error-free common residues $\{r_1^c,r_2^c\}$ are symmetric on the circle of length $\Gamma$. The geometric property of symmetry ensures that even if the error bound is improved to $\Gamma /4$, we can still shift the erroneous common residues correctly to obtain a robust reconstruction. In addition, our algorithm is also highly efficient according to the real running time and the theoretical analysis. We use the prior condition of the real waveform to form a quadratic equation in one unknown to determine the folding numbers, which realizes the high efficiency of the algorithm.

In summary, our proposed method provides a feasible solution for the frequency determination from the undersampled single-tone real waveform. In addition, we complete the study of CRT-based frequency determination from undersampled waveform, which shows that the optimal error tolerance bound can be achieved in the real waveform case. The limitation of our proposed method is that since it is based on the prior knowledge of the real waveform and the prior condition is invalid; it cannot handle the complex waveform. In addition, this algorithm cannot deal with the case of multiple frequency estimation from undersampled real waveforms. We will investigate these problems in our future studies.

6. Conclusions

We proposed the first polynomial-time RCRT-based frequency estimation for a noisy single-tone real waveform, which matches the optimal error bound. The proposed method can be applied in SAR imaging of moving targets or sensor networks where the sampling rate may be lower than the Nyquist rate of the input signal. The time complexity of the proposed method is linear to the number of samplers. Moreover, the proposed method can estimate the frequency from the real waveform by sub-Nyquist rates, which reduces the cost and system size, especially in sensor networks that require noticeable sensors. We believe the method can be further extended to the multiple frequencies case.

Author Contributions

The contribution of the authors for this publication article are as follows: Y.-W.Z.: methodology, software, conceptualization, writing—original draft, writing—review and editing. X.-F.H.: writing—review and editing. G.-Q.X.: conceptualization, supervision, writing—review and editing. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Table

Figure 1. Illustration of the intervals.

Figure 2. Sketch of the Definition of [Forumla omitted. See PDF.].

Figure 3. Estimation errors versus the maximal error level.

Figure 4. Probability [Forumla omitted. See PDF.] versus the maximal error level.

Figure 5. Performance simulation comparison among searching-based method [29], robust generalized CRT [23] and proposed RCRT.

Table 1

List of Notations.

Notations	Explanation
$M_l$	Co-prime moduli
$m_l$	Moduli selected
$X_i$	Number to be recovered
$\widehat{X_i}$	Estimation of $X_i$
$\lfloor X_i/\Gamma \rfloor$	The folding number of $X_i$
$q_i$	Estimation of $\lfloor X_i/\Gamma \rfloor$
${\tilde{r}}_{i,l}={⟨X_i+{\Delta }_{i,l}⟩}_{m_l}$	Erroneous residue of $X_i$ modulo $m_l$
$r_i^c={⟨X_i⟩}_{\Gamma }$	Common residue of $X_i$
${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }$	Erroneous common residue of $X_i$
${\widehat{r}}_{i,l}^c$	Shifted common residue of $X_i$
$d({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$	Minimum circular distance between ${\tilde{r}}_{i,l_1}^c$ and ${\tilde{r}}_{i,l_2}^c$ on the circle of length $\Gamma$
$I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$	Interval between ${\tilde{r}}_{i,l_1}^c$ and ${\tilde{r}}_{i,l_2}^c$

Appendix A. Proof of Lemma 1

 Proof. 

For brevity, we only consider the case when $r_1^c\le r_2^c$, i.e., $r_1^c$ is on the right half of the circle $\Gamma$. For the case $r_1^c\ge r_2^c$, which is obviously symmetric with $r_1^c\le r_2^c$, one can obtain the same conclusion based on the following idea.

Since ${max}_{l}I({\tilde{r}}_{1,l_1}^c,{\tilde{r}}_{1,l_2}^c)\cup {max}_{l}I({\tilde{r}}_{2,l_1}^c,{\tilde{r}}_{2,l_2}^c)$ can not contain 0 and $\Gamma /2$ simultaneously, the intervals must satisfy one of the three cases:

• (1)

  $0\in {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$

• (2)

  $\Gamma /2\in {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$

• (3)

  ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ contains neither 0 nor $\Gamma /2$

Case (1): $0\in {max}_{l}I({\tilde{r}}_{1,l_1}^c,{\tilde{r}}_{1,l_2}^c)$ or ${max}_{l}I({\tilde{r}}_{2,l_1}^c,{\tilde{r}}_{2,l_2}^c)$.

If $0\in {max}_{l}I({\tilde{r}}_{1,l_1}^c,{\tilde{r}}_{1,l_2}^c)$, there must exist at least one ${\tilde{r}}_{1,k}^c$ to the left of the point 0, and another ${\tilde{r}}_{1,l}^c$ to the right of the point 0, where $k,l\in \{1,2,\cdots ,L\}$. Since $r_1^c$ is on the right half of the circle $\Gamma$ while ${\tilde{r}}_{1,k}^c={⟨r_1^c+{\Delta }_{1,k}⟩}_{\Gamma }$ is to the left of the point 0 and $|{\Delta }_{1,k}|<\Gamma /4$, we have $r_1^c\in [0,\Gamma /4)$. Based on the fact that $r_2^c=\Gamma -r_1^c$, $r_2^c\in (3\Gamma /4,\Gamma ]$. The same conclusion can be derived if $0\in {max}_{l}I({\tilde{r}}_{2,l_1}^c,{\tilde{r}}_{2,l_2}^c)$. Since $r_1^c\in [0,\Gamma /4)$ and ${\tilde{r}}_{1,k}^c$ is to the left of the point 0, we obtain (A1)$$\underset{il}{min}d(0,{\tilde{r}}_{i,l}^c)\le d(0,{\tilde{r}}_{1,k}^c)<d(0,r_1^c-\frac{\Gamma }{4})=\frac{\Gamma }{4}-r_1^c.$$

Now, we calculate ${min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$. When $i=1$, since $r_1^c\in [0,\Gamma /4)$ and $|{\Delta }_{i,l}|<\Gamma /4$, it’s clear that ${min}_{l}d(\frac{\Gamma }{2},{\tilde{r}}_{1,l}^c)>d(\frac{\Gamma }{2},r_1^c+\frac{\Gamma }{4})=\frac{\Gamma }{4}-r_1^c$. When $i=2$, replacing $r_2^c$ with $\Gamma -r_1^c$, we have ${min}_{l}d(\frac{\Gamma }{2},{\tilde{r}}_{2,l}^c)>d(\frac{\Gamma }{2},r_2^c-\frac{\Gamma }{4})=\frac{\Gamma }{4}-r_1^c$. In conclusion, when $0\in {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$, we have (A2)$$\underset{il}{min}d(0,{\tilde{r}}_{i,l}^c)<\frac{\Gamma }{4}-r_1^c<\underset{il}{min}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c).$$

Since Cases (1) and (2) cannot hold simultaneously, we have $\frac{\Gamma }{2}\notin {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ for each i. Thus, cutting the circle at $\Gamma /2$, i.e., applying Operation 2 on ${\tilde{r}}_{i,l}^c$ leads to ${\widehat{r}}_{i,l}^c$ sorted in ascending order of ${\Delta }_{i,l}$.

Case (2): $\Gamma /2\in {max}_{l}I({\tilde{r}}_{1,l_1}^c,{\tilde{r}}_{1,l_2}^c)$ or ${max}_{l}I({\tilde{r}}_{2,l_1}^c,{\tilde{r}}_{2,l_2}^c)$. Case (2) is obviously symmetric with case (1) on the circle of length $\Gamma$. The conclusion can be derived based on the same idea. If $\Gamma /2\in {max}_{l}I({\tilde{r}}_{1,l_1}^c,{\tilde{r}}_{1,l_2}^c)$, there must exist at least one ${\tilde{r}}_{1,k}^c$ to the left of the point $\Gamma /2$, and another ${\tilde{r}}_{1,l}^c$ to the right of the point $\Gamma /2$. Likewise, since ${\tilde{r}}_{1,k}^c={⟨r_1^c+{\Delta }_{1,k}⟩}_{\Gamma }$ is to the left of the point $\Gamma /2$ while $r_1^c$ is on the right half and $|{\Delta }_{1,k}|<\Gamma /4$, we have $r_1^c\in (\Gamma /4,\Gamma /2]$ and $r_2^c\in [\Gamma /2,3\Gamma /4)$. The same conclusion can be derived if $\Gamma /2\in {max}_{l}I({\tilde{r}}_{2,l_1}^c,{\tilde{r}}_{2,l_2}^c)$. Since $r_1^c\in (\Gamma /4,\Gamma /2]$ and ${\tilde{r}}_{1,k}^c$ is to the left of the point $\Gamma /2$, we obtain (A3)$$\underset{il}{min}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)\le d(\frac{\Gamma }{2},{\tilde{r}}_{1,k}^c)<d(\frac{\Gamma }{2},r_1^c+\frac{\Gamma }{4})=r_1^c-\frac{\Gamma }{4}.$$

Then, we discuss ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)$. When $i=1$, since $r_1^c\in (\Gamma /4,\Gamma /2]$ and $|{\Delta }_{i,l}|<\Gamma /4$, one can obtain ${min}_{l}d(0,{\tilde{r}}_{1,l}^c)>d(0,r_1^c-\frac{\Gamma }{4})=r_1^c-\frac{\Gamma }{4}$. When $i=2$, replacing $r_2^c$ with $\Gamma -r_1^c$, we have ${min}_{l}d(0,{\tilde{r}}_{2,l}^c)>d(0,r_2^c+\frac{\Gamma }{4})=r_1^c-\frac{\Gamma }{4}$. Based on the discussion above, when $\Gamma /2\in {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$, we have (A4)$$\underset{il}{min}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)<r_1^c-\frac{\Gamma }{4}<\underset{il}{min}d(0,{\tilde{r}}_{i,l}^c).$$

Since Cases (1) and (2) cannot hold simultaneously, we have $0\notin {max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ for each i. Thus, cutting the circle at 0, i.e., applying Operation 1 on ${\tilde{r}}_{i,l}^c$ leads to ${\widehat{r}}_{i,l}^c$ sorted in ascending order of ${\Delta }_{i,l}$. Case (3): Since neither 0 nor $\frac{\Gamma }{2}$ is covered by ${max}_{l}I({\tilde{r}}_{i,l_1}^c,{\tilde{r}}_{i,l_2}^c)$ for each i, we can implement either of the two operations on ${\tilde{r}}_{i,l}^c$. Q.E.D. □

Appendix B. Proof of Lemma 2

 Proof. 

The proof has two parts to handle the following two cases, respectively.

• (1)

  $mind(0,{\tilde{r}}_{i,l}^c)\ge mind(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$

• (2)

  $mind(0,{\tilde{r}}_{i,l}^c)<mind(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$

Case (1): Since Operation 1 is the appropriate operation based on Lemma 1, we have ${\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c$ based on (9). Therefore, replacing ${\widehat{r}}_{i,l}^c$ with ${\tilde{r}}_{i,l}^c$, (11) is equal to (A5)$$q_i\equiv \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }mod{M}_l.$$

Then, we discuss $r_i^c+{\Delta }_{i,l}$, which determines $q_i$ in (A5). With $r_i^c\in [0,\Gamma )$ and $|{\Delta }_{i,l}|<\frac{\Gamma }{4}$, $r_i^c+{\Delta }_{i,l}$ must fall into one of the three subcases:

• (a)

  $r_i^c+{\Delta }_{i,l}\in (0,\Gamma )$

• (b)

  $r_i^c+{\Delta }_{i,l}\in (-\frac{\Gamma }{4},0)$

• (c)

  $r_i^c+{\Delta }_{i,l}\in (\Gamma ,\frac{5\Gamma }{4})$

If $r_i^c+{\Delta }_{i,l}$ satisfy subcase (b), it leads to ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<\frac{\Gamma }{4}<{min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$, a contradiction to ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)\ge {min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$. Similarly, if $r_i^c+{\Delta }_{i,l}$ satisfy subcase (c), we have ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<\frac{\Gamma }{4}<{min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$, a contradiction to ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)\ge {min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$. Consequently, only subcase (a), i.e., $r_i^c+{\Delta }_{i,l}\in (0,\Gamma )$ holds, leading to $\frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$ satisfying subcase (1) in (7). Thus, $(\frac{{\tilde{r}}_{1,l}-{\tilde{r}}_{1,l}^c}{\Gamma },\frac{{\tilde{r}}_{2,l}-{\tilde{r}}_{2,l}^c}{\Gamma })$ are residues of $(\lfloor \frac{X_1}{\Gamma }\rfloor ,\lfloor \frac{X_2}{\Gamma }\rfloor )$ modulo $M_l$, where $\lfloor \frac{X_2}{\Gamma }\rfloor =\lfloor \frac{-X_1}{\Gamma }\rfloor =-\lfloor \frac{X_1}{\Gamma }\rfloor -1$. Therefore, when Operation 1 is the appropriate operation, $q_2=-q_1-1$ and $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$.

Case (2): In this case, Operation 2 is the appropriate operation based on Lemma 1. Then, based on (10), ${\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c$ when ${\tilde{r}}_{i,l}^c\in [0,\Gamma /2)$; otherwise, ${\widehat{r}}_{i,l}^c={\tilde{r}}_{i,l}^c-\Gamma$. Thus, replacing ${\widehat{r}}_{i,l}^c$ with ${\tilde{r}}_{i,l}^c$, (11) is equal to (A6)$$\begin{array}{c}\hfill q_i\equiv \left\{\begin{array}{c}\frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }mod{M}_l,\mathrm{if}{\tilde{r}}_i^c\in [0,\Gamma /2)\hfill \\ \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }+1mod{M}_l,\mathrm{otherwise}\hfill \end{array}\right.\end{array}$$

Likewise, we discuss $r_i^c+{\Delta }_{i,l}$ in the following to figure out $q_i$, where $r_i^c+{\Delta }_{i,l}$ must fall into one of the five subcases:

• (a)

  $r_i^c+{\Delta }_{i,l}\in (\frac{\Gamma }{4},\frac{3\Gamma }{4})$

• (b)

  $r_i^c+{\Delta }_{i,l}\in [0,\frac{\Gamma }{4}]$

• (c)

  $r_i^c+{\Delta }_{i,l}\in [\frac{3\Gamma }{4},\Gamma )$

• (d)

  $r_i^c+{\Delta }_{i,l}\in (-\frac{\Gamma }{4},0)$

• (e)

  $r_i^c+{\Delta }_{i,l}\in (\Gamma ,\frac{5\Gamma }{4})$

If $r_i^c+{\Delta }_{i,l}$ satisfies subcase a), we have ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)>\frac{\Gamma }{4}>{min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$, a contradiction to ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)\le {min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$. Consequently, subcase (a) cannot happen. Next, we set out to figure out $q_i$ corresponding to subcases (b), (c), (d), and (e).

Subcase (b): Since $r_i^c+{\Delta }_{i,l}\in [0,\frac{\Gamma }{4}]$, we have ${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }\in [0,\frac{\Gamma }{4}]$. Thus, based on (A6), we have $q_i\equiv \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$. Moreover, it is clear that $\frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$ are residues of $\lfloor \frac{X_i}{\Gamma }\rfloor$ modulo $M_l$ based on (7). So $q_i=\lfloor \frac{X_i}{\Gamma }\rfloor$.

Subcase (c): Likewise, since $r_i^c+{\Delta }_{i,l}\in [\frac{3\Gamma }{4},\Gamma )$, we have ${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }\in [\frac{3\Gamma }{4},\Gamma )$. Therefore, based on (A6), we have $q_i\equiv \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }+1$. From (7), one can obtain $\frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$ are residues of $\lfloor \frac{X_i}{\Gamma }\rfloor$ modulo $M_l$, which leads to $q_i=\lfloor \frac{X_i}{\Gamma }\rfloor +1$.

Subcase (d): Since $r_i^c+{\Delta }_{i,l}\in (-\frac{\Gamma }{4},0)$, we have ${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }\in (\frac{3\Gamma }{4},\Gamma )$. Therefore, based on (A6), we have $q_i\equiv \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }+1$. From (7), one can obtain $\frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$ are residues of $\lfloor \frac{X_i}{\Gamma }\rfloor -1$ modulo $M_l$. Thus, we have $q_i=\lfloor \frac{X_i}{\Gamma }\rfloor$.

Subcase (e): Since $r_i^c+{\Delta }_{i,l}\in (\Gamma ,\frac{5\Gamma }{4})$, we have ${\tilde{r}}_{i,l}^c={⟨r_i^c+{\Delta }_{i,l}⟩}_{\Gamma }\in (0,\frac{\Gamma }{4})$. Therefore, based on (A6), we have $q_i\equiv \frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$. From (7), one can obtain $\frac{{\tilde{r}}_{i,l}-{\tilde{r}}_{i,l}^c}{\Gamma }$ are residues of $\lfloor \frac{X_i}{\Gamma }\rfloor +1$ modulo $M_l$, which results in $q_i=\lfloor \frac{X_i}{\Gamma }\rfloor +1$.

Since $|{\Delta }_{i,l}|<\Gamma /4$, only subcases (b) and (d) or subcases (c) and (e) can occur simultaneously. Clearly, subcases (b) and (d) result in the same $q_i$, i.e., $q_i=\lfloor \frac{X_i}{\Gamma }\rfloor$. Similarly, subcases c) and e) lead to the same $q_i$, where $q_i=\lfloor \frac{X_i}{\Gamma }\rfloor +1$. Based on the discussions above, we start to consider the residue pair $\{r_1^c,r_2^c\}$. Since $r_2^c=\Gamma -r_1^c$, $\{r_1^c,r_2^c\}$ must fall into one the four subcases:

• (1)

  $r_1^c\in (0,\frac{\Gamma }{4})$, $r_2^c\in (\frac{3\Gamma }{4},\Gamma )$

• (2)

  $r_1^c\in (\frac{3\Gamma }{4},\Gamma )$, $r_2^c\in (0,\frac{\Gamma }{4})$

• (3)

  $r_1^c\in (\frac{\Gamma }{4},\frac{\Gamma }{2})$, $r_2^c\in (\frac{\Gamma }{2},\frac{3\Gamma }{4})$

• (4)

  $r_1^c\in (\frac{\Gamma }{2},\frac{3\Gamma }{4})$, $r_2^c\in (\frac{\Gamma }{4},\frac{\Gamma }{2})$

Subcase (1): Since $r_1^c\in (0,\frac{\Gamma }{4})$ and $|{\Delta }_{i,l}|<\frac{\Gamma }{4}$, $r_1^c+{\Delta }_{i,l}$ may fall into subcases (b) and (d), leading to $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$. In the same way, since $r_2^c\in (\frac{3\Gamma }{4},\Gamma )$, $r_2^c+{\Delta }_{i,l}$ can fall into subcases (c) and (e), resulting in $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor +1$. Based on the fact that $x_1=-x_2$, we have $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor +1=-\lfloor \frac{X_1}{\Gamma }\rfloor$, i.e., $q_1=-q_2=\lfloor \frac{X_1}{\Gamma }\rfloor$.

Subcase (2): Subcase (2) is obviously symmetric with subcase (1) on the circle of length $\Gamma$. The proof is very similar to that of subcase (1). It is clear that $r_1^c+{\Delta }_{i,l}$ can fall into subcases (c) and (e), leading to $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$. $r_2^c+{\Delta }_{i,l}$ may fall into subcases (b) and (d), leading to $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor$. Replacing $x_2$ with $-x_1$, we have $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor =-\lfloor \frac{X_1}{\Gamma }\rfloor -1$. Thus, $q_1=-q_2=\lfloor \frac{X_1}{\Gamma }\rfloor +1$.

Subcase (3): Since $r_1^c\in (\frac{\Gamma }{4},\frac{\Gamma }{2})$ and $|{\Delta }_{i,l}|<\frac{\Gamma }{4}$, $r_1^c+{\Delta }_{i,l}$ may fall into subcases (b) and (d). Then, we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$. For $r_2^c\in (\frac{\Gamma }{2},\frac{3\Gamma }{4})$, $r_2^c+{\Delta }_{i,l}$ can fall into subcases (c) and (e), resulting in $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor +1$. Therefore, we have $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor +1=-\lfloor \frac{X_1}{\Gamma }\rfloor$, i.e., $q_1=-q_2=\lfloor \frac{X_1}{\Gamma }\rfloor$.

Subcase (4): Subcase (4) is clearly symmetric with subcase 3) on the circle of length $\Gamma$. Clearly, $r_1^c+{\Delta }_{i,l}$ can fall into subcases (c) and (e), leading to $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$. $r_2^c+{\Delta }_{i,l}$ may fall into subcases (b) and (d), which means $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor$. Replacing $x_2$ with $-x_1$, we have $q_2=\lfloor \frac{X_2}{\Gamma }\rfloor =-\lfloor \frac{X_1}{\Gamma }\rfloor -1$. Thus, $q_1=-q_2=\lfloor \frac{X_1}{\Gamma }\rfloor +1$.

In a nutshell, when Operation 2 is the appropriate operation, $q_2=-q_1$. If $r_1^c\in [0,\Gamma /2)$, $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$. Otherwise, $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$. Q.E.D. □

Appendix C. Proof of Theorem 1

 Proof. 

At a high level, the proof is developed in two parts. First, we verify that $q_1$ has a unique solution when $X_1\in [0,\lfloor \sqrt{M}\rfloor \Gamma -\frac{\Gamma }{2})$. Second, the reconstruction error is discussed under Operations 1 and 2, respectively.

Now, we discuss the uniqueness of the solution to $q_i$. If Operation 1 is implemented, we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$ based on Lemma 2. Since $x_1<\lfloor \sqrt{M}\rfloor \Gamma -\frac{\Gamma }{2}$, we have (A7)$$q_1=\lfloor \frac{X_1}{\Gamma }\rfloor <\lfloor \frac{\lfloor \sqrt{M}\rfloor \Gamma -\frac{\Gamma }{2}}{\Gamma }\rfloor =\lfloor \sqrt{M}\rfloor -1.$$

From Algorithm 1, $q_1$ is determined by (14) when Operation 1 is implemented. Clearly, $q_1^2+q_1$ in (14) satisfies $q_1^2+q_1<M$, which guarantees that $q_1^2+q_1$ can be uniquely determined via CRT. Once $q_1^2+q_1$ is known, $q_1$ can be uniquely determined by solving a quadratic equation.

If Operation 2 is applied on ${\tilde{r}}_{i,l}^c$ and $r_1^c\in [0,\frac{\Gamma }{2})$, we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$ based on Lemma 2, where $X_1\le (\lfloor \sqrt{M}\rfloor -1)\Gamma +r_1^c$, i.e., (A8)$$q_1=\lfloor \frac{X_1}{\Gamma }\rfloor \le \lfloor \frac{(\lfloor \sqrt{M}\rfloor -1)\Gamma +r_1^c}{\Gamma }\rfloor =\lfloor \sqrt{M}\rfloor -1.$$

If $r_1^c\in (\frac{\Gamma }{2},\Gamma )$ and Operation 2 is applied, we obtain $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$ based on Lemma 2. Correspondingly, $X_1\le (\lfloor \sqrt{M}\rfloor -2)\Gamma +r_1^c$, which leads to (A9)$$q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1\le \lfloor \frac{(\lfloor \sqrt{M}\rfloor -2)\Gamma +r_1^c}{\Gamma }\rfloor +1=\lfloor \sqrt{M}\rfloor -1.$$

From Algorithm 1, $q_1$ is calculated by (13) when Operation 2 is implemented. Since $q_1\le \lfloor \sqrt{M}\rfloor -1$, we obtain $q_1^2<M$ in (13), which means $q_1$ can be uniquely recovered.

In the following, we continue to the second part of the proof, i.e., we discuss the robustness of reconstruction using the unique $q_1$, where $q_1\ne q_2$. Once $q_1$ is determined, we can obtain the corresponding ${\widehat{r}}_{1,l}^c$ from (11) and further reconstruct ${\widehat{X}}_1$ from (15). There are two scenarios for the reconstruction error: (i) Operation 1 is the appropriate operation and applied; (ii) Operation 2 is the appropriate operation and implemented.

When Operation 1 is applied: In this case, ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c$ based on (9). Then, we discuss ${\tilde{r}}_{1,l}^c={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }$, where $r_1^c+{\Delta }_{1,l}$ must fall into one of the three subcases:

• (a)

  $r_1^c+{\Delta }_{1,l}\in (0,\Gamma )$

• (b)

  $r_1^c+{\Delta }_{1,l}\in (-\frac{\Gamma }{4},0)$

• (c)

  $r_1^c+{\Delta }_{1,l}\in (\Gamma ,\frac{5\Gamma }{4})$

If $r_1^c+{\Delta }_{1,l}$ satisfies subcase (b), we have ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<\frac{\Gamma }{4}<{min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$, a contradiction to the fact that Operation 1 is the appropriate operation. Likewise, when $r_1^c+{\Delta }_{1,l}$ falls into subcase (c), we have ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)<\frac{\Gamma }{4}<{min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$, which contradicts the fact that Operation 1 is the appropriate operation. Therefore, only subcase a) can happen, i.e., $r_1^c+{\Delta }_{1,l}\in (0,\Gamma )$. Thus, $${\tilde{r}}_{1,l}^c={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }=r_1^c+{\Delta }_{1,l}.$$

Since Operation 1 is applied on ${\tilde{r}}_{1,l}^c$, we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$ based on Lemma 2. Then, reconstructing $X_1$ from (15), we have $|{\widehat{X}}_1-X_1|$ is equal to (A10)$$|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l})}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

When Operation 2 is applied: In this case, ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c$ when ${\tilde{r}}_{1,l}^c\in [0,\Gamma /2)$; otherwise ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c-\Gamma$ based on (9). Similarly, we discuss ${\tilde{r}}_{1,l}^c={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }$, where $r_1^c+{\Delta }_{1,l}$ must fall into one of the five subcases:

• (a)

  $r_1^c+{\Delta }_{1,l}\in (\frac{\Gamma }{4},\frac{3\Gamma }{4})$

• (b)

  $r_1^c+{\Delta }_{1,l}\in [0,\frac{\Gamma }{4}]$

• (c)

  $r_1^c+{\Delta }_{1,l}\in [\frac{3\Gamma }{4},\Gamma )$

• (d)

  $r_1^c+{\Delta }_{1,l}\in (-\frac{\Gamma }{4},0)$

• (e)

  $r_1^c+{\Delta }_{1,l}\in (\Gamma ,\frac{5\Gamma }{4})$

If $r_1^c+{\Delta }_{1,l}$ satisfies subcase (a), we have ${min}_{il}d(0,{\tilde{r}}_{i,l}^c)>\frac{\Gamma }{4}>{min}_{il}d(\frac{\Gamma }{2},{\tilde{r}}_{i,l}^c)$, a contradiction to that Operation 2 is the appropriate operation, which means that subcase (a) cannot happen. As proved in Appendix B, when $r_1^c+{\Delta }_{1,l}$ falls into subcase (b) or (d), we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$. When $r_1^c+{\Delta }_{1,l}$ falls into subcase (c) or (e), we obtain $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$. Based on these conclusions, we discuss the reconstruction error: (i). only one subcase occurs; (ii). subcases (b) and (d) or subcases (c) and (e) happen simultaneously.

Subcase (b): Since $r_1^c+{\Delta }_{1,l}\in [0,\frac{\Gamma }{4}]$ and Operation 2 is applied, we have ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }=r_1^c+{\Delta }_{1,l}$. Since $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$, $|{\widehat{X}}_1-X_1|$ is equal to (A11)$$|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l})}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

Subcase (c): Since $r_1^c+{\Delta }_{1,l}\in [\frac{3\Gamma }{4},\Gamma )$ and Operation 2 is applied, we have ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c-\Gamma ={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }-\Gamma =r_1^c+{\Delta }_{1,l}-\Gamma$. Since $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$, $|{\widehat{X}}_1-X_1|$ is equal to (A12)$$|(\lfloor \frac{X_1}{\Gamma }\rfloor +1)\Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l}-\Gamma )}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

Subcase (d): Since $r_1^c+{\Delta }_{1,l}\in (-\frac{\Gamma }{4},0)$ and Operation 2 is applied, we have ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c-\Gamma ={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }-\Gamma =r_1^c+{\Delta }_{1,l}$. Since $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$, $|{\widehat{X}}_1-X_1|$ is equal to (A13)$$|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l})}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

Subcase (e): Since $r_1^c+{\Delta }_{1,l}\in (\Gamma ,\frac{5\Gamma }{4})$ and Operation 2 is applied, we have ${\widehat{r}}_{1,l}^c={\tilde{r}}_{1,l}^c={⟨r_1^c+{\Delta }_{1,l}⟩}_{\Gamma }=r_1^c+{\Delta }_{1,l}-\Gamma$. Since $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$, $|{\widehat{X}}_1-X_1|$ is equal to (A14)$$|(\lfloor \frac{X_1}{\Gamma }\rfloor +1)\Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l}-\Gamma )}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

Subcase (b) and (d) happen simultaneously: Based on the discussions above, we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor$ and ${\widehat{r}}_{1,l}^c=r_1^c+{\Delta }_{1,l}$. Therefore, $|{\widehat{X}}_1-X_1|$ is equal to (A15)$$|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l})}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

Subcase (c) and (e) happen simultaneously: Likewise, based on the discussions above, we have $q_1=\lfloor \frac{X_1}{\Gamma }\rfloor +1$ and ${\widehat{r}}_{1,l}^c=r_1^c+{\Delta }_{1,l}-\Gamma$. As a result, $|{\widehat{X}}_1-X_1|$ is equal to (A16)$$|(\lfloor \frac{X_1}{\Gamma }\rfloor +1)\Gamma +\frac{{\sum }_{l=1}^L{\widehat{r}}_{1,l}^c}{L}-X_1|=|\lfloor \frac{X_1}{\Gamma }\rfloor \Gamma +\Gamma +\frac{{\sum }_{l=1}^L(r_1^c+{\Delta }_{1,l}-\Gamma )}{L}-X_1|=|\frac{{\sum }_{l=1}^L{\Delta }_{1,l}}{L}|<\frac{\Gamma }{4}.$$

Thus, the reconstruction error is bounded by $\frac{\Gamma }{4}$. Q.E.D. □

References

1. Chessa, S.; Maestrini, P. Robust distributed storage of residue encoded data. IEEE Trans. Inf. Theory; 2012; 58, pp. 7280-7294. [DOI: https://dx.doi.org/10.1109/TIT.2012.2216937]

2. Xiao, L.; Xia, X.-G.; Huo, H. Towards robustness in residue number systems. IEEE Trans. Signal Process.; 2017; 65, pp. 1497-1510. [DOI: https://dx.doi.org/10.1109/TSP.2016.2641398]

3. Goldreich, O.; Ron, D.; Sudan, M. Chinese remaindering with errors. IEEE Trans. Inf. Theory; 2006; 46, pp. 1330-1338. [DOI: https://dx.doi.org/10.1109/18.850672]

4. Xiao, H.; Garg, H.K.; Hu, J.; Xiao, G. New error control algorithms for residue number system codes. ETRI J.; 2016; 38, pp. 326-336. [DOI: https://dx.doi.org/10.4218/etrij.16.0115.0575]

5. Ding, C.; Pei, D.; Salomaa, A. Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography; World Scientific Publishing Company: Singapore, 1996.

6. Krishna, H.; Krishna, B.; Lin, K.Y.; Sun, J.D. Computational Number Theory and Digital Signal Processing: Fast Algorithms and Error Control Techniques; CRC Press: Boca Raton, FL, USA, 1994.

7. Li, C.; Tan, C.W.; Li, J.; Chen, S. Fault-tolerant computation meets network coding: Optimal scheduling in parallel computing. Proceedings of the 2021 IEEE Global Communications Conference (GLOBECOM); Madrid, Spain, 7–11 December 2021; pp. 1-6.

8. Xia, X.G.; Wang, G. Phase unwrapping and a robust chinese remainder theorem. IEEE Signal Process. Lett.; 2007; 14, pp. 247-250. [DOI: https://dx.doi.org/10.1109/LSP.2006.884898]

9. Li, X.; Xia, X.-G. A fast robust chinese remainder theorem based phase unwrapping algorithm. IEEE Signal Process. Lett.; 2008; 15, pp. 665-668. [DOI: https://dx.doi.org/10.1109/LSP.2008.2002926]

10. Xiao, L.; Xia, X.-G.; Wang, Y.-P. Exact and robust reconstructions of integer vectors based on multidimensional chinese remainder theorem (md-crt). IEEE Trans. Signal Process.; 2020; 68, pp. 5349-5364. [DOI: https://dx.doi.org/10.1109/TSP.2020.3023584]

11. Li, W.; Wang, X.; Moran, B. An enhanced lattice algorithm for range estimation using noisy measurement with phase ambiguity. IEEE Trans. Signal Process.; 2022; 70, pp. 890-902. [DOI: https://dx.doi.org/10.1109/TSP.2022.3146023]

12. Xiao, L.; Xia, X.; Wang, W. Multi-stage robust chinese remainder theorem. IEEE Trans. Signal Process.; 2014; 62, pp. 4772-4785. [DOI: https://dx.doi.org/10.1109/TSP.2014.2339798]

13. Xiao, L.; Xia, X.G. Frequency determination from truly sub-nyquist samplers based on robust chinese remainder theorem. Signal Process.; 2018; 150, pp. 248-258. [DOI: https://dx.doi.org/10.1016/j.sigpro.2018.04.022]

14. Wang, W.; Li, X.; Wang, W.; Xia, X.-G. Maximum likelihood estimation based robust chinese remainder theorem for real numbers and its fast algorithm. IEEE Trans. Signal Process.; 2015; 63, pp. 3317-3331. [DOI: https://dx.doi.org/10.1109/TSP.2015.2413378]

15. Li, X.; Huang, T.; Liao, Q.; Xia, X.-G. Optimal estimates of two common remainders for a robust generalized chinese remainder theorem. IEEE Trans. Signal Process.; 2019; 67, pp. 1824-1837. [DOI: https://dx.doi.org/10.1109/TSP.2019.2897945]

16. Xia, L.; Xia, X.-G. A new robust chinese remainder theorem with improved performance in frequency estimation from undersampled waveforms. Signal Process. Off. Publ. Eur. Assoc. Signal Process. (EURASIP); 2015; 117, pp. 242-246. [DOI: https://dx.doi.org/10.1016/j.sigpro.2015.05.017]

17. Xiao, H.; Du, N.; Wang, Z.; Xiao, G. Wrapped ambiguity gaussian mixed model with applications in sparse sampling based multiple parameter estimation. Signal Process; 2021; 179, 107825. [DOI: https://dx.doi.org/10.1016/j.sigpro.2020.107825]

18. Xia, X.G. On estimation of multiple frequencies in undersampled complex valued waveforms. Signal Process. IEEE Trans.; 1999; 47, pp. 3417-3419. [DOI: https://dx.doi.org/10.1109/78.806088]

19. Zhou, G.; Xia, X.G. Multiple frequency detection in undersampled complex-valued waveforms with close multiple frequencies. Electron. Lett.; 1997; 33, pp. 1294-1295. [DOI: https://dx.doi.org/10.1049/el:19970891]

20. Wang, W.; Xia, X.-G. A closed-form robust chinese remainder theorem and its performance analysis. IEEE Trans. Signal Process.; 2010; 58, pp. 5655-5666. [DOI: https://dx.doi.org/10.1109/TSP.2010.2066974]

21. Xiao, H.; Huang, Y.; Ye, Y.; Xiao, G. Robustness in chinese remainder theorem for multiple numbers and remainder coding. IEEE Trans. Signal Process.; 2018; 66, pp. 4347-4361. [DOI: https://dx.doi.org/10.1109/TSP.2018.2846228]

22. Xiao, L.; Xia, X.-G. A generalized chinese remainder theorem for two integers. IEEE Signal Process. Lett.; 2014; 21, pp. 55-59. [DOI: https://dx.doi.org/10.1109/LSP.2013.2289326]

23. Li, X.; Xia, X.-G.; Wang, W.; Wang, W. A robust generalized chinese remainder theorem for two integers. IEEE Trans. Inf. Theory; 2016; 62, pp. 7491-7504. [DOI: https://dx.doi.org/10.1109/TIT.2016.2614322]

24. Xiao, H.; Zhang, Y.; Xiao, G. On the foundation of sparse sensing (part i): Necessary and sufficient sampling theory and robust remaindering problem. arXiv; 2021; arXiv: 2108.10423

25. Xiao, H.; Zhou, B.; Xiao, G. On the foundation of sparse sensing (part ii): Diophantine sampling and array configuration. arXiv; 2021; arXiv: 2108.10425

26. Xia, X.G. An efficient frequency-determination algorithm from multiple undersampled waveforms. IEEE Signal Process. Lett.; 2000; 7, pp. 34-37. [DOI: https://dx.doi.org/10.1109/97.817380]

27. Xia, X.G.; Liu, K. A generalized chinese remainder theorem for residue sets with errors and its application in frequency determination from multiple sensors with low sampling rates. IEEE Signal Process. Lett.; 2005; 12, pp. 768-771. [DOI: https://dx.doi.org/10.1109/LSP.2005.856877]

28. Li, G.; Xu, J.; Peng, Y.-n.; Xia, X.-g. Detection, location and imaging of fast moving targets using non-uniform linear antenna array sar. Proceedings of the 2006 8th International Conference on Signal Processing; Guilin, China, 16–20 November 2006; Volume 4.

29. Maroosi, A.; Bizaki, H.K. Digital frequency determination of real waveforms based on multiple sensors with low sampling rates. IEEE Sens. J.; 2012; 12, pp. 1483-1495. [DOI: https://dx.doi.org/10.1109/JSEN.2011.2173482]

30. Xiao, L.; Xia, X.-G.; Huo, H. New conditions on achieving the maximal possible dynamic range for a generalized chinese remainder theorem of multiple integers. IEEE Signal Process. Lett.; 2015; 22, pp. 2199-2203. [DOI: https://dx.doi.org/10.1109/LSP.2015.2469537]

31. Xiao, H.; Cremers, C.; Garg, H.K. Symmetric polynomial amp; crt based algorithms for multiple frequency determination from undersampled waveforms. Proceedings of the 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP); Washington, DC, USA, 7–9 December 2016; pp. 202-206.

32. Wang, W.; Li, X.; Xia, X.-G.; Wang, W. The largest dynamic range of a generalized chinese remainder theorem for two integers. IEEE Signal Process. Lett.; 2015; 22, pp. 254-258. [DOI: https://dx.doi.org/10.1109/LSP.2014.2322200]

33. Xiao, H.; Xiao, G. Notes on crt-based robust frequency estimation. Signal Process.; 2017; 133, pp. 13-17. [DOI: https://dx.doi.org/10.1016/j.sigpro.2016.10.013]

34. Xiao, H.; Xiao, G. On solving ambiguity resolution with robust chinese remainder theorem for multiple numbers. IEEE Trans. Veh. Technol.; 2019; 68, pp. 5179-5184. [DOI: https://dx.doi.org/10.1109/TVT.2019.2905240]