Direct P-code acquisition algorithm based on bidirectional overlap technique

Ying Xu,Lijuan Xu,Hong Yuan,and Ruidan Luo,2

1.Academy of Opto-Electronics,Chinese Academy of Sciences,Beijing 100094,China;

2.University of Chinese Academy of Sciences,Beijing 100049,China

1.Introduction

There are two common pseudorandom noise(PRN)codes:C/A code and P-code,which are used to offer standard positioning service and precise positioning service respectively in the global positioning system(GPS).The code ranging error is about 1/100 of the chip interval,so the ranging accuracy of the C/A code with a rate of 1.023 MHz is about 2.93 m,while the P-code with a rate of 10.23 MHz is about 0.29 m.The C/A code is taken as a coarse code for rough measurement and the P-code is taken as a precise code for precise measurement.

The code synchronization,as the foundation of dispreading GPS signals,is performed in two steps,which are initial synchronization(i.e.acquisition),and fine synchronization(i.e.tracking).Code synchronization of acquisition is the most challenging task for GPS receivers.The acquisition conducts a two-dimensional search process,and the two-dimensional search pattern consists of code delay and Doppler frequency shift.With a period of 1 023 chips and a rate of 1.023 MHz,the C/A code is easy to be acquired by searching the twodimensional cell,while the P-code has to take as long as 7 days to finish the searching process by the virtue of the C/A code acquisition methods[1].

Generally,the P-code acquisition is usually assisted by the hand-overfrom an acquired C/A code,but the C/A code has a short length and a low code rate,and is vulnerable to jam.With the demand of high precision ranging increasing,P-code ranging becomes a research focus.The P-code has a higher positioning accuracy,better anti-jamming performance and superior anti-interception performance,which is usually taken as a valid method for effective navigation under a complex environment.

The P-code,however,is difficult to acquire,due to its long period and high code rate.The common P-code acquisition methods include the parallel correlation algorithm and the code reconstruction algorithm.The parallel correlation algorithm,such as the fast Fourier transform(FFT)correlation algorithm and the matched filter algorithm[2–7],has an outstanding signal-to-noise ratio(SNR)performance but complex calculations.The Y-EXPRESS chip is a typical representative of parallel correlation,which conducts serial search process for code phase and parallel search process for Doppler frequency shift.The chip can search 511×64 cells at a time.The common code reconstruction algorithms include the extended replica folding acquisition search technique(XFAST)and the P-code average method.

[8–10]put forward XFAST based on the excellent code self-correlation and cross-correlation property of the PRN code.In the XFAST algorithm,the local code with a length ofMNis divided intoMsubsequences with a length ofN.The subsequences are added into a new local code.The input signal with a length ofNis correlated with the new local code to get the correlation peak.The XFAST algorithm can decrease the computational complexity,but cause the SNR loss.Reference[11]utilized a time-frequency folding technique to improve the acquisition time,but the correlation SNR performance was even worse than the XFAST algorithm.

The P-code average method of direct acquisition in[12]decreased the computational complexity and had a better correlation SNR performance than XFAST,but the correlation SNR loss over the whole average phase error intervals was still large.Reference[13]proposed an overlap average method to improve the correlation SNR,which reconstructed the input signal and the local code sequence by multi-point average.The overlap average method decreased the correlation SNR loss compared with the direct average method,but the SNR loss still existed in the whole average phase error intervals.The shifting overlap method was put forward based on the overlap average technique by[14],which can achieve better correlation SNR than the overlap average method.However,the correlation SNR was not a straight line over the whole code phase error space.The highest correlation SNR was about 1.5 dB higher than the lowest correlation SNR.

2.SNR performance analysis

The correlation SNR is an important performance for P-code acquisition.The main application environment of P-code includes complex environment and war environment,where the GPS receiver has to work under low SNR.Supposing the detection SNR is 0 dB＜SNR＜20 dB,compare the detection probability of SNR and SNR+ΔSNR(ΔSNR=2 dB,4 dB and 6 dB).The simulation result is shown in Fig.1.

Fig.1 Detection probability of different detection SNRs with same detection threshold

Fig.1 illustrates that increasing detection SNR results in an increment in the detection probability.A 2 dB increment in correlation SNR can bring approximately 50%–100%improvement in detection probability.Therefore,it has practical significance in improving the detection SNR performance of the P-code.

The direct P-code acquisition algorithms are studied below.Firstly,the correlation SNR performance of common direct P-code acquisition algorithms is analyzed.Then,the direct P-code acquisition method based on the bidirectional overlap technique is proposed.At last,the performance of the proposed method is compared with common methods and the relationships among correlation SNR,average point number,and integration time are analyzed.

3.Common P-code average acquisition algorithms performance analysis

3.1 Direct average algorithm performance analysis

The direct average algorithm,as a direct P-code acquisition algorithm,is established in the circular correlation theory.The incoming signal and locally generated code sequence firstly execute average processing respectively,and the receiver obtains a new incoming signal and a new local code sequence.The two new sequences are correlated.Its work flow graph is shown in Fig.2.

Fig.2 Direct P-code average method work flow

The length of new sequences isN,which is generated by averaging the sequence with a length ofMNin accordance with eachMpoint.The acquisition time shortens because of the correlation points changing formMNintoN.M-points averaging causes peak fuzzy,so anotherMtimes direct search is needed for ambiguity resolution.If the average code phase of the input signal does not match the local code,the correlation SNR will deteriorate.Suppose that the input signal isf,the local code sequence isg,the averaged input signal isx,the averaged local code sequence isy,and the average code phase error between the incoming signal and the local code sequence isM/2,where the correlation peak has the most serious loss.The loss is represented as

Equation(1)illustrates the maximum loss of correlation peak occuring in the half of the correlation peak offandg,which is 6 dB.Thus,the SNR loss is severe when the average code phase of the incoming signal and the local code sequence does not match.

3.2 Overlap average algorithm performance analysis

In order to reduce the SNR loss of the direct average algorithm,Pang proposed the overlap average algorithm which was a linear superposition algorithm.Suppose thatM=128,the code phase error isk,the incoming signal isf,and the local code sequence isg.Then the correlation peak value is

where the function pairs (fkg0,fkg128), (fkg64,fk+128g64)and(fk+128g0,fk+128g128)complement each other on correlation peak values.The complementary relationship is analyzed as follows.

The local code sequence is reconstructed as Fig.3.Average the input signal and the new local code sequence respectively,and correlate the averaged sequence.

Fig.3 Overlap average algorithm phase relationship

The new averaged sequence is generated by adding and averaginggnandgn−M,supposing the new sequence isz,then the elements of the new sequence are represented as

Then,the correlation peak value is obtained as

It can be drawn out from(4)that the average phase error isk=M/2 ifM=4,and the correlation peak value is identical with the maximum correlation peak value of the direct average algorithm.In fact,for anyMand anyk,the correlation peak values ofxandzare identical.

The code cross-correlation is taken as the noise,and the compensation pair doubles the noise power.The overlap average algorithm makes the correlation SNR better as where SNRoverlapaverageis the correlation SNR of the overlap average algorithm,SNRdirectaverageis the correlation SNR of the direct average algorithm,andN0is the cross-correlation noise power.

As the signal is added by amplitude and the noise is added by power,it can be derived from(5)that the correlation SNR of the overlap average algorithm achieves approximately 3 dB improvement compared with the lowest correlation SNR of the direct average algorithm,but 3 dB attenuation with the highest correlation SNR.Therefore,the correlation SNR loss of the direct average algorithm is about 6 dB when the initial average phase error is half of the average point number.Both of the overlap average algorithm and the direct average algorithm have considerably large SNR loss over the whole code phase intervals.

4.Bidirectional overlap direct acquisition algorithm

4.1 Algorithm structure

As can be seen from the above analysis,the average algorithms have better SNR performances than the XFAST algorithm,which are applicable to the P-code acquisition in low SNR.The overlap average algorithm conducts circular correlation for the input signal and the new local sequence obtained by shifting and overlapping the local replica,which avoids the SNR loss induced by different initial code phase differences.Since the overlap operation introduces code cross-correlation noise,and the PRN is added by the magnitude while the noise is added by the power,the SNR performance of the overlap average algorithm is 3 dB worse than the worst SNR performance of the direct average algorithm,and 3 dB better than the best SNR performance of the direct average algorithm.

According to the SNR loss of the overlap average algorithm,the overlap average local code is reconstructed by shifting and overlapping differently.Assume that the average points of the local code isM,the length of the averaged local code isN,the initial average phase difference isk(0≤k≤M/2),and the shift value of shift and overlap operation ist(0≤t≤M).The effect on correction SNR due to shift and overlap operations is analyzed from two aspects of the noise power and the signal power introduced by overlapping.

(i)The noise power introduced by overlapping

Whent=M,the introduced cross-correlation noise is independent,so the noise overlaps by power.Whent=0,the newly introduced cross-correlation noise completely repeats the previous,so the noise overlaps by magnitude.When 0＜t≤M,there aretpoints noise overlap by power andM−tpoints noise overlap by magnitude.Assume that the direct average noise without overlapping isN0,the overlapped direct average noise isNa,then

(ii)The signal power introduced by overlapping

Therefore,the corresponding SNR is obtained as

The normalized correlation SNR value is analyzed under the condition of different average pointM,different initial average phase differencekand different shift valuet.

WhenM=16 andM=8,the performance of normalized correlation SNR with differentkand differenttis shown in Fig.4.WhenM=16,the performance of normalized correlation SNR with differenttunder differentkis shown in Table 1.

It is observed that when the number of overlap points is 16 and the shift valuet＜8,the correlation SNR loss varies with the initial average phase difference.The less the initial average phase,the less the correlation SNR loss,and vice versa.When the shift valuet=8,the result of shift and overlap operations has nothing to do with the initial average phase difference,and the corresponding SNR loss is 1.2 dB compared with the direct average algorithm completely aligned.When the shift valuet=16,the algorithm becomes the typical case,namely the overlap average algorithm,the corresponding SNR loss is 3 dB compared with the direct average algorithm completely aligned.Thus,taking all the values of the initial average phase difference into account,when the shift valuet=8,the correlation SNR is optimum.When the shift valuet=M/2,the correlation SNR is constant in different initial average phase differences,and the SNR loss is approximately 1.2 dB compared with the initial average point completely aligned.

Fig.4 Normalized correlation SNR with differentk and differentt

Table 1 Normalized correlation SNR whenM=16

Based on the above analysis,the bidirectional overlap average algorithm is proposed to improve the correlation SNR,which performs the overlap operation on the sequence withM/2 shifting.The new algorithm will be described with details in the following.

Shift the local code sequence byM/2 and−M/2 respectively and separately add the two shifted sequences with the local code sequence to generate two new local code sequences.Then average the new local code sequences and the input signal,and correlate the averaged sequences to get two correlation peaks.Finally choose the bigger one as the correlation result.The code phase is shown in Fig.5.

Fig.5 Code sequences of bidirectional overlap direct P-code acquisition algorithm

(i)Receive the incoming signal sequencefn,and then averagefnin accordance with the average pointMto obtain the new sequencexn.

(ii)Shift the local PRNgnwith early shiftM/2 and late shiftM/2 respectively,then overlap the two new sequences with local PRN to obtain the new PRNsgn+gn+M/2 andgn+gn−M/2.

(iii)Average the two new PRNs in accordance with average pointM,then obtain the new PRNzc(n)andzd(n).

(iv)Correlatexnwithzc(n)andzd(n)respectively,then contrast the peaks and select the larger peak to detect.

(v)If the signal is detected,conduct the search on PRN with an uncertain range ofMto obtain the final acquisition result;if the signal is not detected,receive the next segment input signal,and search until completing the entire uncertain range ofMor detecting the signal.

4.2 Performance analysis

The algorithm structure is introduced and the SNR loss caused by overlap operation is analyzed in Section 4.1,the correlation SNR and acquisition time are shown in the following.

(i)Correlation SNR

The SNR loss is caused by the Doppler frequency error,the code phase error and the initial average phase difference.Thus the total SNR loss is

whereLdoppis the SNR loss of the Doppler frequency error,Lchipis the SNR loss of the code phase error,andLaveis the SNR loss of the initial average phase difference.

The SNR loss of the Doppler frequency error are the same for all the direct P-code acquisition algorithms,which is

whereωcis the Doppler phase error,andTis the coherent integration time.

The SNR loss of the code phase error is mainly caused by sampling frequency,

whereε(0≤ε＜1)is the code phase error(unit:chip).If the sampling frequency isfs,ε=Ts/2,andTs=1/fs.

According to Section 4.1,the SNR loss of the direct average algorithm caused by the initial average phase difference is

wherekis the initial average phase difference.

The SNR loss of the overlap average algorithm and the bidirectional overlap direct average algorithm caused by the overlap operation can be written as

According to(10),(11),(13)and(9),the total acquisition SNR loss of the proposed algorithm is

then the correlation SNR is

whereis the input carrier noise ratio,Tis the integration time,andLlossis the total SNR loss.

(ii)Acquisition time

The acquisition time of single detection is[15]

whereqis the number of the searching unit,τdis the single searching time,K=1 is the detection parameter,Pdis the detection probability,andPfais the false alarm probability.The single detection probability and false alarm probability can be written as

whereVtis the normalized threshold,rSNRis the detection SNR,andQ(a,u)is the generalized MarcumQfunction.

Therefore,the acquisition time is affected byPdandPfa,the higher thePd,the shorter the acquisition time.When the false alarm probability is constant,the proposed algorithm has better detection probability than the overlap average method and the direct average method.Thus the acquisition time of the proposed algorithm should be shorter than the overlap average method and the direct average method.

5.Simulation analysis

To verify and analyze the bidirectional overlap direct acquisition,it has conducted the following simulations.The simulation parameters are set as follows:the sampling frequency isfs=62 MHz,the intermediate frequency isfI=15.48 MHz,the code rate isfc=10.23 MHz,the P-code is the truncated code generated by a 42 bit code generator,and the correlation is adopted FFT operation.Take no account of the Doppler frequency error.

(i)M=128,N=5 000,take no account of the input noise.Fig.6 shows the relationship of correlation SNR and the average code phase error.

Fig.6 Correlation SNR over the average code phase error interval

It is observed that the lowest correlation SNR of the direct average algorithm is 6 dB less than the highest correlation SNR,when the average phase error isM/2.The correlation SNR of the proposed algorithm is a standard line over the whole average code phase error intervals,which is about 5 dB higher than the lowest correlation SNR of the direct average algorithm and 2 dB higher than that of the overlap average algorithm.

(ii)M=128,N=5 000,the input SNR is−20 dB,and the average code phase errorkisM/2.Fig.7 shows the correlation results of the direct average algorithm,the overlap average algorithm and the proposed algorithm.

Under the simulation condition,although the three algorithms can both obtain obvious correlation peaks by which the signal is detected,the noise of the proposed algorithm is obviously lower than the other algorithms when the correlation peaks are normalized.

(iii)M=128,N=10 000,take the lowest correlation SNR value over the whole code phase error intervals.Fig.8 shows the correlation SNR of the direct average algorithm,the overlap average algorithm and the proposed algorithm.

It can be derived that the correlation SNR of the proposed algorithm is about 3 dB higher than that of the direct average algorithm and 1.5 dB higher than that of the overlap average algorithm under low SNR,and is about 4 dB higher than that of the direct average algorithm and 2 dB higher than that of the overlap average algorithm under high SNR.

Fig.7 Comparison of correlation peak

Fig.8 Correlation SNR corresponding to different input SNR

Fig.9 Correlation SNR corresponding to different input SNR with Doppler frequency error

(iv)Doppler frequency searching unit Δf=1 kHz,M=128,N=5 000,the simulation time is 100,and take the lowest correlation SNR value over the whole code phase error intervals.Fig.9 shows the correlation SNR of the direct average algorithm,the overlap average algorithm and the proposed algorithm.It is observed that the correlation SNR of the proposed algorithm is better than that of the direct average method and the overlap average method with the Doppler frequency error.This is because the SNR loss of code phase error and Doppler frequency error of the three algorithms are the same,the proposed algorithm decreases the SNR loss of the initial average phase difference to improve the correlation SNR.

6.Conclusions

The P-code average method is an effective algorithm for direct P-code acquisition.The direct average algorithm has SNR loss caused by the average code phase error.The overlap average algorithm improves the SNR performance based on the direct average algorithm,which still has a 3 dB SNR loss when the code average phases of the input signal and the local code are not completely identical.A new algorithm based on the bidirectional overlap technique is put forward to improve the correlation SNR loss problem in this paper.The proposed algorithm reconstructs the local code by bidirectional shifting and overlapping.The simulation results indicate that the proposed algorithm has an advantage over the direct average algorithm and the overlap average algorithm on correlation SNR performance.When the correlation point numbers are identical,the proposed algorithm has a better SNR performance than the direct P-code acquisition method,which should be a suitable choice for direct P-code acquisition.

[1]X.Zhang,Y.Zhang.Research on GPS long-code-acquisition method.Journal of University of Electronic Science and Technology of China,2008,37(6):62–65.

[2]N.Wang,Y.Qin,B.Zhang.Direct and rapid P-code acquisition technique.Proc.of the IEEE International Symposium on Communications and Information Technologies,2007:1122–1124.

[3]F.Liu,Y.X.Feng.Proposal and analysis of a new direct acquisition technique of P-code in GPS.Transactions of Shenyang Ligong University,2006,25(6):11–13.

[4]W.Meng,W.Wang.Improved algorithm for direct GPS signal P-code acquisition based on frequency domain search.Journal of Harbin Institute of Technology,2007,39(5):733–736.

[5]R.Wolfert,S.Chen,S.Kohli,et al.Direct P(Y)-code acquisition under a jamming environment.Proc.of the IEEE on Position Location and Navigation Symposium,1998:228–235.

[6]J.W.Betz,J.D.Fite,P.T.Capozza.DirAc:an integrated circuit for direct acquisition of the M-code signal.Proc.of the 17th International Technical Meeting of the Satellite Division of the Institute of Navigation,2004:447–456.

[7]Q.Xu,K.Wang,J.Xu.Research for direct P-code acquisition based on wavelet filtering.Systems Engineering and Electronics,2007,29(4):536–539.(in Chinese)

[8]C.Yang,J.Vasquez,J.Chaffee.Fast direct P(Y)-code acquisition using XFAST.Proc.of the 12th International Technical Meeting of the Satellite Division of The Institute of Navigation,1999:317–324.

[9]C.Yang,J.Chaffee,J.Abel,et al.Extended replica folding for direct acquisition of GPS P-code and its performance analysis.Proc.of the 13th International Technical Meeting of the Satellite Division of The Institute of Navigation,2000:2070–2078.

[10]C.Yang,J.Vasquez,J.Chaffee.Frequency-domain Doppler search and Jam-suppression.Proc.of the 12th International Technical Meeting of the Satellite Division of The Institute of Navigation,1999:1157–1167.

[11]H.Li,M.Q.Lu,Z.M.Feng.Direct P(Y)/M-code acquisition based on time-frequency folding technique.Proc.of the 21st International Technical Meeting of the Satellite Division of the Institute of Navigation,2008:167–173.

[12]J.Pang,F.Graas,J.Starzyk.Fast direct GPS P-code acquisition.GPS Solutions,2003,7(3):168–175.

[13]J.Pang,F.V.Graas,J.Starzyk.Fast direct GPS signal acquisition using FPGA.Proc.of the 16th European Conference on Circuit Theory and Design,2003:182–185.

[14]Y.Xu,J.Wang,S.L.Wu.Improved direct P-code acquisition technique.Journal of Systems Engineering and Electronics,2009,20(5):948–953.

[15]Y.Xu,H.Yuan.High-sensitivity acquisition of ultrahigh dynamic direct sequence spread spectrum signals in space communications.China Communications,2013,10(10):26–36.