Weak GPS signal acquisition method based on DBZP

WANG Jianing,LIAN Baowang,and XUE Zhe

1.School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710072,China;2.Xi’an Modern Control Technology Research Institute,Xi’an 710065,China

1.Introduction

Nowadays,more and more global positioning system(GPS)applications[1]have created a high demand for weak signal acquisition capabilities,especially in dense urban environments.Long coherent integration time and more incoherent integration steps are efficient ways to improve the acquisition performance for weak GPS signals.However,the unknown data bits and edges limit the coherent integration time,and increase the number of Doppler bins to be searched.

In general,longer acquisition time is required to detect weak signals.Therefore,for fast acquisition of weak signals,a conventional receiver needs to utilize very massive correlators.Double block zero padding(DBZP)[2,3]is an approach to processing long data coherently with fewer operations.It uses a frequency domain method to search over a delay-Doppler space and acquire GPS signals.However,the presence of 50 Hz data bitmessages andunknown satellite Doppler shifts limit the ability of DBZP to detect weaker signals.The modified DBZP(MDBZP)algorithm[4]is introduced to solve this problem.Without assuming the availability of any assisting bit edge information,the MDBZP algorithm calculates every possible data bit combination to eliminate data bit transitions,so its calculation costs remain high.A fast MDBZP(FMDBZP)algorithm was described in[5]which eliminated redundant fast Fourier transform(FFT)computations.However,FMDBZP still needs to calculate each possible data bit combination,resulting in large memory requirements.A method based on the Viterbi algorithm theory[6],the optimal path search method(OPSM)for the improved FMDBZP algorithm(IFMDBZP),reduces the computational operations and saves memoryspace.Nevertheless,the memory and searching costs are still high overhead GPS receivers.The differentially coherent combing(DCC)detection scheme was discussed in[7–10].This scheme can suppress the effect of the Doppler shift,but the correlation peak is severely attenuated due to the multiplication of noisy signals at alow signal-to-noiseratio(SNR).A DBZP differential coherent method for acquiring weak GPS signals was describedin[11],but it neglected to mention how the multiplication loss may be reduced.

The application of the discrete cosine transformin wireless telecommunicationhas recently attracted considerable attention for its energy compaction property[12–15].A partial matched filter-discrete cosine transform(PMF-DCT)code acquisition algorithm based on DCT domain filtering was detailed in[16].The PMF-DCT method utilises DCT domain filtering and inverse DCT(IDCT)reconstruction to reduce the noise power and improve detection performance,but this method is only suitable for low frequency uncertainty cases.

To take advantage of the above-mentioned algorithms and overcome their disadvantages,this paper proposes a DCT domain filtering based differentially DBZP(DFDD)algorithm.The remainder of the paper is organized as follows.Section 2 introduces the implementation of the DBZP signal module.In Section 3,the DFDD is proposed,then a theoretical performance analysis is detailed.Some example test results are presented in Section 4.The conclusions follow in Section 5.

2.GPS signal model and DBZP procedure

The signal of GPS L1 C/A code is direct sequence spread spectrum(DSSS)code sequence modulated by binary phase shift keying(BPSK).Here,for simplicity,only the desired satellite signals are considered.Therefore,the received GPS signals mixed to the basebandr(n)can be represented in the following simplified digital form:

where A is the signal amplitude,D is the navigation data,C is the C/A code of satellite,τ is the code delay,fdis the Doppler shift,φ is the initial phase of satellite,w(n)is the complex white Gaussian random variable with zero mean and variance σ2=N0/2TS,N0is the single-side noise power spectral density(PSD),and TSis the sampling interval.

The DBZP calculates the coherent integration result in the frequency domain.It divides the received N milliseconds baseband signals into blocks of size Nms,where Nmsis the number of samples in one millisecond.Each Nmssized block signal and the local replica code are subdivided in to Nstepsub-blocks of size Bsize.Then a circular correlation is carried out between double-block processed 2Bsizesized received GPS baseband signals and the zero padded processed local replica signals to obtain the matrixCI.

In the matrixCI,the column elements S(k)have the following form:

where R(τ)is the correlation result of the pseudo random noise(PRN)code,D(τ)is the databit,φ′= πfdTsBsize+φ,w(k)is the complex white noise with zero mean and variance σ20=Bsizeσ2.The S(k)components have the form of a complex sinusoidal signal;if the noise component is neglected,then the fast Fourier transform(FFT)operation generates an estimate of the Doppler frequency.

As the coherent integration period extends beyond 20 ms,the data bit sequence should be taken into account.MDBZP and the FMDBZP algorithms are proposed to overcome the problem of the data bit transit.The MDBZP and FMDBZP algorithms divide theCIcolumns into several possible data bit edges and consider the different combinations of the bit,then wipe off the unknown data bits.Both algorithms require a large number of FFT operations to calculate the possible bit edges and obtain the matrixCIdb(an extended matrix ofCI,which contains all the possible data bit combinations,see[5]),and these processes need significant memory to store the results for the following incoherent integration.

3.DFDD algorithm for code acquisition

3.1DCC

The DCC approach was firstly suggested in[7]for the acquisition of DSSS signals.Denoting S(k)the kth result of the coherent correlator,the differentially coherent product is formed as

where S∗denotes the complex conjugate of S.The DCC utilizes differential phase information between successive correlator outputs to achieve a higher correlation gain.(It can be seen that each element of the matrixCIin the same column is a correlator output whose correlation integration time is BsizeTswith the same code delay τ.)The Λ(k)eliminates the phase and frequency uncertainty.Subsequently,a differentially coherent result can be accumulated to improve the detection performance.According to[9],under hypothesis H0,when k=1,Λ(k)has a central distribution of χ2with two degrees of freedom(d.o.f.).Therefore,Λ(k)is a central distribution of χ2with a 2(N·Nstep-1)d.o.f.and the decision statistic is given by the following form:

whereσ2=N·NstepandΓ(K)is the Gammafunction:

Under hypothesis H1,the decision statistic is approximately a non-central χ2random variable with a distribution of

where λ is the non-centrality parameter and

is the mean value of the decision statistic,Iν(·)is the νth order modified Bessel function of the first kind.The frequency shift fdcan be calculated by the following equation:

The basic principle is that there will be a high degree of correlation between the phases of successive correlator outputs,when the received signal is synchronized with the local replica code,but they will be essentially independent under the influence of noise alone.In a DCC system with 20ms integration period and under a 1.023MHz sample rate,the loss incurred by data bit transitions is about 0.5 dB,compared with a maximum 3 dB loss by DBZP without data bit truncation.The DCC reduces the square loss to some extent compared with the incoherent integration and the study[10]indicates that DCC outperforms the incoherent integration by about 1.5 dB.Since the DCC is insensitive to data bit transitions,a long integration period could be employed to improve the acquisition performance.

3.2 DCT domain filtering

DCT is often used in signal and image processing,especially for lossy compression,because it has a strong“energy compaction”property.In typical applications,most of the signal information tends to concentrate on a few low-frequency components in the DCT domain sequence.A DCT-based method for GPS signal acquisition was proposed in[16].After the PMF operation,the power centralized property of DCT was utilized to filter some part of the noise power and improve the acquisition performance.The DCT domain low-pass filtering can be represented as

where XDCT(k)is the transform result of the sequence x(n).After processing by DCT,the signal power will only be concentrated on the lower ordercomponent.In contrast,the noise part which is a complex Gaussian white noise will be evenly distributed throughout the whole band.This implies that the noise parts transformed at a higher order of XCcan be neglected,thus the noise is greatly reduced and the signal has almost no loss.After IDCT processes XCpoints of the X′DCT(k),the new outputs will have the noise reduced by

When the DCT domain filtering and IDCT reconstruction have been completed,the noise can still be approximated to complex Gaussian white sequence with zero mean and variance σ20.The resulting signal is almost lossless,but the total noise power is reduced from XNσ20to XCσ20.Thus,the signal to noise ratio(SNR)will be improved by a ratio of XN/XC,then both the detection performance and accuracy of frequency estimation will be improved.

The developments in[16]are only suitable for the relock situation,since the frequency offset is negligible.If the Doppler frequency offset is large enough,the DCT domain low pass filtering(LPF)may filter some part of the signal leading to some loss of signal power.

A new acquisition method that takes advantage of the above methods is proposed in the following section.

3.3 A new DFDD algorithm

The column elements in the matrixCIcan be modeled as a single sinusoidal vector.Here,instead of calculating the column-wise FFT,a differential operation is inserted to reduce the storage and hardware cost,then a DCT domain LPF and IDCT are calculated to reduce the noise power.The entire procedure is shown in Fig.1.

Fig.1 DFDD code acquisition algorithm diagram

The entire algorithm consists of the following steps:

Step 2The DBZP operation is carried out between the received baseband signal and the local code replica to ge-nerate the matrixCI;

Step3Obtain the ith (the initial value of i is 0) column wise elements Si(k)of theCImatrix.The DCC operation is applied to vector Si(k)and the differential vector Λi(k)is produced;

Step 4Λi(k)is processed by DCT and produces the DCT domain vectorDCTi(k);

Step 5The DCT domainLPF andIDCT reconstruction are carried out to obtain thek);

Step 6(k)is handled by incoherent integration to generate the decision statistic||;

Step 7Let i=i+1,and switch to Step 3 until i=Nms-1,then check the decision statistic vector||(i=0,1,...,Nms-1)to decide whether the signal is present.

3.4 Performance analysis

3.4.1 Code acquisition threshold calculation

It is known that the detection threshold is usually calculated from the constant false alarm rate(CFAR)assumption,which means that the false alarm probability Pfais set to be constant and thus the decision threshold VThcan be determined by Pfa.When Pfais given,we can obtain the corresponding threshold.Pfais defined as the probability that the decision metric exceeds the threshold VTh,when no signal is present.Since there are Nmscode phases to be searched and the decision metrics(i=0,1,...,Nms-1)are assumed independent to each other[16],the total false alarm probability is calculated as

As mentioned above,under H0,the decision statisticis a central χ2distribution with 2XN=2(N ·Nstep-1)d.o.f.After filtering by the DCT domain LPF,the d.o.f.of the decision statistic decreases to 2XC,0＜2XC≤2XN.Then the cumulative distribution function(CDF)of Λ′iis given as

When Pfathe approximate Taylor expansion metric(1-x)N≈1-Nx is employed to obtain the final false alarm probability:

From(13),we can find that it is difficult to get the closed form solution of detection threshold VTh.Thus a look-uptable method can be employed to acquire the VTh,for a given Pfa.

3.4.2 Detection performance under additive white Gaussian noise(AWGN)channel

Under hypothesis H1,recall that the output of the differential detector is a non-central χ2distributed random variable with 2XNd.o.f.and non-centrality parameterλ.After the DCT domain LPF,the decision statistic Λ′ifollows a non-central distribution with 2XCd.o.f.with a probability distribution function(PDF)given by

where QK(a,b)is the Kth order Marcum Q-function.According to the above procedure,the d.o.f.is reduced to 2XC.For a constant false alarm probability,the detection threshold will be decreased and the detection probability will be increased.This theoretical result is illustrated by a simulation study that follows.

4.Simulation and analysis

In this section,the results of numerical(Matlab)simulations are described,which compare the performance of the DFDD algorithm(proposed in Section 3),the widelyused FMDBZP and the differential DBZP algorithms(DBZP-DCC)algorithms.

For simplicity,the signal generator generates the baseband GPS signal with the sampling frequency fS=2.048 MHz,The carrier-to-noise density ratio(C/N0)varies for different signal data.For signal acquisition using FMDBZP,DFDD and DBZP-DCC(see[11]),the coherent integration time N is set to 80 ms(Ndb=4),the number of possible navigation bit edge Nbe=10,the number of incoherent integration NTI=4(that is,the incoherent time is 320 ms),and the Doppler frequency shift search range[–500 Hz,500 Hz].The number of Doppler frequency search bins and the number of code phase search points are calculated to be 80 and 2 048,respectively.

ForC/N0=24dB/Hz,the codeshift is 205.5,the signal acquisition results from the DFDD and DBZP-DCC algorithms are shown in Fig.2.According to the figure,the peak position is in 1 539,that is,under the DFDD and DBZP-DCC algorithms,the received signals are moved forward.Note that Matlab has a fixed count shift from 0 to 1,so the results are transformed by(2048-1539+2)/2=205.5.It is found that both algorithms could correctly estimate the code phase,but the DFDD algorithm produces a lower noise power level compared with the DBZP-DCC.It is because after the DCT low-pass filtering and IDCT reconstruction,the noise power is reduced,but the signal power is almost lossless.

Fig.2 Acquisition comparison of the DFDD and DBZP-DCC

4.1 False alarm probability and detection performance

As described in section 3.4.1,for a given false alarm probability Pfa,the detection threshold VThof the DFDD algorithm can be calculated by metric(11),the detection threshold of FMDBZP can be calculated in[5],and the threshold of DBZP-DCC could be obtained through[11].A plot of false alarm probabilities versus C/N0based on the afore-mentioned thresholds is provided in Fig.3.The figure shows for the DFDD algorithm,there is an excellent agreement between the simulation results and the given Pfa=0.02.

Fig.3 Comparison of the false alarm probability

The above results demonstrate the validity of the DFDD method.A further simulation study is described below,which is based on the same signal and Pfaconditions.

The FMDBZP algorithm is widely used in weak GNSS signal acquisition applications.After the circular correlation,the Zoom-FFT(ZFFT)operation is a convenient way to estimate the frequency offset,but,when the frequency offset falls in between the two FFT bins,a power loss will occur.The resolution fresof the FFT depends on the total coherent integration time N,and in this paper fres=1 000/N=1 000/80=12.5 Hz

The proposed DFDD and DBZP-DCC algorithms described in Section 3,are both aimed at improving the global navigation satellite system(GNSS)signal acquisition performance.Fig.4(a)and Fig.4(b)show the simulation results for these algorithms with different frequency offsets under an AWGN channel assumption.In Fig.4(a),the frequency offset is set to 0 Hz,in order to simulate the conditions when the frequency offset is close to spectrum lines,and the FFT peak matches the true Doppler frequency.As shown in the figures,the FMDBZP could get an accurate result for the frequency estimation,the signal acquired by FMDBZP has an additional gain of about 0.8 dB compared with DBZP-DCC(Pd=0.9),and DFDD has an almost the same performance as FMDBZP.

Fig.4 Comparison of detection performance of three algorithms in different Doppler frequencies

Fig.4(b)compares the performance of the above algorithms with the Doppler frequency set to 130 Hz,It can be seen that DFDD outperforms the DBZP-DCC and FMDBZP algorithms.And,the DFDD has a 1.5 dB additional gain compared with FMDBZP(Pd=0.9)and a 0.8 dB additional gain compared with DBZP-DCC.That is because the frequency offset 130=10fres+5 Hz,which means that the frequency offset falls in the almost half of the FFT bin resolution,the correlation peak will be attenuated by the FFT operation.In contrast,after DCT domain filtering and IDCT reconstruction,a coherent integration method is employed.The frequency offset has little influence on the DFDD and DBZP-DCC algorithms,due to the noise reduction caused by DCT domain filtering.Thus,the DFDD algorithm has a better detection performance compared with other algorithms.

A signal generator synthesizing GPS signals with a random Doppler frequency offset in[–500 Hz,500 Hz]under an AWGN channel assumption is introduced to test the algorithms mentioned above.The simulation results are shown in Fig.4(c).It can be seen that DFDD exhibits 0.7 dB more sensitivity than FMDBZP(Pd=0.9)and 0.9 dB more gain compared to DBZP-DCC.

Fig.5 compares the frequency estimation performance of the DFDD and DBZP-DCC algorithms,since both of them use the same metric(8)to estimate the frequency offset.A total coherent time of 320 ms is assumed with 200 Hz and 400 Hz initial Doppler error conditions.Fig.5(a)and Fig.5(b)shows that the average frequency acquired by the DFDD is more accurate and robust than that of DBZP-DCC,and it also shows with a larger initial frequency offset and a lower C/N0,both algorithms have a larger estimation error,and when the C/N0is larger than 28 dB/Hz,the estimation performance is almost the same.It appears that the DFDD algorithm has a smaller frequency estimation standard deviation than the DBZP-DCC,which means that the accuracy of frequency estimation for the DFDD algorithm is higher than the DBZP-DCC.When the C/N0is set as 20 dB/Hz,the DFDD has a 34%improvement compared with DBZP-DCC.This improvement arises because the DCT domain filtering and IDCT reconstruction processes reduce the noise level.

Fig.5 Comparison of frequency estimation performance

4.2 Complexity analysis and comparison

After obtaining theCImatrix,there are still Ndbnavigation data bits in the column elements to be eliminated.FMDBZP needs a series of FFTs(ZFFTs for FMDBZP)to estimate the possible combinations of Ndband Nbe(the number of possible data bits). The proposed algorithm only needs an extra multiplier,and a series of DCT and IDCT transforms.

Table 1 shows a general computational cost comparison of the three algorithms,since all the three methods have the same circular correlation procedure,the main difference in these methods occurs after the DBZP operation,so the calculation cost of the DBZP procedure is ignored here.For simplicity,only FFTs and storage consumption are compared here.Since one single DCT and IDCT operation could be calculated by two FFTs or two IFFTs and operation,according to the analysis in Table 1,the DFDD algorithm needs less computation and memory space compared to the FMDBZP.The improvement DFDD compared with FMDBZP is that FFT isand the storage improvement is

Table 1 Comparison of calculation costs

4.3 Mean acquisition time(MAT)

Since the general acquisition system is based on the cross ambiguity function(CAF),for simplicity,the single-dwell and maximum search strategy is used here.Thus the MAT could be calculated[17]as follows:

where TCAFis the time spent to evaluate the whole CAF;TPis the penalty time due to the false alarm.Therefore,recall the DFDD structure in Fig.2,when the C/N0is 23 dB/Hz,with Pfa=0.02 and Pd=0.9,the DFDD in terms of MAT is 46.8 s,while the FMDBZP is 53.4 s and the DBZP-DCC is 59.3 s.

5.Conclusions

In this paper we introduce a modified GNSS signal acquisition algorithm based on DCT domain filtering and DCC technique.By combining the DCC technique,the proposed algorithm can acquire weak GNSS signals without any other assist information.This algorithm requires less computation and less memory during the coherent integration steps.Through DCT domain filtering and IDCT reconstruction,part of the noise power is eliminated and the signal has almost no loss.Hence,the SNR of detected signals is improved.Simulation results are discussed which demonstrate that the proposed algorithm has a better code acquisition performance at the same false alarm probability.

[1]KAPLAN ED,HEGATRY C J.Understanding GPS principles and applications.2nd ed.Norwood:Artech House,2006.

[2]LIN D M,TSUI L B Y.Comparison of acquisition methods for software GPS receiver.Proceedings of ION GPS,2000:2385–2390.

[3]TSUI J B Y.Fundamentals of global positioning system receivers:a software approach.2nd ed.Hoboken:Wiley-Interscience,2004.

[4]ZIEDAN N I,GARRISON J L.Unaided acquisition of weak GPS signals using circular correlation or double-block zero padding.Proc.of Position Location and Navigation Symposium,2004:461–470.

[5]HECKLER G W,GARRISON J L.Implementation and testing of an unaided method for the acquisition of weak GPS C/A code signals.Navigation,2009,56(4):241–259.

[6]ZHANG W,GHOGHO M.Computational efficiency improvement for unaided weak GPS signal acquisition.Journal of Navigation,2012,65(2):363–375

[7]ZARRABIZADEH M H,SOUSA E S.A differentially coherent PN code acquisition receiver for CDMA systems.IEEE Trans.on Communications,1997,45(11):1456–1465.

[8]IINATTI J,POUTTU A.Differentially coherent code acquisition in jamming and data modulation.Proc.of the IEEE Military Communications Conference,1999:579–573.

[9]SHANMUGAM S K,WATSON R,NIELSEN J,et al.Differential signal processing schemes for enhanced GPS acquisition.Proc.of the 18th International Technical Meeting of the Satellite Division,2005:212–222.

[10]SCHMID A,NEUBAUER A.Performance evaluation of differential correlation for single shot measurement positioning.Proc.of the 17th International Technical Meeting of the Satellite Division of the Institute of Navigation,2004:1998–2009.

[11]MO J W,OUYANG S,XIA H L,et al.GPS signal acquisition algorithm based on DBZP differential coherent.Journal of Systems Engineering and Electronics,2012,34(6):1085–1089.

[12]KOBAYASHI H,MORI K.Proposal of OFDM channel estimation method using discrete cosine transform.Proc.of the IEEE Personal,Indoor and Mobile Radio Communications,2004:1797–1801.

[13]KUMAR A A,MAKUR A.Improved coding-theoretic and subspace-based decoding algorithms for a wider class of DCT and DST codes.IEEE Trans.on Signal Processing,2010,58(2):695–708.

[14]GAO X Q,JIANG B,YOU X H.Efficient channel estimation for MIMO single-cattier block transmission with dual cyclic for MIMO time slot structure.IEEE Trans.on Communications,2007,55(11):2210–2223.

[15]KIM S,YU H,LEE J,et al.Low bias frequency domain SNR estimator using DCT in mobile fading channels.IEEE Trans.on Wireless Communications,2009,8(1):45–50.

[16]LI XJ,XULP,SONGSB,et al.DCT domain filtering method for multi-antenna code acquisition.Journal of Systems Engineering and Electronics,2013,24(5):734–741.

[17]ZHU C,FAN X.A novel method to extend coherent integration for weak GPS signal acquisition.IEEE Communications Letters,2015,19(8):1343–1346.