# GNSS Signal Acquisition Algorithm Based on Two-Stage Compression of Code-Frequency Domain
## 2 Code-Domain Compression Acquisition Algorithm  
### Sparsification of GNSS Signal  
The incoming digital down-converted GNSS intermediate frequency (IF) signal can be expressed as [21]  
\[r(n)=Ad(n)c(n-\tau)\exp[j(2\pi(f_{\text{IF}}+f_{\text{d}})nT_{\text{s}}+\varphi )]+v(n) \tag{1}\]  
where \(A\) is the signal amplitude, \(d\) is the signal data, \(c\) is the spreading code, \(f_{\text{IF}}\) is the intermediate frequency, \(f_{\text{d}}\) is the Doppler frequency offset, \(T_{\text{s}}\) is the sampling interval, \(\tau\) is the code phase, \(v\) is the noise, and \(\varphi\) is the unknown carrier phase.  
From the previous work, we know GNSS signal acquisition is possible at a low sampling rate by employing CS theory to compress the raw GNSS signal data using a measurement matrix [22], which can be expressed as  
\[\mathbf{y}=\mathbf{\Phi}\cdot\mathbf{x} \tag{2}\]  
where \(\mathbf{x}\) is the original signal, \(\mathbf{y}\) is the measurement vector, \(\mathbf{\Phi}\in R^{M\times N}\) is the measurement matrix, \(N\) is the signal length, \(M\) is the measurement length, and \(M<<N\).  
The premise of CS is that the signal is sparse. However, most of the real signals are not sparse but can be expressed as  
\[\mathbf{x}=\mathbf{\
abla}\cdot\mathbf{a} \tag{3}\]  
where \(\mathbf{\
abla}\) is called the sparse basis of the signal, \(\mathbf{a}\) is a sparse vector.  
Shifting the spreading code vector \(\mathbf{c}=[c(0),c(1),\cdots,c(NK-1)]\in R^{NK\times 1}\) to get the code matrix \(\mathbf{C}\)\[\mathbf{C}=[\mathbf{c}_{0},\mathbf{c}_{1},\cdots,\mathbf{c}_{N-1}]{=}\left[\begin{array} []{cccc}c(0)&c(1)&\cdots&c(2K-1)\\ c(K)&c(K+1)&\cdots&c(3K-1)\\ \vdots&\vdots&\ddots&\vdots\\ c[(N-1)K]&c[(N-1)K+1]&\cdots&c[(N+1)K-1]\end{array}\right] \tag{4}\]  
where \(N\) is the amount of points in the FFT, and \(N=2K\).  
Padding zeros to the end of the incoming signal \(r(n)\) to increase its length to \(2K\), which can solve the problem of non-periodicity after block processing of spreading code and reduce computation effectively [23]. It can be described as  
\[\mathbf{r}=[r(0),r(1),\cdots,r(K-1),0_{1\times K}]^{\mathrm{T}} \tag{5}\]  
Then, correlating the padded signal vector \(\mathbf{r}\) with the local spreading code matrix \(\mathbf{C}\), we can obtain the correlation vector \(\mathbf{X}\)  
\[\mathbf{X}=\mathbf{C}\cdot\mathbf{r} \tag{6}\]  
The acorrelation function (CF) of the incoming signal and the spreading code can be described as  
\[X_{i}=<\mathbf{c}_{n},\mathbf{r}>=\sum_{i=0}^{2K-1}c(i+n)r(i){=}\left\{ \begin{array}{cc}v+2 AK\Big{(}1-\frac{|\mathbf{r}|}{T_{\mathrm{c}}}\Big{)},& |\mathbf{r}|\leq T_{\mathrm{c}}\\ v,&|\mathbf{r}|>T_{\mathrm{c}}\end{array}\right. \tag{7}\]  
where \(X_{i}\) is the \(i\)th element of the correlation vector \(\mathbf{X}\), \(\mathbf{c}_{n}\) is the \(n\)th row of the code matrix \(\mathbf{C}\), \(<\cdot>\) is the discrete-time convolution operation, \(T_{\mathrm{c}}\) is the chip time, \(2 AK\) is the maximum peak value.  
As shown in Figure 1, the correlation result \(\mathbf{X}\) can be considered sparse if \(|2 AK|>>|v|\) in Equation (7).