Advanced
GPS Pull-In Search Using Reverse Directional Finite Rate of Innovation (FRI)
GPS Pull-In Search Using Reverse Directional Finite Rate of Innovation (FRI)
Journal of Positioning, Navigation, and Timing. 2014. Sep, 3(3): 107-116
Copyright © 2014, null
  • Received : July 09, 2014
  • Accepted : August 01, 2014
  • Published : September 15, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Seung-Hyun Kong
skong@kaist.ac.kr
Kyungwoo Yoo

Abstract
When an incoming Global Positioning System (GPS) signal is acquired, pull-in search performs a finer search of the Doppler frequency of the incoming signal so that phase lock loop can be quickly stabilized and the receiver can produce an accurate pseudo-range measurement. However, increasing the accuracy of the Doppler frequency estimation often involves a higher computational cost for weaker GPS signals, which delays the position fix. In this paper, we show that the Doppler frequency detectable by a long coherent auto-correlation can be accurately estimated using a complex-weighted sum of consecutive short coherent auto-correlation outputs with a different Doppler frequency hypothesis, and by exploiting this we propose a noise resistant, low-cost and highly accurate Doppler frequency and phase estimation technique based on a reverse directional application of the finite rate of innovation (FRI) technique. We provide a performance and computational complexity analysis to show the feasibility of the proposed technique and compare the performance to conventional techniques using numerous Monte Carlo simulations.
Keywords
1. INTRODUCTION
Successful positioning in harsh Global Positioning System (GPS) environments has been one of the most challenging problems in GPS, and the demand for location-based service (LBS) in harsh environments for GPS, such as dense urban and indoor environments is continuously increasing. To meet the needs for GPS in harsh environments, GPS receivers may need a faster and higher sensitivity acquisition and tracking functions that can produce accurate carrier phase and code phase estimates in various GPS signal conditions. In the literature, a number of acquisition techniques for weak GPS signals have been introduced. For example, a GPS receiver connected to a synchronized cellular communication network ( Kransner 1998 , van Diggelen 2009 ) can make use of the downlink signal measurements and downlink information from the cellular base station to quickly acquire GPS signals with high sensitivity. On the other hand, conventional techniques to enhance the acquisition sensitivity and to reduce the mean acquisition time (MAT) such as long coherent integration and non-coherent accumulation techniques ( Parkinson et al. 1996 ) have been continuously studied, and, recently, techniques such as parallel signal search, FFT-based signal search ( Borre et al. 2007 ), and two-dimensional compressed correlator ( Kong & Kim 2013 ) techniques have been developed.
To produce accurate measurements of code phase and carrier phase of incoming GPS signals, GPS receivers employ tracking functions that require initial code phase and Doppler frequency estimates with sufficient accuracy. In practice, the accuracy required for the initial resolutions of the code phase and Doppler frequency are less than a half chip and about ten Hertz ( Tsui 2005 ), respectively. Since most of the acquisition techniques perform Doppler frequency search for incoming GPS signals with a search step size about 1/(2 T ) Hz, where the coherent integration time T is usually 1~5 ms, the Doppler frequency estimate may have an error of up to 250 Hz, which can be too coarse for a carrier phase tracking loop. However, an initial code phase error of up to a half chip can be tolerable for most of the code phase tracking functions ( Irsigler & Eissfeller 2003 ). Therefore, a GPS receiver has a pull-in state between the acquisition and tracking states to increase the accuracy of the Doppler frequency estimate to a high enough level to accurately run carrier phase tracking. In the pull-in state, a GPS receiver tries to obtain a fine Doppler frequency, carrier phase, and C / N 0 estimates of an incoming GPS signal, which can take about 1.5s ( Kelley et al. 2002 ). To improve the pull-in search performance, conventional techniques, such as Tsui (2005) and Goiser & Berger (1996) , perform a fast Fourier transform (FFT) to find the maximum frequency component from code wiped-off sample data and then utilize the amplitude of the component to obtain a fine Doppler frequency estimate. Consecutive fine Doppler frequency estimates can be averaged to increase accuracy in the presence of noise, but, in general, the conventional techniques work well for high C / N 0 . To lessen the noise effect on the Doppler frequency estimation, Sagiraju et al. (2006) suggest increasing T up to 5 ms, however, the scheme requires a smaller initial Doppler frequency estimation error than 50 Hz, which, in effect increases the complexity of the acquisition state. On the other hand, Zeng & Li (2010) suggest a serial Doppler frequency search using correlation in the time domain, and employ a curve fitting algorithm to find a more accurate Doppler frequency estimate. The curve fitting may be able to provide good Doppler frequency and carrier phase estimates at the cost of increased computational complexity. In general, since a GPS receiver does not yet have the knowledge on the received data bit in the pull-in state, increasing the accuracy of Doppler frequency and carrier phase estimates of weak GPS signals can be a complex problem due to the computational complexity and algorithmic complexity required to mitigate the effect of bit transition. In practice, the carrier phase estimation is performed by the phase locked loop in the tracking state.
Despite the complexity and importance, there has been little attention paid to the pull-in search of GPS receivers in the literature. To reduce the computational complexity and improve the accuracy of the Doppler frequency and carrier phase estimates in the pull-in state, we propose a reverse-directional finite rate of innovation (FRI) technique with iterative Cadzow denoising applied to consecutive coherent auto-correlation function (ACF) outputs to reduce the computational complexity in estimating the Doppler frequency and carrier phase of an incoming GPS signal with high accuracy and to increase noise robustness. The complexity of the proposed technique is analyzed and the performance of the proposed technique is compared to the conventional techniques using numerous Monte Carlo simulations.
The rest of this paper is organized as follows. In Section 2, we introduce a general continuous form expression for a coherent ACF output, and in Section 3, we verify that a long coherent ACF output for a Doppler frequency can be estimated with consecutive short coherent ACF outputs at a close Doppler frequency. Section 4 provides the details and complexity of the proposed technique that exploits the findings in Section 3, and Section 5 shows the analysis of the performance of the proposed technique and a performance comparison to conventional techniques using numerous Monte Carlo simulations. And a conclusion is drawn in Section 6.
Throughout this paper, the following conventions are used for notation. Vectors or matrices are denoted by boldface symbols. Small letters are used for scalars and vectors, and capital letters are used for matrices.
2. COHERENT ACF OUTPUT OF GPS SIGNAL
Let r ( t ) be the frequency down-converted incoming L 1 GPS coarse acquisition (C/A) code signal to an IF frequency fIF , then the complex IF signal can be expressed as
PPT Slide
Lager Image
where Q is the number of GPS satellite signals being received, Aq , τq ,
PPT Slide
Lager Image
, and øq are the slowly varying amplitude, code phase, Doppler frequency, and unknown carrier phase of the q-th satellite signal, respectively, Dq ( t ) and Cq ( t ) are the navigation data bit signal and Pseudo-Random Noise code signal of the q-th satellite at time t, respectively, and n (t) represents an additive whiteGaussian noise with two-sided power spectral density (PSD) N0 /2. Note that the data bit and chip rates are Rb (=50 bps) and Rc (= 1.023 Mcps), respectively, and thet the C/A code has code length Lc =1023 chips so that the code period is only T 1 (= 1 ms). When the coherent integration (correlation) length used in the acquisition state is T = LTT 1 , where LT is an integer much larger than 1, and code phase search resolution is Tc /2, the detected code phase τq and Doppler frequency
PPT Slide
Lager Image
at the acquisition state can have errors upto Tc /4 and 1/(4 T ), respectively. Note that the navigation data remains unknown in the pull-in state. To detect and track the code phase τq and Doppler frequency
PPT Slide
Lager Image
of the q-th satellite signal using correlation, the receiver generates a prompt replica signal
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are the code phase and carrier frequency estimates made by the receiver’s acquisition function, respectively. The receiver integrates the product of r ( t ) and
PPT Slide
Lager Image
( t )(complex conjugate of rq ( t )) over the coherent integration interval T to see the correlation between the two functions. Defining
PPT Slide
Lager Image
and
PPT Slide
Lager Image
, the mathematical expression of the ACF output over the two-dimensional space is readily available from Kong & Kim (2013) .
PPT Slide
Lager Image
where Dq ( t - τq ) is assumed as constant Dq for the integration interval T , and
PPT Slide
Lager Image
is a complex Gaussian noise with two-sided power spectral density N0 /2, since signal powers are negligible when compared to the noise power. When T = Tb (=1/ Rb ) and when ø , δτ , and δf are small enough, R 2 ( δτ , δf )≥0 indicates that Dq =+1, and R 2 ( δτ , δf )<0 indicates that Dq =-1. Note that there are several techniques to remove the effect of the navigation data signal Dq ( t ) from R 2 ( δτ , δf ) ; a number of bit sequences are estimated using Kalman filter ( Psiaki & Jung 2002 ), the binary value of Dq ( t ) is estimated by testing different bit combinations ( Petovello et al. 2008 ), or with the assistance information from the cellular base station in the Assisted-GPS system ( Kransner 1998 , van Diggelen 2009 ). Since figuring out the data Dq ( t ) is one of the primary tasks in the tracking state, we neglect the effect of the unknown data in this paper.
3. FREQUENCY ESTIMATION WITH CONSECUTIVE SHORT COHERENT ACF OUTPUTS
In this section, we break R 2 ( δτ , δf ) obtained with a long coherent interval T>> T 1 into LT (= T/T 1 ) consecutive R 2 ( δτ , δf )s obtained with short coherent interval T 1 and investigate the possibility of precisely estimating the Doppler frequency of r ( t ) with the LT R 2 ( δτ , δf ) s obtained. In the following analysis, we drop the subscript (·) q (unless necessary) for simplicity in algebraic expressions.
Let the input to the pull-in state be denoted by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is alreadly available from Kong & Kim (2013) and (·) l represents that the coherent integration from t = lT 1 = tl to t =( l +1) T 1 = tl + T 1 , and
PPT Slide
Lager Image
is a complex Gaussian process with two-sided PSD N0 /2. Note that in Eq. (5) the expected ACF output for | δτ |≥ Tc is assumed as zero. When the code phase estimation is successful, i.e., δτ = Tc /2, the expression Eq. (5) can be simplified to a single-dimensional function
PPT Slide
Lager Image
and let
PPT Slide
Lager Image
when the carrier frequency of rq (t) is
PPT Slide
Lager Image
, it is found from Eq. (7) that
PPT Slide
Lager Image
where
PPT Slide
Lager Image
which is a complex Gaussian process with the same PSD to Eq. (6). Note that Eq. (10) holds only for a very small |Δ f | T 1 =1. From Eqs. (7,9,10), it is found that
PPT Slide
Lager Image
PPT Slide
Lager Image
which indicates that a long coherent ACF output R 1 ( δf f ) with a long coherent integration interval T and a Doppler frequency estimate
PPT Slide
Lager Image
Δ f can be obtained from the linear sum of LT consecutive short coherent ACF outputs
PPT Slide
Lager Image
from LT integration segments [ lT 1 ,( l +1) T 1 ]( l ∈{0,1,…, RT -1}) of [0, T 1 ] with a neighboring Doppler frequency
PPT Slide
Lager Image
, when |Δ f | = 1/ T 1 and | δf f | = 1/ T 1 are satisfied. In other words, Eq. (11b) states that it is possible to precisely estimate a long coherent ACF output R 1 ( δf f ) for a Doppler frequency hypothesis using consecutive short coherent ACF outputs
PPT Slide
Lager Image
with a close Doppler frequency hypothesis. This observation is exploited in the proposed technique for an accurate and fast GPS pull-in search. In addition, it should be noted that the carrier frequency δf of
PPT Slide
Lager Image
can be estimated by compensating the frequency δf with Δ f which maximizes the linear sum in Eq.(11b).
Fig. 1 shows 10 4 Monte Carlo simulation results demonstrating the estimation accuracy of the expression Eq. (11b) for a random Doppler frequency δf of the incoming signal from 0Hz to 250Hz, when C / N 0 =40 dB-Hz and LT =2 5 . Fig. 1a shows that the result of absolute normalized amplitude difference, i.e., │
PPT Slide
Lager Image
for δf varying from 0 to 250Hz. Fig. 1b shows that the standard deviation of the Doppler frequency and the estimated Doppler frequency using Eq. (11b) is small, also. As a result, it is demonstrated that
PPT Slide
Lager Image
is a set of samples of a noisy complex carrier signal, with a carrier frequency δf , amplitude 1/ LT , and phase πδfT 1 , samples at 1/ T 1 [Hz], and that estimating the carrier frequency and phase of R 1 ( δf ) can provide a mismatch of Doppler frequency and phase estimates between those of the incoming signal and the receiver replica. In addition, when the phase of
PPT Slide
Lager Image
is denoted by ø as in Eq. (7) the accumulation of R 1 ( δf f ) for all ( l ∈{0,1,…, RT -1}) in Eq. (11a), i.e., the summation of LT consecutive short coherent ACF outputs, will have an overall phase ø - π Δ f T 1 . Therefore, when the frequency error is estimated, the phase of the incoming signal can be readily available from
PPT Slide
Lager Image
Validity of the approximation in Eq. (11b).
PPT Slide
Lager Image
consequently, we can see thet estimating the frequency error δf is to search for a solution Δ f that maximizes │ R 1 ( δf f )│ such that
PPT Slide
Lager Image
which is equival to the frequency estimation of carrier signal sample
PPT Slide
Lager Image
.
4. FREQUENCY AND PHASE ESTIMATION USING THE PROPOSED TECHIQUE
Ther are a number of techniques that can provide a solution for the problem in Eq. (13). For example, instead of searching for Δ f , trivial techniques can be the Discrete Fourier Transform (DFT) and the FFT that can estimate the frequency of R 1 ( δf ) by finding the maximum frequency component such that
PPT Slide
Lager Image
which may require only LT log 2 LT complex multiplications. The esimate
PPT Slide
Lager Image
is asymptotically unbiased for a very large LT ( Hayes 1996 ), and the maximum error of the FFTbased scheme Eq. (14) is 1/(2 T ) [Hz]. Since the frequency estimation error with the FFT (or DFT) is uniformly distributed in [-1/(2 T ), 1/(2 T )] [Hz], the absolute mean frequency estimation error 1/(4 T ) [Hz] is not sufficiently accurate when T is not very large. In this section, however, we propose a reverse directional FRI technique to increase the frequency estimation accuracy when T is not very large.
- 4.1 Proposed Reverse Directional FRI Technique
In fact, the observation R 1 ( δf ) is the vector of samples of a signal with FRI ( Vetterli et al. 2002 ), i.e., the samples contain only a finite number K (<∞) of innovation of a periodic signal. For an example, a low pass filtered input signal y ( t ) composed of TP -periodic distinctive Dirac delta functions with complex weights xk ( k =0,1,..., k -1) as shown in Fig. 2a , the FRI technique ( Vetterli et al. 2002 ), is to estimate the delays tk ( k =0,1,..., k -1) of the Dirac delta functions in the input using the minimum number of samples of y ( t ). The estimation of tk ( k =0,1,..., k -1) is performed in the frequency domain, since the time domain samples of y ( t ) are effectively the samples of the linear sum of complex sinusoids. The delays can be accurately estimated from the zeros of the annihilating filter H [z] that annihilates the samples of the linear sum of complex sinusoids. And the amplitude xk is estimated by solving the Vandermonde system of linear equations ( Vetterli et al. 2002 ). On the contrary, the problem in Eq. (13) is to estimate the frequency of a single ( K =1) complex sinusoid that is equivalently a single Dirac delta function in the frequency domain, which means that the problem in Eq. (13) requires reverse directional application of the FRI technique as shown in Fig. 2b and as investigated in Kim et al. (2011) , for synthetic aperture radar (SAR) signal processing. In other words, R 1 ( δf ) can be regarded as a set of noisy time domain samples of a single (i.e., K =1) Dirac delta function in the frequency domain as
PPT Slide
Lager Image
Reverse directional application of FRI for GPS.
PPT Slide
Lager Image
where the sampling is performed at every t = lT 1 . Therefore, we can expect that the single Dirac delta function in the frequency domain is
PPT Slide
Lager Image
-periodic, and that the location and amplitude of the corresponding delta function in the frequency domain can indicate the carrier frequency and phase of the R 1 ( δf ), respectively.
Exploiting Blu et al. (2008) for the case of noisy sample input, R 1 ( δf ), when the input is arranged into a Toeplitz matrix
PPT Slide
Lager Image
where L K , an annihilating filter
PPT Slide
Lager Image
that minimizez the total least squares
PPT Slide
Lager Image
under a constraint || H || 2 =1 provides the frequency estimate
PPT Slide
Lager Image
, i.e., f 1 =
PPT Slide
Lager Image
. The coefficients of the annihilating filter [ h 0 , h 1 ,…, hk ] can be found from the eigenvector of A T A corresponding to the smallest eigenvalue, which is related to Pisarenko’s method ( Pisarenko 1973 , Tufts & Kumaresan 1982 ).
To increase the accuracy of the frequency estimate
PPT Slide
Lager Image
in the presence of heavy noise in the signal sample input, there can be two ways to increase the noise robustness of the algorithm in Eq. (18). One way is to increase LT , which is a trivial solution, and the other way is to apply the iterative Cadzow denoising technique used in Blu et al. (2008) . The first step of the technique is to perform a singular value decomposition (SVD) of A such that
PPT Slide
Lager Image
where U , S , and V are unitary, diagonal with elements in descending order, and unitary matrices of size [( LT - L )×( L +1)], [( L +1)×( L +1)], and [( L +1)×( L +1)], respectively. When the ( K +1) -th largest diagonal element of S is not sufficiently smaller than the K -th largest diagonal element, Cadzow’s iterative denoising technique sets the L - K +1 smallest diagonal elements of S to zero to build a new diagonal matrix S (1) in the first step, where (·) (i) denotes the i -th iteration of the Cadzow denoising technique. In the second step, the technique constructs A (1) using S (1) as
PPT Slide
Lager Image
The resulting A (1) is not Toeplitz anymore, so the technique obtains the best Toeplitz approximation of A (1) by averaging the diagonals of A (1) in the step. The above three steps are usually iterated Ni (>1) times until the ( K +1) -th largest diagonal element of S (Ni) becomes RTH (>>1) times smaller than the K -th latgest diagonal element. From experimental observation, RTH ≥50 is sufficiently high. When it is found that the Cadzow denoising is completed after Ni -th iteration, A (Ni) can be re-arranged to form a matrix B of size [ LT ×2] as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
’ is the denoised
PPT Slide
Lager Image
by the iterative Cadzow denoising technique, and the eigenvector of B T B corresponding to the smallest eigenvalue provides the coefficients of the annihilating filter [ h 0 , h 1 ]. From Eq. (17) and for K =1,
PPT Slide
Lager Image
is the final estimate of the frequency δf buried in R 1 ( δf ) found by the proposed reverse directional FRI technique.
Once the frequency δf is estimated, from Eq. (12), the relative phase of the input signal to the receiver generated carrier signal can be easily obtained as
PPT Slide
Lager Image
which is the arc-tangent of the frequency compensated and averaged In-phase and Quadrature-phase consecutive short coherent ACF outputs. Note that the proposed technique can estimate both the frequency and phase difference between the incoming signal r ( t ) and the receiver replica signal, and that when there is no frequency, i.e., δf =0, the phase estimate of the proposed technique is similar to that of the conventional phase estimation technique.
- 4.2 Realization and Receiver Complexity
A drawback of the proposed technique for the pull-in search maybe the high computational cost for multiple SVD’s in the iterative Cadzow denoising. To reduce the computational cost, computationally efficient SVD algorithms such as Riemannian SVD (R-SVD) and Golub-Reinsch SVD (GR-SVD), introduced in Chan (1982) can be applied as a solution. For an SVD of the matrix A of size[( LT - L )×( L +1)], R-SVD and GR-SVD require
PPT Slide
Lager Image
PPT Slide
Lager Image
respectively ( Golub & van Loan 1996 ). Assuming L = LT /4 for Eq. (24a) and L = LT /2 for Eq. (24b), and L >>1 for both cases, we can find that M 1 M 2 /3. Therefore, 1< L << LT /2 is a preferable choice, and the complexity decreases as L decreases in R-SVD. Letting 1/ LT << α l <1/2 and L = α l LT , and assuming Ni iterations of Cadzow denoising, the total computational complexity for the iterative Cadzow denoising is about
PPT Slide
Lager Image
where Ni ≤5 is usually observed in experimentations ( Blu et al. 2008 ). Notice that MCD in Eq, (25) is a monotonously increasing function with respect to α , so that smaller α results in less computational cost. Fig. 3 shows the results of 10 4 Monte Carlo simulations for a fixed RTH =50 and for various α to estimate the total number of multiplications MCD in the proposed technique employing iterative Cadzow denoising with respect to GPS signal strength. Fig. 3a and b show the simulation results for LT =16 and LT 32, respectively. In both figures, 1/4≤ α ≤1/2 results in a similar total number of multiplications, but α =1/8 results in the largest total number of multiplications, which is because the number of iterations Ni is increased for smaller α . Overall, the computational cost is the lowest or near lowest when α =1/3, so L LT /3 is a choice leading to a computationally efficient application of the iterative Cadzow denoising algorithm. Therfore, in the following, we use L LT /3 for the proposed technique.
PPT Slide
Lager Image
Complexity comparison.
5. PERFORMANCE ANALYSIS AND NUMERICAL SIMULATIONS
In this section, we compare the performance of the proposed technique and other techniques including the conventional technique ( Tsui 2005 ).
Exploiting the analysis on the uncertainty of the estimate with the FRI technique for a single Dirac delta function, the variance of the unbiased frequency estimate
PPT Slide
Lager Image
Eq. (22) is found in Blu et al. (2008) and is lower bounded by the Cramer-Rao lower bound (CRLB) as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the period of the frequency domain spectrum, and PSNR represents the peak signal-to-noise ratio such that
PPT Slide
Lager Image
Fig. 4a shows the standard deviation of frequency estimation errors of the proposed technique and other techniques with respect to the carrier to noise denisty ratio ( C / N 0 ). The performance of the proposed techique is almost the same to the theoretical bound CRLB when C / N 0 is not too weak. Note that when the FFT-based frequency resolution governs the estimation accuracy so that the 64-point FFT (i.e., LT =64) has twice the constant resolution error of the 123 -point FFT as shown in Fig. 4a , where ‘ NF -pt FFT ( NF ms)’ in the legend denote the NF -point FFT from NF ms of data. Similarly, the performance of the serial Doppler frequency search scheme with coherent correlation length TCO = NCO T 1 ms if lowerbounded by the Doppler frequency search step size, where NCO =20. In the serial Doppler frequency search simulations, we chose the search step size of 10 3 /64 Hz to compare with the 64 -point FFT-based technique. When the curve fitting technique ( Zeng & Li 2010 ) is applied to the serial Doppler frequency search result obtained with search step size of 1/20 Hz, the performance is improved and shows that it has the same slope to the CRLB in the moderate and high C = N 0 region. Fig. 4a shows the performance of the conventional techique ( Tsui2005 ) also; the conventional frequency discriminator uses two consecutive ACF outputs, with coherent integration length T 1 = ms, to compute
PPT Slide
Lager Image
Performamce comparison
PPT Slide
Lager Image
where Im and Qm represent the in-phase and quadrature-phase component of the ACF output at t = mT 1 , and the moving average length of N -1 is assumed. Note that the performance of the conventional technique is the worst among the techniques shown in Fig. 4 for C = N 0 not high enough, which is due to the short coherent integration length T 1 for each ACF output, and that we can expert 3 dB more performance gain wher the coherent integration for each ACF output is doubled. Note also thet the ideal frequency estimate in Eq. (28) does not include any measurement error due to the approximation funstion. After some algebraic manipulations, the frequency error variance can be found as
PPT Slide
Lager Image
Notice that when C / N 0 =45 dB-Hz the frequency errors of the proposed technique for LT =16, LT =32 and the curve fitting technique are about 1 Hz, 0.3 Hz, and 0.8 Hz, respectively, and the errors increase much slowly than in the conventional technique as the C / N 0 decreases. The resulting phase estimation performnce of the techniques compared in Fig. 4a shows some similarity as shown in Fig. 4b . Note that the phase estimation is performed with a shorter data length than the data length used for frequency estimation. For example, when the frequency is estimated with NF -point FFT ( NF ) ms, the maximum frequency error is 10 3 /2 NF Hz with which the phase error can increase to π [rad]. Since a phase estimation with an arc-tangent function may result in a large arithmetic error in the presence of noise, we limit the maximum possible phase estimation error by taking a shorter data length than that for the frequency estimation. In Fig. 4b , a legend, for example, ‘64-pt FFT (64 ms)+32 ms’ denotes the phase estimation with 32 ms of data when frequency estimation is performed with LT =64, and it can be found that a shorter data length for phase estimation results in a smaller phase estimation with the proposed technique and with the curve fitting technique is much better than with other techniques for moderate and strong signals.
Fig. 4c shows the computational complexity (i.e., the number of complex multiplications) of the frequency estimation techniques, such as NF -point FFT-based technique ( NF =64), serial Doppler frequency search techique with TCO =20 ms and search step size 10 3 / NF Hz, conventional technique Eq. (28) with N =20, and the proposed technique with LT =16 ms and 32 ms, discussed in this section. When the sampling rate fs =2 Rc =2×1.023 MHz, the computational costs for the frequency estimation techniques can be expressed as
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where MFFT , MSS , Mconv , and MFRI represent the computational complexity of the NF -point FFT based technique, the serial search technique with coherent integration length Tco testing NDF = NF /2=32 Doppler frequency hypotheses tested with a smaller coherent integration length T 1 (i.e., 500 Hz), the conventional technique Eq. (28) with N=20, and the proposed technique, respectively. Notice that computational complexity for computing the arc-tangent function is not counted in the express ions in Eq. (30), and that, for high C = N 0 , MFFT =64×(2046+ log 2 64)=131328, MSS =20×2046×32=1350360, Mconv =20×2046× log 2 2046=450062, MFRI =2046×16+5×[4×11 2 +22×6 2 ]×6+[4×15 2 +22×2 2 ]×2=72992 for LT =16, where Ni =5, and MFRI =2046×32+2×[4×21 2 +22×12 2 ]×12+[4×31 2 +22×2 2 ]×2=191704 for LT =32, where Ni =2, which match the simulation results for C / N 0 =45 dB-Hz shown in Fig. 4c .
Obviously, the total complex multiplications of the curve fitting technique are larger than the serial search technique due to the additional curve fitting process. Furthermore, the three figures in Fig. 4 shows that the proposed technique can produce much more accurate Doppler frequency and phase estimates than other techniques and that the computational complexity of the proposed technique is only around 2×10 5 multiplications for LT ms of data, while other techniques have multiple times of estimation error and computational cost in the GPS pull-in state.
6. CONCLUSIONS
It has been found that a reverse directional finite rate of innovation technique can be applied to GPS pull-in search and improves the accuracy and computational cost of the pull-in search in comparison to the conventional techniques. Analytical expressions are derived to obtain the theoretical estimates of performance improvement and computational complexity with the proposed technique. The simulations have demonstrated that the proposed technique has a performance improvement when SNR is moderate or high, and that the improvement becomes significant as the resolution of frequency estimation of the proposed technique increases linearly as SNR increases, which is not possible with the conventional FFT-based frequency estimation techniques. In addition to the improvement of the frequency estimation, the proposed technique contributes to the accuracy in the phase estimation, and, therefore, improves the phase tracking performance of a receiver.
Acknowledgements
This work is supported by the Electronic Warfare Research Center (EWRC) grant funded by the Agency for Defense Development (ADD).
BIO
Seung-Hyun Kong received a B.S.E.E. from the Sogang University, Korea, in 1992, an M.S.E.E. from the Polytechnic University, New York, in 1994, and a Ph.D. degree in Aeronautics and Astronautics from Stanford University, CA, in 2006. From 1997 to 2004, he worked with Samsung Electronics Inc. and Nexpilot Inc., both in Korea, where his research focus was on 2G CDMA and 3G UMTS PHY and mobile positioning technologies. In 2006, he was involved with the development of hybrid positioning technology using wireless location signature and Assisted GNSS at Polaris Wireles, Inc. and from 2007 to 2009, he was a researcher at Qualcomm Research Center, San Diego, CA, where his R&D focus was on indoor location technologies and advanced GNSS technologies. Since 2010, he as been an Assistant Professor at the CCS Graduate School for Green Transportation in the Korea dvanced Institute of Science and Technology (KAIST). His research interests include super-resolution signal processing, detection and estimation for navigation systems, and Assisted GNSS in wireless communication systems.
Kyungwoo Yoo received a B.S.E.E from Inha University, Korea, in 2012, and a M.S. degree from the CCS Graduate School for Green Transportation in the Korea Advanced Institute of Science and Technology (KAIST), Korea, in 2014. He is currently pursuing a Ph.D. degree with the same institution. His research interests include anti-jamming technique and signal processing for GNSS and navigation system.
References
Blu T. , Dragotti P.-L. , Vetterli M. , Marziliano P. , Coulot L. 2008 Sparse Sampling of Signal Innovations: Theory, Algorithms and Performance Bounds IEEE Signal Process Mag. http://dx.doi.org/10.1109/MSP.2007.914998 25 31 - 40    DOI : 10.1109/MSP.2007.914998
Borre K. , Akos D. , Bertelsen N. , Rinder P. , Jensen S. 2007 A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach Birkhauser Boston, MA
Chan T. F. 1982 An Improved Algorithm for Computing the Singular Value Decomposition ACM Trans. Math. Softw. http://dx.doi.org/10.1145/355984.355990 8 72 - 83    DOI : 10.1145/355984.355990
Goiser M. J. , Berger G. L. 1996 Synchronizing a digital GPS receiver MELCON ’96, Proc. of the 8th Mediterranean Electrotechnical Conference May 1996 http://dx.doi.org/10.1109/MELCON.1996.551387 1043 - 1046    DOI : 10.1109/MELCON.1996.551387
Golub G. H. , van Loan C. F. 1996 Matrix Computations 3rd ed The Johns Hopkins Univ. Press Baltimore
Hayes M. H. 1996 Statistical Digital Signal Processing and Modeling John Wiley & Sons New York
Irsigler M. , Eissfeller B. 2003 Comparison of Multipath Mitigation Techniques with Consideration of Future Signal Structures Proc. of ION GPS/GNSS 2003 Portland, OR Sep 2003
Kelley C. , Cheng J. , Barnes J. 2002 Open source software for learning about GPS Proc. of ION GPS/GNSS 2002 Portland, OR Sep 2002
Kim B. , Muchkaev A. , Kong S.-H. 2011 SAR Image Processing Using Super-Resolution Spectral Estimation with Annihilating Filter 2011 3rd International Asia-Pacific Conference on Synthetic Aperture Radar, APSAR Seoul, Korea 1-4 Sep 2011
Kong S.-H. , Kim B. 2013 Two-Dimensional Compressed Correlator for Fast PN Code Acquisition IEEE Trans. Wirel. Commun. http://dx.doi.org/10.1109/TWC.2013.092313.130407 12 5859 - 5867    DOI : 10.1109/TWC.2013.092313.130407
Kransner N. F. 1998 GPS receiver and method for processing GPS signals US Patent, PN 5,781,156
Parkinson B. , Spilker J. , Axelrad P. , Enge P. 1996 Global Positioning System: Theory and Applications American Institute of Aeronautics and Astronautics Washington, DC
Petovello M. , O&Driscoll C. , Lachapelle G. 2008 Weak Signal Carrier Tracking Using Extended Coherent Integration with an Ultra-Tight GNSS/IMU Receiver Proc. of ENC 2008 Toulouse Apr 2008
Pisarenko V. F. 1973 The Retrieval of Harmonics from a Covariance Function Geophys. J. R. Asfr. Soc. 347 - 366
Psiaki M. L. , Jung H. 2002 Extended Kalman Filter Methods for Tracking Weak GPS Signals Proc. of ION GPS/ITM 2002 Portland, OR Sep 2002 2539 - 2553
Sagiraju P. K. , Akopian D. , Valio H. 2006 Fine Frequency Estimation in Weak Signals for GPS Receivers Proc. of ION GPS/NTM 2006 Monterey, CA Jan 2006 2524 - 2533
Tsui J. B. Y. 2005 Fundamentals of Global Positioning Receivers: A Software Approach 2nd Ed John Willey & Sons New York
Tufts D. W. , Kumaresan R. 1982 Estimation of frequencies of multiple sinusoids: Making linear prediction perform like maximum likelihood Proc. IEEE http://dx.doi.org/10.1109/PROC.1982.12428 975 - 989    DOI : 10.1109/PROC.1982.12428
van Diggelen F. 2009 A-GPS: Assisted GPS, GNSS, and SBAS Artech House Norwood, MA
Vetterli M. , Marziliano P. , Blu T. 2002 Sampling Signals with Finite Rate of Innovation IEEE Trans. Signal Process http://dx.doi.org/10.1109/TSP.2002.1003065 50 1417 - 1428    DOI : 10.1109/TSP.2002.1003065
Zeng D. , Li J. 2010 GPS Signal Fine Acquisition Algorithm, Information Science and Engineering (ICISE) 2010 2nd International Conference on IEEE Dec 2010 http://dx.doi.org/10.1109/ICISE.2010.5691791 3729 - 3732    DOI : 10.1109/ICISE.2010.5691791