Optimizing the co-design of message structure and channel coding to reduce the TTD for a Galileo 2nd generation signal

3.1 Block-fading-channel model

The non-ergodic block-fading channel (Boutros et al., 2010) is a simplified channel model that characterizes slowly varying fading channels. It can be viewed as an extension of the well-known block-erasure channel, which considers that some parts of the message are completely erased due to a deep fade of the channel or because of the lack of received data. Indeed, the block-erasure channel corresponds to the specific case of the largest signal-to-noise ratio case of the block-fading channel, where some parts of the codewords are received with a high signal-to-noise ratio (SNR) and the other parts are received with a lower SNR. Under this context of a non-ergodic channel, a transmitted codeword can be viewed as a finite number n_c

of independent channel realizations.

We consider a block-fading channel with n_c fading blocks, whose discrete-time channel output at time i is given by:

1

where N_f denotes the frame length, x_i ∈ {−1, +1} is the i−th binary phase shift keying (BPSK) modulated symbol, z_i ∼ 𝒩 (0, σ²) are the centered i.i.d. Gaussian noise samples with variance σ² = N₀/2, and h_i is a real fading coefficient that belongs to the set ℕ = {α₁,α₂,…,α_nc}. Figure 2 illustrates a codeword under the block-fading-channel scenario.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 2

Message structure

Similarly to any other non-ergodic channel, the block-fading channel has zero capacity in the strict Shannon sense. To assess performance under this scenario, the information outage probability, which is an implicit function of the average SNR γ, is usually defined as follows:

2

where I_ℕ denotes the instantaneous mutual information between the BPSK constrained input and the noisy observation at the output of the channel for a particular channel realization ℕ, and R is the transmission rate in bits per channel use. Then, I_ℕ can be calculated as:

3

where I_AWGN(s) is the input-output mutual information for a binary input AWGN channel with a SNR equal to s (I_AWGN(s) is also referred to as the constrained input AWGN capacity for BPSK inputs) and α_i,i ∈ (1,…n_c), are the instantaneous fading gains for each block i. These fading gains follow a normalized Rayleigh distribution in the case of the block Rayleigh fading channel. In such a non-ergodic channel, P_out gives a lower bound on the codeword error probability. In Figure 3, P_out is illustrated for a BPSK input with R = 1/2, which represents the ideal behavior of a code for a block-fading channel with n_c = 2.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

Outage probability P_out for a BPSK input with R = 1/2, represents the ideal code for a block-fading channel n_c = 2 (black/solid line)

3.2 Desired code properties

In order to design codes suited for the non-ergodic channels, two main properties are required:

1. MDS (Maximum Distance Separable property)

2. Full Diversity.

Let us consider a channel-coding scheme, which provides codewords divided in n blocks of equal sizes. We further assume that the systematic information is embedded into k blocks with k < n of the same size. The MDS property allows us to retrieve k data blocks of systematic information from any k error-free received blocks. In other words, thanks to this property we can reduce the time to retrieve CED under high C/N₀ environments, since with only k error-free data blocks, the CED can be retrieved. On the other hand, several references (Boutros et al., 2010; Fabregas & Caire, 2006; Knopp & Humblet, 2000) exhibit the poor error-correction performance over non-ergodic channels, which are not able to achieve a good coding gain. In order to achieve better error-correction capabilities, the full diversity property is further required.

Definition 1. An error-correcting code is C said to have full diversity over the block-fading channel if the diversity order is equal to the number of fading blocks n_c. The diversity order determines the slope of the error-rate curve as a function of the SNR on a log-log scale for Rayleigh fading distribution:

4

where P_ew is the codeword error probability at the decoder output and γ is the average SNR. Then, the P_ew of a code with full diversity n_c decreases as 1/γ^n_c at high SNR. Since the error probability of any coding/decoding scheme is lower-bounded by the outage probability P_out, the diversity order is upper-bounded by the intrinsic diversity of the channel, which reflects the slope of the outage limit. In other words, when the coding/decoding scheme has the same slope as for the outage probability curve, then the coding scheme is referred to as full diversity for the aforementioned block-fading channel. Given a codeword x ∈ C from the error-correcting code, we define the blockwise Hamming weight (w₁(x), w₂(x),…,w_nc(x)), where w_j(x) is the Hamming weight of coded bits affected by fading h_j. Then, under the maximum likelihood of decoding, the diversity order can also be determined by Fabregas and Caire (2006)

5

In other words, d is the minimum number of blocks that have nonzero Hamming weight. We refer to it as the block-wise minimum Hamming distance.

When maximum diversity is achieved by a code, the coding gain yields a measure of “SNR proximity” to the outage limit. This optimal design yields the optimal code, which is given by the Singleton bound:

6

Note that d is referred to as the code block diversity and is given by the minimum number of blocks on which any two distinct codewords differ (i.e., the block-wise Hamming distance).

Codes achieving the Singleton bound are termed MDS. MDS codes are outage-achieving over the (noiseless) block-erasure channel, but may not achieve the outage probability limit on noisy block-fading channels and, as a consequence, a good coding gain. As a matter of fact, MDS codes are necessary, but not sufficient to approach the outage probability of the channel. Thus, for noisy channels, we aim to design error-correcting schemes that ensure the full diversity property (P_cm is asymptotically parallel to the outage bound) and to try to operate as close as possible to the outage bound (good coding gain). Notice from Equation (6) that, in order to find a full diversity code (d = n_c), the maximum achievable rate is R = 1/n_c.

4.1 GPS L1C channel-coding scheme and message structure

In this section, we briefly review how the CED information is encoded for GPS L1C (Roudier, 2015).

The message modulated onto the GPS L1C signal consists of a set of consecutive frames, where the complete data message set is broadcasted to users. A frame is divided into three subframes of various lengths. The first subframe consists of 9 bits of Time of Interval (TOI) data. The subframe 2 is composed of 600 bits of non-variable clock and ephemeris data with Cyclic Redundancy Check (CRC). The content of subframe 3 nominally varies from one frame to the next and is identified by a page number; the size of the block is 250 bits. Each of the subframes is encoded as follows:

1. The 9-bit TOI data of subframe 1 are encoded with a BCH code;

2. Subframe 2 data are encoded using a 24-bit CRC code and an irregular Low-Density Parity-Check (LDPC) Forward Error-Correction (FEC) code using a parity check matrix of size 600 × 1200;

3. Subframe 3 data are encoded using a 24-bit CRC code and an irregular Low Density Parity Check (LDPC) Forward Error-Correction (FEC) code with a parity check matrix of size 274 × 548;

4. Encoded data from subframe 2 and 3 are then interleaved. The resulting 1,800 symbols represent one message frame, which are then broadcast at a rate of 100 symbols per second. Figure 4 gives the structure of the described GPS L1C message.

   

   • Download figure
   • Open in new tab
   • Download powerpoint

   FIGURE 4

   GPS L1C message structure

Nowadays, the GPS L1C navigation message provides a structure which allows us to decode the CED in the shortest time when compared with other navigation message structures. For example, the worst-case TTD is of the order of 18s, which has to be compared to the 32s of Galileo E1B I/NAV. The GPS L1C standard also uses state of the art error-correcting codes, such as the irregular LDPC code of rate 1/2 used to protect the GPS L1C structure subframe 2 (where the CED is located), which provides low demodulation threshold and outstanding error-correction capabilities. Additionally, the GPS L1C structure uses a block interleaver, which is used for the symbols allocated within the subframe 2 and subframe 3 in order to improve the performance over block-fading channels. For all these reasons, GPS L1C can be considered as a natural choice for benchmarking when we aim to design a navigation message that enables us to improve the time to retrieve the CED. It is also a practical lower bound for existing systems. The idea of our proposal is to try to keep best features among existing (and still efficient) structures while enabling modifications that can help to improve the decoding delay. This is mainly the reason why we are aiming to capitalize on the naturally efficient structure of the GPS L1C.

4.2 Review of Galileo I/NAV message (baseline and new configurations)

Of course, there are other navigation message structures embedding error-correcting schemes in order to improve the robustness of the CED and to reduce the TTD. However, those structures provide worse results than GPS L1C in terms of error-correction performance and TTD. Thus, as a remarkable example, we first consider the Galileo I/NAV message, used to send the data component of the Galileo E1-B signal. The structure of the I/NAV message is presented in OS SIS ICD (2016). It is composed of 15 nominal pages, each one with a duration of two seconds, giving the 30-second duration of the I/NAV subframe structure illustrated in Figure 5. Within the subframe structure, pages 1, 2, 11, and 12 are used to store the four CED information words. Therefore, every 30 seconds, four CED information words are provided by the I/NAV message. Each nominal page is subdivided into two subpages. Each subpage has 120 bits, and it is encoded by a rate of one-half convolutional code with polynomial generators in octal representation given by (171, 133)₈ (OS SIS ICD, 2016). At the output of the convolutional encoder, 240 data symbols are interleaved by a 30×8 block interleaver. Finally, 10 synchronization bits are added at the beginning of the data frame to achieve synchronization to the page boundary. At the receiver, each page is decoded independently. First, the synchronization pattern allows the receiver to achieve synchronization to the page boundary. Each page is then deinterleaved by a 8×30 block interleaver and decoded using the Viterbi algorithm (Viterbi, 1967) to perform maximum likelihood detection. Finally, the CRC is checked. In order to retrieve the CED, pages 1, 2, 11, and 12 must be validated using the CRC. Using this structure, it can be shown that in some cases the CED cannot be retrieved before 32 seconds. In order to overcome this drawback, some proposal (Ortega Espluga et al., 2018b; Schotsch et al., 2017) has been proposed to improve the I/NAV message. Those proposals take advantage of the possibility to use unassigned pages within the Galileo I/NAV message. This design of the new signal seeks to reduce the TTD and to improve the CED robustness while ensuring the backward compatibility with the current I/NAV message structure. As an example, we decide to implement the RS2 configuration (Schotsch et al., 2017), where pages 6 and 7 were selected to store the redundant data generated by a Reed Solomon (RS) outer channel code. With this setting in mind, a general outer channel-coding (n, k) = (6, 4) structure can be defined in order to generate those extra redundant bits, where n is equivalent to the total number of available bits (redundant + information bits) and k is the number of information bits. In order to keep backward compatibility, systematic information bits are stored in pages 1, 2, 11, and 12 while redundant bits are stored in pages 6 and 7. Remark that the RS codes are MDS codes, then CED can be decoded when a number of at least k = 4 pages are retrieved, which ensures a faster recovery than for the baseline I/NAV message. In Figure 5, the I/NAV S_E1−OSdata nominal subframe layout (Baseline and RS2 examples) is illustrated.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 5

I/NAV S_E1−OSdata nominal subframe layout (Baseline and RS2 configuration)

5.1 Lowest density maximum distance separable (LD-MDS) codes

LD-MDS (Blaum & Roth, 1999) codes were already proposed in Ortega Espluga et al. (2018b) as a possible solution for the new Galileo I/NAV navigation coding scheme. Those codes combine two main properties. The first property is the Maximum Distance Separable (MDS) property (Blaum & Roth, 1999), which allows us to retrieve k data symbols of information from any k error-free symbols (no matter systematic or redundant information). The second property is the sparsity of the parity-check matrix. This enables the use of efficient low-complexity decoding algorithms (Blaum & Roth, 1999). It must be noted that the lowest sparsity property does not provide codes that can operate close to the outage probability region (due to the fact that they do not exhibit the full diversity property), and as a consequence, the LD-MDS are not considered as good codes under the message-passing algorithm over noisy channels, such as Belief-Propagation (BP). Moreover, since the LD-MDS codes under the BP decoding algorithm do not exhibit the MDS property, a tailored erasure-correcting algorithm must be developed in order to exploit their MDS property. For more details about LD-MDS codes, please refer to Blaum and Roth (1999).

In order to design a LD-MDS code of rate 1/2, Blaum and Roth (1999) presents the construction of a linear [k + 2, k] MDS code over GF(q^b) whose systematic parity check and generator matrices are defined as follows:

7

8

where β = {β₁,β₂,…,β_k} is a collection of b × b matrices over GF(q) and I is the identity matrix. In order to build a MDS code, the collection β must follow the following properties:

• (P1) Each matrix in the set is nonsingular.

• (P2) Every two distinct matrices in the set have a difference that is also nonsingular.

Moreover, the fewer 1’s in the parity check matrix, the lower complexity in the coding and decoding algorithms. As a consequence, we have the following property:

• (P3) Each matrix contains at most b + 1 nonzero elements.

When considering the restriction of those codes to the binary field (q = 2), and in order to construct a set of matrices β satisfying (P1)–(P3) (Blaum & Roth, 1999), we defined the set of matrices as , where v_l,m are defined as follows:

Definition 2. Let p as an odd prime and α as an element of GF(q) − {0}. In our case as q = 2, α = 1. For 0 ≤ i < p, we define the set of matrix of dimension b × b = (p−1)× (p − 1) as , where l, m ∈ (1, p − 1) over GF(q). Considering the parameters q = 2 and α = 1, the set of matrices over GF(2) are defined by:

9

The operator ⟨.⟩ denotes the mod p operation, and ⟨a/2⟩ denotes the integer between 0 ≤ σ ≤ p, such that a ≡ bσ(mod p). In order to design binary MDS codes, the following theorem provides sufficient conditions on p and α so satisfy (P2).

Theorem 1 (Blaum & Roth, 1999). Let p be a prime such that p − 1 is divisible by 2(q − 1), and let α be an element in GF(q) − {0} such that the polynomial x² + αx +1 is irreducible over GF(q). Then, the difference of any two distinct matrices in the set {v_l,m} is nonsingular.

For our particular case:

• Since q = 2, p − 1 which is an even number is divisible by 2(q − 1) = 2.

• Since q = 2 and α = 1, it is trivial to show that x² + x + 1 is irreducible over GF(2).

From definition 2 and setting parameters q = 2 and α = 1 (which fulfill Theorem 1), the set of matrices β can be any subset of k matrices in .

Considering a LD-MDS code C(600, 1200) with k = 2 and n = k + 2 = 4, the parity check matrix for this code can be shown to be as follows:

10

where β = {β₁, β₂} is a set of b × b matrices and b = 300. In order to fulfill (P2), we have b = (p−1) where p is a prime number. As p = 301 is not a prime number, we set p = 151 leading to b = 150 to design a base matrix that is then expanded to the targeted size using a lifting expansion of order 2 (Ryan & Lin, 2009). For the last step, it consists of replacing the ‘1’ elements of the designed parity check base matrix by a permutation matrix of size 2 × 2, following the classical lifting expansion of protograph based codes. This allows us to achieve a subset of matrices β = {β₁, β₂} of size b′ × b′ where b′ = 2b = 300. For this scheme, the CED and CED redundancy data of Figure 1 have to be divided into 4 blocks (as pictured in figure 4). The division into four blocks is required in order to fully benefit from the MDS capability when applying the erasure-decoding algorithm presented in Appendix A in Section A and that is used within the general decoding procedure as given in Figure 6. Indeed, one of the most important advantages of having a sparse parity check matrix by design for the LD-MDS codes is that low-complexity erasure-decoding algorithms are enabled in order to decode the systematic information. The algorithm implemented for this scheme is presented in Appendix A in Section A.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 6

LD-MDS and sparse MDS decoding schemes

In order to compare the new code with the structure of the GPS L1C or the I/NAV message, we propose to use the structure of GPS L1C. Using this configuration, the CED, which is stored in the subframe 2, is encoded by the proposed LD-MDS code. Moreover, we avoid the use of the interleaver spanning the entire codeword, since it is the main cause of an almost constant TTD in the GPS L1C structure. We now describe the general decoding step, once k = 2 blocks of information are received, the erasure algorithm is used to decode the systematic information. In order to check the reliability of the systematic data, a CRC based detection is applied. In case of error, the BP algorithm is performed on the corresponding Tanner graph when more than k = 2 information blocks are received. The complete description of the proposed decoding scheme is described in Figure 6.

5.2 Sparse maximum distance separable (MDS) coding schemes

5.3 Regular root-LDPC codes

We now investigate on the proposed scheme based on regular Root-LDPC codes. These codes belong to a family of codes having both MDS and full diversity properties under the iterative BP decoding algorithm, and they have been initially introduced for the block-fading channel.

The design of the Root-LDPC codes has roots in the limiting case where the fading coefficient can belong to ℕ ∈ {0, 1}, which corresponds to the well-known block-erasure channel. Indeed, it can be shown that usual single parity check nodes involved in LDPC codes do not meet sufficient conditions to tolerate more than one erasure bit as it is shown in Boutros et al. (2010). As a consequence, a new check node structure, referred to as rootcheck node, has been introduced enabling us to tolerate more than one erasure bit under the BP decoding algorithm. In this context, the construction of a regular (3, 6) rootcheck LDPC has been introduced for the case of a block-f n_c = 2.

Definition 3 (Boutros et al., 2010). Let x₁ be a binary element transmitted on fading α₁. A rootcheck for x₁ is a checknode Φ(x₁,x₂,…,x_y) where all bits x₂,…,x_y are transmitted on fading α₂.

Using Definition 3, the design of a length-N rate-1/2systematic regular LDPC code that has to operate on a two-blocks fading channel can be summarized as follows. Two classes of bits are first defined, i.e., systematic information bits and redundant parity bits. The N/2 systematic information bits are split into two classes: N/4 bits (denoted i₁), which are transmitted on the block with fading α₁ and N/4 bits (denoted i₂), which are transmitted on the block with fading α₂. Parity bits are also partitioned into two sets (denoted p₁ and p₂, respectively) and sent to the channel following the same assumptions as for the information bits. This mapping of the information and redundant/parity bits is represented in Figure 7 using the bipartite Tanner protograph representation that also shows how the different information and parity bits are connected to rootchecks.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 7

Tanner graph for a regular (3,6) root-LDPC code of rate 1/2

The corresponding block structure of the associated parity check matrix H is directly derived from its Tanner protograph and is given in Equation (14) by

14

where I and 0 are N/4 × N/4 identity and all-zero matrices, respectively. H_ik and H_pk, k ∈ (1, 2), are sparse regular matrices of Hamming weight 2 and 3 per row and per column, respectively. Examining Equation (14), under the block-erasure channel scenario, we observe that the only outage event occurs when α₁ = α₂ = 0 (both blocks erased). Indeed, when α₁ = 0 and α₂ = 1, it is straightforward to see that information bits i₁ are determined using rootchecks c₁. Similarly, when α₁ = 1 and α₂ = 0, information bits i₂ are determined using rootchecks c₂.

Finally, two methods to generate the parity matrices have been used:

• The first method is based on the design of parity check matrices using a modified Progressive Edge Growth (PEG) algorithm that enables us to take into account local constraints following (Uchôa, Healy, Lamare, & Souza, 2011).

• The second method considers the design of Quasi-Cyclic (QC) matrices following, for example, Li and Salehi (2010).

From Definition 3, it is trivial that the data structure of a regular Root LDPC (3,6) code must be divided into two different blocks, each one corresponding to α₁ or α₂. Once one of the blocks is received, the decoding process starts by executing the BP algorithm. In case of decoding a correct CRC, the CED is retrieved, otherwise another block must be received. The decoding scheme is described in Figure 8.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 8

Root-LDPC decoding scheme

5.4 Irregular protograph root-LDPC codes scheme

In this section, we investigate on the design of irregular Root LDPC codes based on protographs (Thorpe, 2003). A protograph is a Tanner graph G for which parallel edges are permitted. In order to generate a LDPC code from a protograph, a copy and permute operation also called lifting is used to interleave multiple copys of the original protograph (Thorpe, 2003). LDPC codes generated from protographs can enhance the error-correcting performance compared to Regular LDPC codes, since good irregular LDPC codes can be designed.

Let us now introduce the so-called base matrix H_B associated with the protograph of the regular Root LDPC code given by Equation (14). The base matrix H_B is given by

15

In this representation, the coefficient H_B(j, i) represents the number of connections/edges between the i-th column and the j-th row of the base matrix. Each column i is associated to a group of variable nodes while each row j is associated to a group of check nodes in the final parity-check matrix. All nodes belonging to the same group, also referred to as class or type, share the same local connection properties. Based on the type of local connections you can have (represented by the coefficients H_B(j, i)), variable nodes (respectively check nodes) can be divided into different classes/types. For the regular Root LDPC code, all variable nodes are of degree 3 (they are all connected to exactly 3 check nodes), while check nodes are all of degree 6 (they are all connected to exactly 6 variable nodes). But, when considering the detailed connections between possible groups of variable nodes and check nodes, we can define 4 different types/classes of variable nodes denoted (i₁,p₁,i₂,p₂) and two types/classes of check nodes denoted (c₁,c₂). For example, using this protograph representation, variable nodes of type i₁ are exactly connected to one check node of type/class c₁ and two of class c₂. Variable nodes of type p₁ are only connected to three check nodes of type/class c₂. This is a classical representation for protograph-based codes. Analyzing the threshold of the regular Root-LDPC code using the Protograph EXIT (PEXIT) Chart algorithm (Liva & Chiani, 2007), a demodulation threshold loss of 0.4 dB with respect to the GPS L1C demodulation threshold is obtained. In order to enhance the demodulation threshold, we now present the design of irregular Root-LDPC codes to protect the CED of the navigation message.

To do so, we adopt the following general protograph representation for a Root-LDPC code of rate R = 1/2:

16

where ∗ represents connection weights ∈ ℕ to be optimized. In order to enhance the error-correction performance of the regular Root-LDPC code, we can use the Protograph EXIT (PEXIT) Chart algorithm (Liva & Chiani, 2007) to search for coefficients ∗ in Equation (16), which reduce the demodulation threshold. We can also note that in order to limit the search space, only matrix weights in the subset ∈ (0, 1, 2, 3) are considered as done, for example, in Fang, Bi, and Guan (2014). In Fang et al. (2014), some optimized protograph structures have been presented; however, small gains in the demodulation threshold with respect to the regular Root-LDPC codes have been observed. To enhance the demodulation threshold gains, Fang et al. (2014) rather considered the following lifted protograph representation:

17

where ∗ represents coefficient weights ∈ (0, 1, 2, 3) to be optimized.

The optimized protograph structure in Fang et al. (2014) has been designed to have good error-correcting capabilities in the block-fading channel. However, this protograph structure does not provide the minimum demodulation threshold in the ergodic channel. Since a low demodulation threshold is crucial for the retrieval of the CED, in Equation (18), we rather search for a protograph structure which minimizes the demodulation threshold given the required Root protograph structure given in Equation (17). The obtained base matrix is as follows:

18

We can note that the proposed protograph structures in Fang et al. (2014) and in Equation (18) are both asymmetric. Therefore, the error-correcting capabilities lead to unequal block recovery for the different variable node types. Since an unequal recovery may affect directly the TTD performance, especially in a good channel environment, we have optimized the protograph enforcing a symmetric structure, which minimizes the demodulation threshold given the required Root protograph structure given in Equation (17). The resulting base matrix is given by

19

Finally, LDPC codes matrices expanded from the proposed root-protograph codes are obtained using classical lifting based expansion methods (Ryan & Lin, 2009).

6.1 Effect of the interleaver

Considering the irregular LDPC code of GPS L1C subframe 2 with the block-interleaver structure of GPS L1C over the block-fading channel with n_c = 2, the block interleaver does not provide full diversity. However, the block interleaver helps to average the channel, increasing the diversity compared to the case where no interleaving is considered at all. Concerning the proposed Root structure, full diversity is only achieved when the number of fading blocks is equal to n_c = 2. Otherwise, considering a block-fading channel with n_c > 2, the proposed Root structure does not provide full diversity with the BP algorithm. In Figures 13 and 14, CED error rates are illustrated for different code families (the irregular GPS L1C subframe 2 LDPC code, the irregular GPS L1C subframe 2 LDPC with the GPS L1C block interleaver, the regular (3,6) Root code with R = 1/2, the irregular Protograph Root code with R = 1/2, and the irregular symmetrical Protograph Root code with R = 1/2) considering n_c = 4 and n_c = 8. Each of the fading gains follows a normalized Rayleigh distribution. From these Figures, we see that the block interleaver enhances the diversity (due to the fact that the block interleaver enables us to average the information over the fading blocks) and, consequently, the error-correction performance for the interleaved version of GPS L1C. Moreover, as expected, we see that the Root code structures with R = 1/2 does not provide full diversity when n_c > 2 for the BP algorithm, yielding decreased error-rate performance (please refer to Figures 13 and 14).

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 13

CEDER of the proposed channel-coding schemes for a BPSK input over a block Rayleigh fading channel with n_c = 4

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 14

CEDER of the proposed channel-coding schemes for a BPSK input over a block Rayleigh fading channel with n_c = 8

However, we can do better for the root structure in the case where n_c > 2 by considering, as for the GPS L1C, a strategy of a structured channel interleaving to overcome the loss of full diversity. Having a block interleaver along the entire codeword will result in roughly the same results as those for for GPS L1C. But it will also enforce us to receive the entire codeword to decode the CED, and we will lose the benefit from the Root structure for fast recovering. To overcome this issue, we propose to add two independent block interleavers to each of the output blocks provided by the Root code structure (the scheme is illustrated in Figure 15). Adding those sub-block interleavers helps to enhance the average diversity at the receiver on each part of the Root codeword, improving the error-correcting performance and closing the gap with the performance of GPS L1C. Moreover, since each interleaver is applied independently to each of the output blocks (half part of the Root codewords), the decoding scheme presented in Figure 8 can be integrated at the receiver, allowing a decoder structure that can reduce the TTD. To illustrate this point, Figures 16 and 17 give the CEDER for the irregular GPS L1C subframe 2 LDPC code, the irregular GPS L1C subframe 2 LDPC with the GPS L1C block interleaver, the regular (3,6) Root code with R = 1/2 and with two independent block interleavers, the irregular Protograph Root code with R = 1/2 and with two independent block interleavers and the irregular symmetrical Protograph Root code with R = 1/2 and with two independent block interleavers, considering n_c = 4, and n_c = 8. Each of the fading gains follows a normalized Rayleigh distribution. From these figures, we can notice an enhancement of the decoder diversity thanks to the structured block interleaver, providing almost the same error-correcting performance than the irregular GPS L1C subframe 2 LDPC with the GPS L1C block interleaver. The irregular GPS L1C subframe 2 LDPC with the GPS L1C block interleaver provides slightly better performance due to: (a) its block interleaver averages the block channel over the entire codeword, and (b) the irregularity of the underlying LDPC code gives better thresholds due to a higher maximum variable node degree. By considering higher variable node degrees for the design, performance of our irregular schemes could be improved. As expected, the regular Root structure provides worse error-correcting performance than the irregular structures due to its higher demodulation threshold. Finally, we can remark that even if the proposed Root structures provide slightly worse error-correcting performance over the block-fading channel with n_c > 2, thanks to this structure, the decoder is able to reduce the TTD, which is the final objective of this work.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 15

Encoding Structure of the Root LDPC codes with rate R = 1/2 considering two independent block interleavers for each of the transmitted data blocks

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 16

CEDER of the proposed channel-coding schemes (with block interleaver) for a BPSK input over a block Rayleigh fading channel with n_c = 4

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 17

CEDER of the proposed channel-coding schemes (with block interleaver) for a BPSK input over a block Rayleigh fading channel with n_c = 8

7.1 Retrieved CED error rate

We first consider an AWGN channel. This model does not include fading or interferences coming from other sources. At the receiver, after sampling, the received baseband signal can be written as:

20

where y_k is the received signal, x_k is the transmitted signal, and n_k is the centered AWGN noise with noise variance σ², i.e., n_k ∼ 𝒩 (0, σ²).

For our performance evaluation, we assume that the entire codeword has been received. Figure 18 illustrates the CEDER in terms of C/N₀ for GPS L1C, the Galileo E1B I/NAV message, the proposed RS2 configuration of the I/NAV message, the LD-MDS codes, the sparse MDS codes, the regular Root-LDPC QC code structure, the regular Root-LDPC PEG code structure, the irregular Root Protograph code structure, and the irregular Root Protograph code with a symmetric structure.

Simulation results show that regular Root-LDPC codes obtain the best demodulation threshold compared to the Galileo E1B I/NAV message, the RS2 configuration of Galileo E1B I/NAV message, the LD-MDS codes, and sparse MDS codes with a demodulation threshold gain of 2.5 dBHz, 0.4 dBHz, 6 dBHz, and 0.9 dBHz, respectively, for a targeted error probability of 10⁻². Moreover, an irregular Protograph Root-LDPC code and an irregular Protograph Root-LDPC code with a symmetric structure, designed using the PEXIT charts (Liva & Chiani, 2007; Ryan & Lin, 2009), are simulated. Such irregular codes reduce the demodulation threshold compared to the regular Root LDPC by 0.4 dBHz and achieve the same decoding performance as GPS L1C. It must be noted that thanks to the Root LDPC structure (regular or irregular), a reduction of the TTD without degrading the demodulation threshold can be achieved (or with a negligible degradation in the case of regular Root LDPC). Note that simulation results in Figure 18 are presented without block-interleaver structures since no gain is achieved over the AWGN channel.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 18

CEDER over an AWGN channel

Secondly, we present CEDER considering an urban environment modeled using the two-state Prieto model (Prieto-Cerdeira et al., 2010) for a vehicle speed of 40 km/h and an elevation angle of 40 degrees. In Figure 19, CED error rate is reported for the LMS channel as a function of the C/N₀ considering the following schemes: the Irregular LDPC code of GPS L1C subframe 2 with and without the GPS L1C block interleaver, the sparse MDS codes, the irregular symmetrical Protograph Root code, and the irregular symmetrical Protograph Root code with two independent block interleavers (please refer to the structure presented in Figure 15). We can see that the irregular LDPC code of GPS L1C subframe 2 using the GPS L1C block interleaver, the Irregular Root Protograph code, and the Irregular Symmetrical Root Protograph code has similar performance. Moreover, the sparse MDS code presents a gap of 1 dB with respect to the irregular LDPC code of GPS L1C subframe 2 with the GPS L1C block interleaver. From Figure 19, it can be seen that the block interleaver in the GPS L1C structure and the two block interleavers in the irregular symmetrical Protograph Root structure only provide a slight enhancement of the error-correcting performance (0.05 dBHz and 0.2 dBHz, respectively). It shows that due to the fact that the LMS channel is a very ”volatile” channel, an interleaver seems to have a negligible effect on the decoding performance.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 19

CEDER over the LMS channel modeled using the two-state Prieto model for a vehicle speed of 40 km/h and an elevation angle of 40 degrees

7.2 Time to data (TTD)

The TTD gives an indication of the time required by the receiver to correctly retrieve the CED from the navigation message, starting from the first epoch at which the first data symbol is extracted from the receiver. The following analysis considers the following assumptions:

• TOW is assumed to be known.

• The results are expressed in terms of the TTD values.

In order to obtain the TTD values, we need to define the Probability Density Function (PDF) f(t) of the TTD. The TTD can then be obtained from the Cumulative Distribution Function (CDF) defined as follows:

21

where x describes the percentage of confidence needed in order to represent the time needed by the receiver to retrieve CED. For simulations, we first evaluate 100.000 times the duration needed by one receiver to obtain the error-free CED for each of the proposed error-correcting solutions considering an AWGN channel with C/N₀ = 25 dBHz, C/N₀ = 30 dBHz, and C/N₀ = 45 dBHz. As expected, the first epoch (first synchronized bit) can arrive at any time. In order to initialize the first epoch value for each of the 100.000 simulations, the start symbol is sampled uniformly in the interval defined by the first and the last symbol of the nominal subframe structures.

The error-correcting schemes along with the new message structure are simulated and compared to each other as well as to the Galileo E1B I/NAV, RS2 configuration of Galileo E1B I/NAV and GPS L1C message structure under the AWGN channel assumption. In order to evaluate the reduction of the TTD, an analysis of the time to retrieve the CED based on the calculation of the cumulative distribution function (CDF) is implemented. Simulation results are presented in Figure 20, Figure 21, and Figure 22, respectively.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 20

TTDs over AWGN channel with a C/N₀ = 45 dBHz

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 21

TTDs over AWGN channel with a C/N₀ = 30 dBHz

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 22

TTDs over AWGN channel with a C/N₀ = 25 dBHz

Simulation results in Figure 20 show that the Galileo E1B I/NAV and the RS2 configuration of Galileo E1B I/NAV have higher TTDs than the GPS L1C message structure. Moreover, it is shown as a reduction of more than 30% of for at least 66% of the time compared to the current GPS L1C signal and a reduction of 50% of TTD for at least 30% of the time in case of Root-LDPC scheme (under high C/N₀ = 45 dBHz channel conditions). Those results are even better in the case of LD-MDS and sparse MDS schemes, where simulations show a reduction of 50% of TTD for at least 50% of the time compared to the current GPS L1C signal. The main reason for the improvement of the TTD performance is due to the MDS property. Thanks to this property, under good channel conditions, the proposed error-correcting schemes are able to reduce the time to retrieve the CED since not all the data (redundant or systematic) need to be recovered to decode. Moreover, the sparse MDS and LD-MDS schemes provide better results in terms of TTD compared to the Root codes as the MDS property works for any of the four blocks of the message structure. Since the message structure of the Root codes requires a separation of the redundant and systematic information in a maximum of two blocks in the considered cases, there is not as many degrees of freedom as for the sparse MDS or LD-MDS codes. In Table 1, we illustrate the TTD relevant parameters for a better comparison between proposed message structures.

Since the Galileo E1B I/NAV and the RS2 configuration of Galileo E1B I/NAV have higher TTDs than the GPS L1C message structure, in the following, we compare the proposed scheme only with respect to the GPS L1C message structure. In Figure 21, it is shown that the CDF of the different proposed schemes for a C/N₀ = 30 dBHz. A decrease of the TTD for at least 60% of the time compared to the current GPS L1C signal is shown for the case of Root codes and a decrease of TTD for at least 90% of the time in the case of the LD-MDS scheme. Under this channel condition, it is shown that the sparse MDS candidate provides a better solution in all cases. It must also be noted that the LD-MDS solution performs worse than the sparse MDS one as the error-correcting capabilities of the sparse MDS code are higher than the error-correcting capabilities of the LD-MDS. Note also that the Protograph Root LDPC code with a symmetric structure (regular or irregular) outperforms the Protograph Root code with an asymmetric structure since those codes provide unequal protection for each data block. Therefore, those codes increase the average TTD when the less protected block is first received. In Table 1, we illustrate the TTD relevant parameters for a better comparison between proposed message structures.

In Figure 22, it is shown that the CDF of the error-correcting candidate for a C/N₀ = 25 dBHz, which can be considered as low AWGN carrier-to-noise ratio conditions. A small reduction of the TTD, for almost 20% of the cases, is shown for Root codes, compared to the current GPS L1C signal. Otherwise, the same performance as the GPS L1C channel-coding scheme is reached. The reason for which the Root codes are capable of reaching the same performance as the GPS L1C channel-coding scheme is due to the full diversity property, which provides to the Root codes notable error-correcting capabilities under low carrier-to-noise ratio conditions. It should be noticed that irregular Root-LDPC protograph codes achieve the best performance in terms of TTD compared to the other Root-LDPC codes, since the threshold and the error-correcting capabilities of the codes are better. For the sparse MDS code scheme, a reduction of the TTD is reached, for at least 60% of the cases, thanks to the MDS property. However, since under BP algorithm the sparse MDS code scheme does not have the full diversity property, a reduction in the error-correcting capabilities are observed and a higher TTD is shown in the remaining cases. It should be noticed that the LD-MDS solution is not presented in Figure 22; this is because the LD-MDS codes do not converge for low AWGN carrier-to-noise ratio conditions due to poor error-correcting capabilities. In Table 1, we illustrate the TTD relevant parameters for a better comparison between proposed message structures.

In a second experiment, we evaluate 100.000 times the duration needed by one receiver to obtain the error-free CED for each of the proposed error-correcting solutions considering an urban scenario modeled through the two-state Prieto model for a vehicle speed of 40 km/h and an elevation angle of 40 degrees with C/N₀ = 40 dBHz and C/N₀ = 37 dBHz. As expected, the first epoch (first synchronized bit) can arrive at any time. Then, as it was proposed for the AWGN channel, we initialize the first epoch value considering that the start symbol is sampled uniformly in the interval defined by the first and the last symbol of the nominal subframe structures.

In Figure 23, we have studied the TTD for an urban environment modeled through the two-state Prieto model (Prieto-Cerdeira et al., 2010) for a vehicle speed of 40 km/h and an elevation angle of 40 degrees with a C/N₀ = 37 dBHz. We remark that the Root codes structures reduce the TTD with respect to the GPS L1C subframe 2. Sparse MDS codes provide better results than other code structures until the 75% of the case. Then, they are performing worse than others. In Table 2, we have illustrated the TTD relevant parameters for a better comparison between proposed message structures.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 23

TTD over the LMS channel modeled using the two-state Prieto model for a vehicle speed of 40 km/h and an elevation angle of 40 degrees with a C/N₀ = 37 dBHz

Finally, in Figure 24, we give the TTD over an urban environment modeled through the two-state Prieto model (Prieto-Cerdeira et al., 2010) for a vehicle speed of 40 km/h and an elevation angle of 40 degrees with a C/N₀ = 40 dBHz. We remark that the Root code structures reduce the TTD with respect to the GPS L1C subframe 2. Sparse MDS codes provide better results than other code structures until the 94% of the case. Then, they are performing worse than others. In Table 2, we have illustrated the TTD relevant parameters for a better comparison between proposed message structures.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 24

TTD over the LMS channel modeled using the two-state Prieto model for a vehicle speed of 40 km/h and an elevation angle of 40 degrees with a C/N₀ = 40 dBHz