Signal Processing - September 2017 - 63

N H ^, 41, 000h hypotheses is tested serially (which is why
it is called the serial search), and, assuming the true (correct)
hypothesis H 1 can be any one of the N H hypotheses, the mean
and worst-case acquisition times can be (1/2) N H Tco = 20.5 s
and N H Tco = 41 s, respectively. The MAT ( n T ) can grow
exponentially for acquisition functions using the serial search
strategy when, for example, N i times longer coherent integration length is used; N i times longer time to test each hypothesis and N i times larger number of Doppler-frequency
hypotheses result in MAT increased by N i2 times. Therefore,
it is necessary to have an effective search strategy to reduce
the MAT for the given hardware and computational capacities
to a GNSS receiver.

versa) at the same time. Figure 2 depicts a time-domain acquisition function employing a hybrid search strategy with M
parallel correlators, where D represents a half-chip delay. The
acquisition function in Figure 2 can achieve about M times
smaller MAT than n T,S when the incoming signal is strong
enough and can be realized in the frequency domain, as shown
in Figure 3. The incoming signal samples y 6n@ and receiver
replica x 6n@ are collected for one code period ^T ph to build y
and x vectors of the same size N co (= fs T p), respectively, and
it is found that

Multiple-dwell search strategy

where U is the circular convolution operator; rev 6x@ =
" x 6n@ | n = N co, N co - 1, f, 1 ,; DFT " $ , and IDFT " $ , are the
discrete Fourier transform and inverse DFT operations, respectively; the superscript * represents the complex conjugate operation; X = DFT " x ,; and Y = DFT " y , . Each IDFT " X * $ Y ,
result in (4) is used for the signal detection, and similarly to
the parallel search strategy there are options of detection variables and detection schemes used for the hybrid search strategy in practice. The frequency-domain hybrid search can be
implemented with a digital signal processor (DSP) chip, so it
should be useful to reduce both computational cost and MAT

1

y B [n]
D

Carrier
NCO
λ∆f

2

M

Correlator-M Zco
ZM
∑N
G (·)
co

D

In the parallel (or complete) search strategy, a GNSS receiver
tests all of the hypotheses in the search space and identifies the
true hypothesis H 1 from the complete search result. Testing all
of the hypotheses in parallel may require a massive amount of
correlators, so this search strategy requires the highest acquisition complexity. Conventionally, the maximum integration
output of the complete search result, max " Z ,, is used as the
detection variable to be compared to the detection threshold,
which is similar to the hybrid search strategy in the following.
In practice, when using the parallel and hybrid search strategies, there are options for the detection variables and detection
schemes, as discussed in the section "Detection Schemes."

Code
κ∆τ Generator
Next
Hypothesis

N

>γ
Y
Verification

FIGURE 2. The time-domain parallel/hybrid search with MTC.

Code
Generator

Hybrid search strategy
In the hybrid search strategy, a subset of all hypotheses is tested simultaneously at a time. As an example, a receiver utilizes
N Hc (or N Hf ) correlators in parallel to test the N Hc code-phase
hypotheses for each Doppler-frequency hypothesis (or vice

Z1

Correlator-2 Zco
Z2
∑Nco
G (·)

D

Parallel (complete) search strategy

G (·)

...

y [n]

Zco

Find the Maximum

Correlator-1
∑Nco

...

may employ the double- (or multiple-) dwell search strategy
[10]. The idea is to test hypothesis using a shorter correlation
time (also known as dwell time) in the first stage of search to
quickly distinguish the true hypotheses H 1 from the incorrect hypotheses ( H 0 's). As an example, in the first stage of a
double-dwell search strategy, an acquisition function performs
hypothesis testing with a smaller coherent dwell time Tco,1, and
when a correlation output is found larger than the first stage
threshold c 1, the acquisition function performs the second test
for the same hypothesis using a longer coherent dwell time
Tco,2 (2 Tco,1) and a larger threshold c 2 (2 c 1) . As a result, the
MAT of the double-dwell search, n T,D, can be roughly one half
of n T,S for Tco,1 = Tco /2 when the incoming signal is strong
enough (i.e., when Pm and P f are negligible), where the subscripts S and D represent the single and double-dwell searches, respectively. In general, in the multiple-dwell search, longer
dwell time and higher detection threshold are used in the latter
stages, and the detection threshold for each stage needs to be
carefully selected for optimal acquisition performance, i.e., the
minimum MAT.

...

To reduce the MAT n T , a receiver with a single correlator

rev 6x@ U y = IDFT " DFT " x ,* $ DFT " y ,, = IDFT " X * $ Y ,,
(4)

FFT
FFT

y [n]

( )∗
Y

X∗
YB
Circular
Shift

IFFT

N

G (.)

Z Find the
Maximum

>γ

Y
Verification

FIGURE 3. The frequency-domain parallel/hybrid search with MTC.

IEEE SIGNAL PROCESSING MAGAZINE

|

September 2017

|

63
Table of Contents for the Digital Edition of Signal Processing - September 2017
