Multi Block Overlapping Zero Padding Algorithm for Weak Signal Acquisition

Abstract

Global navigation satellite systems (GNSS) can implement high-precision navigation and positioning, requiring rapid and accurate signal acquisition under very weak signal conditions. Double block zero padding (DBZP) is an efficient algorithm for unaided weak signal acquisition. Considering the acquisition problem of weak direct sequence spread spectrum continuous phase modulation signal, the subblock combining and zero padding method is studied in detail. To solve the weakness of fixed number of subblock and fixed number of signal samples in each subblock given frequency resolution and Doppler searching range in DBZP, a multi block overlapping zero padding (MBOZP) algorithm is proposed, which combines with the ideas of data subblock overlapping. This algorithm optimizes the combination of data subblock by introducing the data subblock overlapping, which can increase the length of coherent accumulation and improve the performance of acquisition under the determined frequency resolution and Doppler searching range. Compared with the traditional DBZP, the simulation results show that MBOZP can obtain higher acquisition probability at small frequency offset.

1 Introduction

High-precision navigation satellite systems play an important role in military fields and are widely used in various fields [1]. Phase shift keying commonly used in satellite communications was limited by power efficiency and bandwidth efficiency, however, continuous phase modulation [2] can solve this problem effectively. With the development of navigation technology, it has important significance to implement weak CPM signal acquisition under the harsh environment.

In traditional acquisition algorithms, serial search method [3] obtains signal acquisition by two-dimensional search in carrier frequency offset and local code phase; parallel frequency domain search method transforms two-dimension searching into one-dimension searching, which can raise calculation speed and decrease acquisition time; parallel code phase search method [4] changes time-domain convolution operation into frequency-domain multiplication, with one IFFT operation to calculate the correlation values at all code delays. In general, traditional acquisition algorithms exist the problem of huge computational complexity. Therefore, Lin and Tsui [5] proposed the DBZP based on traditional acquisition algorithms, with the advantages of fast acquisition and high sensitivity. DBZP uses bi-frequency domain Fourier transformation for circular correlation, and the long correlation integral was divided into several blocks with the same length to perform correlation integral. In recent years, various improved algorithms based on DBZP were proposed, such as MDBZP [6], FMDBZP [7], IFMDBZP [8], DBZPTI [9] and restructured DBZP [10]. These improved algorithms mainly consider the decrease of the detection probability caused by date bit transition [11], and most of the algorithms focus on simplifying the detection decision and optimizing the frequency domain transform of correlation matrix.

Considering the influence of Doppler frequency offset on the length of data subblock, DBZP adopts fixed number of data subblock and fixed length of data subblock in order to guarantee the Doppler search range and frequency resolution. In terms of Doppler search range, it keeps the length of data subblock not too long to search the maximum Doppler frequency offset, whereas short data block will degrade the detection performance and increase the computation under the small or moderate frequency offsets. Thus, acquisition sensitivity can be increased by increasing the length of data subblock. The influence of the subblock combining and zero padding method on acquisition sensitivity in DBZP is further studied. When the new data subblocks are formed respectively by the received signal and the local signal, the overlapping multiple subblocks are introduced to increase the length of each new data subblock, which the number of data subblock remains unchanged. So the increase in the length of the coherent accumulation can improve the acquisition performance.

2 System Model

The system model of the direct sequence spread spectrum continuous phase modulation is shown in Fig. 1. The discrete time baseband signal arrived at the receiver can be expressed as

Fig. 1.

Acquisition model of DSSS CPM system

$$ r_{n} = s\left( {nT_{s} - \tau } \right)\exp \left( {j2\pi f_{d} nT_{s} } \right) + w_{n} $$

(1)

where $r_{n}$ is the $n$ th sample of the received signal, $s\left( {nT_{s} - \tau } \right)$ is the complex baseband DSSS-CPM signal. $\tau$ is the code phase delay, $T_{s}$ is the sampling interval ($f_{s} = {1 \mathord{\left/ {\vphantom {1 {T_{s} }}} \right. \kern-0pt} {T_{s} }}$ is the sampling frequency), $f_{d}$ is the Doppler frequency offset, $w_{n}$ is the additive Gaussian white noise sample with power spectral density $N_{0}$.

The acquisition module is mainly to process the received complex baseband signal and the local spread spectrum signal, and get the cross-correlation function of them. Then the estimated values of code phase and Doppler frequency offset are obtained according to its strong correlation peak of the correlation values.

When the DBZP algorithm is applied, the parameters of algorithm need to be determined by the system requirement at first. We assume that the correlation integral time $T = 20\;\text{ms}$, the sampling rate $f_{s} = 1.024\;{\text{MHz}}$, and the Doppler frequency search bandwidth $B_{{f_{d} }} = 8\;{\text{KHz}}$, which means the search range is $\left( { - 4\;{\text{KHz}}\sim 4\;{\text{KHz}}} \right)$. Hence the total data samples $N_{\text{total}} = f_{s} T = 20480$, the frequency resolution $f_{res} = {{f_{s} } \mathord{\left/ {\vphantom {{f_{s} } {N_{\text{total}} }}} \right. \kern-0pt} {N_{\text{total}} }} = {1 \mathord{\left/ {\vphantom {1 T}} \right. \kern-0pt} T} = 50\;\text{Hz}$, the total number of data block $N_{s} = {{B_{{f_{d} }} } \mathord{\left/ {\vphantom {{B_{{f_{d} }} } {f_{res} }}} \right. \kern-0pt} {f_{res} }} = 160$ and the length of each data block $L_{s} = {{N_{\text{total}} } \mathord{\left/ {\vphantom {{N_{\text{total}} } {N_{s} }}} \right. \kern-0pt} {N_{s} }} = 128$. Because of the periodicity of spread sequence, it just requires completing a period search for spread sequence when the data block is shifted in DBZP. The number of data block contained in $1\,\text{ms}$ $N_{ms} = {{N_{s} } \mathord{\left/ {\vphantom {{N_{s} } {\left( {{T \mathord{\left/ {\vphantom {T {1\,\text{ms}}}} \right. \kern-0pt} {1\,\text{ms}}}} \right)}}} \right. \kern-0pt} {\left( {{T \mathord{\left/ {\vphantom {T {1\,\text{ms}}}} \right. \kern-0pt} {1\,\text{ms}}}} \right)}} = 8$.

3 Multi Block Overlapping Zero Padding

The combination method of data subblock is discussed in this paper. First of all, the principle of DBZP is introduced so as to better understand the MBOZP algorithm.

3.1 Double Block Zero Padding

In DBZP, the search of all code phase is completed by circular correlation within the data subblock and the data subblock shifting. Then the correlation value matrix corresponding to different Doppler shift is obtained using FFT, which is equivalent to the parallel frequency search. The core of DBZP lies in double blocking and zero padding, which can ensure the search of data fully and without repetition, and avoid the loss of power caused by long data, and the FFT/IFFT operation of short data subblock in circular correlation can reduce the computation complexity. So DBZP not only reduces the influence of Doppler frequency offset to the correlation values but also reduces the computational complexity greatly. The algorithm integrated with the advantages of parallel frequency domain search and parallel code phase search. The main procedures of this algorithm are listed as follows:

Step1. Blocking, Double blocking and Zero padding

Blocking: The received signal and the local signal with the correlation integral time of $T$, are divided into $N_{s}$ blocks respectively and each block contains $L_{s}$ data samples.

Double blocking: The adjacent two data blocks of the received signal are combined to form a new data block, that is, the $i$ th block and the $i + 1$ th block are combined into the new $i$ th data subblock $\left( {i = 1,2,3, \cdot \cdot \cdot \cdot \cdot \cdot ,N_{s} } \right)$. Each new data subblock contains $2L_{s}$ data samples.

Zero padding: The new $N_{s}$ local spreading code subblocks are formed by filling the same length of zero after each data block of local signal, each new local spreading code subblock contains $2L_{s}$ data samples.

Step2. Circular correlation

Circular correlation within a subblock: The data subblock of the received signal is circular correlated with the corresponding subblock of local signal, the operation within the subblock is equivalent to the parallel code phase search. The length of subblock for circular correlation is $L = 2L_{s}$. The results of circular correlation only retain the first $L_{s}$ points data in the $2L_{s}$ points.

Subblock shifting: The data of the received signal is block shifted to the left, and then the data subblock of the received signal after shifting is circular correlated with the subblock of local signal, the search is completed when the received signal is shifted $N_{ms} - 1$ times. Finally, a time domain correlation value matrix with the size $N_{s} \times \left( {L_{s} \times N_{ms} } \right)$ is obtained, in which $N_{s}$ stands for possible Doppler frequency offsets and $L_{s} \times N_{ms}$ stands for all possible code phases.

Step3. Detection and decision

After FFT, the time domain correlation value matrix is transformed into the frequency domain correlation value matrix, the energy of all points in the matrix is calculated. The signal is acquired precisely if the maximum in the matrix is greater than the given threshold and the estimated code phase is within a symbol, otherwise acquisition is failed.

3.2 Multi Block Overlapping Zero Padding

The length and the number of the blocks in traditional DBZP are determined by the frequency resolution and the range of Doppler frequency offset. It generally uses the smaller length of block in order to give consideration to the large Doppler frequency offset, however, for the smaller Doppler frequency offset, the shorter circular correlation data will make the acquisition performance lower than the longer block. The MBOZP is proposed in this paper keeping the number of blocks fixed, compared with original DBZP. It can properly increase the length of data subblock so as to obtain higher processing gain. This requires the introduction of data block overlapping, as shown in Fig. 2.

Fig. 2.

Block and zero padding in MBOZP ($L_{s} = 128$)

For MBOZP, the number of block is still $N_{s}$ and the length of each block is still $L_{s}$, the length of data subblock for circular correlation is $L = 2L_{s}$ when the data overlapping is $L_{s}$. The new data subblock of the received signal is obtained by combining the adjacent three blocks and the new subblock of local spread signal is obtained by combining the adjacent two blocks and then added a block of zero with length $L_{s}$, so the length of new subblock is $3L_{s}$; it is required to perform the FFT/IFFT transform with $3L_{s}$ points in circular correlation within a subblock, only the first $L_{s}$ points in the final $3L_{s}$ points are saved.

As shown in Fig. 3, this method is equivalent to the parallel frequency domain search when the section is also overlapping.

Fig. 3.

Data subblock overlap correlation process in time domain

4 The Performance Analysis of MBOZP

The correlation result of MBOZP is equivalent to the parallel frequency search with data overlapping. The acquisition algorithm based on matched filter is on the basis of parallel frequency search, designing a kind of transversal filter by sequence correlation to accomplish the correlation operation and using the FFT to reduce the time of acquisition. The matched filter is divided into a set of short matched filter in PMF-FFT [12], which can reduce the performance of correlation power and decrease the hardware overhead. The blocking and correlation in MBOZP is equivalent to the segmentation and matching in PMF-FFT, thus, the performance analysis of MBOZP can be studied based on the performance of PMF-FFT.

The received signal is shown as (1). Assuming that the noise is ignored, when the received signal is aligned with the local signal, $s\left( {nT_{s} - \tau } \right)s^{*} \left( {nT_{s} - \hat{\tau }} \right)$ is regarded as 1, so the normalized correlation output value of the received signal and the local signal can be expressed as

$$ G_{{_{DMF} }} = \frac{1}{{N_{total} }}\sum\limits_{n = 0}^{{N_{total} - 1}} {r_{n} s^{*} \left( {nT_{s} - \hat{\tau }} \right)} = \frac{1}{{N_{total} }}\left| {\frac{{\sin \left( {\pi f_{d} N_{total} T_{s} } \right)}}{{\sin \left( {\pi f_{d} T_{s} } \right)}}} \right|\exp \left[ {j\pi f_{d} \left( {N_{total} - 1} \right)T_{s} } \right] $$

(2)

The data with $N_{total}$ samples is divided into $N_{s}$ block, each data block has the length $L_{s}$ so the correlation output of the $k$ th block is shown as,

$$ G_{{_{PMF} }} \left( k \right) = \frac{1}{{L_{s} }}\sum\limits_{{n = \left( {k - 1} \right)L_{s} }}^{{N_{s} L_{s} - 1}} {r_{n} s^{*} \left( {nT_{s} - \hat{\tau }} \right)} = \frac{1}{{L_{s} }}\left| {\frac{{\sin \left( {\pi f_{d} L_{s} T_{s} } \right)}}{{\sin \left( {\pi f_{d} T_{s} } \right)}}} \right|\exp \left[ {j\varphi } \right]\exp \left[ {j\pi f_{d} \left( {k - 1} \right)L_{s} T_{s} } \right] $$

(3)

Where $k = \left( {1,2,3, \cdot \cdot \cdot ,N_{s} } \right)$, $\varphi = \pi f_{d} \left( {L_{s} - 1} \right)T_{s}$ represents the phase characteristic of PMF.

Determining $N_{s}$-point FFT for $R\left( k \right)$, the output of the normalized frequency response for $l$ th points is

$$ \begin{aligned} G_{PMF - FFT} \left( l \right) & = \frac{1}{{N_{total} }}\sum\limits_{k = 0}^{{N_{s} - 1}} {G_{PMF} \left( k \right)\exp \left[ {{{ - j2\pi kl} \mathord{\left/ {\vphantom {{ - j2\pi kl} {N_{s} }}} \right. \kern-0pt} {N_{s} }}} \right]} \\ & = \frac{1}{{N_{total} }}\frac{{\sin \left( {\pi f_{d} L_{s} T_{s} } \right)}}{{\sin \left( {\pi f_{d} T_{s} } \right)}}\frac{{\sin \left( {\pi f_{d} N_{s} L_{s} T_{s} - \pi l} \right)}}{{\sin \left( {\pi f_{d} T_{s} L_{s} - \pi \frac{l}{{N_{s} }}} \right)}}\exp \left[ {j\varPhi } \right] \\ \end{aligned} $$

(4)

Where $l = \left( {1,2,3, \cdot \cdot \cdot ,N_{s} - 1} \right)$, $\varPhi = \pi \left( {N_{s} - 1} \right)\left( {f_{d} L_{s} T_{s} - {l \mathord{\left/ {\vphantom {l {N_{s} }}} \right. \kern-0pt} {N_{s} }}} \right)T_{s} - \pi f_{d} \left( {L_{s} - 1} \right)T_{s}$ represents the phase characteristic of PMF-FFT.

Accordingly, the final normalized amplitude frequency response is

$$ G_{PMF - FFT} \left( {f_{d} ,l} \right) = \left| {\frac{{\sin \left( {\pi f_{d} L_{s} T_{s} } \right)}}{{L_{s} \sin \left( {\pi f_{d} T_{s} } \right)}}} \right|\left| {\frac{{\sin \left( {\pi f_{d} N_{s} L_{s} T_{s} - \pi l} \right)}}{{N_{s} \sin \left( {\pi f_{d} L_{s} T_{s} - \pi \frac{l}{{N_{s} }}} \right)}}} \right| = G_{1} \left( {f_{d} ,l} \right) * G_{2} \left( {f_{d} ,l} \right) $$

(5)

where $G_{1} \left( {f_{d} ,l} \right) = {1 \mathord{\left/ {\vphantom {1 {L_{s} }}} \right. \kern-0pt} {L_{s} }}\left| {{{\sin \left( {\pi f_{d} L_{s} T_{s} } \right)} \mathord{\left/ {\vphantom {{\sin \left( {\pi f_{d} L_{s} T_{s} } \right)} {\sin \left( {\pi f_{d} T_{s} } \right)}}} \right. \kern-0pt} {\sin \left( {\pi f_{d} T_{s} } \right)}}} \right|$ is the attenuation which is caused by the process of correlation, the output correlation value shows significant attenuation when the larger Doppler frequency offsets exist in received signal. $G_{2} \left( {f_{d} ,l} \right) = \left| {{{\sin \left( {\pi f_{d} N_{s} L_{s} T_{s} - \pi l} \right)} \mathord{\left/ {\vphantom {{\sin \left( {\pi f_{d} N_{s} L_{s} T_{s} - \pi l} \right)} {N_{s} \sin \left( {\pi f_{d} L_{s} T_{s} - \pi \left( {{l \mathord{\left/ {\vphantom {l {N_{s} }}} \right. \kern-0pt} {N_{s} }}} \right)} \right)}}} \right. \kern-0pt} {N_{s} \sin \left( {\pi f_{d} L_{s} T_{s} - \pi \left( {{l \mathord{\left/ {\vphantom {l {N_{s} }}} \right. \kern-0pt} {N_{s} }}} \right)} \right)}}} \right|$ is caused by incomplete phase compensation in FFT operation, which gets the maximum value when $l = L_{s} f_{d} N_{s} T_{s}$. This indicates that the acquisition sensitivity is decided by the length and the number of data blocks, when the length of data block is fixed, increasing number of data block can improve the estimation accuracy of Doppler frequency offset and code phase.

5 Simulation Analysis

5.1 The Influence of the Length of Data Block and Doppler Frequency Offset

The search range of Doppler frequency offset changes when the number of data block changes in DBZP, so the acquisition sensitivity is influenced by $f_{d}$, $L_{s}$, and $N_{s}$. The influence of different numbers of data block acquisition sensitivity under different frequency offsets is given in Fig. 4. The search range $B_{{f_{d} }} = \left( { - 4\,\text{KHz},\, + 4 \;\text{KHz}} \right)$, $L_{s} = 128$. The search range of Doppler frequency will halve while the length of block doubles.

Fig. 4.

The influence of block length on acquisition performance under different frequency offset

Figure 4 presents the influence of changing block length on acquisition performance under different frequency offsets. Figure 4(a) is the normalized gain of correlation output at different block length. It is seen that the larger Doppler frequency offsets will cause the attenuation of the output correlation value, when the block length is increasing, the search range of the corresponding frequency offsets will narrow. The detection probability under different block length is given in Fig. 4(b), where $f_{d}$ is 100 Hz, 800 H and 1500 Hz. We can see that when the frequency offset is small, the higher detection probability can be obtained with longer block length, however, with the increase of the frequency offset, the long data correlation is affected by the Doppler offset. In summary, in the choice of the length and numbers of data block, the search range and Doppler frequency offset should be considered first. We can choose the long data block with small correlation loss when the frequency offset is small.

5.2 The Blocking Method

The detection probabilities under the different blocking methods are compared in Fig. 5, where $L_{s}$ is the block length, $N_{s}$ is the number of data block and $L$ is the length of data subblock for circular correlation which is equivalent to the length of piecewise summation in PMF-FFT. Figure 5(b) shows the detection probability corresponding to frequency parallel search algorithm. It can be seen that the correlation result of DBZP is absolutely equivalent to the frequency parallelize search from Fig. 4(a), we have seen that the correlation value is less vulnerable to small frequency offsets, the acquisition sensitivity is higher when the block length is longer, thus, the acquisition sensitivity can be improved by increasing the block length when the Doppler frequency offset is small, such as $f_{d} = 100\;\text{Hz}$.

Fig. 5.

The detection probability under the different block method

It can also be seen from Fig. 5 that the acquisition sensitivity of MBOZP is the highest. From the normalized amplitude frequency response we see that acquisition sensitivity is codetermined by $N_{s}$, $L_{s}$ and $f_{d}$. We assume that $f_{d}$ is $100\,\text{Hz}$, for BM3(MBOZP with $L_{s} = 128$, $N_{s} = 160$ and $L = 256$) and BM1(DBZP with $L_{s} = 128$, $N_{s} = 160$ and $L = 128$), the numbers of data block are the same, but the length of data subblock for MBOZP increases, so its detection probability is higher. The length of data subblock for BM2 and BM3 remains the same, but the number of data block for BM3 increases because of the data overlapping, so that the MBOZP gets higher detection probability. From above, the acquisition sensitivity of MBOZP is improved by 1 dB at small frequency offsets.

Figure 6 is the acquisition performance of MBOZP and DBZP under different frequency offsets.

Fig. 6.

The influence of frequency offset on acquisition performance

We can see that the performance of MBOZP is better than DBZP at small frequency offsets, however, the acquisition performance of MBOZP decreased faster than DBZP by increasing the frequency offsets. In other words, MBOZP is sensitive to frequency offset. This indicates that MBOZP is more suitable for fine estimation with small frequency offset. In practice, we can use DBZP to estimate the frequency offset firstly and obtain the coarse estimation of frequency offset, then, we can use MBOZP to improve the acquisition performance while the frequency offset is small.

5.3 Complexity Analysis of MBOZP

In this section we will analyze the computation complexity. Parallel frequency search algorithm includes multiplication, piecewise summation and FFT, and the algorithm shown in Fig. 3 adds data overlapping based on parallel frequency. DBZP includes double blocking, zero padding, FFT and IFFT, MBOZP changes the combination of data subblock, the overlapping data makes the length of data subblock for circular correlation increase.

Table 1 shows the computational complexity of several acquisition algorithms based on real multiplication and real addition.

Table 1. Computational complexity of several acquisition algorithms

We assume that $f_{s} = 1.024\,\text{MHz}$, $N_{s} = 160$, $L_{s} = 128$, $N_{ms} = 8$, therefore, the real addition of parallel frequency search algorithm is 8.36e7 and the real multiplication is 8.39e7; if introduced the data overlapping in this algorithm, its real addition becomes 1.26e8 and its real multiplication remain the same. The real addition and real multiplication of DBZP are 1.02e7 and 7.21e6 respectively; while for MBOZP, its real addition becomes 1.65e7 and its real multiplication becomes 1.19e7.

Compared with parallel frequency search algorithm, when the data overlapping is introduced, its real addition rises by 33.7% and its real multiplication keeps unchanged. Its real addition and real multiplication of MBOZP rise by 38.2% and 39.4% compared with DBZP. This shows that the data overlapping will cause the increase of computation.

Compared to the capture algorithm in single frequency domain, the computation of MBOZP and DBZP decrease significantly. When $L_{s} = 128$, compared with the parallel frequency search algorithm, the real addition and real multiplication computation of DBZP are reduced by 87.8% and 91.4%, that of MBOZP are reduced by 86.9% and 85.8%, which means multi block combination acquisition algorithm in dual frequency domain has lower computation complexity.

From the foregoing, the acquisition sensitivity of algorithm based on DBZP is higher than the algorithm in single domain frequency, and its computation is lower; the smaller frequency offsets lead to the longer block length, the lower computation and the higher acquisition sensitivity. While MBOZP increases the acquisition performance by sacrificing computation, however, this sacrifice is acceptable.

6 Conclusion

Considering the problem of weak signal acquisition in spread spectrum communication systems, the acquisition performance is improved by MBOZP algorithm. Theoretical analysis and simulation results show that data block overlapping can achieve more accurate acquisition sensitivity without increasing too much complexity. However, the proposed algorithm is effective in engineering applications.