A Fast Power Spectrum Sensing Solution for Generalized Coprime Sampling

The demand for spectrum resources is increasing due to the rapid development of low-orbit satellite constellation systems (e.g. SpaceX, OneWeb), 5G/6G networks, and the Internet of Things (IoT), etc [1]-[2]. These applications are driving a growing demand for wideband spectrum sensing. Correspondingly, direct sampling requires a high-speed analog-to-digital converter (ADC) based on the Shannon-Nyquist sampling theorem, leading to a prohibitive volume of data and high energy cost.

Currently, the most widely used methods are sweep-tune sampling and filter band sampling [3], both of which fall under the category of low-speed sampling. Nevertheless, the scanning scheme has a detection latency and may miss short-lived signals. Additionally, the filter band scheme has a complicated structure and is prone to serious channel crosstalk. As a result, there has been a trend towards using wideband spectrum sensing as a guide.

The recent compressive sensing (CS) theory provides a sub-sampling scheme with low-speed and large instantaneous bandwidth by utilizing the sparsity in the frequency domain [4]-[5]. The typical CS schemes include analog-to-information converter (AIC), multi-coset sampling (MCS), and multi-rate sampling (MRS). However, the sparse signal recovery algorithms have high computational complexity and are extremely sensitive to noise. On the other hand, the engineering implementation of these schemes also presents a major difficulty, restricting their application.

To overcome these difficulties, the approach to spectrum estimation has been shifted processing the original signal to analyzing its second-order statistics. In this context, the compressive covariance sensing (CCS) theory provides a wideband spectrum sensing scheme that operates at low-speed and has a large instantaneous bandwidth. It is reliable even in environments with a low signal-to-noise ratio (SNR) and non-sparse conditions. The typical CCS methods include entropy functions minimization [6], matrix norm minimization [7], and Toeplize matrix completion [8], among others. However, all these methods are based on the reconstruction of the covariance matrix and the use of mutiple signal classification (MUSIC) algorithm, which have high computational complexity and require pre-estimation the number of signals.

Furthermore, a computationally efficient method is developed based on the relationship between the autocorrelation sequence and sub-sampling samples of the MCS scheme [9]. Building on this, a fast solution for generalized coprime sampling is introduced, which utilizes only parallel FFT and multiplication operations. As a result, it achieves reduced time and low estimation error, presenting a tradeoff between system performance and the number of degrees of freedom (DOFs). Moreover, model mismatch has little effect on performance, making a more practical solution for real-time and distributed wideband spectrum sensing applications.

Notations: The bold characters denote vectors. The notations $\mathbb{R}$, $\mathbb{N}$ and $\mathbb{N}^{+}$ represent the set of real numbers, nonnegative integers, and positive integers, respectively. The superscripts $(\cdot)^{T}$ and $(\cdot)^{H}$ indicate the transpose and conjugate transpose of a vector or a matrix, respectively. The operator $\circ$ signifies the Hadamard product, $|\cdot|^{2}$ signifies the element-wise square modulus of a vector, and ceil($\cdot$) signifies round up to an integer. The symbols $\boldsymbol{F}_{a}$ and $\boldsymbol{F}_{a}^{-1}$ mean the $a$-point fast Fourier transofrm (FFT) and the inverse fast Fourier transofrm (IFFT), respectively.

The generalized coprime sampling architecture consists of two uniform sub-Nyquist sampling channels, whose sampling periods are coprime multiples of the Nyquist sampling period. The introduction of two other operations, the multiple coprime unit factor $p\in\mathbb{N}^{+}$ and the non-overlapping factor $q\in\mathbb{N}^{+}$, increases the number of DOFs and improves the estimation accuracy. Therewith, the coprime sampling scheme is presented with sampling intervals $r_{0}T_{s}$ and $r_{1}T_{s}$, as shown in Figure 1. Without loss of generality, it is assumed that $r_{0}<r_{1}$ with $r_{0},r_{1}\in\mathbb{N}^{+}$, where $r_{0}$ and $r_{1}$ are coprime. And the sampling interval $T_{s}$ corresponds to the Nyquist sampling rate $f_{s}$.

For a wide-sense stationarity or cyclostationary process $X(t),t\in\mathbb{R}$, it consists of a number of frequencies that are confined wihtin the bandwidth $B_{s}\leq f_{s}/2$. The outputs of two uniform sub-Nyquist sampling channels can then be expressed as

where $x[n],n\in\mathbb{N}$ denotes the Nyquist sampling samples, and the highest sampling rate of the coprime sampling system is given by $1/(r_{0}T_{s})=f_{s}/r_{0}$.

Accordingly, the elements of the sensing vector corresponding to the two coprime samplers can be donoted as

and

where $l_{0}=0,1,\dots,r_{1}-1$, $l_{1}=0,1,\dots,r_{0}-1$, and $k=0,1,\dots,p-1$.

From a data acquisition perspective, the output samples obtained from the generalized coprime sampling scheme are a subset of the Nyquist samples, positioned at

Based on the sensing vectors, the connection between the elements of the generalized coprime sampling vector and the Nyquist sampling vector can be expressed as

and the elements of the connection sensing vector are defined as

As a result, there is

where $\mathbf{x}[n]=\big{[}x[0],x[1],\dots,x[N-1]\big{]}^{T}$, $\mathbf{a}[n]=\big{[}a[0],a[1],$ $\dots,a[N-1]\big{]}^{T}$ and $\mathbf{y}[n]=\big{[}y[0],y[1],\dots,y[N-1]\big{]}^{T}$ are all vectors of size $N\times 1$.

Considering the widely-used unbiased estimation of the autocorrelation sequence for the output of generalized coprime sampling, the elements $r_{y}[m]$ can be given as

Substituting equation (7) into equation (8) yields

where $\lvert m\rvert\leq N-1$. Thus, the power spectrum can be obtained by performing FFT on the autocorrelation sequence $\{r_{x}[m]\}$, which is derived from the autocorrelation sequence $\{r_{y}[m]\}$ and $\{r_{a}[m]\}$. Then, a practical solution that computationally efficient is employed to obtain the estimation of the autocorrelation sequence. The steps are as follows:

Step 1: Pad vectors $\mathbf{a}[n]$ and $\mathbf{y}[n]$ with an additional N-length zeros.

and

Step 2: Calculate the autocorrelation sequence based on the power spectrum estimation of vector $\mathbf{a}_{2N}[n]=\big{[}a[0],a[1],$ $\dots,a[2N-1]\big{]}^{T}$ and $\mathbf{y}_{2N}[n]=\big{[}y[0],y[1],\dots,y[2N-1]\big{]}^{T}$ by involving FFT and IFFT.

and

where $k=0,1,\dots,2N-1$.

Step 3: Truncate the autocorrelation sequence of interest according to the frequency resolution of the system $\Delta f$.

and

where $M=\textit{ceil}(fs/2/\Delta f)+1$.

Step 4: Compute the autocorrelation sequence of the inputs using the obatined sequences $\{\hat{r}_{y}[m]\}$ and $\{\hat{r}_{a}[m]\}$.

where $m=-M+1,\dots,-1,0,1,\dots,M-1$.

Step 5: Obtain the power spectrum estimation by taking the FFT of vector $\hat{\mathbf{r}}_{x}[m]=\big{[}\hat{r}_{x}[-M+1],\dots,\hat{r}_{x}[1],\hat{r}_{x}[0],\hat{r}_{x}[1],\dots,\hat{r}_{x}[M-1]\big{]}^{T}$.

The block diagram illustrating the fast power spectrum sensing solution for generalized coprime sampling is depicted in Figure 2. The proposed solution is efficient, as it only involves FFT/IFFT operations and some basic multiplication operations. Moreover, the autocorrelation sequence $\{\hat{r}_{a}[m]\}$ of the sensing vector can be pre-calculated offline, as shown in the red section of Figure 2. This calculation is solely dependent on the generalized coprime sampling scheme.

Consequently, the computational complexity of the proposed solution involves the FFT of a $(2N)$-point sequence twice, resulting in $(2N)\text{log}(2N)$ floating-point operations according to (13). In addition, the FFT of a $(2M-1)$-point sequence is executed once, leading to $(2M-1)\text{log}(2M-1)$ floating-point operations according to (17). Upon incorporating $2M-1$ multiplication calculations, the total computational complexity necessitates $(4N)\text{log}(2N)+(2M-1)\text{log}(2M-1)+(2M-1)$ floating-point operations. This results in a lower computational complexity compared to the state-of-the-art methods. Meanwhile, it is feasible to compute the FFT operations in parallel effectively, which is a more suitable practical solution to meet the real-time wideband power spectrum sensing applications.

In the experiments, it is assume that there are $I$ inputs with identical powers, which are distributed in the frequency band $[2,18]$GHz. Subsequently, the coprime integers $r_{0}=3$, $r_{1}=4$ and the Nyquist sampling rate $f_{s}=32$GHz are set. Furthermore, the relative root mean square error (RMSE) is adopted to evaluate the performance of the proposed fast power spectrum sensing method, which is defined as follows

where $\hat{f}_{i}(j)$ is the estimation of $f_{i}$ from the $j$th Monte Carlo trial, and five hundred Monte Carlo trials are conducted.

Herein, the estimated power spectrum results are first displayed in Figure 3, with $p=3000$ and an input SNR of 15dB. There are $I=50$ mono-frequency pulse (MP) signals randomly distributed in (a), $I=20$ binary phase shift keying (BPSK) signals for 1M symbols per second with random frequency and code depicted in (b), $I=2$ linear frequency modulation (LFM) signals with 10GHz bandwidth under $\pm 6$GHz initial frequencies given in (c) and $I=21$ mixture signals of three types for (d). As can be observed, all frequencies are estimated accurately with the proposed method.

As shown in Figure 4, the RMSE results are compared as a function of the input SNR, where $I=18$ MP signals are used and the frequency is randomly selected. It can be seen that the RMSE tends to be stabilized when SNR is greater than -2dB for $p=300$. Under the same condition, the original method has the better performance at a low SNR by using the Toeplize matrix completion. Meanwhile, the estimation performance is improved as $p$ increases, due to that the DOF increases with $p$ and the resolution also improves. As expected, the Figure 5 has the same result. However, the selection of coprime sampling rate makes less difference to performance when p is greater than 1000. That is because the system redundancy under simulation is enough.

Furthermore, the multiple coprime unit factor $p$ not only affects the resolution, but also determines the execution time of algorithms. Thus, the execution time results are compared as a function of $p$ as displayed in Figure 6, where $I=10$ MP signals are used and the frequency is randomly selected with the 0dB SNR. It can be seen that the execution time of the proposed method has obvious advantages over the matrix completion method. Similar to the Figure 7, the proposed method outperforms the matrix completion method under the same execution time. Furthermore, the proposed method takes less time than the matrix completion method under the same performance. However, both methods rely on the larger number of samples. Therefore, there is a tradeoff between execution time and the system performance.

At last, the influence of the model matching degree between the sensing vector and measurements on the performance is discussed in Figure 8 with the 5dB SNR. Here, $I=18$ frequencies are randomly selected for MP signals, and different time delay are used which is unknown for the sensing vector. As a result, the influence of the model mismatch has little fluctuation of RMSE within $200\mu$s. That is interesting, which means that the fact potentially enables the spectrum resource in a distributed swarm scenario to be more efficiently utilized.

A fast power spectrum sensing solution for generalized coprime sampling is proposed, that only uses the parallel FFT and simple multiplication operations. It has obvious advantages over existing methods in terms of spectrum estimation performance and execution time, and there is no need to pre-estimate the number of inputs. Moreover, the influence of the model mismatch has little impact on the spectrum estimation performance, making it more suitable for further discussion on its application in the distributed swarm scenario.