Ferdaouss Mattoussi

Valentin Savin
email: valentin.savin@cea.fr

Vincent Roca
email: vincent.roca@inria.fr

Bessem Sayadi
email: bessem.sayadi@alcatel-lucent.com

Optimization with EXIT Functions of GLDPC-Staircase Codes for the BEC

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Generalized LDPC (GLDPC) codes [START_REF] Tanner | A recursive approach to low complexity codes[END_REF], invented by Tanner, are an extension of LDPC codes where the Single Parity Check (SPC) nodes are replaced with linear block codes, referred to as component codes. An advantage of GLDPC codes is that more powerful component codes can be employed (instead of SPC codes), therefore yielding better erasure recovery performance. Many researches have been carried out in order to improve GLDPC performance [START_REF] Yue | Generalized low-density parity-check codes based on Hadamard constraints[END_REF][3] [4] [START_REF] Wang | Exit chart analysis for doubly generalized ldpc codes[END_REF] [START_REF] Paolini | Analysis of doublygeneralized LDPC codes with random component codes for the binary erasure channel[END_REF]. The EXtrinsic Information Transfer (EXIT) functions method, introduced by Ten Brink [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF] [START_REF] Ashikhmin | Extrinsic information transfer functions: model and erasure channel properties[END_REF], turned out to be a powerful tool. This method first appeared as a handy way to visualize the ITerative (IT) decoding process of LDPC codes, using EXIT curves, to easily identify the bottlenecks in the decoding process. Then the method has been used to design codes with improved performance and has been applied to GLDPC codes in [START_REF] Ashikhmin | Extrinsic information transfer functions: model and erasure channel properties[END_REF] and in [START_REF] Paolini | Analysis of doublygeneralized LDPC codes with random component codes for the binary erasure channel[END_REF].

Our work relies on the GLDPC-Staircase codes [START_REF] Cunche | Lowrate coding using incremental redundancy for GLDPC codes[END_REF], a class of small rate GLDPC codes (i.e. that can efficiently produce a large number of repair symbols, on demand) with interesting erasure recovery performance under IT decoding. This performance is achieved thanks to the use of the Density Evolution (DE) method [START_REF] Richardson | The capacity of low-density paritycheck codes under message-passing decoding[END_REF] that enabled an optimization of the distribution of repair symbols produced by the component codes. These codes are the core of the present work, but the decoding scheme is extended: to the initial IT plus Reed-Solomon This work is supported by the ANR-09-VERS-019-02 grant (ARSSO project) and by the Inria -Alcatel Lucent Bell Labs joint laboratory.

(RS) scheme of [START_REF] Cunche | Lowrate coding using incremental redundancy for GLDPC codes[END_REF], we add a Maximum Likelihood (ML) decoding scheme to further improve the code performance (the reasons why this is a good practical solution are detailed in Section 2.2). This extension, called hybrid decoding, results in exceptional performance gains (see Section 2.3).

The contributions of our work are twofold. First of all we derive DE equations and EXIT functions for the proposed GLDPC-Staircase codes. We follow the ideas from [11][12], where a relationship between IT and ML decoding of LDPC codes over the BEC is established, based EXIT functions and the area theorem. In our work we extend this approach to our GLDPC-Staircase codes with a hybrid decoding.

Secondly we use the EXIT method to tune an internal parameter of our codes. More precisely we explain (Section 2) that a given GLDPC-Staircase code rate (i.e. as seen by the user) can be achieved in different ways, for instance by adding a large number E of extra-repair symbols produced by RS encoding and a small number of repair symbols produced by LDPC-Staircase encoding, or vice versa. Therefore we apply the EXIT method and show that increasing the number E up to a value of 2 or 3 enables to approach the channel capacity very closely.

This paper is organized as follows. We detail GLDPC-Staircase codes in Section 2. Then we propose the DE equations of GLDPC-Staircase codes in Section 3. We extend the ideas of [START_REF] Méasson | An upper-bound for the ML threshold of iterative coding systems over the BEC[END_REF] to our case study and give the EXIT functions of the (IT+RS) and ML decoding in section 4. We apply this method and study the impacts of the internal parameter E in Section 5. Finally we conclude.

INTRODUCTION TO GLDPC-STAIRCASE CODES

We first introduce the GLDPC-Staircase code design, their hybrid decoding, and give a few results showing their excellent performance and flexibility.

GLDPC-Staircase code construction

GLDPC-Staircase (N G , K) codes [START_REF] Cunche | Lowrate coding using incremental redundancy for GLDPC codes[END_REF] [14] can be represented by a Tanner graph (Fig. 1) with the following meaning:

• each check node corresponds to a RS code based on Hankel matrices, a specific construction of RS codes that has the interesting property that the first repair symbol is also equal to the XOR sum of the source symbols.

This symbol can therefore be encoded either by means of an LDPC-Staircase encoding (faster) or RS encoding. This property does no hold for the other repair symbols, called extra repair symbols;

• the variable nodes are broken into three categories: For the reasons detailed in [START_REF] Mattoussi | Design of small rate, close to ideal, GLDPC-Staircase codes for the erasure channel[END_REF] (i.e. improved performance under ML decoding compared to an irregular distribution), we assume that all the check nodes have the same number, E, of extra-repair symbols. So for a fixed GLDPC code rate, r G , the code rate of the LDPC-Staircase base code is given by:

r L = r G (1 + E) 1 + r G E (1)
Let N L and K be the LDPC-Staircase code length and dimension, and N G be the length of the GLDPC-Staircase code (which is also of dimension K).

Then N G = N L + n extra ,
where n extra is the total number of extra-repair RS symbols. Let H L be the binary parity-check matrix of the LDPC-Staircase code, of size M L = N L -K rows and N L columns. H L has the form (H 1 |H 2 ). H 1 is the M L × K left-hand side part (information part) and each column is of degree N 1 (number of "1s" per column). H 2 is the M L × M L right-hand side part (redundancy part) and features a staircase (i.e. double diagonal) structure. H 1 is created in a fully regular way, in order to have constant column and row degrees. More precisely, each column of H 1 is of degree N 1 (number of "1s" per column), which is an input parameter during the LDPC-Staircase code creation [START_REF] Roca | Low density parity check (LDPC)-staircase and triangle forward error correction (FEC) schemes[END_REF]. Each row m of H 1 is of degree

N1 1 r L -1
, and because of the staircase structure of H 2 , depending on whether m = 1 or m > 1, a row m of H L is of degree:

d 1 = N 1 1 r L -1 + 1 and d m>1 = N 1 1 r L -1 + 2 (2)
The E extra-repair symbols associated to the m th row of H L are generated by RS(n m , k m ) encoding over GF (2 8 ).

Here n m and k m are respectively the RS code length and dimension, and they are related to the other parameters of row m as follows. For row m > 1, the various source symbols (i.e. from the user point of view) that are involved in this row plus the previous repair symbol are considered as source symbols from the RS point of view. The new LDPC-Staircase repair symbol for this row plus the E extra-repair symbols are considered as repair symbols from the RS point of view. For the first row the only difference is the fact there is no previous repair symbol (it's the beginning of the staircase). So:

n m = k m + 1 + E (3)
with k m = d m -1 (no matter the row).

GLDPC-Staircase decoding

One approach consists in using an ML decoding over the full system, with operations over GF (2 8 ), which enables to achieve the best possible erasure recovery capabilities. However, it does not take into account the complexity reduction gains made possible by GLDPC-Staircase specificities. Therefore we chose a different strategy, called hybrid decoding, that consists of a joint use of four decoders:

• IT decoder over the binary LDPC-Staircase system: extra-repair symbols are ignored at this step. This solution features a linear complexity with sub-optimal erasure recovery capabilities; • RS decoder for a given check node: this is a classic RS decoding that takes into account the three types of symbols. It has a higher complexity but is MDS; • Binary ML decoder over the LDPC-Staircase system: extra-repair symbols are once again ignored at this step.

If this solution features a quadratic complexity in terms of the number of XOR operations between symbols, it allows to reach the maximum correction capabilities when ignoring extra-repair symbols; • Non binary ML decoder: this solution also features a quadratic complexity but operations are now significantly more complex (performed on GF (2 8 )) than simply XORing two symbols. However it allows reaching the maximum correction capabilities of the code. It is equivalent to the ML decoding over the full system mentioned above, but the system on which it is applied is hopefully simplified by the previous three decoders.

Decoding succeeds if one or several of these decoders succeed and recover all the missing source symbols.

GLDPC-Staircase performance

As shown in [START_REF] Mattoussi | Design of small rate, close to ideal, GLDPC-Staircase codes for the erasure channel[END_REF], GLDPC-Staircase codes exhibit excellent performances under hybrid decoding over the BEC, both for large and very small objects, and both in terms of average performance and low error floor. For instance, with a source block of size K = 1 000 symbols (resp. K = 32 symbols), a code rate r G = 1/2, an overhead of 5 symbols (resp. 3 symbols) (i.e. after receiving 1 005 symbols (resp. 35 symbols) chosen randomly in the set of N G symbols) is sufficient to have a decoding failure probability below 10 -4 . 1 Several additional benefits are detailed in [START_REF] Mattoussi | Design of small rate, close to ideal, GLDPC-Staircase codes for the erasure channel[END_REF], like their small rate feature (a large number of repair symbols can be produced, in an incremental way, on demand, while keeping excellent performances) and their major flexibility (the GLDPC-Staircase behavior can be tuned to look more like MDS codes or LDPC-Staircase codes). It makes it possible to adapt to the exact use-case and channel conditions (e.g. when used in fountain like applications, e.g. within a FLUTE carousel [START_REF] Paila | FLUTE -File Delivery over Unidirectional Transport[END_REF], over wireless networks).

DENSITY EVOLUTION (DE) EQUATIONS

Preliminaries

In the sequel, we denote by dv and dc the maximum variable and check node degrees in the bipartite (Tanner) graph associated with the LDPC-Staircase code. Following [START_REF] Richardson | The capacity of low-density paritycheck codes under message-passing decoding[END_REF], we define the edge-perspective Degree Distribution (DD) polynomials by λ(x) = Given a GLDPC-Staircase code, DD polynomials λ and ρ are defined by the underlying LDPC-Staircase code, defined by the bottom graph of Figure 1 (that is, not containing the extra-repair nodes). We denote by E(λ, ρ, E) the ensemble of GLDPC-Staircase with edge-perspective DD polynomials λ and ρ, and with E extra-repair symbols per check-node.

Assume that an arbitrary code from E(λ, ρ, E), of length N G , is used over the BEC, and let ε denote the channel erasure probability. The probability threshold of the ensemble E(λ, ρ, E) is defined as the supremum value of ε (that is, the worst channel condition) that allows transmission with an arbitrary small error probability, assuming that N G goes to infinity. The threshold value of a given ensemble of codes can be efficiently computed by using the Density Evolution (DE) method [START_REF] Richardson | The capacity of low-density paritycheck codes under message-passing decoding[END_REF], which recursively computes the fraction of erased messages passed during the belief propagation decoding. Density evolution equations are derived in the next section, by using the methodology introduced in [START_REF] Cunche | Lowrate coding using incremental redundancy for GLDPC codes[END_REF]. 1 In these tests the LDPC-Staircase code rate is set to r L = 2/3 and N 1 = 5. Clearly, with K = 32 symbols, an option is to set r L = 1 so that only extra-repair symbols are used, which means that GLDPC-Staircase codes are turned into MDS codes.

DE equations for GLDPC-Staircase codes

In this section we derive the DE equation for the ensemble E(λ, ρ, E) of GLDPC-Staircase codes. In the sequel, the degree of a check or variable (source or repair) node will always refer to its degree in the underlying LDPC-Staircase code. We are interested in the erasure probability of messages exchanges by the IT+RS decoding along the messages of the LDPC-Staircase code. We denote by P ℓ , the probability of a LDPC symbol (source or repair) node sending an erasure at iteration ℓ. Similarly, Q ℓ denotes the probability of a check node sending an erasure (to an LDPC symbol-node) at iteration ℓ. Clearly, P 0 is equal to the channel erasure probability ε. In order to derive a recursive relation between P ℓ and P ℓ+1 , we proceed as follows.

Consider a constraint node c connected to symbol-nodes (v 1 , . . . , v d , e 1 , . . . , e E ) where v i denotes an LDPC (source or repair) symbol node and e i denotes an extra-repair node. Since c corresponds to an RS code, it can recover the value of an LDPC symbol node, say v 1 , if and only if the number of erasures among the other symbol-nodes (v 2 , . . . , e E ) is less than or equal to E. Now, at iteration ℓ, the LDPC symbols are erased with probability P ℓ , while extra repair symbols are always erased with probability ε, the channel erasure probability. It follows that the probability of a check node of degree d recovering the value of an LDPC symbol at iteration ℓ + 1, denoted by Qℓ+1 (d), is given by:

Qℓ+1 (d) = 0≤i<d,0≤j≤E i+j≤E d-1 i P i ℓ (1 -P ℓ ) d-1-i E j ε j (1 -ε) E-j (4)
Averaging over all possible values of d, we get:

Q ℓ+1 = 1 - dc d=1 ρ d Qℓ+1 (d) (5)
Conversely, an LDPC symbol node v of degree d, connected to check nodes c 1 , . . . , c d , sends an erasure to the check node c 1 iff it was erased by the channel, and it received erased messages from all check nodes c 2 , . . . , c d . Since this happens with probability ε

• Q d-1
ℓ+1 , and averaging over all possible degrees d, we get:

P ℓ+1 = ε dv d=1 λ d Q d-1 ℓ+1 = ελ(Q ℓ+1 ) (6)
Using equations ( 4), ( 5), ( 6) we can determine a recursive relation between P ℓ and P ℓ+1 , with P 0 = ε. The decoder can recover from a fraction of ε erased symbols iff lim ℓ→+∞ P l = 0.

Therefore, the threshold probability can be computed by:

ǫ (IT+RS) (λ, ρ, E) = max{P 0 | lim ℓ→+∞ P l = 0} (7)
When no confusion is possible, the above threshold value will be simply denoted by ǫ (IT+RS) .

EXIT FUNCTIONS AND ML THRESHOLD UPPER BOUND

EXtrinsic Information Transfer (EXIT) curves were first introduced in [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF] as a technique to analyse the convergence of iterative decoding process of parallel concatenated component codes. For binary LDPC codes, a slightly different definition of the EXIT curve has been introduced in [START_REF] Méasson | Maxwell's construction: The hidden bridge between maximum-likelihood and iterative decoding[END_REF], where the EXIT curve is associated with the sparse graph system rather than with component codes). Roughly speaking, the EXIT curve gives the fraction of erased bits "contained" in the extrinsic information produced by the decoding algorithm, assuming that the code length tends to infinity. The EXIT curve can be defined for any decoding algorithm (e.g. IT or ML decoding), and it relates to the asymptotical performance of an ensemble of codes under the considered decoding. Obviously, in case of IT decoding, there a tight relation between the EXIT curve and the density evolution equations derived in the previous section. This relation will be discussed for GLDPC-Staircase codes under (IT+RS) decoding in Section 4.1. For the ML decoding, it has been shown in [START_REF] Méasson | Maxwell's construction: The hidden bridge between maximum-likelihood and iterative decoding[END_REF] that the area under the EXIT curve is always equal to the asymptotic rate of the ensemble. This allows deriving an upper bound of the ML threshold, which is conjunctured to be tight in a quite general settings, especially for codes defined by almost regular graphs. We extend this technique to our GLDPC-Staircase codes in Section 4.2

EXIT curve for the (IT+RS) decoding

The EXIT curve defined in this section relates to the asymptotical performance of the ensemble E(λ, ρ, E) under the (IT+RS) decoding. Precisely, we start with a fixed number of decoding iterations, say ℓ, and let the code length tend to infinity. Within this limit, we denote by p(ε) the probability of the extrinsic information 2 of a random LDPC symbolnode being erased. Using the DE equations from Section 3.2, we obtain p(ε)

= dv d=1 L d Q d ℓ = L(Q ℓ )
, where L is the node-perspective DD polynomial of LDPC symbol-nodes. The EXIT curve of the (IT+RS) decoding is defined as the limit of the above probability when the number of iterations goes to infinity, that is,

h (IT+RS) (ε) = lim ℓ→+∞ L(Q ℓ ). Since L
is a finite-degree polynomial, we can also write:

h (IT+RS) (ε) = L(Q +∞ ), (8)
where

Q +∞ = lim ℓ→+∞ Q ℓ .
As a consequence, the probability threshold and the EXIT-curve satisfy the following equality:

ǫ (IT+RS) = sup{ε ∈ [0, 1] | h (IT+RS) (ε) = 0} (9)
An example of EXIT function under the (IT+RS) decoding, for an ensemble of GLDPC codes, will be discussed in the next section. 2 The information we get by tacking into account the messages from the neighbor check-nodes, but not the channel output

EXIT curve for the ML decoding

As for the (IT+RS) decoding, the EXIT curve of the ML decoding is also defined in terms of extrinsic erasure probability. Precisely, in the limit of infinite code length, for a given channel erasure probability ε, h ML (ε) is the probability of a symbol node being erased after ML decoding, assuming that the received value (if any) of this particular symbol has not been submitted to the decoder. The ML probability threshold is given by:

ǫ ML = sup{ε ∈ [0, 1] | h ML (ε) = 0} (10)
The exact computation of the EXIT function for the ML decoding is a difficult task. However, using the area theorem3 [START_REF] Méasson | Maxwell's construction: The hidden bridge between maximum-likelihood and iterative decoding[END_REF], we get

1 ǫ ML h ML (ε) dε = r G
, where r G is the designed coding rate of the given ensemble of GLDPC codes. Moreover, since the (IT+RS) decoding is suboptimal with respect to the ML decoding, we have h (IT+RS) (ε) ≥ h ML (ε). Hence, if for some ǭML

1 ǭML h (IT+RS) (ε) dε = r G , (11)
we necessarily have ǭML ≥ ǫ ML . This gives an upper bound on the ML-threshold, which is known to be tight in the binary case. Fig. 2 shows the EXIT curve, under (IT+RS) decoding, for the ensemble of GLDPC codes with node-perspective DD polynomials L(x) = 0.4x 2 +0.6x 5 and R(x) = x 10 , and with E = 2 extra repair symbols per check-node. We note that the LDPC code is of rate r L = 3/5, with all source symbolnodes of degree 5 and all repair symbol-nodes of degree 2. The coding rate of the GLDPC code is given by r G = 1/3. The (IT+RS) threshold value is ǫ (IT+RS) = 0.5376. It can be seen that h (IT+RS) (ε) = 0 for values ε < ǫ (IT+RS) , then for ε = ǫ (IT+RS) it jumps to a non-zero value and increases until it reaches a value of 1 for ε = 1. The ML-threshold upperbound is the unique point ǭML ∈ [ǫ (IT+RS) , 1] such that the hatched area below the (IT+RS)-EXIT curve, delimited by ε = ǭML at the left and by ε = 1 at the right, is equal to the GLDPC rate r G = 1/3. In this case, we obtain ǭML = 0.6664.

APPLICATION: CHOOSING A VALUE FOR E

Let us consider a GLDPC-Staircase code of rate r G . Several values of E, or equivalently of the internal LDPC-Staircase code rate r L , enable to achieve this global code rate (see Eq. 1). However choosing a value impacts the performance achieved. Therefore we now apply the techniques developed in section 4 to adjust E, by computing the upper bound on the ML threshold for several values of E. These results are 1 and compared to the capacity limit (δ sh ). We notice that increasing E (or equivalently increasing the LDPC code rate) quickly increases the upper bound on the ML threshold, until it reaches a stable value very close to the Shannon limit δ sh . Depending on r G this stable value is obtained with E = 1, 2 or 3. Therefore, a small number of extra-repair RS-symbols per check-node is sufficient to get extremely close to the channel capacity.

Let us now compare these theoretical results with practical results, obtained by simulations with a software GLDPC-Staircase codec that we designed. We see in Fig. 3 that the average erasure recovery performance (measured here in terms of inefficiency, i.e. the ratio between the number of symbols needed for decoding to succeed and k) quickly approaches 1 (i.e. no overhead, decoding is possible with exactly k symbols) as E = 3, even for very small code dimension.

CONCLUSIONS

In this paper we have analyzed the asymptotic behavior of GLDPC-Staircase codes for the BEC, through the DE and EXIT functions methods. More specifically, after explaining how these techniques apply to our use-case, we used them to tune an internal parameter of the code. Our results indicate that increasing the number E of extra repair symbols quickly increases the upper bound on the ML thresholds until it reaches a stable value very close to the Shannon limit. In practice choosing E = 2 or 3 yield performance that approach those of an ideal, MDS code, even for very small code dimensions.

( 1 )!Fig. 1 .

 11 Fig. 1. GLDPC-Staircase (13, 4) code with E = 2.

dv d=1 λ d x d- 1

 1 and ρ(x) = dc d=1 ρ d x d-1 , where λ d (resp. ρ d ) represents the fraction of edges connected to variable-nodes (resp. check-nodes) of degree d. From a node perspective, the DD polynomials are given by L(x) = dv d=1 L d x d and R(x) = dc d=1 R d x d where L d (resp. R d ) represents the fraction of variable-nodes (resp. check-nodes) of degree d.

Fig. 3 .

 3 Fig. 3. Finite length analysis of the impacts of E.

Table 1 .

 1 ǭML of GLDPC codes as a function of rG

			(IT+RS) EXIT Function of GLDPC codes with rate r G	= 1/3
		1
		0.9
		0.8
		0.7
	h (IT+RS) (ε)	0.4 0.5 0.6			r L = 0.6
		0.3
		0.2
		0.1				ε (IT+RS) =		ε ML =
						0.5376		0.6664
		0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
					ε (channel erasure probability)
	Fig. 2. Example of EXIT function, (IT+RS) threshold value, and
	ML threshold upper bound for an ensemble of GLDPC codes
	r G		E = 0	E= 1		E= 2		E= 3	E= 4		E=5	δ sh
	1/3.5		0.7054	0.7124		0.7138	0.7141	0.7142		0.7142	0.7142
	1/3		0.6634	0.6652		0.6664	0.6665	0.6666		0.6666	0.6667
	1/2		0.4946	0.4993		0.4999	0.4999	0.4999		0.4999	0.5000
	2/3		0.3301	0.3330		0.3333	0.3333	0.3333		0.3333	0.3333
	3/4		0.2484	0.2498		0.2499	0.2499	0.2499		0.2499	0.2500
	9/10		0.0991	0.0999		0.0999	0.0999	0.0999		0.0999	0.1000
	summarized in Table

Note that the area theorem applies for the MAP decoding, but over the BEC, MAP and ML decoding are equivalent.