Partly systematic Luby transform codes based on improved progressive edge-growth algorithm for Mars communications

Abstract

The Luby transform code is a forward error correction code and was originally designed for the erasure channel. In this paper, the Luby transform codes over the Mars communication channel are investigated. To guarantee the reliable data transmission over the Mars communication channel which are usually affected by fading and noises, the progressive edge-growth algorithm is improved and used in for encoding the Luby transform codes. And then a partly systematic Luby transform code with an improved progressive edge-growth algorithm is designed to improve the error propagation phenomenon in Mars communications. Performance evaluations of the designed partly systematic Luby transform code based on the random graph, PEG and improved progressive edge-growth algorithms, respectively, are conducted through a series of simulations. Simulation results show that the performance of the partly systematic Luby transform code based on the improved progressive edge-growth algorithm outperforms those of the partly systematic Luby transform code based on two other algorithms and has the lower bit error rate and overhead.

Introduction

Mars communications have characteristics such as long distance, long propagation delays, very weak received signal, high code error rate and easily broken link, etc. ¹ The reliable information transmission for Mars communications can be guaranteed using channel encoding and decoding technologies. However, the traditional channel error correcting code technologies based on automatic repeat request (ARQ) cannot satisfy the transmission requirements of deep space communication, such as long distance, long propagation delay, and so on. ²

Fountain codes were first put forward by Michael Luby and John Byers and others, which could exhibit excellent performance over time-varying channels without the need of channel state information (CSI) at the transmitter side.^3–5 LT codes, the first practical fountain codes, are rateless in the sense that a possibly limitless number of output symbols can be generated in the encoding of a finite number of message symbols. Each receiver can successfully decode when it receives a given number of output symbols. ⁴ In recent years, numerous researchers endeavored to improve the achievable performance of LT codes, which still exist limitations to its application environment.^6–8 Moreover, LT codes are considered for deep space communications and could deliver large amounts of data effectively and reliably.^9–12

In this paper, we focus on the investigation of LT codes in Mars communication environments. To protect data transmission over Mars communication channel where fading and noise are encountered, the LT codes need to be modified. The classical LT encoding can be implemented by the progressive edge-growth (PEG) algorithm and the random graph (RG) algorithm, first proposed in Hu et al. ¹³ The PEG algorithm can eliminate the short cycles in RG construction in a best-effort sense. Therefore, the PEG algorithm can be used for the LT encoding in this paper.

The key contributions of our work can be summarized as follows.

The PEG algorithm is modified and the edge-selection method of encoded symbols with degree-1 is changed. The meaning of degree-1 is that the degree of encoded symbols is one. This improvement can enlarge the ripple size in decoding, reduce the decoding overhead and improve the decoding efficiency.

A partly systematic LT code based on the improved PEG algorithm is designed to mitigate the error propagation phenomenon when the encoded packets are affected by channel errors in Mars communication environments.

The rest of this paper is organized as follows: The radio wave propagation characteristics of Mars communications are presented in the next section. Then, the improved PEG algorithm is described. The designed partly systematic LT codes and the soft iterative decoding of LT codes over complicated channels are then described. This is followed by a section that describes the performance evaluation of the partly systematic LT codes constructed by the improved PEG algorithm. Finally, the conclusions are drawn.

Radio wave propagation characteristics of Mars communications

When the signal is transmitted over the Mars channel, the environmental influence factors include the Martian atmosphere, ionosphere, global dust storms, aerosols, clouds, free space loss and solar wind. Consequently, this paper focuses on the dominating effects of free space loss and solar wind, which can result in Rician fading.^14,15

Signal spread loss in free space is defined as L_FS

$$L_{FS}(dB)=32.45+20\log (f)+20\log (d)$$

(1)

Using equation (1), we can calculate the free space loss which can be partially compensated by using higher antenna gain.

Because of the greater distance from the Sun to Mars than to the Earth, solar wind has weaker influence on Mars communications. The influence of weak solar scintillation can be considered as multiplicative noise. Under the influence of weak solar scintillation, there are line-of-sight link and multipath fading in Mars communications, which can be modeled by a Rician model. In addition, because of the influence of the inherent additive noises of communication, the multiplicative weak solar scintillation noise and the multiplicative free space loss, the received signal y through the Mars communication channel can be simply expressed as follows

$$y=h(S)\cdot x+n$$

(2)

where x represents the signals achieved by LT encoding and BPSK modulation, n is the additive Gaussian white noise, S is the weak scintillation index ranging from 0 to 0.3 which determines the Rician fading factor K, h(S) is the Rician fading coefficient which can be calculated by the relationship between S and K in equation (3) and y is the received signal affected by the noise and fading through the Mars communication channel.

Through an extensive literature search, the relationship between the Rician factor K and intensity scintillation index S can be described as follows ¹⁶

$$K=\frac{\sqrt{1-S^2}}{1-\sqrt{1-S^2}}$$

(3)

And the probability density function of the envelope of the received signal can be described as Rician distribution

$$P(R)=\frac{R}{{\delta }^2}\exp (-K)\exp (-\frac{R^2}{2{\delta }^2})\cdot I_0{\left(\frac{2K{R}^2}{{\delta }^2}\right)}^{\frac{1}{2}}$$

(4)

where K is the Rician factor, which is defined as the power ratio of a single, fixed component, and the power of zero mean, complex Gaussian, diffuse components. ${\delta }^{\text{2}}$ is the average power of the signal transmitted by the scattering paths.

Improved PEG encoding algorithm

In the PEG algorithm, for a given encoded symbol $t_j$ , its neighbor within depth $l$ is defined as $N_{t_j}^l$ , which is the set consisting of all information symbols reached by a tree spreading from $t_j$ within depth $l$ . The tree graph is shown in Figure 1. The complementary set of $N_{t_j}^l$ , ${\overline{N}}_{t_j}^l$ , is defined as $V_t\backslash N_{t_j}^l$ . $V_{\text{t}}$ is the set of encoded symbols and ${\overline{N}}_{t_j}^l\cup N_{t_j}^l=V_t$ . Instead of selecting edges randomly in the RG algorithm, $d_{t_j}$ edges of $t_j$ are added to the current graph on an edge-by-edge basis. And the length of the shortest cycle passing through $t_j$ is maximized whenever a new edge originating in $t_j$ is being added. First the tree originating in encoded symbol $t_j$ is expanded up to depth $l$ , where ${\overline{N}}_{t_j}^l\ne \Phi$ but ${\overline{N}}_{t_j}^{l+1}=\Phi$ or the cardinality of $N_{t_j}^l$ stops increasing but is smaller than $K$ . Then a new edge of $t_j$ can be determined by placing an edge between $t_j$ and a specified information symbol selected from ${\overline{N}}_{t_j}^l$ . The girth g is lower bounded by $\text{g}\ge 2(l+2)$ .

Figure 1.

Neighbor $N_{t_j}^l$ within depth l of encoded symbol $t_j$ .

The encoded symbols of degree-1, which were defined as active nodes, are extremely vital upon decoding and will not influence the girth. The active nodes start decoding process and maintain the decoding ripple size. The problem of the generator matrix constructed by the PEG algorithm is shown in Figure 2. It can be seen from Figure 2 that the edge of symbol $t_5$ is selected by the PEG algorithm; edge $(s_3,t_5)$ will be added and $s_3$ is an information symbol with the lowest degree under the current graph. On decoding, only two edges including edge $(s_3,t_1)$ and edge $(s_3,t_1)$ will be released. However, if $s_1$ with the highest degree in the current graph is selected, three edges connected to $s_1$ will be immediately released upon decoding. Consequently, the PEG algorithm is modified and the edge-selection method of active nodes in PEG algorithm is changed. Instead of selecting an information symbol with the lowest degree under the current graph, an information symbol with the highest degree is selected. This improvement can release more edges upon decoding and enlarge the ripple size during the LT decoding.

Figure 2.

A tanner graph of encoded symbol degree {2, 3, 2, 3, 1, 1} constructed by the traditional PEG algorithm. PEG: progressive edge-growth.

However, the improved PEG algorithm has a problem that multiple active nodes select the same information symbol, as shown in Figure 3. The active node $t_5$ selects $s_1$ as the neighbor and so does $t_6$ . This problem leads to waste of the rare active nodes and degradation of decoding efficiency. Moreover, it increases the decoding overhead and seriously affects the iterative decoding process. To efficiently select the edges of active nodes, an indicator set $\Gamma$ for information symbols is defined. The indicator set $\Gamma$ is initialized to $\Phi$ . When the information symbol $s_i$ is selected by one active node, the element $i$ is added into the set $\Gamma$ . Then the edges of other active nodes are selected. For example, the information symbol with the same highest degree is first sorted according to their subscripts, and the first one whose subscript is not in the set $\Gamma$ is picked. Then the picked symbol's subscript is added into the set $\Gamma$ .

Figure 3.

An example of active nodes selecting same information symbol.

The improved PEG algorithm proposed in this paper is summarized as follows.

Step 1. Determine the degree $d_{t_j}$ of the j-th encoded symbol $t_j$ through the degree distribution. If the $d_{t_j}!=1$ , go to Step 2. Else, skip to Step 3.

Step 2. Draw the edge $(s_i,t_j)$ as the first edge of $t_j$ . $s_i$ is an information symbol with the lowest information degree under the current graph setting. Then expand a tree from $t_j$ up to depth $l$ under the current graph setting such that ${\overline{N}}_{t_j}^l\ne \Phi$ but ${\overline{N}}_{t_j}^{l+1}=\Phi$ or the cardinality of $N_{t_j}^l$ stops increasing but is smaller than K. Then draw an edge between $t_j$ and $s_i$ . $s_i$ is one information symbol picked from ${\overline{N}}_{t_j}^l$ with the lowest information degree. Repeat the above procedure until all the edges are selected. Then skip to Step 4.

Step 3. Choose the information symbol with the same highest degree according to their subscripts, and then pick the first information symbol $s_i$ whose subscript is not in the set $\Gamma$ . Then draw an edge between $t_j$ and $s_i$ . Add the subscript of $s_i$ into the set $\Gamma$ . Then go to Step 4.

Step 4. Repeat from Step 1 until all encoded symbols are encoded.

As is shown in Figure 4, the symbol $t_5$ selects $s_1$ as its neighbor and $\Gamma =\left\{\text{1}\right\}$ . Then $t_6$ selects $s_2$ with the highest information degree except $s_1$ .

Figure 4.

Tanner graph constructed by the improved PEG algorithm. PEG: progressive edge-growth.

The improved PEG algorithm can reduce the existence of circle with length 4 and guarantee a large girth in a best-effort sense, thereby enlarging the ripple size during the LT decoding, reducing the decoding overhead and improving the decoding efficiency.

Partly systematic LT codes and soft decoding

Let $s=(s_1,s_2,\mathrm{\dots },s_k)$ be the information symbols with length $k$ and $t=(t_1,t_2,\mathrm{\dots },t_n)$ the encoded symbols with length $n$ , respectively. Let $\widehat{r}=\left(\widehat{r_1},\widehat{r_2},\mathrm{\dots },\widehat{r_n}\right)$ be the received encoded symbols through the Mars communication channel. And $t$ is obtained by the improved PEG algorithm. The following degree distribution is adopted.

$$\begin{array}{l}\Omega \left(x\right)=\text{0}\text{.00797x}+\text{0}{\text{.49357x}}^{\text{2}}+\text{0}{\text{.16622x}}^{\text{3}}+\text{0}{\text{.07265x}}^{\text{4}}\\ +\text{0}{\text{.08255x}}^{\text{5}}+\text{0}{\text{.05606x}}^{\text{8}}+\text{0}{\text{.03723x}}^{\text{9}}\\ +\text{0}{\text{.05559x}}^{\text{19}}+\text{0}{\text{.02502x}}^{\text{65}}+\text{0}{\text{.00314x}}^{\text{66}}\end{array}$$

(5)

This degree distribution given in equation (5) is an optimal degree distribution proposed in Shokrollahi. ¹⁶ When the channel is contaminated by Rician fading and noise, soft decoding algorithm of LT codes is used. The soft iterative decoding of LT codes is performed by passing messages from check nodes to variable nodes using the belief propagation algorithm and vice versa, in an iterative manner. ¹⁷ Soft iterative decoding is performed alternatively by estimating log-likelihood (LLR) between the encoding nodes and information nodes. L^{( η )}(t_{j, i} ) is the LLR estimated from the j-th encoding node to the i-th information node at the η-th iteration, where $1\le j\le n$ and $1\le i\le k$ . L^{( η )}(h_{i, j} ) is the LLR estimated from the i-th information node to the j-th encoding node in the η-th iteration. The decoding process is first started by initialization of L⁽⁰⁾(h_{i, j} ) as follows.

$$L^{\left(0\right)}\left(h_{i,j}\right)=0$$

(6)

With these initial values, the LT decoder updates the messages between the encoding nodes and information nodes alternatively using equations (7) and (8).

$$L^{\left(\eta \right)}\left(t_{j,i}\right)=2{\tan }^{-1}\left(\tanh \frac{r_j}{2}\cdot \prod _{x\in N_j,x\ne i}\tanh \frac{L^{\left(\eta -1\right)}\left(h_{x,j}\right)}{2}\right)$$

(7)

where $N_j$ is the index set of the neighborhood information nodes of the j-th encoding node.

$$L^{\left(\eta \right)}\left(h_{i,j}\right)={\displaystyle \sum _{e\in {\epsilon }_i,e\ne j}{L}^{\left(\eta \right)}\left(t_{e,i}\right)}$$

(8)

where ${\epsilon }_i$ is the index set of the encoded nodes connected with the j-th information node. This iterative process is continued until it reaches the maximum iteration number, ${\eta }_{\max }$ . Finally, the soft output information is then calculated by equation (9).

$$\widehat{s_i^{\eta }}={\displaystyle \sum _{e\in {\epsilon }_i}{L}^{\left(\eta \right)}\left(t_{e,i}\right)}$$

(9)

In the proposed method, soft decoding algorithm performs directly on the Tanner graph corresponding to the Generator matrix of LT codes. Using equations (6) to (9), L^{( η )}(h_{j, i} ) = 0 with these initial values are calculated when there are no encoded symbols of degree-1. Consequently, the performance of the LT codes is poor when there are only little encoded symbols with degree-1. And the conventional non-systematic LT codes will aggravate the error propagation when the encoded packets are contaminated by Rician fading and noise. However, little soft information can be achieved from encoded symbols when the systematic LT codes are decoded. Therefore, a partly systematic LT codes constructed by the improved PEG algorithm is proposed in this paper.

The structure of partly systematic LT code is shown in Figure 5. $\alpha (0\le \alpha \le 1)$ is defined as the proportion of the systematic LT codes. The partly systematic LT code with parameter α is constructed as follows:

Step 1. Construct the first αK encoded symbol by connecting $t_i$ with $s_i(\text{1}\le i\le \alpha K)$ . Then go to step 2.

Step 2. Construct the next encoded symbol by the improved PEG algorithm described in Section 3.

Figure 5.

The partly systematic LT codes with α.LT: Luby transform.

The parameter α in the partly systematic LT codes is discussed in Section 5.

Performance evaluation

The performance of the partly systematic LT codes based on the improved PEG algorithm for the Mars communications is evaluated. Degree distribution given in equation (5) is used in the following simulations.

First, the performance of the designed partly systematic LT codes with different code length is studied to select the suitable code length. Figure 6 shows the relationship between bit error rate (BER) and signal-to-noise ratio (SNR) of the partly systematic LT codes with different code length when $S=0.1$ and overhead = 0.5. It can be seen that the partly systematic LT code with 1000 length has the lowest BER and best performance in the same channel environment. Figure 7 shows the performance of the partly systematic LT codes with different code length and SNR = 5 dB. It can be seen that the LT codes with 1000 code length can reduce the overhead. In the next simulations, 1000 code length is adopted.

Figure 6.

BER Performance of different code length with overhead = 0.5. BER: bit error rate.

Figure 7.

BER Performance of different code length with SNR = 5 dB. BER: bit error rate; SNR: signal-to-noise ratio.

Next, the degree distributions of the LT codes' information symbols constructed by the RG, PEG and improved PEG algorithms, respectively, are investigated. Figure 8 shows the comparison of the average degree distributions of information symbols among three algorithms with k = 1000 and overhead = 0.2. As is shown in Figure 8, the degrees of information symbols constructed by the improved PEG and the PEG algorithms are mainly distributed around 7 and 8, respectively. While the degrees of information symbols constructed by the RG algorithm are scattered, it is shown that the improved PEG and the PEG algorithms could guarantee an approximately uniform distribution of information symbols. They can ensure that all source symbols are involved in encoding, while the RG algorithm not. Moreover, the improved PEG algorithm can degrade the average degree and encoding complexity.

Figure 8.

Comparison of the average degree distributions of information symbols constructed by three algorithms.

Third, the BER comparisons among the partly systematic LT codes that respectively adopt the RG, the PEG and the improved PEG algorithms over the Mars communication channel are given in Figures 9 and 10. Figure 9 shows the relationship between BER and SNR of the three algorithms when overhead = 0.7, $S=0.1$ and ${\eta }_{\max }=\text{10}$ . Figure 10 shows the relationship between BER and the decoding overhead of three algorithms when SNR = 5 dB, $S=0.1$ and ${\eta }_{\max }=10$ . Simulation results show that the improved PEG algorithm can reduce BER and overhead compared with two other algorithms. It is clear that the partly systematic LT code based on the improved PEG algorithm outperforms those based on two other algorithms and could achieve better performance over the Mars communication channel.

Figure 9.

BER vs. SNR performance comparisons among three algorithms. BER: bit error rate; SNR: signal-to-noise ratio.

Figure 10.

BER vs. overhead performance comparisons among three algorithms.BER: bit error rate.

Figures 11 to 13 show the BER performance of the partly systematic LT codes with different $\alpha$ and different ${\eta }_{\max }$ , respectively. The channel here is with SNR = 5 dB and S = 0.1. The improved PEG algorithm is used to construct the partly systematic LT codes. From these three figures, three conclusions can be drawn. First, the partly systematic LT codes with higher α outperform those with lower α when the ${\eta }_{\max }$ is rather small. Second, with the increasing of ${\eta }_{\max }$ , the partly systematic LT codes with lower $\alpha$ can obtain the greater improvement. Third, the partly systematic LT codes with higher $\alpha$ always perform better when the decoding overhead is small. Consequently, taking into consideration, the BER performance and algorithm complexity $\alpha$ = 80% and ${\eta }_{\max }$ = 10 are selected to evaluate the BER performance of the partly systematic LT codes over the Mars communication channel with different S.

Figure 11.

BER performance under different $\alpha$ with ${\eta }_{\max }=\text{5}$ . BER: bit error rate.

Figure 12.

BER performance under different $\alpha$ with ${\eta }_{\max }=\text{10}$ .BER: bit error rate.

Figure 13.

BER performance under different $\alpha$ with ${\eta }_{\max }=\text{20}$ . BER: bit error rate.

Theoretically, LT codes could perform better over the Mars communication channel with lower intensity scintillation index S. The results given in Figure 14 clearly show that the LT codes with the lowest S perform best, which is consistent with the theoretical analysis. In general, the partly systematic LT codes outperform the conventionally non-systematic LT codes and guarantee the relatively reliable Mars communication.

Figure 14.

BER performance under different S with $\alpha =80\%$ and ${\eta }_{\max }=\text{10}$ . BER: bit error rate.

Conclusions

The conventional LT codes are not suitable for the Mars communication environments, where fading and noise exist. Consequently, the PEG algorithm is modified to be used for the LT codes. And a partly systematic LT code for the Mars communication is designed on the basis of the improved PEG algorithm. Simulation results show that the designed partly systematic LT code can reduce the decoding overhead and improve the error propagation phenomenon when the encoded packets are affected by channel errors. Moreover, it can guarantee the effectiveness and reliability of Mars communications.