Aerospace and Electronic Systems Magazine August 2017 - 56

Acquisition of GNSS Signals with Secondary Code
(NS/2 - 1) 2NP additions in average (i.e. if half of the samples of
s′ are zeros), and the addition of a′i and xΣ requires 1 × 2NP additions. Thus, the total number of operations for the NS outputs yk
is N S − 1 + N S ( N S / 2 − 1 + 1) 2 N P = N S2 / 2 + N S − 1 2 N P. Table
5 shows the number of additions of both equations considering
50% of zeros in s′ and for the actual number of zeros with the
GNSS secondary codes. It can be seen that when NS increases, the
reduction of the number of operations approaches 50% in the worst
case, and it is slightly above 50% for the GNSS signals. The same
reduction is obtained for the post-FFT equation. Therefore, since
this method reduces the number of operations, it can be useful for
digital signal processor based receivers for example.
Now let's see the applicability for FPGA based receivers. For
this, we will focus on the pre-FFT sequential implementation and
(13). Previously, with (8), for each portion of the output (y0, y1, ...), it
was necessary to combine NS portions of the incoming code (x0, x1,
...) before performing one FFT-based correlation, as already shown
in Figure 15. Now, with (13), for each portion of the output (y0, y1,
...), it is necessary to combine only about half of the portions of the
incoming code (x0, x1, ...) since in average half of the samples of s′n
are zero. Therefore, if a portion of the incoming code is multiplied
by 0, we simply do not read it from the memory, and therefore the
reading of the memory is about twice faster. However, we also need
to add a special combination of the incoming code (xΣ, the sum of
all the portions). But since this special combination is identical for
all the portions of the output, we can compute it only once and store
it into another memory. This memory will then be read when we
will want to add xΣ and a′i. Therefore, accessing this second memory
does not impact the processing time, because it is read simultaneously to the last xi used to compute a′i, as shown in Figure 24. The
corresponding implementation is shown in Figure 11.
For example, if we consider that s = [-1 1 1 -1]T, then s′ = [-2
0 0 -2]T, and the combinations of the portions of the incoming
code become

(

)

(

)

a′0   −2 0 0 −2   x 0 
 ′ 
 
 a1  =  −2 −2 0 0   x1  .
a′2   0 −2 −2 0   x 2 
  
 
a′3   0 0 −2 −2   x3 

Figure 11.

Implementation of the pre-FFT secondary code removal using the
proposed technique (see (13)) computing each combination of the input
sequentially. See the timing diagram in Figure 24.

Therefore, to compute each portion of the output (y0, y1, ...), it is
necessary to read only two portions of the incoming code (x0, x1,
...) instead of four, as illustrated in Figure 24. The processing starts
by accessing all the portions of the input (x0, x1, ...) and summing
them to compute and store xΣ. Then, it works as the pre-FFT sequential implementation except that only the portions of the input
that are not multiplied by zero are accessed, and that xΣ will be
added when each a′i will be available.
With this implementation, the memory needed is twice 4NP(B0
+ ⌈log2NS⌉) bits for the accumulation, as for the pre-FFT parallel implementation using two accumulators. However, looking at
the processing time of both implementations (Figures 17 and 24),
the one using the new method can have a lower processing time
because it is possible than more than half of the sample of s′ are
zeros, and because the zero-padding has less impact.
For example, the L5 pilot secondary code contains 12 ones and
8 minus ones. Therefore, the code s′ will contain 12 zeros, i.e. 60%
of the total length. Making the same numerical application as previously used with the "low-cost" receiver, the memory needed for both
implementations is 72NP = 1,474,560 bits, and the processing time is
36,003NP + 2NZ = 737,390,592 clock cycles for the pre-FFT sequential implementation using the new method, and 40,005NP + 1,002NZ
= 843,927,552 clock cycles for the pre-FFT parallel implementation
using two accumulators, which means a reduction of about 12.6%.
Therefore, the use of the proposed technique may be interesting for
a hardware implementation. Note that the use of double read access
can be exploited to approximately halve the processing time.
Of course, the choice of subtracting or adding one to the secondary code in (12) depends on the code that we have. The goal

(15)

Table 5.

Number of Additions of Vector of 2 N P Points for (8) and (13), in the Worst Case (50% of Zeros in s′), and in the
GNSS Case (60% of Zeros in s′ for L5 and E1 Codes, 53.44% of Zeros in s′ on Average for E5 Codes)
NS

for (8)

Worst Case
for (13)

GNSS Case

Reduction

for (13)

Reduction

8.3%

380

219

42.4%

179

52.9%

600

336.5

43.9%

274

54.3%

100

9,900

48.5%

4,755

52.0%

5,099

IEEE A&E SYSTEMS MAGAZINE

AUGUST 2017

Table of Contents for the Digital Edition of Aerospace and Electronic Systems Magazine August 2017