A new frequency estimation method for a real-valued waveform with multiple sub-Nyquist channels based on the ESPRIT algorithm
Lulu Wang^{1} , Shang Liu^{2}
^{1}College of Mechanical and Electronic Engineering, Northwest A&F University, Xianyang, China
^{2}College of Automation Science and Electrical Engineering, Beihang University, Beijing, China
^{1}Corresponding author
Vibroengineering PROCEDIA, Vol. 44, 2022, p. 71-76.
https://doi.org/10.21595/vp.2022.22835
Received 28 July 2022; accepted 7 August 2022; published 25 August 2022
58th International Conference on Vibroengineering, Ventspils, Latvia, August 25-26, 2022
Real-valued waveform frequency measurement problems are often encountered in signal processing and they can be solved by designing a linear system. However, they require the sampling frequency to reach twice the maximum of the measured frequency, that is, to meet the Nyquist condition, which in many cases cannot be satisfied considering the hardware limitation. Therefore, how to design a nonlinear method to reconstruct the signal frequency is of great significance. To solve the frequency estimation problem for a real-valued waveform with sub-Nyquist channels, we propose a frequency estimator based on multiple sub-Nyquist channels. Our algorithm mainly consists of the following parts: 1) Calculate the folded frequencies which are lying on the first Nyquist region for each channel based on ESPRIT. 2) Reconstruct the signal frequency by a search method according to the set of folded frequencies. Finally, the simulation results verify the good performance of our proposed algorithm.
Keywords: sub-Nyquist channel, ESPRIT, search-based, real-valued waveform.
1. Introduction
In practice, measurements of high-frequency signals are often used in the field of radar signals [1] and infinite sensors [2]. Most current frequency estimation algorithms are based on the Nyquist theorem, which can estimate the signal in the time domain based on the differential linear relationship or map the signal from the time domain to the frequency domain based on the linear Fourier transform. However, as the signal bandwidth increases, those methods often require ADCs with a high sampling rate, which is very expensive and sometimes difficult to implement [3]. Therefore, how to reconstruct the signal frequency using the sub-Nyquist channel is an important nonlinear reconstruction problem.
The development of the Chinese remainder theorem (CRT) provides a possible solution to solve this nonlinear reconstruction problem. The traditional search-based CRT method is proposed in [4-5], but it is time-consuming and requires the sampling frequency to be coprime. The closed-form CRT proposed in [6-7] can further reduce the operation complexity while improving the generalizability of the algorithm. However, to use the CRT reconstruction method, we need to filter out the true residual from the two folded frequencies which are symmetrical about half of the sampling frequency. In practice, it is hard to select the correct residue. Therefore, the CRT is mostly applicable only in the frequency estimation for complex signals. To measure the frequency of the real-valued signal, Huang [8] added a zero-crossing detector in front of the sampling channel and selected the right remainder according to the signal phase. But this method has a limited noise immunity considering that the signal phase is easily affected by noise.
Maroosi [9] gave the theoretical upper bound of the real-valued signal frequency for stable reconstruction. Based on Maroosi’s work, Su [10] proposed an estimator with better noise immunity based on least squares and a search algorithm that does not depend on the phase of the signal. We further propose a new real-valued signal frequency estimation method based on [9-10], which improves the estimation accuracy and specifies the sampling requirements of this search algorithm. The simulation experiments demonstrate that our estimator does have better accuracy compared to [10].
Fig. 1. System overall flow chart
2. Frequency estimator using multiple sub-Nyquist channels
2.1. Estimator overview
Our proposed multi-channel-based frequency estimator for high-frequency signals is shown in Fig. 1. First, the signal is under sampled through multiple ADC channels. Then we obtain the residual frequency of the signal frequency in each channel according to the ESPRIT algorithm. Finally, we use the search-based method to reconstruct the signal frequency according to the set of sampling frequencies and residual frequencies obtained in the previous step.
2.2. Obtaining folded frequency
If we use an ADC with a sampling frequency of ${f}_{s}$ to undersample the signal with frequency $f$, the digital signal sequence is as follows:
where the $w\left[n\right]$ is the signal noise. Considering that the signal frequency may be greater than the sampling frequency, we have:
where we denote the ${f}_{r}$ as the folded frequency or the residue of the signal frequency moduli the sampling frequency. Thus, we can rewrite Eq. (1) as:
Considering that:
Thus, the signal sequence model is as follows:
We denote that:
${\mathbf{P}}_{1}=\left(\begin{array}{c}\begin{array}{cc}1& 1\\ {e}^{i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}& {e}^{-i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}\end{array}\\ \begin{array}{cc}\cdots & \cdots \\ {e}^{\left(N-1\right)i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}& {e}^{-\left(N-1\right)i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}\end{array}\end{array}\right),{\mathbf{P}}_{2}=\left(\begin{array}{c}\begin{array}{cc}{e}^{i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}& {e}^{-i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}s\\ {e}^{2i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}& {e}^{-2i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}\end{array}\\ \begin{array}{cc}\cdots & \cdots \\ {e}^{Ni\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}& {e}^{-Ni\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}\end{array}\end{array}\right),$
$\mathbf{\Phi}=\left(\begin{array}{c}{e}^{i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}\\ 0\end{array}\begin{array}{c}0\\ {e}^{-i\left(\frac{2\pi {f}_{r}}{{f}_{s}}\right)}\end{array}\right),\mathbf{w}=\left(\genfrac{}{}{0pt}{}{\begin{array}{c}\begin{array}{c}w\left[0\right]\\ w\left[1\right]\end{array}\\ \cdots \end{array}}{w[N-1]}\right).$
To obtain${f}_{r}$, we choose the widely used parameter estimation method ESPRIT [11] (Estimation of Signal Parameters Via Rotational Invariance Techniques) based on signal eigenspace.
Thus we have: ${\mathbf{P}}_{2}={\mathbf{P}}_{1}\mathbf{\Phi}$ and we can also find selection matrix ${\mathbf{J}}_{1}$ and ${\mathbf{J}}_{2}$ which satisfy:
Based on the signal sequence$\mathbf{s}$, we can build the autocorrelation matrix:
Thus, we can obtain the eigenvector matrix $\mathbf{V}$ which could span the signal subspace through eigenvalue decomposition of ${\mathbf{R}}_{\mathbf{s}\mathbf{s}}$. Therefore, we could find a full rank matrix $\mathbf{T}$ which satisfies:
Considering Eq. (7), we have:
We find an eigen decomposition of $\mathbf{T}\mathbf{\Phi}{\mathbf{T}}^{\mathbf{H}}$ and finally we have:
2.3. Signal frequency reconstruction
As we have obtained the folded frequency ${f}_{r}$ and ${{f}_{s}-f}_{r}$ in Section 2.2, we can choose the one ${f}_{rt}$ from ${f}_{r}$ and ${{f}_{s}-f}_{r}$ which satisfies $0<{f}_{rt}<\frac{{f}_{s}}{2}$.
Thus, we have the following reconstruction model:
where the ${f}_{s}^{i}$ denotes the sampling frequency in the $i$th AD channel and ${f}_{rt}^{i}$ denotes the selected folded frequency in the $i$th AD channel. Maroosi [9] gave the reconstruction upper bound as:
In other words, we can reconstruct the signal frequency without aliasing only if $f<{f}_{\mathrm{m}\mathrm{a}\mathrm{x}1}$.
As we have three channels, there exist too many parameter combinations of ${p}^{i}\in {N}_{+}$ and ${q}^{i}$ for $i\in \{\mathrm{1,2},3\}$. To reduce the search complexity, we add a constraint to the sampling rateswhich makes the three sampling frequencies close to each other.
Assume:
$\u230a\frac{{f}_{\mathrm{m}\mathrm{a}\mathrm{x}}}{{f}_{s}^{3}}\u230b\left({f}_{s}^{3}-{f}_{s}^{1}\right)\le \frac{{f}_{s}^{1}}{2}.$
Thus, the frequency upper bound is:
Then we have the following parameter combinations as shown in table 1according to Su [10] and each row represents a specific frequency region.
Table 1. Reconstruction method
$f$ | ${p}^{1}$ | ${p}^{2}$ | ${p}^{3}$ | ${q}^{1}$ | ${q}^{2}$ | ${q}^{3}$ |
[0, ${f}_{s}^{1}/2)$ | 0 | 0 | 0 | 1 | 1 | 1 |
[${f}_{s}^{1}/2$, ${f}_{s}^{2}/2)$ | 0 | 0 | 1 | 1 | 1 | –1 |
[${f}_{s}^{2}/2$, ${f}_{s}^{3}/2)$ | 0 | 1 | 1 | 1 | –1 | –1 |
[${f}_{s}^{3}/2$, ${f}_{s}^{1})$ | 1 | 1 | 1 | –1 | –1 | –1 |
[${f}_{s}^{1}$, ${f}_{s}^{2})$ | 1 | 1 | 1 | –1 | –1 | 1 |
[${f}_{s}^{2}$, ${f}_{s}^{3})$ | 1 | 1 | 1 | –1 | 1 | 1 |
[${f}_{s}^{3}$, ${3f}_{s}^{1}/2)$ | 1 | 1 | 1 | 1 | 1 | 1 |
[${3f}_{s}^{1}/2$, ${3f}_{s}^{2}/2)$ | 1 | 1 | 2 | 1 | 1 | –1 |
[${3f}_{s}^{2}/2$, ${3f}_{s}^{3}/2)$ | 1 | 2 | 2 | 1 | –1 | –1 |
[${3f}_{s}^{3}/2$, ${2f}_{s}^{1})$ | 2 | 2 | 2 | –1 | –1 | –1 |
… | … | … | … | … | … | … |
We define the reconstruction loss function as:
$+\left|\left({p}^{1}{f}_{s}^{1}+{q}^{1}{f}_{rt}^{1}\right)-\left({p}^{3}{f}_{s}^{3}+{q}^{3}{f}_{rt}^{3}\right)\right|.$
Then we can choose the best parameter combination with least ${f}_{loss}$ to reconstruct the signal frequency.
3. Simulation and results
We set the three sampling frequencies as1500 Hz, 1510 Hz and 1520 Hz. The maximum frequency which can be measured by our proposed estimator based on Eq. (15) is 57760 Hz. We can see that our estimator improves the upper bound of frequency measurement significantly.
Firstly, we test the performance of our estimator compared with Su [10]. We set the data length $N=$ 30 and signal frequency $f=$ 10000. In order to improve the speed of calculation, we construct a 5×5 autocorrelation matrix. If the data sequence with length greater than 5, we can construct multiple autocorrelation matrices using a sliding window with a length of 5and then compute the average matrix from them.
Fig. 2. Estimator performance compared with Su [10]
The experiment result is shown in Fig. 2. We can see from the simulation result that our estimator not only has better accuracy at the high SNR region, but also is more resistant to noise. Su’s algorithm becomes unstable at 16 dB, while our algorithm starts to diverge at 10 dB.
In addition, we also test the effect of the number of data points selected on the estimation accuracy. We still set to construct a 5×5 autocorrelation matrix, but the selected data lengths are 10, 20, and 30, and the other parameters are the same as in the previous experiment. Fig. 3 shows that the reconstruction accuracy improves as the number of data points increases, and the noise immunity also becomes stronger. However, it can also be found that the performance improvement gradually decreases as the number of points increases.
Fig. 3. Estimator performance with different data lengths
4. Conclusions
To solve the single real-valued signal frequency estimation problem using ADC with a low sampling rate, we propose a multiple sub-Nyquist channel-based estimation algorithm. We first estimate the folded frequency of the signal based on the ESPRIT algorithm, and then use a search algorithm to reconstruct the signal frequency in the presence of constraints on the sampling frequencies. Experiments verify that our algorithm has good accuracy and noise immunity. Since the ESPRIT algorithm can handle multi-frequency estimation problems, it is a future research direction for us to improve the search algorithm to achieve multi-frequency reconstruction afterward.
References
- S. Bhattacharya, T. Blumensath, B. Mulgrew, and M. Davies, “Fast encoding of synthetic aperture radar raw data using compressed sensing,” in 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, p. 14, Aug. 2007, https://doi.org/10.1109/ssp.2007.4301298 [Publisher]
- W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak, “Compressive wireless sensing,” in The 5th International Conference, pp. 134–142, 2006, https://doi.org/10.1145/1127777.1127801 [Publisher]
- Bin Le, T. W. Rondeau, J. H. Reed, and C. W. Bostian, “Analog-to-digital converters,” IEEE Signal Processing Magazine, Vol. 22, No. 6, pp. 69–77, Nov. 2005, https://doi.org/10.1109/msp.2005.1550190 [Publisher]
- P. P. Vaidyanathan and P. Pal, “Sparse sensing with co-prime samplers and arrays,” IEEE Transactions on Signal Processing, Vol. 59, No. 2, pp. 573–586, Feb. 2011, https://doi.org/10.1109/tsp.2010.2089682 [Publisher]
- X. Huang, Z. Yan, S. Jing, H. Fang, and L. Xiao, “Co-prime sensing-based frequency estimation using reduced single-tone snapshots,” Circuits, Systems, and Signal Processing, Vol. 35, No. 9, pp. 3355–3366, Sep. 2016, https://doi.org/10.1007/s00034-015-0193-3 [Publisher]
- L. Xiao, X.-G. Xia, and W. Wang, “Multi-stage robust Chinese remainder theorem,” IEEE Transactions on Signal Processing, Vol. 62, No. 18, pp. 4772–4785, Sep. 2014, https://doi.org/10.1109/tsp.2014.2339798 [Publisher]
- L. Xiao and X.-G. Xia, “A new robust Chinese remainder theorem with improved performance in frequency estimation from under sampled waveforms,” Signal Processing, Vol. 117, pp. 242–246, Dec. 2015, https://doi.org/10.1016/j.sigpro.2015.05.017 [Publisher]
- X. Huang, H. Wang, H. Qin, and W. Nie, “Frequency estimator based on spectrum correction and remainder sifting for under sampled real-valued waveforms,” IEEE Access, Vol. 7, pp. 25980–25988, 2019, https://doi.org/10.1109/access.2019.2900284 [Publisher]
- A. Maroosi and H. K. Bizaki, “Digital frequency determination of real waveforms based on multiple sensors with low sampling rates,” IEEE Sensors Journal, Vol. 12, No. 5, pp. 1483–1495, May 2012, https://doi.org/10.1109/jsen.2011.2173482 [Publisher]
- Y. Su and D. Jiang, “Digital instantaneous frequency measurement of a real sinusoid based on three sub-nyquist sampling channels,” Mathematical Problems in Engineering, Vol. 2020, pp. 1–11, Mar. 2020, https://doi.org/10.1155/2020/5089761 [Publisher]
- R. Roy and T. Kailath, “ESPRIT-estimation of signal parameters via rotational invariance techniques,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 37, No. 7, pp. 984–995, Jul. 1989, https://doi.org/10.1109/29.32276 [Publisher]