Designing Low-Correlation GPS Spreading Codes with a Natural Evolution Strategy Machine-Learning Algorithm

2.1 Binary Sequence Representation

For mathematical convenience, we represent a binary sequence with elements of the set {0, 1} as a sequence with elements of the set {+1, −1} by using the following conversion:

1

where and represent the i-th element of the two binary sequence representations. In this paper, unless otherwise specified, we represent sequences using the (+1, −1) binary representation. To denote sequences with the (0, 1) binary representation, we utilize an additional superscript of (0, 1), i.e. .

The (+1, −1) representation of the binary sequences simplifies the auto-correlation and cross-correlation computations performed on one or more binary sequences. In particular, an exclusive-OR operation (i.e., b₁ ⊕ b₂) between two elements of the (0, 1) binary representation becomes a simple multiplication operation (i.e., b₁ · b₂) between two elements of the (+1, −1) binary representation, as illustrated in Figure 2.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 2

Illustration of the conversion from the (0, 1) binary sequence representation to the (+1, −1) representation used for mathematical convenience; consequently, the exclusive-OR operation between elements of the (0, 1) representation becomes a multiplication operation.

2.2 Periodic Auto-Correlation and Cross-Correlation

Using the (+1, −1) binary sequence representation defined in Equation (1), let represent the k-th binary sequence in a family of length-ℓ spreading code sequences. Let represent the i-th element of the sequence, where and represent the set of all integer values. Because is a periodic sequence, we have that . The normalized, periodic, even auto-correlation of sequence k at a relative delay of δ bits is defined as:

2

Similarly, in Equation (3) we define the normalized, periodic, even cross-correlation between sequences k and m at a relative delay of δ bits as:

3

The even correlation is distinguished from the odd correlation, which defines the correlation in the case that a data flip occurs within the integration period of the correlators (Wallner et al., 2011; Winkel, 2011). Correspondingly, the odd correlation for sequence k would be computed by flipping the sign of the second multiplicative terms of Equation (2) and (3), i.e. and respectively, when i < δ.

2.3 Algorithmically Generable GPS Spreading Codes

Currently, all broadcast GPS signals use algorithmically generable spreading code sequences. The legacy L1 C/A GPS signal, for example, uses length-1023 Gold codes, which can be generated with two 10-bit linear feedback shift registers (LFSRs), as shown in Figure 3. Gold codes (Gold, 1967) are a class of binary spreading code families which can be generated from two maximum-length sequences, or m-sequences. Maximum-length sequences are pseudorandom sequences of length ℓ = 2ⁿ −1, which are generated using an n-bit LFSR (Golomb, 2017).

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

Diagram of the linear feedback shift register (LFSR) pair with their corresponding characteristic equations (G1 and G2) utilized to generate length-1023 bit Gold codes used in GPS L1 C/A (Navstar GPS Joint Program Office, 2021a); only two 10-bit LFSRs are required for the generation of the GPS L1 C/A spreading codes.

Recently developed for the modernized GPS L1C signal, Weil codes are families of spreading codes which were initially proposed by Guohua and Quan (2002) and further analyzed and proposed for the L1C signal by Rushanan (2006, 2007). A Weil code family exists for any prime number sequence length-p and is generated from the corresponding length-p Legendre sequence, constructed from the Legendre symbol (Legendre, 1808; Yan, 2002). In this work, we construct both Gold codes and Weil codes in order to compare the performance of these spreading code families utilized in GPS with the performance of the spreading codes generated from our proposed NES machine-learning algorithm.

2.4 Natural Evolution Strategy Algorithms

Natural evolution strategies (NES; Kochenderfer & Wheeler, 2019; Rechenberg, 1973; Wierstra et al., 2014, 2008) are a subset of stochastic optimization methods which model a probability distribution, or a proposal distribution, over the optimization design space. Each sample from this proposal distribution outputs a candidate design point. In the context of designing navigation spreading codes, for example, each sample of the proposal distribution would output a set of binary sequences. NES requires choosing a family of parameterized proposal distributions , explicitly defined as:

where Θ is the set of possible vector-valued parameters θ defining each distribution in the family and where represents the design space over which we are optimizing.

Within the specified family of probability distributions, NES methods directly optimize the proposal distribution p_θ with respect to its parameterization θ in order to guide the search process towards higher performing regions of the design space. NES algorithms are especially useful for non-convex optimization problems with large design spaces, including combinatorial design spaces, which applies to our application of interest with the design of navigation spreading codes.

For high-dimensional design spaces, often diagonal covariance matrices are considered for the proposal distribution in order to improve computational efficiency with regards to the number of NES parameters to optimize as well as sample efficiency with regards to the number of required Monte Carlo samples to effectively estimate the search gradient during the optimization step (Schaul et al., 2011; Wierstra et al., 2014). Further variations of traditional NES methods have also been explored to handle highly multi-modal optimization landscapes by leveraging heavy-tailed distributions, including those with undefined variances, such as the Cauchy distribution (Schaul et al., 2011).

NES methods optimize the proposal distribution within the defined family by seeking to minimize the expected objective function J, defined as:

4

where x represents a particular point in the design space represents the probability of selecting x given the parameter θ, and f(x) represents the objective function value of the design point x, which we seek to minimize. Thus, NES methods seek to find the best proposal distribution by solving the optimization problem:

5

To optimize the proposal distribution, the gradient of the expected objective function, i.e. ∇_θ J(θ), can be estimated using Monte Carlo sampling of the objective function using the current proposal distribution (Glynn, 1990; Kochenderfer & Wheeler, 2019; Mohamed et al., 2020):

6

7

8

9

where N represents the number of samples from the proposal distribution and xⁱ represents the i-th sample. Equations (6) and (7) demonstrate the so-called log-derivative trick which is observed in a variety of machine-learning contexts, including reinforcement learning and variational inference (Mohamed et al., 2020).

From this gradient estimate, using any first-order optimizer (e.g. stochastic gradient descent algorithm, Adam [Kingma & Ba, 2015]), NES improves its proposal distribution vector-valued parameter θ in order to minimize the expected objective function in Equation (4):

10

where g_opt is the generic first-order optimizer utilized to iteratively improve the proposal distribution. As illustrated in Figure 4, this optimization process increases the probability of design points which lead to lower values of the objective function f to be minimized and decreases the probability of those which result in higher values of the objective function. Indeed, the stochasticity of the proposal distribution induces the NES algorithm to explore the high-dimensional design space and further improve its proposal distribution to output better performing design points.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 4

Illustration depicting how the NES algorithm optimizes the expected objective J(θ); from Instance A to Instance B, the NES optimizer updates the parameters of the proposal distribution in order to increase the likelihood of design points which lead to lower values of the objective function (indicated by the green sampled points), while decreasing the likelihood of design points which have higher objective function values (indicated by the red sampled points). This update then guides the proposal distribution down the objective function landscape in Instance B toward regions where the objective is lower. The optimizer again repeats this process from Instance B to Instance C, thereby further guiding the proposal distribution down the objective function landscape. Indeed, the stochasticity of the proposal distribution induces the NES algorithm to explore the design space; and the optimization step iteratively steers the search process toward better performing regions of the design space, where the objective function value is lower.

3.1 High-Level Learning Framework

For the spreading code design application, the machine-learning framework utilized is represented at a high level in Figure 5. A code generator maintains a proposal distribution over the spreading code design space. Then, an evaluator assesses the performance of the code generator with respect to the objective function f by sampling from its proposal distribution.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 5

High-level learning framework utilized for spreading code generation; the code generator outputs a set of sampled candidate code sets which are assessed by the evaluator. From the sampled design points and corresponding objective function values, the optimizer improves the proposal distribution by updating its parameters as represented by a generative neural network.

The objective function represents an evaluation metric for the spreading code family based on the auto- and cross-correlation properties of the code set. Finally, as in Equation (9), the optimizer estimates the gradient of the expected objective function with respect to the parameters of the proposal distribution, as represented by a generative neural network (GNN). The optimizer then updates the network parameters in order to improve the proposal distribution for the code generator.

3.2 Gaussian Proposal Distribution Representation

Using a neural network architecture, we represent a probability distribution over the design space of all possible binary spreading code families. Thus, the parameters of the proposal distribution θ correspond to the hidden layers of the network. As depicted in Figure 6, for the code generator to output a set of binary codes, it must sample from this proposal distribution provided by the GNN with the currently learned network parameters θ. For a concise introduction to artificial neural networks, see Section A1.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 6

Illustration of generative neural network (GNN) and proposal distribution representation. The GNN outputs the mean vector of the multivariate Gaussian proposal distribution from which a sampled output code set for the complete spreading code family is generated. In particular, the sampled output code set is a binary vector of length-Kℓ bits, where K denotes the number of codes in the family and ℓ denotes the length of each spreading code sequence. With this representation of the proposal distribution, the network parameters correspond to the NES parameters θ, which are optimized during training.

We modeled the code design proposal distribution as an uncorrelated multivariate Gaussian family as depicted in Figure 7, in which each component corresponds to an index in the complete family of binary spreading codes. Our neural network model represents this proposal distribution by parameterizing the mean vector of the Gaussian distribution via a bounded output activation function, such as the logistic or hyperbolic tangent output activations. The variance σ² of each component is maintained as a constant value. We can represent this Gaussian proposal distribution in terms of the network parameters θ as:

11

where K denotes the number of codes in the family, ℓ denotes the length of each sequence in the code family, represents the identity matrix of size (m × m) where m is a positive integer, and μ(θ) represents the mean of the Gaussian proposal distribution, as output by the GNN with parameters θ. Note that the mean of p_θ is bounded, i.e. μ(θ) ∈ [μ_L, μ_U]^Kℓ, due to the bounded nature of the output activation function of the network.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 7

Illustration of the proposal distribution utilized for spreading code design; we model the code design proposal distribution as an uncorrelated multivariate Gaussian family, where each component corresponds to an index in the family of binary spreading codes. Correspondingly, the total length of the spreading code set is Kℓ, where K denotes the number of codes in the family and ℓ denotes the length of each binary spreading code sequence.

Due to the uncorrelated model of the multivariate Gaussian proposal distribution, each component represents a univariate Gaussian distribution over each binary value in the spreading code family. As depicted in Figure 7, to obtain a random output family of spreading codes, the code generator first samples directly from the multivariate Gaussian proposal distribution defined in Equation (11) (i.e., x ~ p_θ) From this sampled vector x, the output code set is deterministically obtained by discretizing each component according to a threshold ζ defined in Equation (13), which we choose to be the midpoint of the bounded output range of the GNN. Correspondingly, the output binary code family can be defined in an element-wise manner as in Equation (14):

12

13

14

Thus, after sampling the design point x from the proposal distribution p_θ, if a component of x is above the threshold ζ, the corresponding sampled bit in the output binary code set is a one; otherwise, the corresponding bit is a zero. Note that the design space , where , is in fact a continuous design space. Indeed, we map each continuous design point x to a binary vector according to the threshold ζ as in Equation (14). Correspondingly, we evaluate the performance of the design point x by utilizing its discretized binary vector with the spreading code evaluation metric, as defined in Section 3.3.

3.3 Spreading Code Evaluation Metric

In the NES framework, the evaluation metric provides feedback to the code generator in order to improve its proposal distribution. In this work, we consider the mean-square non-central even auto-correlation and the mean-square even cross-correlation as the two objectives to minimize, defined respectively as:

15

16

where K represents the number of sequences in the output code family , ℓ represents the length of each sequence, represents the number of pairs of sequences in the code family of size K, R_k represents the auto-correlation of the k-th sequence in the output code family as defined in Equation (2), and R_k,j represents the cross-correlation of sequences k and j of the output code family as defined in Equation (3).

In order to ensure the code generator reduces both objectives, we define the comprehensive objective function as the maximum of the two components from Equations (15) and (16):

17

Thus, to minimize the objective, the NES algorithm will seek to reduce both components of the objectives simultaneously, without compromising one component over the other. Indeed, modifications of the objective function in Equation (17) could be readily incorporated within this machine-learning framework. In particular, if seeking to design spreading codes with smaller auto-correlation sidelobes than cross-correlation sidelobes, one could scale f_AC by a corresponding factor that is greater than one in Equation (17), which would encourage the algorithm to generate codes that reduce the auto-correlation metric in comparison to the cross-correlation metric by the corresponding user-defined factor.

Furthermore, additional components of objectives could be incorporated into the comprehensive objective function, including, for example, odd correlation performance metrics and relative Doppler frequency correlation metrics. These additional objectives could be incorporated as new arguments within the maximization function of Equation (17) with relative scaling factors if desired, or these objective could be combined via a weighted summation, as proposed in Soualle et al. (2005).

3.4 NES Optimization

We optimize the network parameters θ, which define the proposal distribution p_θ, by following the NES optimization process described in Section 2.4. To reduce the variance in the gradient estimate, we incorporate a constant baseline b, which is subtracted from the objective function in the gradient estimate expression of Equation (9; Mohamed et al., 2020). Thus, with the baseline subtraction, the gradient estimate from Equation (9) becomes:

18

where N represents the cardinality of the batch of samples {x¹, x², …, x^N}. For our constant baseline b, we utilize the mean return in the current batch of samples, defined as:

19

Subtracting a constant value does not introduce any bias in the gradient estimate, but it can significantly reduce its variance (Mohamed et al., 2020; Wierstra et al., 2008). Indeed, by reducing the variance of the gradient estimate, we observe improved convergence and overall learning performance during training. Section 4.2 demonstrates the learning rate of the NES algorithm with and without the incorporation of this baseline from Equation (19).

4.1 Details of Experimental Setup

We validated the ability of our NES machine-learning algorithm to devise low-correlation spreading codes and further compared its performance with that of well-chosen families of equal-length Gold codes and Weil codes. We compared the performance of our algorithm with Gold codes of length-63, 127, 511, and 1023 bits. Similarly, since Weil codes only exist for sequence lengths that correspond to a prime number length, we compared our algorithm with Weil codes of length-67, 127, 257, 521, and 1031 bits.

From our NES method, we generated sequences for family sizes of three codes up to 31 codes. We additionally compared our proposed algorithm with the best performing code family across 10, 000 sampled families of Gold codes and Weil codes. In a few of the sample runs of Gold and Weil codes, we observed a large deviation in the auto- and cross-correlation cost components which frequently led to worse performance on the overall objective defined in Equation (17). In these instances, when possible to reduce the deviation in auto- and cross-correlation objectives, we would resample the conventional code families, leading to an improvement in the performance metric of the Gold and Weil codes. The Gold and Weil code performance results have been updated since those presented in our previous conference paper (Mina & Gao, 2020), resulting in similar or slightly worse performance of the Gold and Weil codes on the overall objective.

The details of our NES machine-learning algorithm are indicated in Table 1. We utilize a slightly smaller learning rate for learning families with sequences of over length-500 bits, since we observed more consistent performance with a reduced learning rate for these longer sequence test cases. We use the hyperbolic tangent function as our bounded output activation function and the Adam algorithm (Kingma & Ba, 2015) as the optimizer of the GNN.

Furthermore, we compared the performance of our algorithm with that of an analogous genetic algorithm which was set to optimize over the same maximization evaluation objective defined in Equation (17). The GA implementation used fitness proportionate selection (Holland, 1992), which stochastically selected a candidate solution from the population with a probability proportional to its normalized objective. Selected individuals were recombined using uniform crossover (Syswerda, 1989) which allowed for greater recombination of candidate solutions and was observed to have better performance during initial testing. We additionally incorporated elitism (Baluja & Caruana, 1995), which ensured that the genetic algorithm would continuously improve during its optimization process.

In Table 2, we describe the parameters of the analogous genetic algorithm. For the GA to be comparable with the NES method, we set its population size to be the batch size of the NES machine-learning algorithm, and we set the number of iterations for both algorithms to be the same.

4.2 Effect of Baseline Incorporation on Learning Performance

Figure 8 demonstrates the effect of incorporating the constant mean baseline on the learning performance during training, as measured by the normalized maximum correlation objective, i.e. max{f_AC, f_CC}, which the algorithm seeks to minimize. For both of the code length scenarios shown in Figure 8, we observed that the incorporation of the baseline, shown in violet, led to significant improvement in the learning performance during training due to the reduction of variance in the gradient estimate. In particular, the baseline incorporation allowed for more systematic learning and more consistent improvement on the correlation objective.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 8

Training performance on the normalized maximum correlation objective, i.e. max(f_AC, f_CC), of the NES machine-learning algorithm, with (violet) and without (green) baseline incorporation; we observe that baseline incorporation leads to faster and more consistent learning performance during training.

4.3 Comparison with Best Performing Gold and Weil Codes

Figures 9 and 10 show the converged performance of our NES algorithm after training, comparing it with the best-performing sets of Gold and Weil code families of equal length. We plotted the final performance in terms of the maximization evaluation objective defined in Equation (17), i.e. max{f_AC, f_CC}, as a function of the code family size. From these results, we empirically observed how designing spreading code sequences for larger family sizes generally leads to worse performance on the optimization objective for all types of code sequences. As a result, developing a flexible optimization framework to tailor the design of the code family to the desired, smaller number of spreading codes may lead to better performance of the complete navigation system.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 9

Comparison of the proposed NES machine-learning method with that of well-chosen Gold and Weil code families as a function of family size; performance is optimized in terms of the maximization evaluation objective, i.e. max(f_AC, f_CC), defined in Equation (17), plotted here in terms of the normalized correlations. The Gold code correlation performance is indicated in the gold line with circle markers denoting the particular, discrete set of family sizes tested in each case, while the Weil code performance is indicated in blue with × markers and the performance of the codes generated by our proposed NES algorithm is indicated in violet with asterisk markers. We observed that the NES method outperformed the best Gold and Weil codes across all tested sequence lengths and code family sizes.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 10

Comparison of the proposed NES machine learning method with that of well-chosen Gold and Weil code families as a function of family size for length-1023 and length-1031 sequences; performance is optimized in terms of the maximization evaluation objective, i.e. max(f_AC, f_CC), defined in Equation (17), plotted here in terms of the normalized correlations. The Gold code correlation performance is indicated in the gold line with circle markers denoting the particular, discrete set of family sizes tested in each case, while the Weil code performance is indicated in blue with × markers and the performance of the codes generated by our proposed NES algorithm is indicated in violet with asterisk markers. We observed that the NES method outperformed the best Gold and Weil codes across all tested code family sizes.

From Figures 9 and 10, we observe that the proposed NES method in violet outperforms the best Gold code and Weil code families across all tested code lengths and code family sizes. To determine if this performance improvement against the best-performing sets of Gold and Weil codes would continue for larger families of the NES-generated spreading codes, further testing would be required with more extensive memory and computational resources. In Section 4.5, we discuss how the proposed NES method scales with the spreading code length and the size of the code family, while discussing potential techniques to reduce the memory requirements and resources during the training process.

4.4 Comparison with Analogous Genetic Algorithm and Elitism

Finally, we compared our NES method with that of the analogous genetic algorithm described in Section 4.1. Figure 11 shows separate plots of the normalized correlation performance from length-127 up to length-1031 bit spreading code families. Both optimization algorithms sought to minimize the same spreading code correlation objective defined in Equation (17). The GA additionally incorporates elitism to guarantee the algorithm continuously improves during its optimization process. We observe in Figure 11 that our NES method consistently outperforms the implemented GA with elitism across all tested sequence lengths and family sizes.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 11

Comparison of the proposed NES machine-learning method with that of the analogous genetic algorithm with incorporated elitism; performance is optimized in terms of the maximization evaluation objective, i.e., max(f_AC, f_CC), defined in Equation (17), plotted here in terms of the normalized correlations. The genetic algorithm (GA) performance is indicated in green with + markers denoting the particular, discrete set of family sizes tested in each case, while the performance of our proposed NES method is indicated in violet with asterisk markers. We observe that for all spreading code lengths, the NES method outperforms the GA implementation in designing spreading codes which minimize the spreading code evaluation metric in Equation (17).

4.5 Scaling of Network Size with the Size of the Learned Code Family

With this proposed method, the total number of parameters in the GNN, and correspondingly the memory required for the network to train, scales quadratically with the length of the total code set to be determined (i.e., K ℓ total binary values for length-ℓ binary sequences and K codes). Indeed, these network parameters are only necessary during the training phase of the algorithm while the codes are being learned. Once the algorithm converges to a final, optimized spreading code family, the network parameters are no longer needed and can safely be discarded. However, the memory required during training correspondingly scales quadratically with the length of the total code set, thereby requiring significantly greater investments in computing resources, especially for very large family sizes of longer spreading codes, such as a family of 420 length-10,230 sequences as used for GPS L1C (Navstar GPS Joint Program Office, 2021b).

Besides simplifying the neural network structure, one could reduce memory requirements for training large-scale neural networks by modeling network parameters with lower precision as well as by exploring the use of sparsity in the network model, where some of the network parameters are set to zero and are correspondingly no longer necessary to store in memory. In this work, we used a fully connected network model; however, leveraging sparsity has been shown to significantly reduce the number of network parameters required for deep networks while achieving similar or even better performance (Mostafa & Wang, 2019; Sohoni et al., 2019). Another advantage to utilizing sparse models is the corresponding reduction in the number of gradient computations as well as the size of the momentum buffer for the optimizer, thereby also leading to reduced memory requirements during training.