1 of 29

Large-scale GNSS Spreading Code Optimization

Alan Yang, Tara Mina, Stephen Boyd, and Grace Gao

ION GNSS+ 2024

2 of 29

Advances in Satellite Navigation

1

All can benefit from optimized spreading codes / PRN codes

Navigation Technology Satellite-3 (NTS-3)

LEO PNT, e.g.

Xona Space Systems

Future Lunar PNT applications

3 of 29

Spreading Codes

2

Low auto-correlation: distinct peak & noise tolerance

Low cross-correlation: low inter-system interference

4 of 29

Algebraic vs. Memory Codes

  • Algebraic codes
      • May be generated using shift registers
      • Are only available at certain code lengths, limited number of codes
      • Includes Gold codes, Weil codes
  • Memory codes
      • Directly stored in digital memory, instead of generated
      • Can be optimized for a specific design objective functions
      • Used by Galileo constellation[1]

[1] Wallner et al., ION GNSS, 2007

3

5 of 29

Outline

  • Spreading code optimization problem
  • Efficient computation
  • Bit-flip descent method
  • Experiments

​

4

6 of 29

Auto- and Cross-correlation

  •  

5

7 of 29

Auto- and Cross-correlation

6

 

 

 

 

 

 

 

8 of 29

Spreading Code Optimization Problem

  •  

7

 

 

9 of 29

Challenges

  •  

8

10 of 29

Outline

  • Spreading code optimization problem
  • Efficient computation
  • Bit-flip descent method
  • Experiments

​

9

11 of 29

Efficient computation

  •  

10

12 of 29

Correlation Matrix Update

  •  

[2] Winkel, US Patent, 2011

11

13 of 29

Objective Function Delta

  •  

12

14 of 29

Delta Matrix Update

  •  

13

15 of 29

Outline

  • Spreading code optimization problem
  • Efficient computation
  • Bit-flip descent method
  • Experiments

​

14

16 of 29

Bit-flip Descent[3,4]

  •  

[3] Alaee-Kerahroodi et al., IEEE Trans. Sig. Proc., 2019

[4] Yang et al., ION GNSS+ 2023

15

-1

1

-1

-1

1

-1

1

1

-1

-1

1

-1

1

1

-1

-1

-1

1

-1

-1

1

-1

1

1

1

-1

-1

-1

1

1

1

-1

1

-1

-1

1

1

-1

1

-1

-1

-1

1

1

-1

-1

1

-1

-1

1

-1

1

-1

-1

1

-1

1

1

-1

-1

1

-1

1

1

-1

-1

-1

1

-1

-1

1

-1

1

1

1

-1

-1

-1

1

1

1

-1

1

-1

-1

1

1

-1

1

-1

-1

-1

1

1

-1

-1

1

-1

-1

1

1

1

-1

-1

1

-1

1

1

-1

-1

1

-1

1

1

-1

-1

-1

1

-1

-1

1

-1

1

1

1

-1

-1

-1

1

1

1

-1

1

-1

-1

1

1

-1

1

-1

-1

-1

1

1

-1

-1

1

-1

-1

1

1

1

-1

-1

1

-1

1

1

-1

-1

1

-1

1

1

-1

-1

-1

1

-1

-1

1

-1

1

1

1

-1

-1

-1

1

1

1

-1

1

-1

-1

1

1

-1

1

-1

-1

-1

1

1

-1

-1

1

-1

-1

1

1

1

-1

-1

1

-1

1

1

-1

-1

1

-1

1

1

-1

-1

-1

1

-1

-1

1

-1

1

1

-1

-1

-1

-1

1

1

1

-1

1

-1

-1

1

1

-1

1

-1

-1

-1

1

1

-1

-1

1

-1

-1

1

17 of 29

Bit-selection Strategies

  •  

16

18 of 29

Bit-selection Strategies

  •  

17

19 of 29

Advantages

  • Low per-iteration computational cost
  • Guaranteed to converge
  • Performance is on-par with more sophisticated methods[4]
  • Requires little to no tuning

​

[4] Yang et al., ION GNSS+ 2023

18

20 of 29

Outline

  • Spreading code optimization problem
  • Efficient computation
  • Bit-flip descent method
  • Experiments

​

19

21 of 29

Test Cases

20

​

​

​

GPS L1 C/A[5]

1023

63

Galileo E1[6]

4092

100

GPS L1C[5]

10230

210

[5] MilComm & PNT Directorate, Space Systems Command 2022

[6] European Union, 2021

22 of 29

 

  •  

21

23 of 29

 

22

 

 

24 of 29

Performance comparison

23

 

 

 

25 of 29

Performance comparison

24

​

Greedy

​

​

Adaptive

GPS L1 C/A

42.0%

42.1%

42.1%

42.2%

Galileo E1

19.0%

35.1%

36.6%

36.6%

GPS L1C

0.3%

16.2%

25.8%

26.0%

Percent improvement over initial codes after 24 hours

26 of 29

Extensions and Variations

  • Variations on the objective function
      • Weighted objective functions
      • Minimax (worst-case) objective
  • Variations on the correlation function
      • Aperiodic cross-correlation[7]
      • Secondary codes [7]
      • Doppler effects [8]
  • Constraints[1,9]
      • Balanced codes (equal number of +1 and -1’s)
      • Autocorrelation sidelobe zero

[7] Soualle et al., ENC, 2005

[8] Yang et al., ION ITM 2024

[9] Yang et al., EURASIP J. Adv. Sig. Proc., 2024

[1] Wallner et al., ION GNSS, 2007

25

27 of 29

Conclusions

  • There is a need for spreading code optimization methods that work well for large-scale problem instances
  • Bit-flip descent methods are particularly suitable
      • Low per-iteration cost that scales roughly linearly with problem size
      • Can effectively optimize code families with millions of bits
  • Little to no tuning required to work well
      • Feasible to test different problem configurations

26

28 of 29

Acknowledgements

27

29 of 29

Thank you!

28