QIU Wenqi,ZENG Qingxi,*,GAO Chang,and LYU Chade

1.State Key Laboratory of Automotive Simulation and Control,Jilin University,Changchun 130012,China;2.Non-destructive Detection and Monitoring Technology for High-speed Transportation Facilities Key Laboratory of Ministry of Industry and Information Technology,Nanjing 211106,China;3.College of Automation Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China

Abstract: The BeiDou software receiver uses the fast Fourier transform (FFT) to perform the acquisition. The Doppler shift estimation accuracy should be less than 500 Hz to ensure satellite signals to enter a locked state in the tracking loop. Since the frequency step is usually 500 Hz or larger,the Doppler shift estimation accuracy cannot guarantee that satellite signals are brought into a stable tracking state. The straightforward solutions consist in increasing the sampling time and using zero-padding to improve the frequency resolution of the FFT.However,these solutions intensify the complexity and amount of computation. The contradiction between the acquisition accuracy and the computational load leads us to research for a more simple and effective algorithm, which achieves fine acquisition by a look-up table. After coarse acquisition using the parallel frequency acquisition (PFA) algorithm, the proposed algorithm optimizes the Doppler shift estimation through the look-up table method based on the FFT results to improve the acquisition accuracy of the Doppler shift with a minimal additional computing load. When the Doppler shift is within the queryable range of the table,the proposed algorithm can improve the Doppler shift estimation accuracy to 50 Hz for the BeiDou B1I signal.

Keywords: fine acquisition, fast Fourier transform (FFT), table look-up,parallel frequency acquisition(PFA),BeiDou.

1.Introduction

The satellites of the BeiDou satellite navigation positioning system send signals to the earth continuously. Those signals have mainly three components:(i)A carrier,which is a sinusoidal signal of a certain frequency band that serves as a physical carrier for transmitting satellite information. The satellite signals of the BeiDou navigation system at present mainly include carriers of four frequencies: 1 561.098 MHz (B1), 1 589.752 MHz (B1-2),1 207.14 MHz(B2)and 1 268.52 MHz(B3).(ii)A pseudorandom noise(PRN)code,which is a sequence of discrete codes specific to each satellite with values of 0 and 1.There are two orthogonal PRN codes modulated on each carrier:ordinary PRN codes on branch I,and precise PRN codes on branch Q. There are 37 PRN codes defined in the official document of the BeiDou system “Space Signal Interface Control Document V3.0” [1]. These PRN codes are used to determine which satellite the satellite signal comes from,and also widen the original signal band.The code chipping rate of BeiDou B1 and B2 signals is 2.046 Mchip/s, and the code length is 2 046 chips.(iii)Navigation data,which provide ephemeris,almanac,time and other necessary parameters for the navigation system.

The first step of base-band signal processing for the Bei-Dou software receiver is acquisition. The acquisition has three purposes as follows: (i)detect the satellites in view,that is,obtain the PRN code;(ii)obtain a coarse estimation of the Doppler shift,because there is an uncertainty due to the receiver oscillator inaccuracy and the Doppler effect[2];and(iii)obtain a coarse estimation of the phase of the PRN code,which is unknown without a priori knowledge of the geometry and time synchronization [3]. If the accuracy of Doppler shift estimation obtained by acquisition is less than 500 Hz, then the software receiver can use a closed loop to track satellite signals and extract navigation data. As soon as the base-band signal processing is performed for at least four satellites,the software receiver can calculate the location.

The satellite signal structure has been adjusted in the BeiDou system,that is,the Neumann-Hoffman(NH)code is added to modulate the carrier synchronously,but this adjustment will result in a decrease in the acquisition accuracy[4].The Doppler shift estimation accuracy decreases when bit hopping occurs in the coherent integration process. The effect cannot be eliminated by reducing the coherent integration time or using other integration methods,resulting in the subsequent tracking process being impossible.Therefore,the BeiDou software receiver needs a precise Doppler shift acquisition method.

At present,the research on fine acquisition is to improve the accuracy of Doppler shift estimation by improving the frequency resolution of fast Fourier transform (FFT) using a parallel code-phase acquisition (PCA) architecture or a parallel frequency acquisition(PFA)architecture[5–10]. C?agatay proposed a two-stage acquisition method to improve the accuracy of Doppler shift estimation[11,12].In the first stage,N-point discrete Fourier transformation(DFT)is performed on an input sequence of the lengthNfor the coarse acquisition.In the second stage,accurate frequency estimation is obtained by a fitting curve,which is fitted using several points around the peak of theN-point DFT.This method can accurately obtain the Doppler shift estimation when the signal-to-noise ratio (SNR) ranges from 10 dB to 40 dB,while it cannot be used at any other SNR level. It means that this method for a fine acquisition is suitable for radar signals,but not for satellite signals with the SNR around–20 dB.A new fine acquisition algorithm uses the correlation of satellite signals to improve the accuracy of the signal obtained by a coarse acquisition to 50 Hz.However,when the carrier-to-noise ratio is low,longer data are required to ensure the accuracy of acquisition[13].In order to solve the problem brought by the signal noise,a robust fine acquisition method using an orthogonal search algorithm was proposed in[14].The method improves the acquisition accuracy by more than 70%and maintains high performance in the presence of noise.However,the method utilizes the Gram-Schmidt orthogonalization technology,resulting in a high algorithm complexity.The method suggested in [15] uses seven complex exponential signals whose center frequency is in the arithmetic progression to perform coherent integration with the satellite signal,and a Doppler shift estimation is obtained from the quadratic curve fitted by three FFT samples. The accuracy of the Doppler shift estimation with this method can be less than 80 Hz, but it will seriously increase the calculation amount. In order to find the balance between the acquisition accuracy and the acquisition time,three local carriers with a phase difference of a specified interval are used to perform correlation calculations with satellite signals, and the frequency error of fine acquisition results is within 60 Hz [16]. Zhen et al. proposed a fine acquisition algorithm that improves the accuracy of the search frequency by successively reducing the search frequency interval,and improves the acquisition accuracy to 62.5 Hz with a small increase in the amount of calculation[17].

In this context, this paper proposes a new acquisition algorithm for a fine Doppler shift estimation based on a look-up table. The proposed algorithm first obtains a coarse estimation of the Doppler shift in the PFA framework. Then the FFT results are used to look up the table for a correction value of the Doppler shift coarse estimation. With this method, the accuracy of the Doppler shift estimation can be improved with little increase in the amount of computation. This paper is organized as follows. Section 2 gives a brief description of the structure of the BeiDou B1 signal. Section 3 presents the acquisition principle of the PFA algorithm and the characteristics of the FFT results.Section 4 details the proposed algorithm,including the establishment and operation of the table, through which the correction value of the Doppler shift can be obtained according to the FFT results.In Section 5 experiments are conducted to test signals generated by Matlab and the real BeiDou B1 signal by using the proposed algorithm,with a discussion on the accuracy of the Doppler shift estimation for a software implementation using Matlab.Finally,Section 6 concludes the results obtained on the applicability to other satellite signals.

2.BeiDou B1 signal

In 2019,the China Satellite Navigation Office released an interface control document(ICD)for the open service B1I signal[1].It describes the structure,fundamental parameters,characteristics of PRN codes,and the navigation data format of the BeiDou B1 signal. Global positioning system(GPS)signals use a binary phase-shift keying(BPSK)modulation [18], whereas BeiDou signals use a quadrature phase-shift keying(QPSK)modulation[19,20].QPSK transmits the channels of in-phase(I)and quadrature-phase(Q) simultaneously and is more efficient in utilizing frequency bands than BPSK.The BeiDou B1 signal consists of the channel I(open)and the channel Q(authorization),and can be expressed as

wherejis an index that denotes the satellite,AB1IandAB1Qare the amplitudes for the channels I and Q,respectively,andare the PRN codes for the channels I and Q, respectively,andare the data for the channels I and Q, respectively,fB1is the intermediate frequency,andare the phases of the PRN codes for the channels I and Q,respectively.

The BeiDou B1I signal is generated by modulating the carrier with both PRN codes and navigation data in the QPSK mode.Unlike the traditional QPSK mode,the digital data (PRN codes and navigation data) of the BeiDou B1 signal are not multiplied by the multiplexer but directly with the carrier of the channel I (or Q). The modulation process of the BeiDou B1 signal is depicted in Fig.1.Only the channel I is considered in the proposed algorithm since the channel Q is an authorized service and is not open to the public.

Fig.1 Modulation mode of BeiDou B1 signal

3.Acquisition using PFA algorithm

3.1 The principle

There are three algorithms used for the acquisition of satellite signals, the core idea of which is to utilize the strong auto-correlation of the PRN codes to perform acquisition.These algorithms are the serial search acquisition (SSA)algorithm, which performs a scanning two-dimensional search on the time-frequency search space, the PFA algorithm, which uses the FFT as a spectrum analyzer, and the PCA algorithm, which uses the FFT to convert the search of code-phase and frequency into a search only in the frequency search space [21]. Among the three algorithms, the SSA algorithm takes the longest time to acquire signals. In the case of the cold-start of a receiver,the acquisition using the PFA algorithm consumes more computing resources than that using the PCA algorithm,since the number of searches required by using the PFA(e.g.,a span of 2 046 chips with a code step of 1 chip requires 2 046 times) is larger than the number of searches required by using the PCA(e.g.,a span of±5 kHz with a frequency step of 500 Hz requires 21 times)[22,23].However,in the case of the warm-start and the hot-start of the receiver, receivers can get information that can help with the acquisition process from other sources. The information can help receivers know which satellites are in view and reduce the code-phase search space and the frequency search space [21]. In the case of the warm-start and the hot-start of the receiver, the PFA algorithm only needs to perform the FFT once in each search process, while the PCA algorithm needs to perform the FFT for two times and the inverse FFT (IFFT) once in each search process.Therefore,the PFA algorithm consumes less computing resources than the PCA algorithm.In this context,this paper studies the proposed algorithm in the PFA architecture.

The PFA architecture is depicted in Fig. 2. There are three steps: (i) multiplication of the complex input signal with the local code replica, (ii) FFT for the Doppler shift estimation, and (iii) comparison of the peak value in the FFT magnitude spectrum with the threshold.

Fig.2 Diagram of PFA acquisition

Step 1Remove the PRN code.

After the antenna receives the satellite signal,the satellite signal is pre-processed through the radio frequency(RF) front-end circuit. The RF front-end circuit includes the low-noise amplifier,the filter,the mixer,the automatic gain control (AGC), and the intermediate frequency (IF)amplifier, through which a stable digital IF signal can be obtained and sent to the acquisition module.The first step in acquisition is to remove the PRN code from the BeiDou B1 signal.Considering only the channel I,the BeiDou B1 signal received from thejth satellite can be modeled as

wherefIFis the intermediate frequency,fdB1is the Doppler frequency shift,?B1Iis the phase andw(n)is the Gaussian white noise component.

The principle of removing the PRN code from the Bei-Dou B1 signal is the same as the GPS L1 signal, which utilizes the correlation property of the PRN code.The removal of the PRN code is performed by multiplying the input signal with the local replica of the PRN code.However,unlike the GPS L1 signal,the NH code with a code rate of 1 kbps is modulated on the navigation data in the BeiDou B1 signal. To avoid the influence of the NH code on the auto-correlation result of the PRN code,the removal of the PRN code is performed by a modified method, as shown in Fig. 3. First, the local replica with a length of 1 ms is generated.Then the input signal and the local replica are correlated at a particular phase so that an output signal of 1 ms can be obtained.In Fig.3,mis the phase difference between the local replica and the PRN code modulated on the input signal,and it is changed by shifting the phase of the incoming PRN code.Whenm=0,the local replica of the PRN code is aligned with the incoming PRN code,so that a signal of 1 ms having the PRN code removed can be obtained.The process is shown as

whereR(m)is the correlation value between the incoming PRN code and its local replica. When the local replica is aligned with the incoming PRN code,the correlation valueR(m)is

Fig.3 Process of removing the PRN code

Step 2Operate the FFT process.

After Step 1,a signal with a length of 1 ms stripped of the PRN code can be obtained,and the signal is not relevant to the navigation data.The signal can thus be simplified as

The discrete signalS(n) can be treated as a result of sampling the continuous signalS(t) in the time domain.We assume an intermediate frequencyfIFof 2.5 MHz,and the sampling frequency is set as 10 MHz(the sampling periodTs=10?7s),so thatS(n)can be written as

The signal given in(3)is an infinite-length signal,while the FFT can only process the finite-length signal. Therefore, it is necessary to perform a multiplying window.Commonly used window functions include rectangular window, triangular window, Hanning window, Hamming window, and Gaussian window. This paper processes the signalS(n) by a rectangular window, which is expressed as

whereLis the FFT point.

The discrete-time Fourier transform (DTFT) process converts the finite-length discrete signalS(n) in the time domain into an infinite-length continuous signalS(f) in the frequency domain based on the principle that multiplication in the time domain is equivalent to convolution in the frequency domain.The process is shown as

wherefdenotes frequency,andkis an integer repressing thekth sample value.

When the width of the rectangular windowL · Ts=1 ms,the sampling period in the time domainTs=10?7s,and the influence of noise is neglected, the DTFT spectrum with different Doppler shifts can be obtained by(8),as shown in Fig.4.

Fig.4 DTFT spectrum with different Doppler shifts in the absence of noise

As can be observed from Fig. 4, the spectral patterns with the Doppler shifts –2 kHz, –1 kHz, 0 kHz, 1 kHz,and 2 kHz are the same, that is, the spectral pattern with any Doppler shift can be obtained by shifting the spectrum with the Doppler shift of 0 kHz. Fig. 5 shows the DTFT spectrum with different SNRs with the Doppler shift of 0 kHz. It can be seen that, compared with the spectrum in the absence of noise,the shape of the DTFT spectrum in the presence of noise is shorter and fatter.

Fig.5 DTFT spectrum with different SNRs with the Doppler shift of 0 kHz

Since the FFT result is a finite-length discrete spectrum rather than an infinite-length continuous spectrum, it is necessary to discretize the continuous signalS(f)and then multiply it by a rectangular window. The obtained finitelength discrete signalS(k)is written as

with

where Δfis the sampling period in the frequency domain.

The FFT magnitude spectrumS(k) can be obtained by(9),which should be analyzed in detail.If the peak value in the FFT magnitude spectrum is above the threshold, it indicates that the satellite signal has been acquired.Since the spectrumS(k) is obtained by sampling the spectrumS(f)with a sampling period of Δf,the peak value of the spectrumS(k) is equal to the peak value of the spectrumS(f)only when the Doppler shift is an integer multiple of Δf.That is,when the Doppler shift is not an integer multiple of Δf,the peak value of the spectrumS(k)is below the peak value ofS(f).When the width of the rectangular windowL · Ts= 1 ms, the sampling period in the frequency domainTs= 10?7s,and the influence of noise is neglected,the FFT spectrum with different Doppler shifts can be obtained by(9),as shown in Fig.6.There is a main peak and a secondary peak in the FFT magnitude spectrum with each Doppler shift,and the secondary peak is adjacent to the main peak.For example,when the Doppler shift is 400 Hz, the main peak is at the intermediate frequency,and the secondary peak occurs at 1 kHz from the intermediate frequency. It means that the secondary peak is the immediate right neighbor of the main peak.The secondary peak occurs because the signal is multiplied by a rectangular window in the process of analyzing the spectrum by FFT so that there are spectral lines around the intermediate frequency,and the amplitude of the secondary peak is maximal among these lines. Therefore, the energy of the signal is mainly concentrated on the main peak and the secondary peak.In the presence of noise,because the bandwidth of the noise is infinite, and it is evenly distributed over the entire frequency band, the energy difference between the main peak and the secondary peak will decrease for an FFT result at a certain Doppler shift.The smaller the SNR,the lower the energy difference between the main and the secondary peaks.

Fig.6 FFT spectrum with different Doppler shifts in the absence of noise

Fig. 7 shows the main peak and the secondary peak in the FFT magnitude spectrum with different Doppler shifts.The horizontal axis shows the distance between the Doppler shift and the main peak, and the distance can be used as the correction value for optimizing the Doppler shift estimation acquired by a coarse acquisition since the frequency to obtain the main peak is the Doppler shift coarse estimation. It can be seen in Fig. 7 that as the distance between the Doppler shift and the main peak is close to 500 Hz, the main peak gradually decreases, and the secondary peak gradually increases.When the distance between the Doppler shift and the main peak is 500 Hz, the main peak and the secondary peak have the same energy.

It can be seen in Fig. 7 that the distance between the Doppler shift and the main peak(i.e.,the correction value for the Doppler shift coarse estimation)has a specific func-tional relationship with the main peak and the secondary peak in the FFT magnitude spectrum. The amplitudes of the main peak and the secondary peak change with the received signal power,while the ratio of the amplitude of the main peak to that of the secondary peak does not change with the received signal power.Therefore,it is considered that the relationship between the ratio of the main peak to the secondary peak and the distance between the Doppler shift and the main peak can be utilized to improve the accuracy of the Doppler shift estimation after the coarse acquisition in the PFA architecture.

Fig.7 The main peak and the secondary peak in the FFT magnitude spectrum with different Doppler shifts

Step 3Obtain the threshold decision.

The random variableS'(k)is obtained by performing a modulo operation on the FFT result.Then compareS'(k)with the thresholdYtto determine whether the satellite is acquired. In this step, it is critical to determine a reasonable threshold.On the one hand,setting the threshold low may lead to misjudgment. That is, the receiver acquires the satellite while the satellite does not exist.On the other hand,setting the threshold high may result in the failure to acquire the satellite signal.

False alarm probabilityPfaand detection probabilityPdare two key factors to be considered when setting the threshold. SinceS'(k) obeys the Rice distribution,its probability density distribution function isfn(z). The noise ofS'(k) obeys the Rayleigh distribution, and its probability density distribution function isfs(z).The relationship between the false alarm ratePfaand the thresholdYtis provided,which is

whereσ2is the noise power, andPfais set to 1% in the paper. The relationship between the detection probabilityPdand the thresholdYtis

3.2 Acquisition performance analysis

Since the base-band processing of the received signal runs in the central processing unit(CPU),the software receiver has an excellent design flexibility but runs very slowly.Therefore,if the fine acquisition can be achieved without significantly increasing the number of calculations, then software receivers will become more useful than traditional hardware receivers.

Considering that the software receiver operates in a highly dynamic situation, the Doppler frequency shift ranges from–10 kHz to 10 kHz. It is set to acquire satellite signals with a code phase step of one chip. Then, the PFA algorithm needs to perform 2 046 searches during the coarse acquisition phase. The computational load of the coarse acquire phase is calculated with a sampling depth ofNpoints. HereNadddenotes the amount of addition,andNmuldenotes the amount of multiplication.

The proposed fine acquisition algorithm calculates the ratio of the main peak to the secondary peak in the FFT magnitude spectrum after the coarse acquisition phase.Then use the ratio as an address to look up the table. Finally,the Doppler shift coarse estimation and the Doppler shift correction value obtained by looking up the table are added to obtain the fine acquisition result. Therefore, the proposed fine acquisition algorithm only needs to perform a division operation and an addition operation after the coarse acquisition phase. Compared with the calculation amount of addition and multiplication of the coarse acquisition phase,the amount of calculation increased in the fine acquisition phase can be ignored.The proposed algorithm improves the accuracy of the Doppler shift with little increase in the computational load.

4.The proposed algorithm based on a look-up table

In this section,based on the relationship between the correction value for the Doppler shift coarse estimation and the ratio of the main peak to the secondary peak in the FFT magnitude spectrum obtained in Section 3, a new acquisition algorithm for a fine Doppler shift estimation based on a look-up table is proposed.First, a table for querying the correction value for the Doppler shift coarse estimation is established in Section 4.1.The table provides the correction value for the Doppler shift coarse estimation under the address of the ratio of the main peak to the secondary peak in the FFT magnitude spectrum.Then,the operation of the table in the PFA framework is explained in Section 4.2.

4.1 Establishment of the table

It can be seen in Fig. 7 that the correction value for the Doppler shift coarse estimation has a specific relationship with the ratio of the main peak to the secondary peak in the FFT magnitude spectrum. The noise is ignored in Fig. 7,but the actual satellite signal is mixed with the noise.In order to study the relationship between the correction value for the Doppler shift coarse estimation and the ratio of the main peak to the secondary peak in the FFT magnitude spectrum for the actual satellite, 5 000 simulation experiments are performed on the distance between the Doppler shift and the main peaks of 50 Hz,100 Hz,150 Hz,200 Hz,250 Hz, 300 Hz,350 Hz,400 Hz, 450 Hz and 500 Hz respectively in different SNRs. The ratio of the main peak to the secondary peak with different correction values for the Doppler shift coarse estimation is obtained through experiments.The coherence time isL·Ts= 1 ms, and the sampling period in the time domain isTs= 10?7s in the experiments. The result of the simulation experiments is shown in Fig.8.

Fig. 8 Curve of the ratio of the main peak to the secondary peak with different correction values for the Doppler shift coarse estimation in different SNRs

Fig.8 shows the confidence intervals for the ratio of the main peak to the secondary peak corresponding to each correction value for the Doppler shift coarse estimation in different SNRs.The lower limit of the confidence interval is obtained by subtracting the standard deviation of 5 000 experiments from the mean of 5 000 experiments,and the upper limit of the confidence interval is obtained by the mean of 5 000 experiments plus the standard deviation of 5 000 experiments.

It can be seen in Fig.8 that when the distance between the Doppler shift and the main peak is small, the ratio of the main peak to the secondary peak does not approximate to the theoretical value since the secondary peak is almost submerged by the noise. When the distance between the Doppler shift and the main peak is large, the ratio of the main peak to the secondary peak approximates to the theoretical value.In the case where the SNR is set to–10 dB,the simulated curve coincides well with the theoretical curve when the distance between the Doppler shift and the main peak is greater than 150 Hz. In the case where the SNR is set to –20 dB, the simulated curve coincides well with the theoretical curve when the distance between the Doppler shift and the main peak is greater than 300 Hz.That is, with a high quality of the signal satellite, the farther the Doppler shift is from the main peak, the smaller the influence of noise is on the ratio of the main peak to the secondary peak, and the closer the simulated curve is to the theoretical curve.Based on the above analysis,there is a correspondence between the correction value for the Doppler shift coarse estimation and the ratio of the main peak to the secondary peak in the FFT magnitude spectrum.Therefore,the correction value for the Doppler shift coarse estimation can be obtained from the ratio of the main peak to the secondary peak in the FFT magnitude spectrum by looking up the table.

The SNR of the satellite signal received by the receiver is generally around–20 dB, but there are some intersections among the confidence intervals with different Doppler shifts when the distance between the Doppler shift and the main peak is greater than 300 Hz on the simulation curve with an SNR of –20 dB. Therefore, the simulation curve with an SNR of–10 dB is used for the establishment of the table, instead of the simulation curve with an SNR of–20 dB.Based on the simulation curve with an SNR of–10 dB,Table 1 records the mean of 5 000 simulation experiments, the standard deviation of 5 000 simulation experiments, and the confidence interval with different distances between the Doppler shift and the main peak.When the distance between the Doppler shift and the main peak is relatively close,the processes of discretization and multiplying window have less influence on the spectral energy of the signal, so that the secondary peak is smaller and is easy to be submerged by the noise.Therefore,in the process of looking up the table, there is a blind zone when the distance between the Doppler shift and the main peak is less than 200 Hz. In the blind zone, the look-up table method fails,and the accuracy of the Doppler shift coarse estimation cannot be improved by the proposed algorithm.

A table for querying the correction value for the Doppler shift coarse estimation,which is queried by the ratio of the main peak to the secondary peak in the FFT magnitude spectrum, is established based on the data in Table 1, as shown in Fig.9.

Table 1 Confidence interval with different distances between the Doppler shift and the main peak when SNR=–10 dB

Fig.9 Table for querying the correction value for the Doppler shift coarse estimation

The first and second rows of data in Fig. 9 (200, 250,300, 350, 400, 450, 500) are the correction values for the Doppler shift coarse estimation in hertz, and the third row of data in Fig. 9 (3.719, 4.301, 2.840, 3.192, 2.224,2.441, 1.783, 1.941, 1.440, 1.560, 1.178, 1.267, 0.993,1.038)is the ratio of the main peak to the secondary peak in the FFT magnitude spectrum. Fig. 9 is divided into two zones: the left side is the blind zone, and the right side is the queryable zone. When the distance between the Doppler shift and the main peak is less than 200 Hz,because the secondary peak is submerged by the noise,the correction value for the Doppler shift coarse estimation cannot be obtained by looking up the table, resulting in the appearance of the blind zone.The first and third rows of data in Fig.9 are directly obtained from Table 1.It can be seen that if the ratio of the main peak to the secondary peak in the FFT magnitude spectrum is within the interval of [3.719, 4.301], [2.840, 3.192], [2.224, 2.441], [1.783,1.941], [1.440, 1.560], [1.178, 1.267]and [0.993, 1.038],the corresponding correction values for the Doppler shift coarse estimation are 200 Hz, 250 Hz, 300 Hz, 350 Hz,400 Hz, 450 Hz, 500 Hz, respectively. If the ratio of the main peak to the secondary peak in the FFT magnitude spectrum is between two adjacent intervals, the correction value for the Doppler shift coarse estimation takes the smaller one of the correction values corresponding to these two intervals.For example,when the ratio of the main peak to the secondary peak in the FFT magnitude spectrum is 2, which is between the intervals of [2.224, 2.441] and[1.783, 1.941], the correction value for the Doppler shift coarse estimation is taken as 300 Hz.In this way,the correction value for the Doppler shift coarse estimation of all the queryable zone can be obtained.

Finally, the third row in Fig. 9 is used as the address to query the table, and the second row in Fig. 9 is used as the content of the table. A table for optimizing the Doppler shift coarse estimation is thus established.Within the queryable range of the table, there is a unique correction value for the Doppler shift coarse estimation corresponding to the ratio of the main peak to the secondary peak in the FFT magnitude spectrum.

4.2 Operation of the table

In Section 4.1, a table for optimizing the Doppler shift coarse estimation is established whose address is the ratio of the main peak to the secondary peak in the FFT magnitude spectrum and the content is the correction value for the Doppler shift coarse estimation. However, there is a blind zone in the table. When the distance between the Doppler shift and the main peak is less than 200 Hz, the Doppler shift coarse estimation cannot be optimized by looking up the table.Therefore,it is necessary to confirm that the FFT magnitude spectrum satisfies the precondition of the look-up table before using the table to optimize the Doppler shift coarse estimation. This section presents the specific operation of the table,as shown in Fig.10.

Fig. 10 Flow diagram of acquisition combined with the look-up table

In Fig.10,we use the following notations:

Ymax: the amplitude of the main peak;

Ysubmax: the amplitude of the secondary peak;

Lmax:the frequency point position corresponding to the main peak;

Lsubmax: the frequency point position corresponding to the secondary peak;

Δfd: the correction value for the Doppler shift coarse estimationfd.

As shown in Fig.10,the input signal is the FFT magnitude spectrumS(k).There are four processing steps.

Step 1Determine if the main peakYmaxexceeds the thresholdYt. IfYmax> Yt, then the satellite is acquired,and the frequency to obtain the main peak is the coarse estimation of the Doppler shift,denoted asfd.Otherwise,no satellites are found.

Step 2Determine if the secondary peakYsubmaxexceeds the thresholdYt. IfYsubmax< Yt, then the coarse estimation of the Doppler shift cannot be optimized, i.e.,the final Doppler shift estimation isfd. Otherwise, go to Step 3.

Step 3Determine whether the secondary peak is the right neighbor or the left neighbor of the main peak, i.e.,whether the equationLsubmax=Lmax±1 holds. If the equationLsubmax=Lmax±1 does not hold, then the coarse estimation of the Doppler shift cannot be optimized,i.e., the final Doppler shift estimation isfd. Otherwise,the correction value for the Doppler shift coarse estimation Δfdcan be obtained by looking up the table.

Step 4Optimize the Doppler shift coarse estimationfd.IfLsubmax=Lmax?1,then the Doppler shift estimation optimized by the look-up table isfd ?Δfd.Otherwise,the Doppler shift estimation optimized by the look-up table isfd+Δfd.

By combining with the look-up table, a new acquisition algorithm in the PFA framework is presented.Fig.11 shows the diagram of PFA acquisition combined with the look-up table.

Fig. 11 Diagram of PFA acquisition combined with the look-up table

Compared with the traditional PFA algorithm, the new algorithm combines the look-up table. After the coarse estimation of the Doppler shift is obtained by the traditional PFA algorithm,the correction value for the Doppler shift coarse estimation is obtained by looking up the table,thereby improving the Doppler shift estimation accuracy.

5.Software implementation

This section designs experiments to verify the fine acquisition algorithm proposed in Section 4.The proposed algorithm is applied to the acquisition of the test signal and the real BeiDou B1 signal using Matlab.

5.1 Experimental equipment

Fig.12 shows a global navigation satellite system(GNSS)IF signal sampler,which is used to sample satellite signals for the validation tests. Fig. 13 shows the GNSS receiver platform.The type of antenna is GNSS(GPSL1+BD2B1)dual frequency measuring antenna and the capture platform is Matlab 2014a.The parameters used in the sampling process are tabulated in Table 2.

Fig.12 GNSS IF signal sampler

Fig.13 GNSS receiver platform used for validation tests

Table 2 System parameters

5.2 Experimental equipment

The process of software implementation for the test signal is as follows.Firstly,we sample the BeiDou satellite signal for 2 ms and use the SSA algorithm to perform acquisition on the sampled signal directly, so that the Doppler shift estimation with the accuracy of 1 Hz can be obtained,denoted asfdB1.Then,signals with different Doppler shiftsare obtained by changing the intermediate frequency of the numerically controlled oscillator (NCO). Finally, the FFT is performed on the signal whose Doppler shift is,and the fine estimation of the Doppler shift can be obtained by the look-up table.By comparing the Doppler shift estimation obtained by the proposed algorithm with, the acquisition accuracy of the Doppler shift using the proposed algorithm can be obtained and analyzed.

The above process is described in detail as follows.

Step 1Obtain the results of acquisition using the SSA algorithm.

The SSA algorithm uses correlators in the time domain to perform a two-dimensional scanning search on the timefrequency search space.The algorithm has the best acquisition sensitivity but takes a long time because of the broad search range.

In the experiment, the sampled BeiDou satellite signal for 2 ms is first acquired by the SSA algorithm with a frequency step of 1 Hz and a code step of 1 chip,so that the Doppler shift estimationfdB1can be obtained. Since the accuracy offdB1is 1 Hz,fdB1can be regarded as the actual Doppler shift of the sampled BeiDou satellite signal.Fig. 14 shows the results of the acquisition for the third BeiDou satellite using the SSA algorithm.

Fig. 14 Results of acquisition for the third BeiDou satellite using SSA algorithm

It can be seen that the code-phase of the third BeiDou satellite is the 909th chip and the Doppler shift of the third BeiDou satellite is 8 Hz.

Step 2Generate a test signal with the Doppler shift

After the PRN code is removed,the satellite signalS(n)is mixed with the local carrier signalS1(n) generated by the NCO to obtain the test signalx1(n)with the Doppler shiftas depicted in Fig.15.

Fig.15 Diagram of PFA acquisition for validation tests

The second step in Fig.15 is to mix the satellite signal with the local carrier signal for the purpose of removing the Doppler shiftfdB1from the satellite signal and generating a test signal with the Doppler shiftThe local carrier signalS1(n)can be written as

The test signalx1(n) is obtained by multiplying the satellite signalS(n)of removing the PRN code by the local carrier signalS1(n).Therefore,the test signal is given by

Thus, the satellite signal can retain both the original spectral energy and the characteristics of the noise. The signalx1(n)and the signalS(n)carry the same information,except that the Doppler shift is different.The Doppler shift ofS(n)isfdB1,and the Doppler shift ofx1(n)is.

Step 3Perform the FFT.

By settingin the second step to 50, 100, 150, 200,250,300,350,400,450 and 500 in hertz,respectively,the test signalx1(n) with the Doppler shift of 50, 100, 150,200,250,300,350,400,450 and 500 in hertz,respectively,can be obtained,and then the FFT is performed on the test signalx1(n).The FFT result is shown in Fig.16.

Fig.16 FFT magnitude spectrum for the test signal

Observed from Fig.16,the horizontal line indicates the thresholdYt. It can be seen that as the Doppler shiftincreases, the main peak gradually decreases and the secondary peak gradually increases. Whendoes not exceed 250 Hz, the secondary peak does not reach the threshold,so the Doppler shift coarse estimation cannot be optimized.Whenexceeds 250 Hz,the main peak and the secondary peak both exceed the threshold,so the Doppler shift coarse estimation can be optimized by the look-up table.

Step 4Look up the table.

The ratio of the main peak to the secondary peak in Fig.16 is taken as the address of the look-up table,and the correction value for the Doppler shift coarse estimation is obtained by looking up the table,as detailed in Section 4.2.The Doppler shift estimation obtained by the proposed algorithm is compared to the actual Doppler shiftas depicted in Fig. 17. The Doppler shift estimation obtained by the proposed algorithm differs from the actual Doppler shift by 50 Hz when the Doppler shift does not exceed 250 Hz.The Doppler shift estimation obtained by the proposed algorithm is the same as the actual Doppler shift when the Doppler shift exceeds 250 Hz.

Fig.17 Comparison of the Doppler shift estimation obtained by the proposed algorithm with the actual Doppler shift

Since the Doppler shift of the real satellite signal is not limited to the set{50,100,150, 200,250,300,400, 450,500},the Doppler shift of the test signal is set to

The acquisition experiment is performed by the proposed algorithm for each test signal so that the difference between the Doppler shift estimation obtained by the proposed algorithm and the actual Doppler shiftcan be obtained,as shown in Fig.18.

Fig.18 Difference between the Doppler shift estimation obtained by the proposed algorithm with the actual Doppler shift curve

It can be seen that the difference between the Doppler shift estimation obtained by the proposed algorithm with the real Doppler shift curve in Fig. 18 is jagged. The jagged curve is formed because the correction value for the Doppler shift coarse estimation obtained by the lookup table is discontinuous.Specifically,the correction value is limited to the set{50,100,150,200,250,300,400,450,500}.The vertical axis in Fig.18 is the difference between the Doppler shift estimation obtained by the proposed algorithm with the actual Doppler shift,which represents the acquisition accuracy of the Doppler shift in the proposed algorithm.It can be seen from the range of the vertical axis that when the Doppler shift exceeds 250 Hz, the acquisition accuracy of the Doppler shift can be improved to 50 Hz by the proposed algorithm.

5.3 Implementation of the proposed algorithm for the real BeiDou B1 signal

In this section,the real BeiDou satellite signal is sampled as the experimental object. Then the acquisition experiment is performed on the real BeiDou satellite signal using the SSA algorithm with a frequency step of 1 Hz and a code step of 1 chip and the PFA algorithm combined with the look-up table,respectively.The experimental results of acquisition for the real BeiDou satellite signal by these two methods are shown in Table 3.

Table 3 Experimental results of acquisition for the real BeiDou satellite signal by the SSA algorithm and the proposed algorithm

In Table 3,fdSSAis the Doppler shift estimation acquired by the SSA algorithm, andfdtableis the Doppler shift estimation acquired by the PFA algorithm combined with the look-up table.The error is|fdtable?fdSSA|,which represents the acquisition accuracy of the Doppler shift.It can be seen that there are seven BeiDou satellites with an SNR around–20 dB in view. Among them, the 2nd, 3rd,7th,10th,and 14th satellites are not in the queryable zone of the table,so the Doppler shift estimation cannot be optimized by looking up the table.The 1st and 10th satellites are in the queryable zone of the table,so the Doppler shift estimation is optimized by the look-up table. The acquisition accuracies of the Doppler shift for the 1st and 10th satellites are 32 Hz and 11 Hz,respectively.

The experimental results show that the Doppler shift estimation cannot be optimized by the look-up table when the Doppler shift is not within the queryable range of the table. The Doppler shift estimation can be optimized by the look-up table when the Doppler shift is within the queryable range of the table,and the acquisition accuracy of the Doppler shift can be improved to 50 Hz.

6.Conclusions

The problem of the low accuracy of Doppler shift estimation acquired by traditional acquisition algorithms is discussed in this paper. The straightforward solution of increasing the sampling time and using zero-padding is not satisfying, which leads us to looking for a new acquisition algorithm that improves the acquisition accuracy of the Doppler shift without a large increase in the computing load.The proposed algorithm is studied in the PFA framework. After performing FFT in the PFA framework, the Doppler shift estimation can be optimized by a look-up table. The proposed algorithm achieves a fine acquisition with a very little additional computing load.

The Doppler shift estimation obtained by the proposed algorithm is more accurate than the Doppler shift estimation obtained by the traditional algorithm when the Doppler shift is within the queryable range of the table.Acquisition for real BeiDou satellite signals shows that when the Doppler shift is within the queryable range of the table,the Doppler shift estimation can be optimized by the lookup table,and the acquisition accuracy of the Doppler shift can be improved to 50 Hz.

Note that while the BeiDou B1 signal is considered throughout this paper for illustration purposes, the proposed algorithm is suitable for other GNSS signals.Using similar analysis as done in this paper,it is easy to establish a table for other GNSS signals to optimize the Doppler shift coarse estimation, whose address is the ratio of the main peak to the secondary peak in the FFT magnitude spectrum.