Two-step compressed acquisition method for Doppler frequency and Doppler rate estimation in high-dynamic and weak signal environments

WU Chao ,LIU Erxiao ,and JIAN Zhihua

1.School of Communication Engineering,Hangzhou Dianzi University,Hangzhou 310018,China;2.School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710082,China

Abstract:To acquire global navigation satellite system (GNSS)signals means four-dimension acquisition of bit transition,Doppler frequency,Doppler rate,and code phase in high-dynamic and weak signal environments,which needs a high computational cost.To reduce the computations,this paper proposes a twostep compressed acquisition method (TCAM) for the post-correlation signal parameters estimation.Compared with the fast Fourier transform (FFT) based methods,TCAM uses fewer frequency search points.In this way,the proposed method reduces complex multiplications,and uses real multiplications instead of improving the accuracy of the Doppler frequency and the Doppler rate.Furthermore,the differential process between two adjacent milliseconds is used for avoiding the impact of bit transition and the Doppler frequency on the integration peak.The results demonstrate that due to the reduction of complex multiplications,the computational cost of TCAM is lower than that of the FFT based method under the same signal to noise ratio (SNR).

Keywords:high-dynamic and weak signal environment,compressed acquisition,frequency parameters estimation.

1.Introduction

Global navigation satellite system (GNSS) signal acquisition plays a very important role in the software defined receiver (SDR),and Doppler frequency and code phase should be estimated in this stage for location-based services (LBSs). In the GNSS-challenged environments[1−3],a fast acquisition method with low computational complexity [4−7] is needed.Furthermore,with integration time increasing,the acquisition may need four-dimension detection of bit transition,Doppler frequency,Doppler rate,and code phase.

Compared with the fast Fourier transform (FFT)-based method [8],the method in [9] compressed code phases to realize the fast acquisition.To further reduce the computational complexity,the Doppler frequency and code phase two-dimension compress method [10] has been proposed.However,those methods [9,10] ignore the effect of bit transition on the integration peak.To solve the problem,Zhu et al11] proposed the weak acquisition method extending the coherent integration time to one entire navigation data bit duration based on FFT.To reduce the computational burden,Kong et al12] proposed the synthesized Doppler frequency hypothesis testing(SDHT) method,which reduced the number of Doppler frequency searches.However,the impact of the Doppler rate on integration is not considered in the SDHT,which is an important factor for integration peak detection in high-dynamic acquisition [13−15].

For acquisition in the high-dynamic and weak signal environments [16,17],four-dimension detection of bit transition [18,19],Doppler frequency[20],Doppler rate,and code phase is needed [21],which costs more computational burdens compared with the two-dimension acquisition.Frequency parameters estimation includes Doppler frequency and Doppler rate estimation.Due to the reason that frequency parameters interact with each other,the differential process [22−25] can be used.To reduce the computational burden in the high-dynamic and weak signal environments,Yang et al21] proposed a block accumulating semi-coherent integration of the correlations method (BASIC).Regardless of bit sign transition,Luo et al26] proposed the post-correlation signal parameters estimation method based on the fractional Fourier transform (FRFT) for high-dynamic signals.The probability of bit transition is analyzed for improving the detection probability in [27]. Since discrete chirp-Fourier transform (DCFT) can be used to improve the L5 signal acquisition detection probability [28],we proposed a block zero-padding method based on DCFT for parameter estimation in weak signals and high dynamic environments in [29].In this way,the post-correlation signal is coherently post-integrated with the bit sequence stripped off,and the high dynamic parameters are precisely estimated using the threshold set based on a false alarm probability [30,31].However,DCFT costs a lot of computations,the detection efficiency needs to be further improved.

To further reduce the computational complexity in highdynamic and weak signal environments,the two-step compressed acquisition method (TCAM) has been proposed in this paper.In the simulated test,because mean acquisition computation (MAC) contains the effect of detection performance and computational complexity on the acquisition method,MAC is chosen as the assessment criteria of acquisition efficiency.Since TCAM has compressed the number of frequency parameters search and reduced complex multiplications,the computational cost of TCAM is lower than that of the FFT based method under the same signal to noise ratio (SNR).

This paper is organized as follows.Firstly,the high-dynamic post-correlation signal model is derived.Then,to avoid effect of bit sign,Doppler frequency and Doppler rate on the detection peak,the differential process is depicted. Moreover,TCAM for Doppler frequency and Doppler rate estimation have been proposed.The detection probabilities and MAC of TCAM are derived and analyzed.Finally,the tests for acquisition performance comparison are proposed.

2.Signal model

In the absence of noise,the received intermediate frequency (IF) signal can be modeled as

whereArepresents the amplitude of the IF signal,Cτ(·)represents the pseudorandom code with initial code phase τ,B(·) represents the bit sign,fIrepresents IF,fdreprese nts the Doppler frequency,α0represents theDoppler r ate,Ttrepresents the sampling interval of digital IF,and ς0represents the initial phase.The local code can be constructed as

wherefkf=2kf Mf∆f,where ∆f=1/(2T) withTbeing the integration time (IT) andMfrepresents the compression factor of the Doppler frequency,kf=−Kf,−Kf+1,···,Kfrepresents the search index.Considering the c ode phase and the Doppler frequency,the post-correlation signalR(n) can be expressed as

3.Proposed method

In this section,to estimate the frequency parameters (f0andα) efficiently,the two compressed processes have been stated for avoiding the interaction among bit sign,Doppler frequency and Doppler rate respectively.Then,the parameters estimation method based on combining the two processes has been proposed.

3.1 Compressed Doppler rate estimation process

The differential process [25] can be performed,and the differential signald(nd) can be written as

wherend=b0,b0+1,···,Ns−NB+b0−1,b0=0,···,NB−1,andNBrepresents the number of samples per bit period,φ0=jπNsTsAα=

Now α0can be solved by Doppler rate search.Assuming thatLα(nd,αk) is the local signal,it can be written as

where αkα=2kαMα∆α,kα=−Kα,···,Kα−1,Kαrepresents the search index,Mαrepresents the compression factor of the Doppler rate,and Δαis the estimation accuracy of the Doppler rate.

wheren1=1,···,NS B,NSB=Ns/NB−1,and Γ1=kα.For detecting the bit transition position,it is assumed that φ(d,b0) can be written as

whereD=[Dk],k=1,···andbgf1,−1g.The detection variableJ1for Doppler rate estimation detection can be written as

3.2 Compressed Doppler frequency estimation process

The parameter α0and bit transition of signalR(n) can be estimated by Doppler rate search. Then,the signal φ2for the compressed frequency estimation process can be modeled as

Based on the integration process,detection variableJ2for Doppler frequency estimation corresponding toi0can be written as

Then,the detection process based on (14) should be repeated untilJ2≥T2.Based on (16),only real additions and real multiplications are needed compared with complex multiplications used by (3),and Doppler frequency accuracy can be improved.Moreover,andcan be obtained from memory,andcan be calculated in advance,which will not cost computation in the acquisition process.Moreover,is the periodic function with the period.ThusJ2for Doppler frequency estimation corresponding tocan be written as

3.3 TCAM for Doppler frequency and Doppler rate estimation

The TCAM has been shown inFig.1,and can be depicted with more details as follows.

Step 1In the presence of noise,the received postcorrelation signalRs(n) can be modeled as

where both the real part and the imaginary part ofw(n)obey a normal distribution with mean value 0 and varianceσ2.Then,same as the process of (6),the differential signal(nd) can be obtained,and(nd,Γ1) can be obtained based on (8),where Γ1=kα.Furthermore,based on (9) to (11),the integration process can be performed,and the detection variableJ1for Doppler rate estimation detection can be obtained.IfJ1is bigger than the set thresholdT1,the bit transition positondsand estimated Doppler ratecan be obtained.Otherwise,h1=h1+1,and the improvement of search accuracy of the Doppler rate should be performed based on (12).InFig.1,φ1(h1,g1),φ1(h1,g1+0.5),and φ1(h1,g1+1) represent(nd,kα+in the presence of noise,respectively.Ifh1>andJ1

Fig.1 TCAM diagram

Step 2If the bit transition positondsand the estimated Doppler ratecan be obtained from Step 1,Step 2 should be performed.Based ondsandR2can be obtained after processingRs(n):

Based on (14),the integration process can be performed,and the detection variableJ2for Doppler frequency estimation detection can be obtained.IfJ2is bigger than the set thresholdT2,the estimated Doppler frequencyf0can be obtained.Otherwise,h2=h2+1,and the improvement of search accuracy of the Doppler frequency should be performed based on (16).InFig.1,φ2((h2,g2),φ2(h)2,g2+0.5),and φ2(h2,g2+1) represent φ2,andin the presence of noise,respectively.Then,based on (17),the integration process can be performed andJ2can be obtained.Ifh2>andJ2

4.Performance analysis

Based on the analysis in [24],it is hard to accomplish the statistical characterization of the detection variables,and the Gaussian distribution is used to approximate this probability distribution.Based on (11) and (14),the detection variables can be written as

Fig.2 TCAM detection probabilities

In the search state diagram,M1represents the number of search for the Doppler rate,andM2represents the number of search for the Doppler frequency.Based onFig.3and the analysis in [12],the overall transfer function for the computational complexity can be found as

Fig.3 Search state diagram of the TCAM

wherecdenotes the unit computational complexity for a complex multiplication.Nc,irepresents the average number of complex multiplications for theith step detection,wherei=1,2.

MAC [12] is the mean complex multiplications cost to detect correct parameters in GNSS acquisition.The theoretical MAC of the search state of TCAM in unit ofccan be found as

When the detection probability is high (Pi,D=1) and the false alarm probability is low (Pi,FA=0),G1(1)=G2(1)=1,and the lower bound of theoretical MAC of the search state can be written as

Based on the analysis in [12],one complex multiplication is equal to two real multiplications,and based onFig.1,the average number of complex multiplicationsNc,ican be written as

To compare with TCAM,the FFT-based method,BASIC [21],is chosen as the compared method.The process of BASIC is shown inFig 4.

Fig.4 Compared method BASIC

In the preparing process of BASIC,the number of complex multiplications about calculating the inter-block conjugate products isWhen the bit sign and the Doppler rate are obtained,the number of complex multiplications about removing the Doppler rate isNs.In the searching process of BASIC,due to the zeropadding process,the number of complex multiplications about Doppler rate estimation based on FFT per block isM1l og2M1.Thus the total number of complex multiplications about Doppler rate estimation based on FFT is(M1log2M1).The number of complex multiplications about Doppler frequency estimation based on FFT isM2log2M2.This is based on assumption [21] that the Doppler frequency range is [−250,250] Hz,and[−500,500] Hz/s.

In the preparing process of TCAM same as BASIC,the number of complex multiplications about calculating the differential signal and removing the Doppler rate isBased on the analysis [12],(10) and(11) can be effectively performed by using only complex additions or complex subtractions,and the lower bound of MAC µcLis chosen as the number of complex multiplications in the searching process.

Based on the analysis above,the FFT based method BASIC needs to search all possible frequency parameters points by using complex multiplications. However,TCAM only needs to search a few possible frequency parameters points using complex multiplications,and search some possible frequency parameters points using real multiplications based on the set threshold.This is why the computational cost of TCAM is lower than that of BASIC.The total number of complex multiplications of methods can be shown inTable 1.

Table 1 Theoretical MAC comparison

InTable 1,M2=andM1=⌈2α0m/∆α+1⌉,where α0=Hz/s.The DCFT method needs two-dimensional FFTs which costM2complex multiplications. Moreover,there areNs/NB−1 blocks andnpositions bit flipping.Every block needs the two-dimensional FFTs. Above all,the method DCFT costsNB(Ns/NB−1)M2complex multiplications.

Based onTable 1,the theoretical MAC that equals to search process multiplications added by preparing process multiplications can be drawn asFig.5.

The Doppler rate range is assumed to be from −500 Hz/s to 500 Hz/s,and α0m=500 Hz/s.Doppler frequency accuracy ∆fis about 1/(2T) Hz,whereTrepresents integration time or post-correlation signal length.Doppler rate accuracy ∆αis set to beHz/s,whereMα=2.The Doppler frequency range is from −250 Hz to 250 Hz,andfdm=250 Hz.The signal length ranges from 40 ms to 1 000 ms for integration.

It can be seen fromFig.5that the theoretical total number of complex multiplications increases when the signal length increases.Moreover,since (12),(17),and(18) are adopted,the computational cost of TCAM is much lower than that of the FFT based methods (BASIC and DCFT) under the same signal length.

Fig.5 MAC comparison

5.Detection performance comparison

To prove that TCAM has a low computational complexity,this section has been conducted by Matlab simulation and semi-physical simulation,and the FFT-based method BASIC has been chosen as a compared method with the simulated MAC as the computational criterion.The simulated parameters can be written asTable 2.

Table 2 Simulation parameters

5.1 Performance comparison by Matlab

In this section,the MACs and detection probabilities of TCAM and BASIC have been simulated by Monte-Carlo simulation when frequency parameters (Doppler frequency and Doppler rate) and data bits change uniformly in the range at each simulation.

InFig 6. (a),since the approximation thatin (12) andin (15) is adopted,the detection probability of TCAM is lower than that of BASIC.However,since the compressed processes based on (12),(15) and (17) with the detection based on the threshold is adopted,TCAM does not need to search all possible frequency parameter units,and many complex multiplications can be reduced.Thus inFig 6.(b),the simulated MAC of TCAM is much lower than MACs of BASIC and DCFT at the same SNR condition.

5.2 Performance comparison by semi-physical simulation

The post-correlation signal should be prepared for TCAM and BASIC (seeFig.7).Firstly,the global position system (GPS) L1 C/A signal is produced by the signal simulator (HWA-RNSS-7200) and sent by its antenna.Then,the GPS intermediate frequency (IF) sampled data (IF is 4.092 MHz,the sampling frequency is 16.368 MHz,and the data type is int8) can be obtained by the IF signal collector. Finally,the post-correlation signal can be obtained based on (1) to (3).Then,based on configuration parameters of the simulator,the code phase can be obtained,and signals are correlated with the local code,respectively.Rs(n) corresponding to the correct Doppler unit can be found,where the range of residual Doppler frequency α0is [−250,250] Hz,and the range of α0is[−500,500] Hz.Some noise is added to the post-correlation signalRs(n) for calculating simulated MACs in different SNRs,the post-correlation signal length is 100 ms.

InFig.8 (b),same as inFig.6 (b),it also proves that since compressed processes with the detection based on threshold is adopted,the simulated MAC of TCAM is much lower than MACs of BASIC and DCFT at the same SNR condition. When SNR is −40 dB,the TCAM’s MAC inFig.8 (b)is lower than the TCAM’s MAC inFig.6 (b).This is because MAC depends on setNsbased on (30) to (32).Moreover,Nsis set based on signal length.There are different signal lengths in the two figures.

Fig.6 Performance comparison in simulation

Fig.7 Process to obtain IF signal of the GPS L1 C/A signal

Fig.8 Performance comparison in practical experiment

6.Conclusions

To further reduce the computational burden in high-dynamic and weak signal situations,we propose a two-step compressed acquisition method.Compression factorsMαandMfare adopted in the set threshold detection.In this way,searching all possible frequency parameter units is not needed,and estimation accuracy can be improved based on (12),(15),and (17) with low computational complexity.The detection and false alarm probabilities of the proposed method are derived.Based on that,the theoretical MAC is derived.Moreover,inFig.5,the theoretical MAC of TCAM is much lower than MACs of BASIC and DCFT at the same post-correlation signal length.The test proves that although the detection probability of TCAM is lower than that of BASIC inFig 6.(a),the simulated MAC of TCAM is much lower than the simulated MACs of BASIC and DCFT at the same SNR condition inFig 6.(b)andFig 8.(b).