Open AccessArticle

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

Yao-Wen Zhang

Xian-Feng Han

and

Guo-Qiang Xiao

College of Computer and Information Science, Southwest University, Chongqing 400715, China

Author to whom correspondence should be addressed.

Sensors 2023, 23(1), 452; https://doi.org/10.3390/s23010452

Submission received: 14 November 2022 / Revised: 20 December 2022 / Accepted: 27 December 2022 / Published: 1 January 2023

(This article belongs to the Special Issue Digital Signal Processing, Computational Methods and Sensor Networks for Engineering Application)

Download

Browse Figures

Versions Notes

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 (L)

, where L is the number of samplers. Furthermore, our algorithm also matches the optimal error-tolerance bound.

Keywords:

robust Chinese Remainder Theorem; frequency estimation; undersampling; error bound; sensor network

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 $Γ$ as redundancy to the co-prime moduli ${M_{1}, M_{2},$ $\dots, M_{L}}$ in a form ${m_{l} = M_{l} Γ | l = 1, 2, \dots, 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 $⌊ X / Γ ⌋$ once the error in each residue is upper bounded by $Γ / 4$ . Hence, one can ensure the reconstruction error is upper bounded by $Γ / 4$ . The $Γ / 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 ${X_{i} | i = 1, 2, \dots N}$ and residues in each residue set $R_{l} = {r_{i, l} | i = 1, 2, \dots, N}$ , $l = 1, 2, \dots, 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 $Γ / 8$ [23]. As shown in recent works [24,25]; theoretically, one can approach the optimal error bound $Γ / 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., $Γ / 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

x (t) = A cos (2 π X t) = \frac{1}{2} (A e^{(2 π j X t)} + A e^{(- 2 π j X t)}),

(1)

where A denotes the amplitude, X represents the frequency. Sampling

x (t)

with L ADCs at frequency rates of

{m_{l} | l = 1, 2, \dots, L}

[24,30], where

{max}_{l} m_{l} < 2 X

, i.e., the sampling rates are below the Nyquist rate, we have

x_{m_{l}} [u] = \frac{1}{2} (A e^{\frac{2 π j X u}{m_{l}}} + A e^{\frac{- 2 π j X u}{m_{l}}}), u \in Z .

(2)

Applying the

m_{l}

-point Discrete Fourier Transform (DFT) to

x_{m_{l}} [u]

[31,32], we obtain

D F T_{x_{m_{l}} [u]} [k] = \frac{A}{2} δ (k - {〈 X 〉}_{m_{l}}) + \frac{A}{2} δ (k - {〈 - X 〉}_{m_{l}}) .

(3)

Here,

δ (*)

is the the Kronecker delta function, i.e.,

δ (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} Γ | l = 1, 2, \dots L}

, where

{M_{l}}

are pairwise co-prime.

{\tilde{r}}_{i, l} = {〈 X_{i} + Δ_{i, l} 〉}_{m_{l}}

denotes the erroneous residue of

X_{i}

modulo

m_{l}

, where

Δ_{i, l}

represents the underlying error such that

| Δ_{i, l} | < Γ / 4

. Moreover,

r_{i}^{c} = {〈 X_{i} 〉}_{Γ}

denotes the common residue of

X_{i}

{\tilde{r}}_{i, l}^{c} = {〈 X_{i} + Δ_{i, l} 〉}_{Γ} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ}

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} + Δ_{i, l} 〉}_{Γ} = {〈 {〈 X_{i} + Δ_{i, l} 〉}_{M_{l} Γ} 〉}_{Γ} = {〈 {\tilde{r}}_{i, l} 〉}_{Γ}

, which ensures that

{\tilde{r}}_{i, l}^{c}

and

{\tilde{r}}_{i, l}

share the same

Δ_{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} = ⌊ X_{i} / Γ ⌋ Γ + r_{i}^{c}

, we recover

X_{i}

by estimating the folding number

⌊ X_{i} / Γ ⌋

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} Γ + r_{i, l}$ , where $k_{i} \in Z$ , we have $⌊ X_{i} / Γ ⌋ = k_{i} M_{l} + ⌊ r_{i, l} / Γ ⌋ = k_{i} M_{l} + (r_{i, l} - {〈 r_{i, l} 〉}_{Γ}) / Γ$ . Clearly, ${〈 r_{i, l} 〉}_{Γ} = {〈 {〈 X_{i} 〉}_{M_{l} Γ} 〉}_{Γ} = {〈 X_{i} 〉}_{Γ} = r_{i}^{c}$ . Thus, we have $⌊ X_{i} / Γ ⌋ = k_{i} M_{l} + (r_{i, l} - r_{i}^{c}) / Γ$ . By taking the modulo arithmetic, one can obtain

$⌊ \frac{X_{i}}{Γ} ⌋ \equiv \frac{r_{i, l} - r_{i}^{c}}{Γ} mod M_{l},$

(4)

From (4), the folding number $⌊ X_{i} / Γ ⌋$ is estimated by the equation below via CRT [24],

$q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} mod M_{l},$

(5)

where $q_{i}$ denotes the estimation of $⌊ X_{i} / Γ ⌋$ .
(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} = ⌊ X_{i} / Γ ⌋ Γ + r_{i}^{c}$ , $X_{i}$ is reconstructed by

$\hat{X_{i}} = q_{i} Γ + \frac{\sum_{l = 1}^{L} {\tilde{r}}_{i, l}^{c}}{L},$

(6)

where ${\hat{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}) / Γ$ . In other words, since $r_{i}^{c} \in [0, Γ)$ and $| Δ_{i, l} | < Γ / 4$ , $({\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}) / Γ$ must satisfy one of the three subcases below based on (4) [33],

$\begin{matrix} \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} \equiv \{\begin{matrix} ⌊ X_{i} / Γ ⌋ \mod M_{l}, if r_{i}^{c} + Δ_{i, l} \in [0, Γ) \\ ⌊ X_{i} / Γ ⌋ - 1 \mod M_{l}, if r_{i}^{c} + Δ_{i, l} \in (- Γ / 4, 0) \\ ⌊ X_{i} / Γ ⌋ + 1 \mod M_{l}, if r_{i}^{c} + Δ_{i, l} \in [Γ, 5 Γ / 4) \end{matrix} \end{matrix}$

(7)

If $r_{i}^{c} + Δ_{i, l_{1}}$ and $r_{i}^{c} + Δ_{i, l_{2}}$ fall into different subcases in (7), where $l_{1}, l_{2} \in {1, 2, \dots, 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}) / Γ$ 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} + Δ_{i, l} 〉}_{Γ}$ , in the order such that the corresponding $Δ_{i, l}$ are in an ascending order for each i. However, the above operation is only implementable when $| Δ_{i, l} | < Γ / 8$ [34], while it still remains open in the generic setup $| Δ_{i, l} | < Γ / 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

Γ

, i.e.,

d ({\tilde{r}}_{i, l_{1}}^{c}, {\tilde{r}}_{i, l_{2}}^{c}) = min_{z} | {\tilde{r}}_{i, l_{1}}^{c} - {\tilde{r}}_{i, l_{2}}^{c} + z Γ |, z \in {- 1, 0, 1} .

(8)

For example, if

Γ = 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

Δ_{i, l}

are in ascending order for each i, where

{\tilde{r}}_{i, l}^{c} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ}

. According to [21], sorting is equivalent to finding a cutting point

ξ

on the circle of length

Γ

and stretching it to a real axis. If

ξ \notin {max}_{l} I ({\tilde{r}}_{i, l_{1}}^{c}, {\tilde{r}}_{i, l_{2}}^{c})

for each i, the shifted common residues

{\hat{r}}_{i, l}^{c}

on the real axis are sorted in ascending order of

Δ_{i, l}

For example, in Figure 1,

Γ / 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

Γ / 2

leads to

{\hat{r}}_{2, 3}^{c} < {\hat{r}}_{2, 2}^{c} < {\hat{r}}_{2, 1}^{c}

and

{\hat{r}}_{1, 1}^{c} < {\hat{r}}_{1, 2}^{c} < {\hat{r}}_{1, 3}^{c}

sorted in ascending order of

Δ_{i, l}

, i.e.,

Δ_{2, 3} < Δ_{2, 2} < 0 < Δ_{2, 1}

and

Δ_{1, 1} < Δ_{1, 2} < 0 < Δ_{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})

Δ_{1, 1}

breaks the ascending order, as shown in Figure 2b. Here,

{\hat{r}}_{1, 2}^{c} < {\hat{r}}_{1, 3}^{c} < {\hat{r}}_{1, 1}^{c}

, but

Δ_{1, 2}, Δ_{1, 3}, Δ_{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

Γ / 8

. Nonetheless, we reach the error bound

Γ / 4

by using the symmetry of residues, i.e.,

r_{2}^{c} = {〈 X_{2} 〉}_{Γ} = {〈 - X_{1} 〉}_{Γ} = Γ - r_{1}^{c} .

That is to say,

r_{1}^{c}

and

r_{2}^{c}

are axially symmetric about line

α

shown in Figure 1. Since

| Δ_{i, l} | < Γ / 4

d ({\tilde{r}}_{i, l_{1}}^{c}, {\tilde{r}}_{i, l_{2}}^{c}) < d (r_{i}^{c} - Γ / 4, r_{i}^{c} + Γ / 4) = Γ / 2

, i.e.,

{max}_{l} I ({\tilde{r}}_{i, l_{1}}^{c}, {\tilde{r}}_{i, l_{2}}^{c})

cannot contain 0 and

Γ / 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

Γ / 2

. Thus, either 0 or

Γ / 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}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < {min}_{i l} d (Γ / 2, {\tilde{r}}_{i, l}^{c})

holds. Similarly,

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) > {min}_{i l} d (Γ / 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

Γ / 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}_{i l} d (0, {\tilde{r}}_{i, l}^{c})

and

{min}_{i l} d (Γ / 2, {\tilde{r}}_{i, l}^{c})

Before giving Lemma 1, we define Operation 1 and 2 corresponding to the cutting point is 0 and

Γ / 2

, respectively.

Operations 1:

${\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c}$

(9)
Operation 2:

${\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c} if {\tilde{r}}_{i, l}^{c} \in [0, \frac{Γ}{2}), otherwise {\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c} - Γ$

(10)

Lemma 1.

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < {min}_{i l} d (Γ / 2, {\tilde{r}}_{i, l}^{c})

, where

1 \leq i \leq 2

and

1 \leq l \leq L

, apply Operation 2 on

{\tilde{r}}_{i, l}^{c}

; otherwise, Operation 1. The resultant

{\hat{r}}_{i, l}^{c}

are sorted in ascending order of

Δ_{i, l}

for each i.

For example, as shown in Figure 1,

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) = d (0, {\tilde{r}}_{1, 1}^{c}) < {min}_{i l} d (Γ / 2, {\tilde{r}}_{i, l}^{c}) = d (Γ / 2, {\tilde{r}}_{2, 3}^{c})

. Thus, Operation 2 is applied. The resultant

{\hat{r}}_{i, l}^{c}

are sorted in the order that the corresponding

Δ_{i, l}

are in ascending order for each i, shown in Figure 2a.

3.2. Residue Ambiguity

With

{\hat{r}}_{i, l}^{c}

sorted in ascending order of

Δ_{i, l}

({\tilde{r}}_{i, l} - {\hat{r}}_{i, l}^{c}) / Γ

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

⌊ X_{i} / Γ ⌋

can be estimated based on (5) [34]:

q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\hat{r}}_{i, l}^{c}}{Γ} mod M_{l} .

(11)

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} - {\hat{r}}_{1, l}^{c}) / Γ, ({\tilde{r}}_{2, l} - {\hat{r}}_{2, l}^{c}) / Γ}

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.,

q_{1} q_{2} \equiv \frac{{\tilde{r}}_{1, l} - {\hat{r}}_{1, l}^{c}}{Γ} \times \frac{{\tilde{r}}_{2, l} - {\hat{r}}_{2, l}^{c}}{Γ} mod M_{l} .

(12)

Then, with

X_{2} = - X_{1}

, it can be proved that either

q_{2} = - q_{1}

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}

- 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.

q_{1}^{2} \equiv M_{l} - \frac{{\tilde{r}}_{1, l} - {\hat{r}}_{1, l}^{c}}{Γ} \times \frac{{\tilde{r}}_{2, l} - {\hat{r}}_{2, l}^{c}}{Γ} mod M_{l}

(13)

q_{1}^{2} + q_{1} \equiv M_{l} - \frac{{\tilde{r}}_{1, l} - {\hat{r}}_{1, l}^{c}}{Γ} \times \frac{{\tilde{r}}_{2, l} - {\hat{r}}_{2, l}^{c}}{Γ} mod M_{l}

(14)

Lemma 2.

| Δ_{i, l} | < Γ / 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} = ⌊ X_{1} / Γ ⌋$ .
$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, Γ / 2)$ , $q_{1} = ⌊ X_{1} / Γ ⌋$ . Otherwise, $q_{1} = ⌊ X_{1} / Γ ⌋ + 1$ .

3.3. Reconstruction Scheme

With identified

q_{1}

, we consider the last two steps mentioned in Section 2.2. Clearly,

{\hat{r}}_{1, l}^{c}

can be distinguished from (11) since

q_{1}

is determined. Thus,

X_{1}

is estimated based on Section 2.2:

{\hat{X}}_{1} = q_{1} Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} .

(15)

With the above understanding, we state the final conclusion, i.e., Theorem 1, that reconstruction error is bounded by

Γ / 4

, where the proof is in Appendix C.

Theorem 1.

X_{1} \in [0, ⌊ \sqrt{M} ⌋ Γ - Γ / 2)

and

| Δ_{i, l} | < Γ / 4

| {\hat{X}}_{1} - X_{1} | < Γ / 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 (1)

. Since we need to process at most

2 L

{\tilde{r}}_{i, l}^{c}

{\hat{r}}_{i, l}^{c}

in each step, the time complexity of Algorithm 1 is

O (L)

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

Input: Moduli:

{m_{l} | m_{l} = M_{l} Γ, l = 1, 2, \dots, L}

Erroneous residue sets:

S_{l} = {{\tilde{r}}_{1, l}, {\tilde{r}}_{2, l}}

l = 1, 2, \dots, L

1:: Calculate the erroneous common residues ${\tilde{r}}_{i, l}^{c} = {〈 {\tilde{r}}_{i, l} 〉}_{Γ}$ .
2:: Calculate ${min}_{i l} d (0, {\tilde{r}}_{i, l}^{c})$ and ${min}_{i l} d (Γ / 2, {\tilde{r}}_{i, l}^{c})$ from (8).
3:: If ${min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < {min}_{i l} d (Γ / 2, {\tilde{r}}_{i, l}^{c})$ , perform (10) on ${\tilde{r}}_{i, l}^{c}$ to obtain ${\hat{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 ${\hat{r}}_{i, l}^{c}$ satisfying $(11)$ .
6:: Calculate ${\hat{X}}_{1}$ according to (15).

Output:

{\hat{X}}_{1}

Example 1.

Operation 1 is applied. The moduli are

m_{l} = M_{l} Γ \in {3 \times 10, 5 \times 10, 7 \times 10}

, where the greatest common divisor

Γ = 10

and

| Δ_{i, l} | < Γ / 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}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) = 2 > {min}_{i l} d (5, {\tilde{r}}_{i, l}^{c}) = 0

, so Operation 1 is performed, i.e.,

{\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c}

. According to (14), we obtain: (1).

q_{1}^{2} + q_{1} \equiv 0 mod 3

; (2).

q_{1}^{2} + q_{1} \equiv 0 mod 5

; (3).

q_{1}^{2} + q_{1} \equiv 6 mod 7

. One can obtain

q_{1}^{2} + q_{1} = 90

via CRT, which leads to

q_{1} = 9

. From (11), the shifted common residues

{\hat{r}}_{i, l}^{c}

q_{1}

are

{2, 4, 3}

. So

{\hat{X}}_{1} = 9 \times 10 + (2 + 4 + 3) / 3 = 93

Example 2.

Operation 2 is applied. Likewise, the moduli are

m_{l} = M_{l} Γ \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}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) = 0 < {min}_{i l} 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):

{{\hat{r}}_{1, 1}^{c}, {\hat{r}}_{2, 1}^{c}} = {0, 1}

{{\hat{r}}_{1, 2}^{c}, {\hat{r}}_{2, 2}^{c}} = {- 1, - 2}

, and

{{\hat{r}}_{1, 3}^{c}, {\hat{r}}_{2, 3}^{c}} = {2, - 3}

. According to (13), one can derive that: (1).

q_{1}^{2} \equiv 1 mod 3

; (2).

q_{1}^{2} \equiv 4 mod 5

; (3).

q_{1}^{2} \equiv 1 mod 7

. 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,

{\hat{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

Γ = 80

and the maximal error level

τ \in {1, 2, \dots, 25}

. Based on Theorem 1,

τ

needs to be bounded by

Γ / 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

τ

Figure 3 shows the mean absolute error

E_{τ}

between the estimate

\hat{X}

and the true number X for each error bound. The mean absolute error

E_{τ}

is defined as below,

E_{τ} = E_{t r i a l s} (| \hat{X} - X |),

(16)

where

E_{t r i a l s}

denotes the mean of all the trials,

\hat{X}

and X are the estimate and true number in a trial, respectively. Clearly,

E_{τ}

is less than

τ

when

τ \leq Γ / 4 = 20

, which matches well with our conclusion. Once

τ

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

τ

, where

P_{e} = P (| \hat{X} - X | > τ) .

(17)

One can see that when

τ \leq Γ / 4

, the probability of failure is zero while non−zero when

τ

exceeds the bound. In a word, if

τ < \frac{Γ}{4}

, the reconstruction error is linearly bounded by

τ

, 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] = Γ \times {11, 13, 17}

, which share a greatest common factor

Γ

. We test different sampling rates where

Γ = {40, 80}

. The unknown frequency X is randomly selected from the range

[0, 48.5 \times Γ)

. Each noise

Δ_{i, l}

is assumed to be some independent uniform noise within

(- τ, τ)

, where

τ

varies from 1 to 25.

We repeat 5000 trials for each selection of

Γ

and

τ

. On the on hand, the root mean square error (RMSE) is investigated, where

RMSE = {E {(\hat{X} - X)}^{2}}^{1 / 2} .

(18)

Figure 5a,c show that our method outperforms the best known robust generalized CRT, where the maximal error tolerance is improved from

Γ / 8

Γ / 4

. Morever, our method performs as well as the best searching−based method when the maximal error level is less than

Γ / 4

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

TFR = P (| \hat{X} - X | > Γ / 4) .

(19)

As shown in Figure 5b,d, if

τ \leq Γ / 4

, the estimation error is bounded by

Γ / 4

, the probability of which is one. Once the maximal error level exceeds

Γ / 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

τ > Γ / 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

Γ / 8

Γ / 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

Γ

. The geometric property of symmetry ensures that even if the error bound is improved to

Γ / 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.

Funding

This research received no external funding.

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.

Appendix A. Proof of Lemma 1

Proof.

For brevity, we only consider the case when

r_{1}^{c} \leq r_{2}^{c}

, i.e.,

r_{1}^{c}

is on the right half of the circle

Γ

. For the case

r_{1}^{c} \geq r_{2}^{c}

, which is obviously symmetric with

r_{1}^{c} \leq 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

Γ / 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): $Γ / 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 $Γ / 2$

Case (1):

0 \in {max}_{l} I ({\tilde{r}}_{1, l_{1}}^{c}, {\tilde{r}}_{1, l_{2}}^{c})

{max}_{l} I ({\tilde{r}}_{2, l_{1}}^{c}, {\tilde{r}}_{2, l_{2}}^{c})

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, \dots, L}

. Since

r_{1}^{c}

is on the right half of the circle

Γ

while

{\tilde{r}}_{1, k}^{c} = {〈 r_{1}^{c} + Δ_{1, k} 〉}_{Γ}

is to the left of the point 0 and

| Δ_{1, k} | < Γ / 4

, we have

r_{1}^{c} \in [0, Γ / 4)

. Based on the fact that

r_{2}^{c} = Γ - r_{1}^{c}

r_{2}^{c} \in (3 Γ / 4, Γ]

. 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, Γ / 4)

and

{\tilde{r}}_{1, k}^{c}

is to the left of the point 0, we obtain

min_{i l} d (0, {\tilde{r}}_{i, l}^{c}) \leq d (0, {\tilde{r}}_{1, k}^{c}) < d (0, r_{1}^{c} - \frac{Γ}{4}) = \frac{Γ}{4} - r_{1}^{c} .

(A1)

Now, we calculate

{min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

. When

i = 1

, since

r_{1}^{c} \in [0, Γ / 4)

and

| Δ_{i, l} | < Γ / 4

, it’s clear that

{min}_{l} d (\frac{Γ}{2}, {\tilde{r}}_{1, l}^{c}) > d (\frac{Γ}{2}, r_{1}^{c} + \frac{Γ}{4}) = \frac{Γ}{4} - r_{1}^{c}

. When

i = 2

, replacing

r_{2}^{c}

with

Γ - r_{1}^{c}

, we have

{min}_{l} d (\frac{Γ}{2}, {\tilde{r}}_{2, l}^{c}) > d (\frac{Γ}{2}, r_{2}^{c} - \frac{Γ}{4}) = \frac{Γ}{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

min_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < \frac{Γ}{4} - r_{1}^{c} < min_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c}) .

(A2)

Since Cases (1) and (2) cannot hold simultaneously, we have

\frac{Γ}{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

Γ / 2

, i.e., applying Operation 2 on

{\tilde{r}}_{i, l}^{c}

leads to

{\hat{r}}_{i, l}^{c}

sorted in ascending order of

Δ_{i, l}

Case (2):

Γ / 2 \in {max}_{l} I ({\tilde{r}}_{1, l_{1}}^{c}, {\tilde{r}}_{1, l_{2}}^{c})

{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

Γ

. The conclusion can be derived based on the same idea. If

Γ / 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

Γ / 2

, and another

{\tilde{r}}_{1, l}^{c}

to the right of the point

Γ / 2

. Likewise, since

{\tilde{r}}_{1, k}^{c} = {〈 r_{1}^{c} + Δ_{1, k} 〉}_{Γ}

is to the left of the point

Γ / 2

while

r_{1}^{c}

is on the right half and

| Δ_{1, k} | < Γ / 4

, we have

r_{1}^{c} \in (Γ / 4, Γ / 2]

and

r_{2}^{c} \in [Γ / 2, 3 Γ / 4)

. The same conclusion can be derived if

Γ / 2 \in {max}_{l} I ({\tilde{r}}_{2, l_{1}}^{c}, {\tilde{r}}_{2, l_{2}}^{c})

. Since

r_{1}^{c} \in (Γ / 4, Γ / 2]

and

{\tilde{r}}_{1, k}^{c}

is to the left of the point

Γ / 2

, we obtain

min_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c}) \leq d (\frac{Γ}{2}, {\tilde{r}}_{1, k}^{c}) < d (\frac{Γ}{2}, r_{1}^{c} + \frac{Γ}{4}) = r_{1}^{c} - \frac{Γ}{4} .

(A3)

Then, we discuss

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c})

. When

i = 1

, since

r_{1}^{c} \in (Γ / 4, Γ / 2]

and

| Δ_{i, l} | < Γ / 4

, one can obtain

{min}_{l} d (0, {\tilde{r}}_{1, l}^{c}) > d (0, r_{1}^{c} - \frac{Γ}{4}) = r_{1}^{c} - \frac{Γ}{4}

. When

i = 2

, replacing

r_{2}^{c}

with

Γ - r_{1}^{c}

, we have

{min}_{l} d (0, {\tilde{r}}_{2, l}^{c}) > d (0, r_{2}^{c} + \frac{Γ}{4}) = r_{1}^{c} - \frac{Γ}{4}

. Based on the discussion above, when

Γ / 2 \in {max}_{l} I ({\tilde{r}}_{i, l_{1}}^{c}, {\tilde{r}}_{i, l_{2}}^{c})

, we have

min_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c}) < r_{1}^{c} - \frac{Γ}{4} < min_{i l} d (0, {\tilde{r}}_{i, l}^{c}) .

(A4)

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

{\hat{r}}_{i, l}^{c}

sorted in ascending order of

Δ_{i, l}

. Case (3): Since neither 0 nor

\frac{Γ}{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): $min d (0, {\tilde{r}}_{i, l}^{c}) \geq min d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})$
(2): $min d (0, {\tilde{r}}_{i, l}^{c}) < min d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})$

Case (1): Since Operation 1 is the appropriate operation based on Lemma 1, we have

{\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c}

based on (9). Therefore, replacing

{\hat{r}}_{i, l}^{c}

with

{\tilde{r}}_{i, l}^{c}

, (11) is equal to

q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} mod M_{l} .

(A5)

Then, we discuss

r_{i}^{c} + Δ_{i, l}

, which determines

q_{i}

in (A5). With

r_{i}^{c} \in [0, Γ)

and

| Δ_{i, l} | < \frac{Γ}{4}

r_{i}^{c} + Δ_{i, l}

must fall into one of the three subcases:

(a): $r_{i}^{c} + Δ_{i, l} \in (0, Γ)$
(b): $r_{i}^{c} + Δ_{i, l} \in (- \frac{Γ}{4}, 0)$
(c): $r_{i}^{c} + Δ_{i, l} \in (Γ, \frac{5 Γ}{4})$

r_{i}^{c} + Δ_{i, l}

satisfy subcase (b), it leads to

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < \frac{Γ}{4} < {min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

, a contradiction to

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) \geq {min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

. Similarly, if

r_{i}^{c} + Δ_{i, l}

satisfy subcase (c), we have

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < \frac{Γ}{4} < {min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

, a contradiction to

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) \geq {min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

. Consequently, only subcase (a), i.e.,

r_{i}^{c} + Δ_{i, l} \in (0, Γ)

holds, leading to

\frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

satisfying subcase (1) in (7). Thus,

(\frac{{\tilde{r}}_{1, l} - {\tilde{r}}_{1, l}^{c}}{Γ}, \frac{{\tilde{r}}_{2, l} - {\tilde{r}}_{2, l}^{c}}{Γ})

are residues of

(⌊ \frac{X_{1}}{Γ} ⌋, ⌊ \frac{X_{2}}{Γ} ⌋)

modulo

M_{l}

, where

⌊ \frac{X_{2}}{Γ} ⌋ = ⌊ \frac{- X_{1}}{Γ} ⌋ = - ⌊ \frac{X_{1}}{Γ} ⌋ - 1

. Therefore, when Operation 1 is the appropriate operation,

q_{2} = - q_{1} - 1

and

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

Case (2): In this case, Operation 2 is the appropriate operation based on Lemma 1. Then, based on (10),

{\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c}

when

{\tilde{r}}_{i, l}^{c} \in [0, Γ / 2)

; otherwise,

{\hat{r}}_{i, l}^{c} = {\tilde{r}}_{i, l}^{c} - Γ

. Thus, replacing

{\hat{r}}_{i, l}^{c}

with

{\tilde{r}}_{i, l}^{c}

, (11) is equal to

\begin{matrix} q_{i} \equiv \{\begin{matrix} \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} mod M_{l}, if {\tilde{r}}_{i}^{c} \in [0, Γ / 2) \\ \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} + 1 mod M_{l}, otherwise \end{matrix} \end{matrix}

(A6)

Likewise, we discuss

r_{i}^{c} + Δ_{i, l}

in the following to figure out

q_{i}

, where

r_{i}^{c} + Δ_{i, l}

must fall into one of the five subcases:

(a): $r_{i}^{c} + Δ_{i, l} \in (\frac{Γ}{4}, \frac{3 Γ}{4})$
(b): $r_{i}^{c} + Δ_{i, l} \in [0, \frac{Γ}{4}]$
(c): $r_{i}^{c} + Δ_{i, l} \in [\frac{3 Γ}{4}, Γ)$
(d): $r_{i}^{c} + Δ_{i, l} \in (- \frac{Γ}{4}, 0)$
(e): $r_{i}^{c} + Δ_{i, l} \in (Γ, \frac{5 Γ}{4})$

r_{i}^{c} + Δ_{i, l}

satisfies subcase a), we have

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) > \frac{Γ}{4} > {min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

, a contradiction to

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) \leq {min}_{i l} d (\frac{Γ}{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} + Δ_{i, l} \in [0, \frac{Γ}{4}]

, we have

{\tilde{r}}_{i, l}^{c} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ} \in [0, \frac{Γ}{4}]

. Thus, based on (A6), we have

q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

. Moreover, it is clear that

\frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

are residues of

⌊ \frac{X_{i}}{Γ} ⌋

modulo

M_{l}

based on (7). So

q_{i} = ⌊ \frac{X_{i}}{Γ} ⌋

Subcase (c): Likewise, since

r_{i}^{c} + Δ_{i, l} \in [\frac{3 Γ}{4}, Γ)

, we have

{\tilde{r}}_{i, l}^{c} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ} \in [\frac{3 Γ}{4}, Γ)

. Therefore, based on (A6), we have

q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} + 1

. From (7), one can obtain

\frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

are residues of

⌊ \frac{X_{i}}{Γ} ⌋

modulo

M_{l}

, which leads to

q_{i} = ⌊ \frac{X_{i}}{Γ} ⌋ + 1

Subcase (d): Since

r_{i}^{c} + Δ_{i, l} \in (- \frac{Γ}{4}, 0)

, we have

{\tilde{r}}_{i, l}^{c} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ} \in (\frac{3 Γ}{4}, Γ)

. Therefore, based on (A6), we have

q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ} + 1

. From (7), one can obtain

\frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

are residues of

⌊ \frac{X_{i}}{Γ} ⌋ - 1

modulo

M_{l}

. Thus, we have

q_{i} = ⌊ \frac{X_{i}}{Γ} ⌋

Subcase (e): Since

r_{i}^{c} + Δ_{i, l} \in (Γ, \frac{5 Γ}{4})

, we have

{\tilde{r}}_{i, l}^{c} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ} \in (0, \frac{Γ}{4})

. Therefore, based on (A6), we have

q_{i} \equiv \frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

. From (7), one can obtain

\frac{{\tilde{r}}_{i, l} - {\tilde{r}}_{i, l}^{c}}{Γ}

are residues of

⌊ \frac{X_{i}}{Γ} ⌋ + 1

modulo

M_{l}

, which results in

q_{i} = ⌊ \frac{X_{i}}{Γ} ⌋ + 1

Since

| Δ_{i, l} | < Γ / 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} = ⌊ \frac{X_{i}}{Γ} ⌋

. Similarly, subcases c) and e) lead to the same

q_{i}

, where

q_{i} = ⌊ \frac{X_{i}}{Γ} ⌋ + 1

. Based on the discussions above, we start to consider the residue pair

{r_{1}^{c}, r_{2}^{c}}

. Since

r_{2}^{c} = Γ - r_{1}^{c}

{r_{1}^{c}, r_{2}^{c}}

must fall into one the four subcases:

(1): $r_{1}^{c} \in (0, \frac{Γ}{4})$ , $r_{2}^{c} \in (\frac{3 Γ}{4}, Γ)$
(2): $r_{1}^{c} \in (\frac{3 Γ}{4}, Γ)$ , $r_{2}^{c} \in (0, \frac{Γ}{4})$
(3): $r_{1}^{c} \in (\frac{Γ}{4}, \frac{Γ}{2})$ , $r_{2}^{c} \in (\frac{Γ}{2}, \frac{3 Γ}{4})$
(4): $r_{1}^{c} \in (\frac{Γ}{2}, \frac{3 Γ}{4})$ , $r_{2}^{c} \in (\frac{Γ}{4}, \frac{Γ}{2})$

Subcase (1): Since

r_{1}^{c} \in (0, \frac{Γ}{4})

and

| Δ_{i, l} | < \frac{Γ}{4}

r_{1}^{c} + Δ_{i, l}

may fall into subcases (b) and (d), leading to

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

. In the same way, since

r_{2}^{c} \in (\frac{3 Γ}{4}, Γ)

r_{2}^{c} + Δ_{i, l}

can fall into subcases (c) and (e), resulting in

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋ + 1

. Based on the fact that

x_{1} = - x_{2}

, we have

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋ + 1 = - ⌊ \frac{X_{1}}{Γ} ⌋

, i.e.,

q_{1} = - q_{2} = ⌊ \frac{X_{1}}{Γ} ⌋

Subcase (2): Subcase (2) is obviously symmetric with subcase (1) on the circle of length

Γ

. The proof is very similar to that of subcase (1). It is clear that

r_{1}^{c} + Δ_{i, l}

can fall into subcases (c) and (e), leading to

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

r_{2}^{c} + Δ_{i, l}

may fall into subcases (b) and (d), leading to

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋

. Replacing

x_{2}

with

- x_{1}

, we have

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋ = - ⌊ \frac{X_{1}}{Γ} ⌋ - 1

. Thus,

q_{1} = - q_{2} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

Subcase (3): Since

r_{1}^{c} \in (\frac{Γ}{4}, \frac{Γ}{2})

and

| Δ_{i, l} | < \frac{Γ}{4}

r_{1}^{c} + Δ_{i, l}

may fall into subcases (b) and (d). Then, we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

. For

r_{2}^{c} \in (\frac{Γ}{2}, \frac{3 Γ}{4})

r_{2}^{c} + Δ_{i, l}

can fall into subcases (c) and (e), resulting in

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋ + 1

. Therefore, we have

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋ + 1 = - ⌊ \frac{X_{1}}{Γ} ⌋

, i.e.,

q_{1} = - q_{2} = ⌊ \frac{X_{1}}{Γ} ⌋

Subcase (4): Subcase (4) is clearly symmetric with subcase 3) on the circle of length

Γ

. Clearly,

r_{1}^{c} + Δ_{i, l}

can fall into subcases (c) and (e), leading to

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

r_{2}^{c} + Δ_{i, l}

may fall into subcases (b) and (d), which means

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋

. Replacing

x_{2}

with

- x_{1}

, we have

q_{2} = ⌊ \frac{X_{2}}{Γ} ⌋ = - ⌊ \frac{X_{1}}{Γ} ⌋ - 1

. Thus,

q_{1} = - q_{2} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

In a nutshell, when Operation 2 is the appropriate operation,

q_{2} = - q_{1}

. If

r_{1}^{c} \in [0, Γ / 2)

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

. Otherwise,

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 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, ⌊ \sqrt{M} ⌋ Γ - \frac{Γ}{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} = ⌊ \frac{X_{1}}{Γ} ⌋

based on Lemma 2. Since

x_{1} < ⌊ \sqrt{M} ⌋ Γ - \frac{Γ}{2}

, we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ < ⌊ \frac{⌊ \sqrt{M} ⌋ Γ - \frac{Γ}{2}}{Γ} ⌋ = ⌊ \sqrt{M} ⌋ - 1 .

(A7)

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{Γ}{2})

, we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

based on Lemma 2, where

X_{1} \leq (⌊ \sqrt{M} ⌋ - 1) Γ + r_{1}^{c}

, i.e.,

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ \leq ⌊ \frac{(⌊ \sqrt{M} ⌋ - 1) Γ + r_{1}^{c}}{Γ} ⌋ = ⌊ \sqrt{M} ⌋ - 1 .

(A8)

r_{1}^{c} \in (\frac{Γ}{2}, Γ)

and Operation 2 is applied, we obtain

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

based on Lemma 2. Correspondingly,

X_{1} \leq (⌊ \sqrt{M} ⌋ - 2) Γ + r_{1}^{c}

, which leads to

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1 \leq ⌊ \frac{(⌊ \sqrt{M} ⌋ - 2) Γ + r_{1}^{c}}{Γ} ⌋ + 1 = ⌊ \sqrt{M} ⌋ - 1 .

(A9)

From Algorithm 1,

q_{1}

is calculated by (13) when Operation 2 is implemented. Since

q_{1} \leq ⌊ \sqrt{M} ⌋ - 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} \neq q_{2}

. Once

q_{1}

is determined, we can obtain the corresponding

{\hat{r}}_{1, l}^{c}

from (11) and further reconstruct

{\hat{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,

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c}

based on (9). Then, we discuss

{\tilde{r}}_{1, l}^{c} = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ}

, where

r_{1}^{c} + Δ_{1, l}

must fall into one of the three subcases:

(a): $r_{1}^{c} + Δ_{1, l} \in (0, Γ)$
(b): $r_{1}^{c} + Δ_{1, l} \in (- \frac{Γ}{4}, 0)$
(c): $r_{1}^{c} + Δ_{1, l} \in (Γ, \frac{5 Γ}{4})$

r_{1}^{c} + Δ_{1, l}

satisfies subcase (b), we have

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < \frac{Γ}{4} < {min}_{i l} d (\frac{Γ}{2}, {\tilde{r}}_{i, l}^{c})

, a contradiction to the fact that Operation 1 is the appropriate operation. Likewise, when

r_{1}^{c} + Δ_{1, l}

falls into subcase (c), we have

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) < \frac{Γ}{4} < {min}_{i l} d (\frac{Γ}{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} + Δ_{1, l} \in (0, Γ)

. Thus,

{\tilde{r}}_{1, l}^{c} = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ} = r_{1}^{c} + Δ_{1, l} .

Since Operation 1 is applied on

{\tilde{r}}_{1, l}^{c}

, we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

based on Lemma 2. Then, reconstructing

X_{1}

from (15), we have

| {\hat{X}}_{1} - X_{1} |

is equal to

| ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l})}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A10)

When Operation 2 is applied: In this case,

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c}

when

{\tilde{r}}_{1, l}^{c} \in [0, Γ / 2)

; otherwise

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c} - Γ

based on (9). Similarly, we discuss

{\tilde{r}}_{1, l}^{c} = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ}

, where

r_{1}^{c} + Δ_{1, l}

must fall into one of the five subcases:

(a): $r_{1}^{c} + Δ_{1, l} \in (\frac{Γ}{4}, \frac{3 Γ}{4})$
(b): $r_{1}^{c} + Δ_{1, l} \in [0, \frac{Γ}{4}]$
(c): $r_{1}^{c} + Δ_{1, l} \in [\frac{3 Γ}{4}, Γ)$
(d): $r_{1}^{c} + Δ_{1, l} \in (- \frac{Γ}{4}, 0)$
(e): $r_{1}^{c} + Δ_{1, l} \in (Γ, \frac{5 Γ}{4})$

r_{1}^{c} + Δ_{1, l}

satisfies subcase (a), we have

{min}_{i l} d (0, {\tilde{r}}_{i, l}^{c}) > \frac{Γ}{4} > {min}_{i l} d (\frac{Γ}{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} + Δ_{1, l}

falls into subcase (b) or (d), we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

. When

r_{1}^{c} + Δ_{1, l}

falls into subcase (c) or (e), we obtain

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 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} + Δ_{1, l} \in [0, \frac{Γ}{4}]

and Operation 2 is applied, we have

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c} = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ} = r_{1}^{c} + Δ_{1, l}

. Since

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

| {\hat{X}}_{1} - X_{1} |

is equal to

| ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l})}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A11)

Subcase (c): Since

r_{1}^{c} + Δ_{1, l} \in [\frac{3 Γ}{4}, Γ)

and Operation 2 is applied, we have

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c} - Γ = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ} - Γ = r_{1}^{c} + Δ_{1, l} - Γ

. Since

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

| {\hat{X}}_{1} - X_{1} |

is equal to

| (⌊ \frac{X_{1}}{Γ} ⌋ + 1) Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l} - Γ)}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A12)

Subcase (d): Since

r_{1}^{c} + Δ_{1, l} \in (- \frac{Γ}{4}, 0)

and Operation 2 is applied, we have

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c} - Γ = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ} - Γ = r_{1}^{c} + Δ_{1, l}

. Since

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

| {\hat{X}}_{1} - X_{1} |

is equal to

| ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l})}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A13)

Subcase (e): Since

r_{1}^{c} + Δ_{1, l} \in (Γ, \frac{5 Γ}{4})

and Operation 2 is applied, we have

{\hat{r}}_{1, l}^{c} = {\tilde{r}}_{1, l}^{c} = {〈 r_{1}^{c} + Δ_{1, l} 〉}_{Γ} = r_{1}^{c} + Δ_{1, l} - Γ

. Since

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

| {\hat{X}}_{1} - X_{1} |

is equal to

| (⌊ \frac{X_{1}}{Γ} ⌋ + 1) Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l} - Γ)}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A14)

Subcase (b) and (d) happen simultaneously: Based on the discussions above, we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋

and

{\hat{r}}_{1, l}^{c} = r_{1}^{c} + Δ_{1, l}

. Therefore,

| {\hat{X}}_{1} - X_{1} |

is equal to

| ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l})}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A15)

Subcase (c) and (e) happen simultaneously: Likewise, based on the discussions above, we have

q_{1} = ⌊ \frac{X_{1}}{Γ} ⌋ + 1

and

{\hat{r}}_{1, l}^{c} = r_{1}^{c} + Δ_{1, l} - Γ

. As a result,

| {\hat{X}}_{1} - X_{1} |

is equal to

| (⌊ \frac{X_{1}}{Γ} ⌋ + 1) Γ + \frac{\sum_{l = 1}^{L} {\hat{r}}_{1, l}^{c}}{L} - X_{1} | = | ⌊ \frac{X_{1}}{Γ} ⌋ Γ + Γ + \frac{\sum_{l = 1}^{L} (r_{1}^{c} + Δ_{1, l} - Γ)}{L} - X_{1} | = | \frac{\sum_{l = 1}^{L} Δ_{1, l}}{L} | < \frac{Γ}{4} .

(A16)

Thus, the reconstruction error is bounded by

\frac{Γ}{4}

. Q.E.D. □

References

Chessa, S.; Maestrini, P. Robust distributed storage of residue encoded data. IEEE Trans. Inf. Theory 2012, 58, 7280–7294. [Google Scholar] [CrossRef]
Xiao, L.; Xia, X.-G.; Huo, H. Towards robustness in residue number systems. IEEE Trans. Signal Process. 2017, 65, 1497–1510. [Google Scholar] [CrossRef] [Green Version]
Goldreich, O.; Ron, D.; Sudan, M. Chinese remaindering with errors. IEEE Trans. Inf. Theory 2006, 46, 1330–1338. [Google Scholar] [CrossRef]
Xiao, H.; Garg, H.K.; Hu, J.; Xiao, G. New error control algorithms for residue number system codes. ETRI J. 2016, 38, 326–336. [Google Scholar] [CrossRef]
Ding, C.; Pei, D.; Salomaa, A. Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography; World Scientific Publishing Company: Singapore, 1996. [Google Scholar]
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. [Google Scholar]
Li, C.; Tan, C.W.; Li, J.; Chen, S. Fault-tolerant computation meets network coding: Optimal scheduling in parallel computing. In Proceedings of the 2021 IEEE Global Communications Conference (GLOBECOM), Madrid, Spain, 7–11 December 2021; pp. 1–6. [Google Scholar]
Xia, X.G.; Wang, G. Phase unwrapping and a robust chinese remainder theorem. IEEE Signal Process. Lett. 2007, 14, 247–250. [Google Scholar] [CrossRef]
Li, X.; Xia, X.-G. A fast robust chinese remainder theorem based phase unwrapping algorithm. IEEE Signal Process. Lett. 2008, 15, 665–668. [Google Scholar] [CrossRef]
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, 5349–5364. [Google Scholar] [CrossRef]
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, 890–902. [Google Scholar] [CrossRef]
Xiao, L.; Xia, X.; Wang, W. Multi-stage robust chinese remainder theorem. IEEE Trans. Signal Process. 2014, 62, 4772–4785. [Google Scholar] [CrossRef] [Green Version]
Xiao, L.; Xia, X.G. Frequency determination from truly sub-nyquist samplers based on robust chinese remainder theorem. Signal Process. 2018, 150, 248–258. [Google Scholar] [CrossRef]
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, 3317–3331. [Google Scholar] [CrossRef]
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, 1824–1837. [Google Scholar] [CrossRef]
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, 242–246. [Google Scholar] [CrossRef]
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. [Google Scholar] [CrossRef]
Xia, X.G. On estimation of multiple frequencies in undersampled complex valued waveforms. Signal Process. IEEE Trans. 1999, 47, 3417–3419. [Google Scholar] [CrossRef]
Zhou, G.; Xia, X.G. Multiple frequency detection in undersampled complex-valued waveforms with close multiple frequencies. Electron. Lett. 1997, 33, 1294–1295. [Google Scholar] [CrossRef]
Wang, W.; Xia, X.-G. A closed-form robust chinese remainder theorem and its performance analysis. IEEE Trans. Signal Process. 2010, 58, 5655–5666. [Google Scholar] [CrossRef] [Green Version]
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, 4347–4361. [Google Scholar] [CrossRef]
Xiao, L.; Xia, X.-G. A generalized chinese remainder theorem for two integers. IEEE Signal Process. Lett. 2014, 21, 55–59. [Google Scholar] [CrossRef]
Li, X.; Xia, X.-G.; Wang, W.; Wang, W. A robust generalized chinese remainder theorem for two integers. IEEE Trans. Inf. Theory 2016, 62, 7491–7504. [Google Scholar] [CrossRef]
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. [Google Scholar]
Xiao, H.; Zhou, B.; Xiao, G. On the foundation of sparse sensing (part ii): Diophantine sampling and array configuration. arXiv 2021, arXiv:2108.10425. [Google Scholar]
Xia, X.G. An efficient frequency-determination algorithm from multiple undersampled waveforms. IEEE Signal Process. Lett. 2000, 7, 34–37. [Google Scholar] [CrossRef]
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, 768–771. [Google Scholar] [CrossRef]
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. In Proceedings of the 2006 8th International Conference on Signal Processing, Guilin, China, 16–20 November 2006; Volume 4. [Google Scholar]
Maroosi, A.; Bizaki, H.K. Digital frequency determination of real waveforms based on multiple sensors with low sampling rates. IEEE Sens. J. 2012, 12, 1483–1495. [Google Scholar] [CrossRef]
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, 2199–2203. [Google Scholar] [CrossRef]
Xiao, H.; Cremers, C.; Garg, H.K. Symmetric polynomial amp; crt based algorithms for multiple frequency determination from undersampled waveforms. In Proceedings of the 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), Washington, DC, USA, 7–9 December 2016; pp. 202–206. [Google Scholar]
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, 254–258. [Google Scholar] [CrossRef]
Xiao, H.; Xiao, G. Notes on crt-based robust frequency estimation. Signal Process. 2017, 133, 13–17. [Google Scholar] [CrossRef]
Xiao, H.; Xiao, G. On solving ambiguity resolution with robust chinese remainder theorem for multiple numbers. IEEE Trans. Veh. Technol. 2019, 68, 5179–5184. [Google Scholar] [CrossRef]

Figure 1. Illustration of the intervals.

Figure 2. Sketch of the Definition of

{\hat{r}}_{i, l}^{c}

Figure 2. Sketch of the Definition of

{\hat{r}}_{i, l}^{c}

Figure 3. Estimation errors versus the maximal error level.

Figure 4. Probability

P_{e}

versus the maximal error level.

Figure 4. Probability

P_{e}

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
$\hat{X_{i}}$	Estimation of $X_{i}$
$⌊ X_{i} / Γ ⌋$	The folding number of $X_{i}$
$q_{i}$	Estimation of $⌊ X_{i} / Γ ⌋$
${\tilde{r}}_{i, l} = {〈 X_{i} + Δ_{i, l} 〉}_{m_{l}}$	Erroneous residue of $X_{i}$ modulo $m_{l}$
$r_{i}^{c} = {〈 X_{i} 〉}_{Γ}$	Common residue of $X_{i}$
${\tilde{r}}_{i, l}^{c} = {〈 r_{i}^{c} + Δ_{i, l} 〉}_{Γ}$	Erroneous common residue of $X_{i}$
${\hat{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 $Γ$
$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}$

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.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Zhang, Y.-W.; Han, X.-F.; Xiao, G.-Q. An Efficient CRT Based Algorithm for Frequency Determination from Undersampled Real Waveform. Sensors 2023, 23, 452. https://doi.org/10.3390/s23010452

AMA Style

Zhang Y-W, Han X-F, Xiao G-Q. An Efficient CRT Based Algorithm for Frequency Determination from Undersampled Real Waveform. Sensors. 2023; 23(1):452. https://doi.org/10.3390/s23010452

Chicago/Turabian Style

Zhang, Yao-Wen, Xian-Feng Han, and Guo-Qiang Xiao. 2023. "An Efficient CRT Based Algorithm for Frequency Determination from Undersampled Real Waveform" Sensors 23, no. 1: 452. https://doi.org/10.3390/s23010452

APA Style

Zhang, Y. -W., Han, X. -F., & Xiao, G. -Q. (2023). An Efficient CRT Based Algorithm for Frequency Determination from Undersampled Real Waveform. Sensors, 23(1), 452. https://doi.org/10.3390/s23010452

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

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

Abstract

1. Introduction

2. Problem Formulation

2.1. Signal Model and Sampling

2.2. Noise Model and RCRT Procedure

2.3. Key Issues in Real Waveform

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

3.1. The Order of Residues

3.2. Residue Ambiguity

3.3. Reconstruction Scheme

4. Simulation Results

5. Discussion

6. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

Appendix A. Proof of Lemma 1

Appendix B. Proof of Lemma 2

Appendix C. Proof of Theorem 1

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI