# GNSS Signal Acquisition Algorithm Based on Two-Stage Compression of Code-Frequency Domain
## 2 Code-Domain Compression Acquisition Algorithm
### Code-Domain Compression Acquisition  
According to Equations (2) and (6), we can use the measurement matrix \(\mathbf{\Phi}\) to compresses the \(N\times 1\) dimensional correlation result \(\mathbf{X}\) to obtain the \(M\times 1\) dimensional measurement data \(\mathbf{Y}\)  
\[\mathbf{Y}_{M\times 1}=\underset{M\times N}{\mathbf{\Phi}}\cdot\underset{N\times 1 }{\mathbf{X}}=\underset{M\times N}{\mathbf{\Phi}}\cdot\underset{N\times 2K}{ \mathbf{\Phi}}\cdot\underset{2K\times 1}{\mathbf{C}}\cdot\underset{2K\times 1}{ \mathbf{F}} \tag{8}\]  
The measurement matrix \(\mathbf{\Phi}\) will be helpful for signal reconstruction when restricted isometry property (RIP) criteria is satisfied. In other words, each column is a unit vector, and the sum of squares of all columns meets the Welch bound [24; 25]  
\[\sum_{i=1}^{N}\sum_{j=1}^{N}\big{|}\big{\langle}\phi_{i},\phi_{j}\big{\rangle} \big{|}^{2}\geq\frac{N^{2}}{M} \tag{9}\]  
The FFT-based parallel search engine is adopted to acquire the correlation peak, which converts time-domain convolution operation into frequency-domain multiplication.  
Figure 1: Model of correlation output.  
The FFT of \(\mathbf{\Phi}\cdot\mathbf{C}\) are taken and multiplied by the FFT of the \(\mathbf{r}\), and then taken the inverse FFT (IFFT) to obtain \(\mathbf{Y}\).  
The correlation result \(\mathbf{X}\) can be reconstructed from \(\mathbf{Y}\) through some reconstruction algorithms, which can be described as follows  
\[\min\parallel\mathbf{X}\|_{0}\quad\text{ s.t. }\quad\mathbf{Y}=\mathbf{\Phi} \cdot\mathbf{X} \tag{10}\]  
where \(\|\cdot\|_{0}\) means the \(l_{0}\) norm which counts the number of nonzero elements.  
The \(l_{0}\) norm is a NP-hard problem, which can be converted into \(l_{2}\) norm if the measurement matrix \(\mathbf{\Phi}\) meets the RIP condition.  
\[\min\parallel\mathbf{X}\parallel_{2}^{2}\quad\quad\text{ s.t. }\quad\mathbf{Y}=\mathbf{\Phi} \cdot\mathbf{X} \tag{11}\]  
where \(\|\cdot\|_{2}\) is the \(l_{2}\) norm, also known as the Euclidean norm, which is used as a standard quantity for measuring a vector difference [26].  
The least square method (LSM) is used to reconstruct the elements from the measurement data \(\mathbf{Y}\)[27].  
\[\mathbf{X}=\mathbf{\Phi}^{\text{T}}(\mathbf{\Phi}\mathbf{\Phi}^{\text{T}})^{ -1}\mathbf{Y} \tag{12}\]  
The correct code phase and Doppler frequency offset are determined by comparing the first \(K\) elements from the correlation result \(\mathbf{X}\). Replacing the circular correlation with a compressed reconstruction in this method decreases the number of correlators from \(N+1\) to \(M+1\)[28].  
As we know, the correlation function \(R(\tau,f_{\text{d}})\) of the spreading code can be described as follows [29]  
\[R(\tau,f_{\text{d}})=2 AK\bigg{(}1-\frac{|\tau|}{T_{\text{c}}}\bigg{)}\frac{ \sin[\tau(f_{\text{d}}-f_{i})2 KT_{\text{s}}]}{\sin[\tau(f_{\text{d}}-f_{i})T_{ \text{s}}]}\exp[j\gamma(\varphi)] \tag{13}\]  
where \(\gamma(\varphi)=\pi(f_{\text{d}}-f_{i})(2K-1)T_{\text{s}}+\varphi\), \(f_{i}\) is the Doppler frequency hypothesis.  
We can find that \(R(\tau,f_{\text{d}})\) is affected by the Doppler frequency as a \(\text{sinc}(\cdot)\) function [29], and the zero of its main lobe is located at  
\[f_{\text{d}}{=}\frac{\pm 1}{KT_{\text{s}}}+f_{i} \tag{14}\]  
The correlation bandwidth \(B_{\text{c}}\) denotes  
\[B_{\text{c}}{=}\frac{2}{KT_{\text{s}}} \tag{15}\]  
Hence the Doppler frequency offset range in each search is obtained as  
\[f_{\text{d}}\in\bigg{[}\frac{-1}{KT_{\text{s}}}+f_{i},\frac{1}{KT_{\text{s}}} +f_{i}\bigg{]} \tag{16}\]  
where the search accuracy is \(1/(KT_{\text{s}})\).  
In above algorithm, the acquisition is serial in the frequency domain, and it will take a long time to acquire the Doppler frequency in high dynamics.