New Solutions to Reduce the Time-To-CED and to Improve the CED Robustness of the Galileo I/NAV Message
Lorenzo Ortega Espluga, TéSA, France; Charly Poulliat, Marie-Laure Boucheret, ENSEEIHT, France; Marion Aubault, CNES, France; Hanaa Al bitar, Thales Alenia Space, France
Within of the framework of Galileo and more precisely inside the European GNSS OS SIS ICD publication , the proposed Galileo I/NAV message provides the flexibility to introduce new pages types. These new pages can be used to propose an optimization of the Galileo I/NAV message on E1-B to meet the following objectives : Under the precondition to keep the backward compatibility with the current I/NAV message structure, the first objective is a reduction of the Time To First Fix (TTFF) achieved by reducing the time to retrieve the complete Clock and Ephemerides Data (CED), so-called Time To Data (TTD), and the second objective consists in improving the CED robustness, especially in difficult environments.
In order to meet these objectives, this paper aims to propose improved backward compatible error correcting solutions to both reduce the TTD and improve of the robustness of the CED. This is achieved by the addition of an outer channel coding scheme  to the baseline coding scheme of the Galileo’s I/NAV messages based on a convolutional code (for error correction) and CRC based error detection. Introduction of this new outer coding scheme is possible when considering the use of some new (unused so far) additional pages than can carry the extra redundancy introduced by this outer coding scheme. Indeed it is foreseen for this new outer coding scheme to be a systematic one in order to meet the backward compatibility constraint.
After presenting the proposed new scheme and the structure of the message , a new category of codes, referred to as Lowest Density Maximum Distance separable Codes (LD-MDS codes) , is thus proposed for this outer coding scheme. This new errors and erasures correcting scheme is presented for hostile GNSS environment and is compared with some reference error correcting schemes that will use both standard irregular Low Density Parity Check (LDPC) codes and Reed Solomon codes  as outer coding schemes. The proposed family of codes combines two properties.
The first property is the Maximum Distance separable property as it exists for Reed Solomon (RS) codes. Thanks to this property, the time to retrieve the CED can be reduced. In fact in the framework of E1-B Galileo data structure, the time to retrieve the CED is equivalent to the time to retrieve all the pages where the CED is stored. Within our new proposed scheme, some pages will be used to store redundant data generated by the outer coding scheme. And thanks to the MDS property, it becomes possible to retrieve the CED through any k free error information pages of the total n information pages (whether nominal CED pages or redundant data pages) and as a consequence under good channel conditions (free error pages), the time to retrieve the first k information units (CED or redundant bits) will be the time to retrieve the CED. In order to reconstruct the CED from any k information units, either with Reed Solomon codes or LD-MDS codes, an erasure correction algorithm is then used. The main difference between both algorithms lies in the extremely low complexity of the LD-MDS erasure correction algorithm due to their sparse code structure.
The second property namely derives from the sparse structure of the parity check matrix, which can be considered as the lowest density parity check matrix, having the MDS property. Using this sparse structure allows for very efficient low complexity erasure correction algorithms, which will be shown to be the suitable type of decoding algorithm to be considered, especially when channel conditions are good. Moreover, in the case of stringent channel conditions, the underlying LDPC-like of LD-MDS code structure enables the use of soft serial iterative decoding between the soft input soft output (SISO) decoder of the mandatory inner convolutional code (i.e. Bitwise maximum a posteriori based on the BCJR algorithm ) and the SISO decoder of the LD-MDS codes which finally reduces to the well-known belief propagation decoding algorithm for LDPC codes . Thus, an important gain on the demodulation threshold is obtained.
In order to evaluate the proposed schemes under bad channel condition, the error correcting algorithms can be assessed in terms of CED retrieve error probability, which is equivalent to the evaluation of the probability of retrieving the CED under one specific Carrier to Noise ratio (C/N0). Simulations will ensure that the use of a more robust decoding scheme, such as serial turbo decoding, involves an increase of the robustness over the CED and as a consequence a reduction of the TTD. In contrast, the use of technique such as serial turbo decoding increases the complexity of the decoding algorithm. As it was done in , the error correcting algorithms for each new proposed scheme will be evaluated and compared for a targeted error probability of ?10?^(-2). Results further show that the serial turbo decoding algorithm gives an improvement of 0.7 dB with respect to the basic Soft Input Belief-Propagation algorithm used by the LDPC decoder and an overcome of the performances bigger than 0.8 dB with respect to the Hard Input Berlekamp-Massey decoding algorithm used by the Reed Solomon decoder, while ensuring a demodulation threshold gain of 3 dB compared with the current I/NAV message.
To sum up, the simulation results show that keeping the backward compatibility with the current I/NAV message, LD-MDS codes provides a new possible solution to reduce the TTD and finally the TTFF, and to allow for a demodulation threshold gain of 3 dB compared with the current I/NAV message. Moreover under good channel conditions, thanks to the low complexity erasure correcting algorithm, it is possible to retrieve the CED information with fewer operations than Reed Solomon erasure correcting algorithm. By the other hand, under bad channel, thanks to the use of low density parity check matrix, we can introduce efficient algorithms to correct errors benefiting from serial turbo decoding.
 European GNSS (Galileo) Open Service - Signal-In-Space Interface Control Document.
 Birgit E. Schotsch, Marco Anghileri, Thomas Burger, Mahamoudou Ouedraogo, “Joint Time-to-CED Reduction and Improvement of CED Robustness in the Galileo I/NAV Message”. "Proceedings of the 30th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2017), Portland, Oregon, September 2017,
 WILLIAM E. RYAN, SHU LIN Channel Codes: Classical and Modern
 BLAUM, M., AND ROTH, R. M. “On lowest density MDS codes”. IEEE Transactions on Information Theory 45, 1 (January 1999), 46-59.