Designing Long GPS Memory Codes Using the Cross Entropy Method

Tara Mina, Alan Yang, Grace Gao

Abstract:	Beginning launches in 2026, the GPS IIIF satellite series will be the first GPS satellites to have a fully reprogrammable signal payload. This upcoming signal capability allows for the GPS signal to be modified and uploaded to satellites in orbit, providing new opportunities to re-explore the design of the GPS signal structure. Currently, all GPS signals use algorithmically generable codes (including Gold codes, short-cycled m-sequences, and Weil codes), which are binary sequences that can be generated from a smaller number of bits via an algorithmic procedure. However, there are several advantages to exploring the space of memory codes, which cannot be algorithmically generated, but must be defined and stored in memory as complete sequences. These advantages include increased flexibility in the choice of the code length and user-defined objective, as well as the ability to tailor the design to a particular code family size for improved overall performance. In this work, we explore memory code design using a novel, computationally efficient strategy called the cross-entropy method (CEM). This approach models a probabilistic search distribution over the exponentially large and discrete binary code design space, from which it samples candidate code families, and then improves its search distribution representation by finding a maximum likelihood distribution. The CEM can be applied to any user-defined code objective function, without requiring any functional properties (e.g. convexity, differentiability). We demonstrate the ability to design low-correlation codes for family sizes of up to 50 codes and lengths of up to 10223 chips – the first work to explore navigation memory code design for these lengths, to the best of the authors’ knowledge. We further demonstrate the ability to design codes with lower mean-squared auto- and cross-correlations than well-chosen families of equal-length Gold and Weil codes.
Published in:	Proceedings of the 36th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2023) September 11 - 15, 2023 Hyatt Regency Denver Denver, Colorado
Pages:	1328 - 1340
Cite this article:	Mina, Tara, Yang, Alan, Gao, Grace, "Designing Long GPS Memory Codes Using the Cross Entropy Method," Proceedings of the 36th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2023), Denver, Colorado, September 2023, pp. 1328-1340. https://doi.org/10.33012/2023.19260
Full Paper:	ION Members/Non-Members: 1 Download Credit Sign In