Design of two-dimensional spatially coupled LDPC codes for combating burst erasures①

LIU Yang(劉 洋), HE Jinglin, WANG Bin, ZHANG Yuzhi

(College of Communication and Information Engineering, Xi’an University of Science and Technology, Xi’an 710054, P.R.China)

(Xi’an Key Laboratory of Network Convergence Communication, Xi’an University of Science and Technology, Xi’an 710054, P.R.China)

Abstract Spatially-coupled low-density parity-check (SC-LDPC) codes are prominent candidates for future communication standards due to their ‘threshold saturation’ properties.However, when facing burst erasures, the decoding process will stop and the decoding performances will dramatically degrade.To improve the ability of burst erasure corrections, this paper proposes a two-dimensional SCLDPC (2D-SC-LDPC) codes constructed by parallelly connecting two asymmetric SC-LDPC coupled chains for resistance to burst erasures.Density evolution algorithm is presented to evaluate the asymptotic performances against burst erasures, by which the maximum correctable burst erasure length can be computed.The analysis results show that the maximum correctable burst erasure lengths of the proposed 2D-SC-LDPC codes are much larger than the SC-LDPC codes and the asymmetric SC-LDPC codes.Finite-length performance simulation results of the 2D-SC-LDPC codes over the burst erasure channel confirm the excellent asymptotic performances.

Key words: burst erasure channel, SC-LDPC code, density evolution, decoding performance

0 Introduction

Burst erasures occur in many common practical communication scenarios, such as deep fading in wireless communications, intense transient noises in magnetic data storage systems, packet losses in Internet transmission systems, collisions in coded slotted ALOHA and so on, which will dramatically affect the communication reliability.Designing a good error-correcting code to mitigate the adverse effects of burst erasures is still a challenging problem.

Recently, spatially-coupled low-density paritycheck (SC-LDPC) codes have attracted much attention since their belief propagation (BP) thresholds can achieve the maximum a posterior (MAP) thresholds of the underlying LDPC block codes.Refs[1,2] named this phenomenon ‘threshold saturation’ and proved it rigorously for the binary erasure channel (BEC)[1]and the binary memoryless symmetric (BMS) channel[2].Afterwards, many new SC-LDPC code structures have emerged to further improve the thresholds[3-4].However, when facing burst erasures, the decoding chain of SC-LDPC codes will break up and the decoding error probability will remain strictly positive from the position where the burst erasures occur.In other words, the excellent decoding performances of SC-LDPC codes will degrade seriously when transmitted over the burst erasure channel.More detailed analysis on the burst erasure correction capabilities of SC-LDPC codes can be found in Refs[5,6] and finite-length analysis over the burst erasure channels was done in Ref.[7].

To combat burst erasures, multi-dimensional SCLDPC codes constructed by expanding the one-dimensional edge-spreading to multiple dimensions were proposed in Ref.[8] and the analysis results showed that multi-dimensional SC-LDPC codes are more robust against the burst erasures compared with the conventional SC-LDPC codes.In Ref.[9], a band-splitting permutation for SC-LDPC codes was proposed to realize the asymptotic optimality in terms of burst erasure correction.Asymmetric SC-LDPC (ASC-LDPC) codes against multiple-burst erasures was proposed in Ref.[10], which proved that the multiple-burst erasure correcting performances of SC-LDPC codes can be greatly improved by introducing the asymmetric structure.Protograph-based folded SC-LDPC (FSC-LDPC)codes constructed by folding the spatial structure of SCLDPC codes were proposed in Ref.[11], which showed that the FSC-LDPC codes performed better than the SC-LDPC codes over single and multiple randomburst erasure channels.Different from modifying the structure of the conventional SC-LDPC code, spatially coupled generalized LDPC (SC-GLDPC) codes were considered in Ref.[12] to combat bust erasures,which improved the capability of the burst erasure corrections by introducing the linear block codes as the super check nodes instead of the standard single parity check constraints.

The decoding chain of SC-LDPC codes abort when facing burst erasures.Since this problem cannot be solved by increasing the chain length, a two-dimensional SC-LDPC (2D-SC-LDPC) codes is proposed constructed by parallelly connecting two SC-LDPC coupled chains for resistance to burst erasures in this paper.Asymmetric structure is also introduced in each coupled chain to further improve the capability of the burst error correction, because the ASC-LDPC codes possess larger minimal cardinality of stopping sets,which is beneficial to the burst erasure corrections.The connection structure is realized by edge exchanges between these two coupled chains, by which two coupling chains can provide support for each other to avoid the decoding termination when either of the coupling chains encounters the burst erasures.Moreover, this connection way can maintain the degree distributions of each SC-LDPC code unchanged, which means the decoding complexity cannot be increased.To evaluate the asymptotic performances against burst erasures, the density evolution algorithm for the proposed 2D-SC-LDPC codes is derived to obtain the maximum correctable burst erasure length.The analysis results show that the maximum correctable burst erasure lengths of 2D-SCLDPC codes are much larger than the ASC-LDPC codes and SC-LDPC codes.To verify the asymptotic performances, the finite-length performances of 2D-SC-LDPC codes are also simulated over the burst erasure channel along with the ASC-LDPC codes and SC-LDPC codes for comparisons.Simulation results demonstrate that the finite-length performances are consistent with the asymptotic performances obtained by density evolution.

1 2D-SC-LDPC codes

1.1 SC-LDPC codes

A (J,K,L) SC-LDPC coupled chain is constructed by couplingLidentical and disjoint (J,K)regular LDPC protographs,whereLdenotes the coupling length.Each LDPC protograph is placed at one position in order and denote each position byu(u=1,2, …,L).A conventional fully-connected coupling pattern is considered to couple theseLprotographs.Specifically, letω=gcd(J,K) be the greatest common divisor ofJandK, there areJ′ check nodes andK′ variable nodes at each position, whereJ′=J/ωandK′=K/ω.To couple theseLprotographs,Jedges of each variable node at positionuare spread to all adjacent check nodes at positionu+i(i=1, 2, …,ω-1).In turn, for each check node at positionu,Kedges will be connected to all nearby variable nodes at positionu-i(i=1, 2, …,ω-1).To terminate the coupled chain,ω-1 extra positions only including additional check nodes will be added at the end.A (3,6,L) SC-LDPC coupled chain is illustrated in Fig.1,where the circles denote the variable nodes and the squares denote the check nodes.

For a clear description, the definitions of the SCLDPC codes are given from the viewpoint of the protograph.A (J,K,L) SC-LDPC coupled chain can be viewed as a protograph and its associated incidence matrix also called as base matrix is denoted asBSC.Denote the base matrix of the underlying LDPC code asBwith a size ofJ′ ×K′.The base matrixBSCis given in Eq.(1).

where the submatricesBi(i=1, 2, …,ω-1)has the same size ofB.It means that the base matrixBis decomposed intoωsubmatrices and they must satisfy Eq.(2).

A (J,K,L,M) SC-LDPC code can be obtained by taking an ‘M-lifting’ operation on the (J,K,L)SC-LDPC coupled chain, whereMis the lifting factor[13].The parity check matrix of the SC-LDPC code can be generated by replacing each nonzero entry inBSCby oneM×Mrandom permutation matrix and each zero entry inBSCby oneM×Mall-zero matrix.

The design rate of the(J,K,L,M) SC-LDPC code is given as follows.

1.2 Construction of 2D-SC-LDPC codes

The proposed 2 D-SC-LDPC codes are constructed by parallelly connecting two coupled chains, where the connection structure is realized by exchanging the edges for each position between these two chains.To further improve the ability to combat burst erasure errors,the asymmetric structure is embedded into each coupled chain.In the following, the ASC-LDPC codes are introduced briefly.

A(J,K,L) ASC-LDPC coupled chain is constructed by changing the edge spreading in the SC-LDPC coupled chain.For a clear description, the variable nodes at each position is first divided into two types with equal fractions:the upper layer variable nodes and the lower layer variable nodes, where the edges of the upper layer variable nodes are connected to the interval check nodes and the edges of the lower layer variable nodes are connected to the consecutive check nodes.Specifically, at positionu,Jedges of each upper layer variable node are spread to the check nodes at positionu+2i(i=0,1,…,ω-1).While for each lower layer variable node, the edges are connected to the check nodes at positionu+i(i=0,1, …,ω-1).The same operation is made for each variable node at each position, then a (J,K,L)ASC-LDPC coupled chain can be constructed.

A(J,K,L,M)ASC-LDPC code can be obtained by applying an ‘M-lifting’ on this coupled chain.Fig.2 shows a ( 3,6,L)ASC-LDPC coupled chain,where the coupling widths for the upper and lower layer variable nodes are 2ω-1 andωrespectively.

The base matrixBASCof a (3, 6,L) ASC-LDPC coupled chain is given as follows.

2 Density evolution analysis

This section analyzes the thresholds of the proposed 2D-SC-LDPC codes transmitted over the burst erasure channel under BP decoding algorithm.Consider that the single and consecutive burst erasure model and define the threshold as the maximum correctable burst erasure length.Here,a modified density evolution algorithm is proposed to compute the threshold and denote the threshold is denoted aseBP.

When a 2D-SC-LDPC code is transmitted over the burst erasure channel under the single and consecutive burst erasure model, it means that the messages within the range of the burst erasures will be erased with probability 1 and the remained messages will be received correctly.For a clear description, the following symbols are defined.

3 Numerical results

3.1 Threshold analysis results

Based on the above derived density evolution algorithm, the maximum correctable burst erasure lengths for the proposed 2D-SC-LDPC codes, SC-LDPC codes and ASC-LDPC codes can be computed.Set the maximum iteration number as 104and the breakout condition of the erasure probability for each variable node as 10-6.The stopping criterion is that the erasure probability for each variable node reaches the breakout condition or the iteration reaches the maximum iteration number.

As demonstrated in Ref.[10], the theoretical upper bound on the maximum correctable burst erasure length for the SC-LDPC code is the number of rows of its base matrix.Therefore, the Shannon limiteSLcan be defined as the number of rows of the base matrix.The(3,6, 3, 6, 30) 2D-SC-LDPC code is first considered and the base matrix has the size of 68 ×120.The threshold analysis results obtained by the density evolution algorithm are shown in Table.1, which also lists the thresholds of the (3,6,30) ASC-LDPC code and the (3, 6, 30) SC-LDPC code for comparisons.The gap in Table 1 represents the difference between the Shannon limiteSLand the thresholdeBP.

Code ensembles eSL eBP gap(3,6,3,6,30)2D-SC-LDPC code 68 59 9(3,6,30)ASC-LDPC code 34 7 27(3,6,30)SC-LDPC code 32 3 29

From Table 1, it can be observed that the gap to the Shannon limit of the 2D-SC-LDPC code is much smaller than the ASC-LDPC code and SC-LDPC code with the same coupling length and degree distributions.The ASC-LDPC code benefiting from its asymmetric structure is slightly better than the conventional SC-LDPC code.The results show that the proposed 2D-SCLDPC codes are more robust against burst erasures than ASC-LDPC codes and SC-LDPC codes.

To investigate it more thoroughly, the thresholds for different 2D-SC-LDPC code ensembles with different degree distributions are also compared.The (4, 8, 4,8,30) 2D-SC-LDPC code and the (5,10,5,10,30)2D-SC-LDPC are taken into consideration.Their threshold analysis results are shown in Table 2 and Table 3 respectively.

Code ensembles eSL eBP gap(4,8,4,8,30)2D-SC-LDPC code 72 59 13(4,8,30)ASC-LDPC code 36 9 27(4,8,30)SC-LDPC code 33 3 30

Code ensembles eSL eBP gap(5,10,5,10,30)2D-SC-LDPC code 76 59 17(5,10,30)ASC-LDPC code 38 11 27(5,10,30)SC-LDPC code 34 3 31

From Table 2 and Table 3, it can be seen that the thresholds of the proposed 2D-SC-LDPC codes are much better than the ASC-LDPC codes and SC-LDPC codes.Moreover, the maximum correctable burst erasure lengths are almost the same for different 2D-SCLDPC codes with different degree distributions, which indicates that the 2D-SC-LDPC codes with low degrees are good enough for combating burst erasures.

The 2D-SC-LDPC code proposed in this paper has stronger robustness in the face of burst erasures than ASC-LDPC codes and SC-LDPC codes, and its superior performance is due to two reasons.First, the ASCLDPC coupling chain is used in each dimension during the construction of the 2D-SC-LDPC code, because the base matrices of the ASC-LDPC codes possess larger minimal cardinality of stopping sets, which is beneficial for improving the error correction capability of burst erasures and making it more robust to burst erasures than the conventional SC-LDPC code.The 2DSC-LDPC code constructed with the asymmetric structure is more robust in the face of burst erasures.Second, it benefits from the two-dimensional construction method, which is a parallel connection of two ASC-LDPC coupling chains by means of edge exchanges.When faced with a burst erasure, the two coupling chains can provide information support to each other and avoid the situation that the decoding terminates when one of the coupling chains undergoes a burst erasure and thus enhances the ability to combat burst erasures.At the same time, it does not change the degree distribution of each coupling chain itself and also does not increase the decoding complexity.

3.2 Finite length performances

To confirm the asymptotic performances obtained by density evolution, the finite-length performances of the 2D-SC-LDPC codes over the burst erasure channels are simulated.First the proposed (3,6,3,6,30, 50) 2DSC-LDPC code is compared with the (3, 6, 30, 50)ASC-LDPC code and (3,6,30,50) SC-LDPC code.The code lengths of these three codes are 6000, 3000, 3000 and the design rates are 0.4333, 0.4333, 0.4667.The code lengths are computed by the denominators of Eq.(7), Eq.(5)and Eq.(3) respectively.The design rates are obtained by Eq.(7), Eq.(5) and Eq.(3) respectively.To further investigate the performance for resistance to the burst erasures,the SC-GLDPC codes is also considered for comparison.SC-GLDPC codes combat the burst erasures by introducing the linear block codes with error-correcting capabilities to replace the traditional single parity codes without error-correcting capabilities.Specifically,consider a (2, 7,L,M) SC-GLDPC code with choosing the (7, 4) Hamming code as the component code.Assume the coupling lengthL=30 and the lifting factorM=30 and then the code length is 6300.The finite-length performance of the 2D-SC-LDPC code transmitted over the burst erasure channels is shown in Fig.4,along with the simulation results of the SC-GLDPC code,ASC-LDPC code and the SC-LDPC code.

Fig.4 Finite-length comparisons between the (3,6,3,6,30,50) 2D-SC-LDPC code, the (2,7,30,30)SC-GLDPC code, the (3,6,30,50) ASC-LDPC code and the (3,6,30,50) SC-LDPC code over the burst erasure channels

From Fig.4, it can be observed that the starting points corresponding to the waterfall region of the 2DSC-LDPC code, ASC-LDPC code and SC-LDPC code are about 2944,346 and 145 respectively.Since the iterative decoding threshold is well known that it corresponds to the starting point of the waterfall region in the BER curve, the starting points of the waterfall region can be estimated by the thresholdeBPmultiplying the lifting factorM, that iseBP×M.Therefore, according to the threshold results shown in Table 1,the estimated starting points can be obtained and they are 2950,350 and 150 respectively.The comparison results indicate that the finite-length simulation results are roughly consistent with the threshold analysis results.As for the simulation results, it can be seen that although the codelength of the 2D-SC-LDPC code is twice as long as the ASC-LDPC code and the SC-LDPC code,the maximum correctable burst erasure length of the proposed 2D-SC-LDPC code is approximately eight times larger than ASC-LDPC code and twenty times larger than SCLDPC code, which indicates that the capability of correcting burst erasures can be improved dramatically by the proposed code structure.One possible reason is that the edge exchange is introduced in constructing the 2DSC-LDPC code, which can provide the information support to each other when either of them faces with the burst erasures.Besides, each dimension adopts the asymptotic structure in the construction of 2D-SC-LDPC code.Since the base matrices of the ASC-LDPC code possess larger minimal cardinality of stopping sets, it is beneficial for improving the error correction capability of burst erasures.Moreover, the performances of the proposed 2D-SC-LDPC codes for combating the burst erasures are much better than the SCGLDPC codes in the case of a comparable code lengths as shown in Fig.4.

In the following, the finite-length performances of the (4, 8, 4, 8, 30, 100) 2D- SC-LDPC code and the (5,10,5,10,30,100) 2D-SC- LDPC code are also simulated.The comparison results of the proposed 2D-SC-LDPC codes with the ASC-LDPC codes and SCLDPC codes are shown in Fig.5 and Fig.6.

From Fig.5, it can be observed that the starting points corresponding to the waterfall region of these three codes are 5898,897,295 and the predicted ones are 5900,900,300,which shows that the finite-length performances for resistance to burst erasures can fit well with the asymptotic performances obtained by density evolution.As for the (5, 10, 5, 10, 30, 100)2D-SC-LDPC code, similar results can be concluded,where the starting points corresponding to the waterfall region of these three codes are 5890,1094,and 296 in simulations while the estimated ones are 5900, 1100 and 300.From the above simulation results, it can be observed that the proposed 2D-SC- LDPC codes perform better than the ASC-LDPC codes and the SC-LDPC codes for combating burst erasures either in the asymptotic performances or the finite-length performances.

4 Conclusion

In this paper, a 2D-SC-LDPC codes to combat the burst erasures is proposed.To evaluate the performances against burst erasures, the density evolution algorithm for 2D-SC-LDPC codes over the burst erasure channels is proposed to compute the maximum correctable burst erasure length.Density evolution analysis shows when transmitted over the burst erasure channel,the proposed 2D-SC-LDPC codes are more robust against burst erasures than the ASC-LDPC codes and SC-LDPC codes.Moreover, the finite-length performances of the proposed 2D-SC-LDPC codes along with the ASC-LDPC codes and SC-LDPC codes over the burst erasure channels are also simulated to confirm the asymptotic performances obtained by density evolution.Simulation results show that the finite-length performances of the proposed 2D-SC-LDPC codes are consistent with the asymptotic performances and they perform much better than ASC-LDPC codes and SC-LDPC codes.