Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe’s Galileo Operations and Evolution.
Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe’s Galileo Operations and Evolution.
Pseudorandom noise (PRN) sequences are an essential element of any radionavigation satellite system that is based on code division multiple access (CDMA) techniques. Indeed, these sequences enable a navigation receiver to distinguish one satellite from another.
A comprehensive introduction to CDMA, including its history in general and PRN sequences in particular, can be found in the Working Papers column by G. W. Hein et alia published in the September 2006 issue of Inside GNSS.
After the finalization of the Galileo PRN codes back in 2004 and the definition of the GPS L1C codes in about the same timeframe, additional attention to this very interesting field of research is now expected in the near future. In fact, not only additional CDMA-based signals will appear from GNSS satellites, but a steadily growing interest in ground based, continuously transmitting pseudolites can also be observed.
This interest will undoubtedly animate further research on high-performing sets of PRN codes with certain characteristics regarding code length and the number of codes to support design of the new signals to be provided by these systems. The New PRN Code Family introduced in this column could be one potential candidate for such systems because it offers a number of highly advantageous characteristics that we will analyze in this article.
System designers need to select the best codes according to some figure of merit (FOM) indicating the performance of the PRN code set. A large variety of FOMs can be imagined, and dedicated publications deal with this subject. See, for example, the paper by F. Soualle et alia referenced in the Additional Resources section near the end of this article.
The correlation function goes back to the mean squared error concept introduced by Carl Friedrich Gauss (1777–1855) and is without doubt one of the most widely used and most powerful means to characterize the performance of PRN sequences.
. . .
The correlation function shown by this equation is also referred to as even correlation because it does not account for a flip of the sequence within the integration period as might be induced due to a data or secondary code bit change.
This article will address the issue of odd correlations later on. The objective of the following discussion is to introduce and mathematically derive the New PRN Code Family and characterize it in terms of correlation performance.
Generation of PRN sequences
Regarding the generation of PRN sequences, we can distinguish between two categories:
- PRN sequences, where the value of each chip of the sequence is based on a mathematical, closed form algorithm, and
- PRN sequences that result from a numerical optimization or selection process.
For the latter category, the individual chips of the PRN codes cannot be determined by applying a closed mathematical formula, while specific algebraic formulas can be given for the first category of sequences that result immediately in the PRN sequences.
Well-known PRN sequences that belong to this first category include
- Gold codes
- Kasami codes
- Weil codes
- Bent-function sequences
- No
- Gong/Paterson, and
- Z4 linear Family I and II.
Articles and papers referenced in the Additional Resources section discuss most of these in further detail.
These codes offer almost ideal auto and cross-correlation properties for zero Doppler frequency offset. Unfortunately, they face the restriction that they can only be constructed for specific code lengths.
The PRN code length results generally from dividing the signal’s chip rate and its corresponding symbol rate. For PRN sequences that are derived from closed analytical expressions, any deviation from the preset code length immediately results in a significant degradation in terms of increased cross-correlation and out-of-phase autocorrelation.
. . .
In order to allow for maximum flexibility regarding the PRN code length, numerical generation and optimization methods have been identified. Genetic algorithms can be used to construct random codes of any desired length, optimized for any potential FOM imaginable, and implemented during the design of the PRN sequences. (For further details, see the patent application by J. Winkel listed in Additional Resources.)
Alternatively, signal designers can make use of chaotic algorithms to set up the PRN sequences displaying properties that are as close as possible to random sequences, as described in the patent application publication by M. Hadef et alia.
The new code family that we shall define next belongs to the first category, with its sequences constructed based on closed-form algebraic formulas.
Generation of New Family with Even Code Length
We introduce next a new code family that can be constructed for code lengths N that follow the form, N = p − 1, where p refers to any prime number larger than 7. So, any sequence contained in the new code family results in an even length.
. . .
As with the new family of PRN codes proposed here, the Weil codes are just based on a single generative sequence. A method to generate binary sequences has been proposed independently by V. M. Sidelnikov and A. Lempel et alia (see Additional Resources). The binary sequence derived from their methods will serve as a generative one for our new PRN code family. From here on, this column will refer to these as SLCE sequences.
. . .
Properties and Performance of New Code Family
Several distinctive properties are associated with the new PRN code family, which we will characterize next. The performance of the code family will also be discussed in the following section.
Balance. The balance property BAL for the n-th PRN sequence is defined by the addition of the individual chips …
Correlation Performance. As already mentioned, the auto and cross-correlation performance is an essential metric by which to characterize the performance of PRN sequences as they are applied for CDMA systems.
We can consider the so-called Welch Lower Bound, or Welch Bound for short, to be the most applied theoretical limit when talking about the best correlation performance that a family of PRN codes can achieve. The Welch Bound indicates the minimum of the maximum achievable out-of-phase auto and cross-correlation magnitudes. Indeed, no set of PRN sequences can result in maximum correlation magnitudes lower than the Welch Bound for any set of PRN sequences.
. . .
Size of Code Family. The new code family includes a number of N/2-1 individual codes where the code length N is given by N=p−1 with a prime number p.
Deriving a Subset Offering Good Odd Correlation
As already indicated at the beginning of this column, even auto- and cross-correlation are not the only measures by which to judge the performance of a PRN code family. Typically the navigation data or the secondary code bits are modulated onto the primary PRN code, applying binary phase shift keying (BPSK).
Whenever the navigation or secondary code bits within the integration period induce a flip of the PRN code sequence, the resulting correlation function is referred to as an odd correlation.
. . .
Conclusions
This article has presented a new family of PRN codes that can be constructed following a closed mathematical formula. This new code family offers excellent even correlation properties.
Following the approach that we have described here, PRN codes of length N=p–1 (p being a prime number) can be generated, allowing for a high level of fidelity regarding the code length. This produces a much higher likelihood that the code length directly matches the system requirement. Consequently, no truncation or elongation of the PRN code — which is associated with a loss of correlation performance — is required. Moreover, just one original SLCE sequence of length N is sufficient to derive a full set of N/2-1 PRN codes by binary-shift-and-add logic. This alleviates the need to store each chip of the PRN code in memory within the receiver device.
The code family described in this column is large enough to serve any needs in the field of navigation, be it for satellites, pseudolites, or both. A request has been initiated for a patent application on the New PRN Code Family.
For the complete story, including figures, graphs, and images, please download the PDF of the article, above.
Additional Resources
[1] Burton, D. M., Elementary Number Theory, 4th Edition, William C. Brown Publishers, 1989
[2] Gao, G. X.,.and A. Chen, S. Lo, D. De Lorenzo, T. Walter, and P. Enge, “Compass-M1 Broadcast Codes in E2, E5b and E6 Frequency Bands,” IEEE Journal of Selected Topics in Signal Processing, Special Issue on Advanced Signal Processing for GNSS and Robust Navigation, August, 2009
[3] Gold, R., “Optimal Binary Sequences for Spread Spectrum Multiplexing,” IEEE Transactions on Information Theory, Vol. 13, pp. 619–621, October 1967
[4] Gong, G., “New Designs for Signal Sets with Low Cross-correlation, Balance Property and Large Linear Span: GF(p) Case,” IEEE Transactions on Information Theory, Vol. 48, pp. 2847– 2867, 2002
[5] Hadef, M.,,and J. Reiss and X. Chen, “Chaotic Spreading Codes and Their Generation,” Patent Application Publication, US 2010/0054225 A1, March, 2010
[6] Hein, G.W., and J.-A. Ávila-Rodríguez and S. Wallner, “The Galileo Codes and Others,” Inside GNSS, Volume 1, September, 2006
[7] Holmes, J. K., Spread Spectrum Systems for GNSS and Wireless Communications, Artech House, Boston, 2007
[8] Kasami, T., Weight Distribution Formula for some Class of Cyclic Codes, Coordinated Science Laboratory, University of Illinois, April 1966
[9] Lempel, A., and M. Cohn and W. L. Eastman, “A Class of Balanced Binary Sequences with Optimal Autocorrelation Properties,” IEEE Transactions on Information Theory, Vol. 23, No. 1, pp. 38– 42, January 1977
[10] No, J. S., and V. Kumar, “A New Family of Binary Pseudorandom Sequences Having Optimal Periodic Correlation Properties and Large Linear Span,” IEEE Transactions on Information Theory, Vol. 35, pp. 371–379, March 1989
[11] Olsen, J. D., and R. A. Scholtz and L. R. Welch, “Bent-Function Sequences,” IEEE Transactions on Information Theory, Vol. 28, pp. 858-864, 1982
[12] Paterson, K.G., “Binary Sequences with Favourable Correlations from Different Sets and MDS Codes,” IEEE Transactions on Information Theory, Vol. 44, pp. 172–180, 1998
[13] Rushanan, J. (2006), “Weil Sequences: A Family of Binary Sequences with Good Correlation Properties,” IEEE International Symposium on Information Theory, Seattle, Washington, July, 2006
[14] Rushanan, J. (2007), “The Spreading and Overlay Codes for the L1C Signal,” Journal of Navigation, Vol. 54, No. 1, pp 43-51, 2007
[15] Sidelnikov, V. M., “Some k-valued pseudorandom sequences and nearly equidistant codes,” Problems of Information Transmission, Vol.5, 1969, pp. 12–16
[16] Soualle, F., and M. Soellner, S. Wallner, et al., “Spreading Code Selection Criteria for the Future GNSS Galileo,” Proceedings of ENC 2005, Munich, Germany, July 19–22, 2005
[17] Wallner, S., and J. J. Rushanan, J.-A., Ávila- Rodríguez, and G. W. Hein, “Galileo E1 OS and GPS L1C Pseudo Random Noise Codes — Requirements, Generation, Optimization and Comparison,” Proceedings of ION GNSS 2007, Fort Worth, Texas, USA, September 25–28, 2007
[18] Welch, L.R., “Lower Bounds on the Maximum Cross Correlation of Signals,” IEEE Transactions on Information Theory, Vol. 20, pp. 397–399, May 1974
[19] Winkel, J., “Spreading Codes for a Satellite Navigation System,” Patent Application Publication, US 2008/0246655 A1, October, 2008
