# Optimized Method for Generating and Acquiring GPS Gold Codes

Authors: Khaled Rouabah; Salim Attia; Rachid Harba; Philippe Ravier; Sabrina Boukerma
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

We propose a simpler and faster Gold codes generator, which can be efficiently initialized to any desired code, with a minimum delay. Its principle consists of generating only one sequence (code number 1) from which we can produce all the other different signal codes. This is realized by simply shifting this sequence by different delays that are judiciously determined by using the bicorrelation function characteristics. This is in contrast to the classical Linear Feedback Shift Register (LFSR) based Gold codes generator that requires, in addition to the shift process, a significant number of logic XOR gates and a phase selector to change the code. The presence of all these logic XOR gates in classical LFSR based Gold codes generator provokes the consumption of an additional time in the generation and acquisition processes. In addition to its simplicity and its rapidity, the proposed architecture, due to the total absence of XOR gates, has fewer resources than the conventional Gold generator and can thus be produced at lower cost. The Digital Signal Processing (DSP) implementations have shown that the proposed architecture presents a solution for acquiring Global Positioning System (GPS) satellites signals optimally and in a parallel way.


---

## Body

## 1. Introduction

The spreading codes are the most important elements of the Direct Sequence Code Division Multiple Access (DS-CDMA) communications [1]. According to their performances and their characteristics, they will determine the quality of transmission and communication because they have the properties of a White Gaussian Noise (WGN). The code sets can be divided into two classes: orthogonal codes, like Walsh Hadamard codes, mainly used in Interim Standard 95 (IS-95) and CDMA 2000 systems [2–5], Orthogonal Variable Spreading Factor (OVSF) codes [6], used in Wideband CDMA (WCDMA) [7] and Time Division Synchronous CDMA (TD-SCDMA) systems [8], orthogonal Gold codes [9, 10], and Golay complementary codes [11–17] and those being nonorthogonal or pseudorandom codes, such as m-sequence codes [18–20], Gold codes [21, 22], Gold-like codes, Kasami codes [23, 24], Weil codes [25, 26], and Barker codes [27]. The performances of a CDMA system are largely dependent on the characteristics of spreading codes and their principle of generation. GPS system uses Gold codes that are generated by two LFSRs expressed each as coefficients of a polynomial. The two polynomials corresponding to the two LFSRs form a preferred polynomial pair of a Gold code. The whole code sequence is defined solely by the generator polynomials and the initial states. The receivers, thus, only need to store the generators functions instead of the whole sequence and the memory space is saved [28]. The codes generation has attracted much attention in both industrial and academic fields. The knowledge of the spread spectrum codes is a prerequisite for designing receivers capable of acquiring and tracking all satellites in the constellation. Global Navigation Satellite Systems (GNSS) include the American GPS, the European Galileo, the Russian GLObal NAvigation Satellite System (GLONASS), and the Chinese BeiDou. Galileo satellite navigation system will use memory codes for the bands E1-OS (Open Service) and E6 that are hard for reverse engineering [26]. These codes are random sequences like Coarse Acquisition (C/A) code used in GPS but do not have a common code generator algorithm. According to [25, 26], the principle of memory codes is to generate a family of codes that fulfills the properties of a random noise at maximum for a given code length. The resulting codes are then optimized by means of artificial intelligence like genetic algorithm in order to have codes with properties that are needed for optimal operation of Galileo system. The optimized codes are then stored in the receiver memory, which is more expensive compared to codes generators. Hence, a lot of memory is required for full system support. Although memory codes will provide an increase in receiver tracking performances, their implementation has a direct implication in the receiver design. In fact, memory increases the hardware cost, the complexity, the use of signal processing resource, and the power consumption of the receiver when compared to LFSRs. As manufacturers move towards low-cost and low-power ASIC implementations, memory code implementation will become more challenging [29]. In this paper, we propose a simpler and faster pseudorandom code generator that can be efficiently initialized to any desired code, with a minimum delay. In addition, we propose an architecture with fewer resources than the conventional ones which can be produced at lower cost. We propose also a new form of the correlation function calculation that is compatible with these codes. The paper is organized as follows: we begin with discussion of the classical principle of generation and the properties of C/A-GPS Gold codes. The principle of the proposed architecture for these codes’ generation and correlation principles are provided in Section 3. After that, we present the results of DSP implementation and, finally, we end up by some conclusions.


## 2. Principle of Generating and Acquiring C/A-Gold Codes

The acquisition is the tiresome job of searching a three-dimensional space for the correlation peak. One dimension is the satellite vehicle signal number (SN) (at least if the receiver has no a priori knowledge). The second dimension is the frequency space, since an unknown Doppler shift of the transmitted signal and an inaccurate frequency reference in the receiver produce a high frequency-offset uncertainty. The third dimension is the code phase [30, 31].Many modern GPS receivers have 8, 12, or 16 channels in parallel to facilitate a faster search process. GPS system contains 32 codes. Each code is generated using a combination of two tapped LFSRsG1 and G2 as shown in Figure 1. Each LSFR generates a maximum-length Pseudorandom Noise (PRN) sequence of “N=2n-1” elements, where n, which is equal to 10 in GPS system, is the number of the LSFR stages as illustrated in Figure 1.Figure 1
LSFRs based Gold codes generator.A shift register is a set of one-bit storage or memory cells. When a clock pulse is applied to the register, the content of each cell shifts one bit to the right. The content of the last cell is “read out” as output [31].The two resulting 1023-chip-long sequences are modulo-2 added to generate a 1023-chip-long code, only if the polynomial is able to generate codes of maximum length. Every 1023rd period, the shift registers are reset with all ones, making the code start over.G1 register always has a feedback configuration with the polynomial: f(x)=1+x3+x10, meaning that state 3 and state 10 are feedback to the input. In the same way, G2 register has the polynomial: f(x)=1+x2+x3+x6+x8+x9+x10. To make different codes for the satellites, the outputs of the two shift registers are combined in a very special manner. G1 register always supplies its output, but G2 register supplies two of its states to a modulo-2 adder to generate its output. The selection of states for the modulo-2 adder is called the phase selection. SN is affected to each satellite of the constellation. Table 1 shows the combination of the phase selections (PS) for each satellite C/A-GPS code [31].Table 1
C/A-GPS code phase assignment.
GPS PRN SN
Code PS in G2
1
2
⊕
6
2
3
⊕
7
3
4
⊕
8
4
5
⊕
9
5
1
⊕
9
6
2
⊕
10
7
1
⊕
8
8
2
⊕
9
9
3
⊕
10
10
2
⊕
3
11
3
⊕
4
12
5
⊕
6
13
6
⊕
7
14
7
⊕
8
15
8
⊕
9
16
9
⊕
10
17
1
⊕
4
18
2
⊕
5
19
3
⊕
6
20
4
⊕
7
21
5
⊕
8
22
6
⊕
9
23
1
⊕
3
24
4
⊕
6
25
5
⊕
7
26
6
⊕
8
27
7
⊕
9
28
8
⊕
10
29
1
⊕
6
30
2
⊕
7
31
3
⊕
8
32
4
⊕
9The most important characteristics of the C/A codes are their correlation properties. The two important correlation properties of the C/A codes can be stated as follows [31].


### 2.1. Nearly No Cross-Correlation

All the C/A codes are nearly uncorrelated with each other. That is, for two codesCi and Cj for satellites i and j, respectively, the cross-correlation can be written as(1)Rijm=∑l=01022CilCjl+m≈0∀m.


### 2.2. Nearly No Autocorrelation Except for Zero Lag

All C/A codes are nearly uncorrelated with themselves, except for zero lag. This property makes it easy to find out when two similar codes are perfectly aligned. The autocorrelation property for satellitek can be written as(2)Rkkm=∑l=01022CklCkl+m≈0form≥1.In the very first time when a receiver is switched on, it has no information about its position or about the position of the satellites. The receiver has no information about which satellites are in view. The receiver starts a sky search by analyzing the input signal with respect to all known satellite ranging codes [32]. If the receiver has been initialized before, it generally uses almanac and ephemerides, the approximate user position, and approximate time estimate to provide aiding information in form of estimated Doppler shift and estimated time shift to the tracking loops. Depending on the availability of the information, three different acquisition modes are distinguished: cold start, hot start, and reacquisition start. In cold-start case, no information is available to help acquiring signals and determining the satellites in view; therefore, the acquisition times may take several minutes. In hot-start case, the receiver has a number of initialization parameters (almanacs or navigation messages), and the acquisition time is reduced to a few tens of seconds. Reacquisition start is the process when satellites signals have just been lost and are acquired again; therefore, the receiver has good knowledge of time and Doppler shift [32].The core element of the receiver is the correlation between the received signal and locally generated replica. The identification of one dedicated satellite signal is performed by searching for the maximum of its autocorrelation function, which works like a filter for all other satellites signals components [32].The acquisition of a specific satellite from the total constellation involves performing the correlation between the code corresponding to this satellite and its replica that is locally generated. Therefore, the number of locally generated replicas depends on the number of satellites that can be acquired. An increasing number of visible satellites increase the requirements of the hardware components and circuitry, which is a limitation of classical LFSR based Gold codes generator.


## 2.1. Nearly No Cross-Correlation

All the C/A codes are nearly uncorrelated with each other. That is, for two codesCi and Cj for satellites i and j, respectively, the cross-correlation can be written as(1)Rijm=∑l=01022CilCjl+m≈0∀m.


## 2.2. Nearly No Autocorrelation Except for Zero Lag

All C/A codes are nearly uncorrelated with themselves, except for zero lag. This property makes it easy to find out when two similar codes are perfectly aligned. The autocorrelation property for satellitek can be written as(2)Rkkm=∑l=01022CklCkl+m≈0form≥1.In the very first time when a receiver is switched on, it has no information about its position or about the position of the satellites. The receiver has no information about which satellites are in view. The receiver starts a sky search by analyzing the input signal with respect to all known satellite ranging codes [32]. If the receiver has been initialized before, it generally uses almanac and ephemerides, the approximate user position, and approximate time estimate to provide aiding information in form of estimated Doppler shift and estimated time shift to the tracking loops. Depending on the availability of the information, three different acquisition modes are distinguished: cold start, hot start, and reacquisition start. In cold-start case, no information is available to help acquiring signals and determining the satellites in view; therefore, the acquisition times may take several minutes. In hot-start case, the receiver has a number of initialization parameters (almanacs or navigation messages), and the acquisition time is reduced to a few tens of seconds. Reacquisition start is the process when satellites signals have just been lost and are acquired again; therefore, the receiver has good knowledge of time and Doppler shift [32].The core element of the receiver is the correlation between the received signal and locally generated replica. The identification of one dedicated satellite signal is performed by searching for the maximum of its autocorrelation function, which works like a filter for all other satellites signals components [32].The acquisition of a specific satellite from the total constellation involves performing the correlation between the code corresponding to this satellite and its replica that is locally generated. Therefore, the number of locally generated replicas depends on the number of satellites that can be acquired. An increasing number of visible satellites increase the requirements of the hardware components and circuitry, which is a limitation of classical LFSR based Gold codes generator.


## 3. Principle of the Proposed Method

In our proposed method, we use the bicorrelation between two different codesCit and Ckt. The main idea is that, in contrast to the intercorrelation function of two different C/A-GPS codes, which is always null, the bicorrelation function can be different from zero.The general expression of the bicorrelation is given by(3)RCiCkτ1,τ2=ECitCkt+τ1Ckt+τ2.By considering the same procedure as the autocorrelation function, we can determine analytically the approached mathematical model of RCiCkτ1,τ2. Here, we have considered three rectangular windows, a fixed one and two others that are, respectively, shifted by τ1 and τ2.In ideal case, which corresponds to the absence of noise, multipaths, and interferences, (3), for C/A-GPS codes, is found to be(4)RCiCkτ1,τ2=τ1+2Tc,for-2Tc≤τ1≤τ2,-2Tc≤τ2≤0,τ2+2Tc,forτ2≤τ1≤0,-2Tc≤τ2≤0,τ2-τ1+2Tc,for0≤τ1≤τ2+2Tc,-2Tc≤τ2≤0,τ1-τ2+2Tc,forτ2-2Tc≤τ1≤0,0≤τ2≤2Tc,-τ2+2Tc,for0≤τ1≤τ2,0≤τ2≤2Tc,-τ1+2Tc,forτ2≤τ1≤2Tc,0≤τ2≤2Tc,0,elsewhere.Here, we use the same principle as that used in [33]. In this case, as presented in Figures 2 and 3, two pyramids whose basis is hexagonal and symmetrical about the diagonal τ2=τ1 characterize the nonnull bicorrelation bidirectional plot. Besides, as illustrated in Figure 4, when considering either one of the plan sections {RCiCkτ1,τ2,τ2=τ1±αi}, we find exactly the ACF triangular waveform of the code Cit which is thus given by RCiCiτ1=RCiCkτ1,τ1±αi. Therefore,(5)ECitCit+τ1=ECitCkt+τ1Ckt+τ1±αi,which gives (6)Cit=CktCkt±αi,where αi is the specific time delay corresponding to the ith code, which permits deriving the ith satellite from the kth satellite. The centers m and n of the hexagons correspond, respectively, to the ACF peaks projections on the straight lines τ2=τ1+αi and τ2=τ1-αi.Figure 2
Plot of the bicorrelation of two Gold codes.Figure 3
Zoomed C/A-GPS code bicorrelation peak presenting a hexagonal basis.Figure 4
Graphical determination ofαi values.α
i, as illustrated in Figure 4, is found by determining the difference between m and n coordinates relative to either τ2 or τ1 axis.According to (5) and (6), we notice that it is possible to generate a C/A-GPS code Cit from the product of another code Ck(t) and its delayed version Ck(t±αi). For example, let us consider the bicorrelation of the two codes i=26 and k=31. This latter is found to be nonnull and the projections of the two autocorrelation peaks on the plan [RCiCkτ1,τ2,τ1], as presented in Figure 5, are b=124 chips and a=813 chips; therefore, αi=689 chips. Hence, according to (6), we conclude that code 26 may be generated from code 31 by multiplying this latter by its same version delayed by αi=689 chips.Figure 5
Example of determiningαi from the bicorrelation of codes i=26 and k=31.Consequently, this characteristic is going to be used to generate all the CA-GPS codes of the satellite constellation from the exclusive use of just one locally generated code. This latter, for convenience, is chosen to bec1t which is generated either by the LSFR generator or from the memory. To initiate the generation of the remaining codes, we will first look for all the codes ci for which Rcic1τ1,τ2≠0. As solutions, we obtain the eight codes ci(t) with [i=4,5,7,9,13,21,24,31]. Then, corresponding αi, which permit their generation from c1t, are determined graphically and given in Table 2. The set of codes so obtained, ci=c1(t)c1t-αi, with [i=4,5,7,9,13,21,24,31], represents the first category of codes generated from c1t.Table 2
Different categories of C/A-GPS Gold codes and their correspondingαi values.
First satellite code
First-category codes
α
i
Second-category codes
α
i
Third-category codes
α
i
1
4
802
8
248
28
424
16
553
32
179
27
827
5
84
10
510
17
433
22
448
30
164
7
169
2
879
3
186
11
659
12
199
14
138
15
506
18
810
23
716
9
605
6
38
20
810
13
553
25
424
29
179
21
3
24
827
19
679
31
257
26
689Afterwards, each of these eight codes will in turn be bicorrelated separately with the rest of the codes. In this case also, by solving for the codesci for which Rcickτ1,τ2≠0 with [k=4,5,7,9,13,21,24,31], we findFork=4:3 codes ci=c4tc4t-αi with [i=8,16,17].Fork=5:4 codes ci=c5tc5t-αi with [i=10,17,22,30].Fork=7:8 codes ci=c7tc7t-αi with [i=2,3,11,12,14,15,18,23].Fork=9:2 codes ci=c9tc9t-αi with [i=6,20].Fork=13:2 codes ci=c13tc13t-αi with [i=25,29].Fork=24:1 code ci=c24tc24t-αi with i=19.Fork=31:1 code ci=c31tc31t-αi with i=31.The cumulative set ofαi values, with [i=2, 3, 6, 8, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 30], is then graphically determined and given in Table 2 which gives the second category of 21 codes that are also initially generated from c1(t).By using the same reasoning, the last remaining two codesci with [i=28,32], which represent the third and last category, are obtained by replacing k=16 in (6) and solving for the codes ci for which Rcic16τ1,τ2≠0. Corresponding αi values graphically determined are given in Table 2.The different steps used to generate the whole set of the GPS constellation codes from the single codec1 are summarized in the flow chart of Figure 6.Figure 6
Flow chart showing the relation between all C/A-GPS codes.Based on these results, we can propose a new structure for acquiring all C/A-GPS codes. The principle of this correlation scheme is shown in Figure7. In this structure, the manner in which the reference C/A code is locally generated depends on the category to which it belongs. The codes of the first category are all generated directly from c1(n) by using the corresponding αi delay lines values of Table 2. Then, each one of these first-category codes is delayed separately with its corresponding αi as given in Table 2, to obtain the second category of codes. Finally, the third category of codes is generated by applying corresponding αi to the appropriate codes of the second category as specified in Table 2. By comparing the outputs of the different correlators, after an integration time to a specific threshold, we can easily detect the absence or the presence of any satellite of the constellation.Figure 7
The proposed acquisition algorithm structure.


## 4. DSP Implementation

As shown in Figure7, the basic element in the proposed C/A-GPS Gold code generation structure is the delay line, which can be implemented in a DSP by using a Digital Delay Line (DDL) that is an elementary functional unit for delay modeling. A fundamental building block of DDL is shown in Figure 8.Figure 8
DDL.The function of a delay line is to introduce a time delay corresponding toM samples between its input and output. Because M is an integer, the DDL can be implemented as a circular buffer, which is one of the highlights of a DSP. In fact, compared to linear buffer, circular buffer is more advantageous in terms of memory and access time. We can also implement the DDL as a Finite Impulse Response (FIR) filter with a transfer function that is given as follows:(7)Hz=z-M.The filter given by (7) has “M” poles at z=0 and “M” zeros at z=∞. Its frequency response is given as follows:(8)Hf=exp-j2πfM,f∈-1,1.The filter, given by (7) and (8), is an all-pass filter with linear phase and it can be implemented as C/A-GPS Gold codes generator [34].There are different DSP families with particular architectures. It is therefore necessary to choose the processor with the essential resources to meet specific needs. The ADSP BF537 processors, Analog Devices, Inc., can reach the highest performances in comparison to the other ones. Processors, ADSP BF537, are new members of the Blackfin family of Analog Devices, Inc., Intel Micro Signal Architecture (MSA), which offer very high performances and low power consumption with the usability advantage. They are clocked at speeds up to 600 MHz. ADSP BF537 processor is shown in Figure9.Figure 9
ADSP BF537 processor.The schemes implemented in this DSP, for our method and traditional LFSR method, are given, respectively, in Figures1 and 10 and the results are shown in Figure 11 as code representation in graphical mode. The obtained results illustrate that the C/A-GPS codes obtained with our method coincide with C/A-GPS LFSR codes.Figure 10
DSP implemented scheme.Figure 11
DDL based C/A-GPS Gold code.In addition, when we compare the execution time of the proposed method to that of the conventional one for one given code, we find that our architecture is 5.3883 times faster. Therefore, the proposed generation process, compared to the classical one, is approximately 172.4 times faster, which shows the efficiency of our method.


## 5. Conclusion

An efficient method for generating and acquiring C/A-GPS signals based on bicorrelation function principle is proposed in this paper. This method takes advantage of the relationships between the different C/A-Gold codes that are derived from the slices of the bicorrelation function. The proposed architecture, compared to the conventional ones, is less time consuming and has fewer resources since it uses a reduced number of XOR functions. In addition, it can be produced at lower cost and may be used for the acquisition of all C/A-Gold GPS satellites signals. The DSP implementations have shown that the proposed architecture presents a real solution for the optimal acquisition of GPS signals. Moreover, it can be easily extended to all CDMA PRN codes especially those of GPS and Galileo CDMA new generation systems.



---

*Source: 956735-2015-11-10.xml*