{'fraction_non_alphanumeric': 0.037998146431881374, 'fraction_numerical': 0.007345621803453129, 'mean_word_length': 4.422296668527824, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Scheduled-PEG construction of LDPC codes for Upper-Layer FEC

The Progressive Edge Growth (PEG) algorithm is one of the most widely-used method for constructing finite length LDPC codes. In this paper we consider the PEG algorithm together with a scheduling distribution, which specifies the order in which edges are established in the graph. The goal is to find a scheduling distribution that yields"the best"performance in terms of decoding overhead, performance metric specific to erasure codes and widely used for upper-layer forward error correction (UL-FEC). We rigorously formulate this optimization problem, and we show that it can be addressed by using genetic optimization algorithms. We also exhibit PEG codes with optimized scheduling distribution, whose decoding overhead is less than half of the decoding overhead of their classical-PEG counterparts.


I. INTRODUCTION
Data loss recovery -for instance, for content distribution applications or for distributed storage systems -is widely addressed using erasure codes that operate at the transport or the application layer of the communication system. These codes, referred to as upper-layer (UL) codes, extend source data packets with repair (redundant) packets, which are used to recover the lost data at the receiver. They are generally proposed in conjunction with physical layer codes, in order to maximize the reliability of the transmission system, especially in case of intermittent connectivity or deep fading of the signal for short periods. In such situations, the physical layer FEC fails and we can either ask for retransmission (only if a return channel exists, and penalizing in broadcast/multicast scenarios) or use UL-FEC. Hence, the use of UL-FEC codes is of critical importance in broadcast communication systems in general, and satellite communications in particular.
Low Density Parity Check (LDPC) codes constitute a very broad class of FEC codes, distinguished by the fact that they are defined by sparse parity-check matrices, and can be iteratively decoded in linear time with respect to their blocklength. Invented by Gallager in early 60's [1], but considered impractical to implement, these codes have been neglected for more that three decades, and "rediscovered" in the late 90's [2]. Nowadays, a large body of knowledge has been acquired (analysis, optimization, construction); LDPC codes are known to be capacity approaching codes for a large class of channels [3], and became synonymous with modern coding. However, this capacity approaching property holds in the asymptotic limit of the code length, and codes optimized from this asymptotic perspective may suffer significant performance degradation at practical lengths. Actually, the asymptotic optimization, performed by using density-evolution methods [4], yields an irregularity profile, which specifies the distribution of node-degrees in the bipartite (Tanner) graph [5] associated with the code. It is assumed that the girth 1 of the bipartite graph goes to infinity with the code-length. Hence, optimized irregularity profiles can be used to construct codes that are "long enough" (at least few thousand bits) to avoid short cycles, although they must be "short enough" to be practical.
One of the most widely-used method for constructing finite length codes is the Progressive Edge Growth (PEG) algorithm [6]. It constructs bipartite graphs with large girth, by establishing edges progressively: the graph grows in an edge-by-edge manner, optimizing each local girth. There is an underlying edge order within the PEG, corresponding to the order in which edges are established in the graph. In general, edges are progressively established starting with those incident to symbol-nodes of degree-2 and ending with those incident to symbol-nodes of maximum degree. However, any other order with respect to the symbol-node degrees would also be possible. Besides, for a given symbol-node degree, edges can be established in a node-by-node manner (all edges incident to some symbol node are established before moving to the next symbol-node), or in a degree-by-degree manner (a first edge is established for each symbol-node, then a second edge is established for each symbol-node, and so on until all the symbol-nodes reach the given degree). Although this order may significantly impact the performance of the constructed code, it is rather difficult to formalize and has practically not been investigated in the literature. There are however several papers that aim to enhance the PEG construction by optimizing some objective function, as for instance minimizing the number of cycles created [7], or minimizing the approximate cycle extrinsic (ACE) message degree [8], [9].
In this paper we consider the PEG algorithm together with a scheduling distribution, which will be referred to as scheduled-PEG, or SPEG for short. Within the SPEG algorithm, symbolnodes are divided into subsets, each subset containing symbolnodes of same degree. Edges incident to the symbol-nodes of a subset are established in a degree-by-degree manner, before moving to the next subset. The scheduling distribution speci-fies the fraction of nodes within each subset. Our purpose is to find a scheduling distribution that yields the best performance in terms of decoding overhead (performance metric widely used for UL-FEC). We rigorously formulate this optimization problem, and we show that it can be addressed by using genetic optimization algorithms.
The paper is organized as follows. Section II gives a brief overview of the basic theory and definitions related to LDPC codes, their iterative decoding, and the associated performance metrics over the BEC. The construction of finite length LDPC codes is addressed in Section III. The proposed Scheduled-PEG algorithm is also introduced in this section. Section IV focuses on the optimization of the Scheduled PEG algorithm and presents simulation results. Finally, Section V concludes the paper.

A. Binary and non-binary LDPC codes
In this paper we consider both binary and non-binary LDPC codes defined over some finite field F q , with q = 2 p [10]. If p = 1, the code is binary. We fix, once for all, a vector space isomorphism: Elements of F q will be called symbols. We say that the binary sequence (x 0 , .., x p−1 ) ∈ F p 2 is the binary image of the symbol X ∈ F q , iff they correspond to each other by the above isomorphism.
An LDPC code is a linear code defined by a sparse parity-check matrix H ∈ M m,n (F q ). Alternatively, it can be represented by a bipartite (Tanner) graph 2 [5], containing n symbol-nodes and m constraint-nodes associated respectively with the n columns and m rows of H. A symbol-node and a constraint-node are connected by an edge if and only if the corresponding entry of H is non-zero, in which case the edge is assumed to be "labeled" by the non-zero entry.
Symbol-nodes take values in F q , and a constraint-node is said to be verified if the linear combination of neighbor symbols (with coefficients given by the corresponding edge labels) is equal to zero. A non-binary word (X 1 , . . . , X n ) is a codeword if it verifies all the constraint nodes of the graph.
The degree of a node is by definition the number of edges incident to that node (number of non-zero entries on the corresponding row/column of H). A code is called (d s , d c )regular if all symbol-nodes are of degree d s and all constraintnodes are of degree d c ; otherwise it is called irregular.
Let Λ d and Γ d denote respectively the fractions of symbol and constraint nodes of degree-d. Let also λ d and ρ d be the fractions of edges connected respectively to symbol and constraint nodes of degree-d. The degree distribution polynomials, from the node and the edge perspective, are defined by: The designed code rate, denoted by r, is by definition: If the parity-check matrix is of rank m, then the (non-binary) code dimension is equal to k = n − m, and r is equal to the code rate, that is r = k n . We also denote by K and N the binary code dimension and the binary code length, respectively. Hence, K = kp and N = np.

B. Iterative erasure decoding
For binary LDPC codes over the BEC, the beliefpropagation (BP) decoding translates into a simple technique of recovering the erased bits, by iteratively searching for check-nodes with only one erased neighbor bit-node [11]. Indeed, if a check-node is connected to only one erased bitnode, the value of the latter can be recovered as the XOR of all the other neighbor bit-nodes. This value is then injected into the decoder, and the decoding continues by searching for some other check-node having a single erased neighbor bit-node. We remark that the erasure decoding can be performed on-the-fly: decoding starts as soon as the first bit is received and each new received bit is injected on-the-fly into the decoder. The decoding will stop by itself if all the bits have been recovered, or when it "gets stuck" because any check-node is connected to at least two erased bit-nodes (such a configuration is called a stopping set).
The above considerations can also be generalized in the case of non-binary codes. It is important to note that we consider non-binary LDPC codes over a binary erasure channel, which means that the channel erases bits from the binary image of the transmitted codeword. Hence, a coded symbol can be completely erased (all the bits of its binary image are erased), completely received (no bit of its binary image is erased), or partially erased/received (some bits of its binary image are erased, some others are received). At the receiver part, the received bits are used to (partially) reconstruct the corresponding symbols of the transmitted codeword. Thus, for each symbol node we can determine the set of eligible symbols, i.e. symbols whose binary images match the received bits. Such a set contains only one symbol (namely the transmitted one) if the corresponding symbol-node is completely received. These sets are then iteratively updated, according to the linear constraints between symbol-nodes [12]. Alternatively, nonbinary LDPC codes can be decoded by using their extended binary image [13].

C. Performance metrics for finite-length codes
A performance metric that is often associated with on-thefly decoding is the decoding inefficiency, defined as the ratio between the number of received bits when decoding completes and the number of information bits [14]. More precisely, we assume that the encoded bit-stream is permuted according to some random permutation π. The permuted bit-stream is sequentially delivered to the decoder, which performs erasure decoding on-the-fly 3 : each bit is injected into the decoder in the appropriate position and erasure decoding is performed until either decoding completes or it gets stuck. If decoding gets stuck, we inject the next bit from the permuted bit-stream. We denote by k π the number of bits from the permuted bitstream that have been injected into the decoder when the erasure decoding completes; the value k π − k is referred to as reception overhead. The decoding inefficiency is defined as µ(π) = kπ k . It is a random variable, whose value depends on the (random) permutation π. Note also that µ(π) ∈ 1, 1 r , where r is the code rate. The average decoding inefficiency is defined as the expected value of µ; that is: Note thatμ = 1 if and only if the code is MDS (its minimum distance is equal to n − k + 1). More accurate statistics about the decoding inefficiency are provided by the probability of decoding failure, defined as the complementary cumulative distribution function (CCDF) of µ: Hence, F (x) is the probability of decoding failure assuming that the number of bits received from the channel is equal to kx, or equivalently, the reception overhead is equal to k(x−1). Indeed, the kx bits received from the channel are the first kx bits of the encoded bit-stream permuted by some permutation π. Hence, a decoding failure occurs if and only if µ(π) > x. From the above definition, it also follows that: Therefore, if C 1 and C 2 are two codes such thatμ(C 1 ) <μ(C 2 ), then C 1 presents a better performance in the waterfall region of F , but this might happen at the expense of a higher error floor 4 . Finally, we note that the probability of decoding failure can also be expressed in relation with the fraction of erased bits (rather than the fraction of received bits); in this case it will be referred to as Frame Error Rate (FER). The Bit Error Rate (BER) will denote the probability of a bit being erased (after the decoding process), assuming that a certain fraction of bits have been received.

D. Asymptotic performance
Unlike the finite-length performance, the asymptotic performance does not refer to the performance of a given code, but to the performance of a given family or ensemble of codes. Such an ensemble contains arbitrary-length codes that share the same properties in terms of distributions of node-degrees in the associated bipartite graph.
Let E(λ, ρ) denote the ensemble of LDPC codes of arbitrary length n > 0, with edge perspective degree-distributions polynomials λ and ρ. When n goes to infinity, (almost) all the codes behave alike, and they exhibit a threshold phenomenon, separating the region where reliable transmission is possible from that where it is not [4]. Assume that an arbitrary code C n ∈ E(λ, ρ), of length n, is used over the BEC, and let p e denote the channel erasure probability. The threshold of the ensemble E(λ, ρ) is defined as the supremum value of p e (i.e. the worst channel condition) that allows transmission with an arbitrary small error probability, assuming that n goes to infinity. Let us denote this threshold value by p th (λ, ρ). The threshold value is necessarily less than the channel capacity, that is p th (λ, ρ) ≤ 1 − r, where r is the (asymptotic) code rate of the ensemble E(λ, ρ). Roughly speaking, this means that if an encoded sequence of length n is transmitted over the channel, it can be successfully decoded iff the fraction of erased bits is less than p e < p th (λ, ρ), with p e → p th (λ, ρ) as n → +∞. It is assumed here that the girth of the graph goes to infinity with n, which actually happens for almost all the codes in E(λ, ρ). It follows that the decoding inefficiency, which can be expressed as (1−pe)N K = 1−pe r , also goes to a threshold value: which will be referred to as inefficiency threshold.
Given an ensemble E(λ, ρ), its threshold value can be efficiently computed by tracking the fraction of erased messages passed during the belief propagation decoding. This method is called density evolution (the name is due to the fact that over more general channels, we have to track the message densities). For more details on density evolution we refer to [4] for binary codes, and [15] and [12] for nonbinary LDPC codes. The introduction of irregular codes, as well as the asymptotic optimization based on the density evolution method, made possible the construction of capacity approaching ensembles of LDPC codes [3].
III. FINITE LENGTH LDPC CODES CONSTRUCTION As discussed in the above section, the asymptotic threshold can be approached by long codes, which do not contain short cycles. Short cycles may also harm the performance of short (finite-length) codes, as they can result in short stopping sets. Hence, the PEG algorithm has been proposed, and is widely used, for constructing bipartite graphs with large girth, in a best effort sense, by progressively establishing edges between symbol and check nodes in an edge-by-edge manner [6].

A. Progressive Edge Growth algorithm
A bipartite (Tanner) graph is denoted as (S, C, E), where S = {s 1 , s 2 , ..., s n } is the set of symbol-nodes, C = {c 1 , c 2 , ..., c m } is the set of constraint nodes and E ⊆ S × C is the set of edges. An edge (c i , s j ) ∈ E corresponds to a non-zero entry h i,j of the parity check matrix H. We also denote by D S the "target sequence" of symbol-node degrees, which is assumed to be sorted in non-decreasing order: where d sj is the degree of symbol node s j .
When the PEG algorithm starts, the set of edges is empty, E = ∅. Edges will be progressively added to E, as explained shortly. Given a symbol node s j , we denote by C sj the set of constraint-nodes whose distance to s j is maximum, in the current settings; that is, given the current set of edges. The distance between two nodes is the length of the shortest path connecting them. If there is no path between s j and some constraint node c j , the distance between them is set to +∞. Hence, if E sj = ∅, the distance from s j to any constraint-node is +∞ and C sj = C, the set of all the constraint-nodes. If E sj = ∅, C sj can be determined by expanding a subgraph from symbol node s j up to the maximal depth (see [6]).
Finally, we use c i ←− C sj | min deg to denote a random constraint node c i ∈ C sj , having the lowest degree (given the current set of edges of the graph). The PEG algorithm can be summarized as follows:

Algorithm 1 Progressive Edge Growth algorithm
for j = 1 to n do for k = 1 to d sj do Determine C sj , given the current E; c i ←− C sj | min deg ; Add edge (s j , c i ) to E; end for end for We note that edges are established in a node-by-node manner, meaning that all edges incident to some symbol-node are established before moving to the next symbol-node. We have further assumed that symbol nodes are sorted in increasing order with respect to their degrees. Finally, we observe that the constraint-node degree distribution of the constructed Tanner graph is almost uniform, i.e. all constraint nodes have only one or at most two consecutive degrees [6].
Let G PEG (n, m, D s ) denote the ensemble of all Tanner graphs constructed by using the PEG algorithm. The average inefficiency ratio over all graphs in G PEG (n, m, D s ) is defined as:μ When parameters (n, m, D s ) are implied, it will be simply denoted byμ PEG . The corresponding standard deviation is denoted by σ PEG .

B. Modified Progressive Edge Growth algorithm
The PEG graphs have large girth with respect to random graphs. Consequently, PEG graphs have low error floor in comparison with random graphs. However, the error floor can be further lowered, by using a modification of the PEG algorithm, called ModPEG.
Let S d denote the set of symbol nodes of degree d, where 1 ≤ d ≤ d max and d max denotes the maximum symbol-node degree. Let n d denote number of symbol nodes within S d , hence d n d = n.
Within the ModPEG algorithm, for each S d , edges are established in a degree-by-degree manner: a first edge is established for each symbol-node, then a second edge is established for each symbol-node, and so on until all the symbol-nodes in S d reach the required degree d. When parameters (n, m, D s ) are implied, it will be simply denoted byμ ModPEG . The corresponding standard deviation is denoted by σ ModPEG .
Example III.1. We consider irregular LDPC codes of rate 1/2, defined over the F 2 , F 4 , F 8 , F 16 . The node-perspective symbol-node degree distributions and the asymptotic performance are shown in Table I (the constraint-node degree distributions are considered to be almost uniform). These codes have been optimized by using density evolution methods. The binary code can be found in [16], while non-binary codes have been optimized within this work. For each degree distribution, 100 Tanner graphs have been constructed, by both PEG and ModPEG algorithms, for codes with binary dimension K = 5000. The corresponding average inefficiency ratios are also shown in Table I. The details of these inefficiency ratios are shown in Figure 1, where it can be seen that using ≈ 20 graphs is sufficient for obtaining good estimates ofμ PEG and µ ModPEG values.
We also observe that, in all the four cases, the average inefficiency ratiosμ PEG andμ ModPEG are much larger than µ th .  Figure 1: Average inefficiency ratios of ensemble Tanner graphs constructed by using optimized Scheduled PEG algorithm in comparison with original PEG and modified PEG algorithms for K = 5000 information bits Also, the average inefficiency ratios corresponding to Mod-PEG are larger than those corresponding to the original PEG. The reason is that the ModPEG algorithm improves the error floor region but also worsens the waterfall region, as it can be seen in Figure 2: there are eight BER curves, corresponding to eight LDPC codes drawn from the corresponding PEG and ModPEG ensembles of graphs.

C. Scheduled Progressive Edge Growth algorithm
Both PEG and ModPEG algorithms construct Tanner graph with large girth and low error floor. For optimized irregular LDPC codes, however, the average inefficiency of finite length graphs is far away from the predicted (asymptotical) threshold (even for codes with K = 5000 and N = 10000 bits, cf. Example III.1).
The Scheduled Progressive Edge Growth (SPEG) algorithm, proposed in this section, aims to improve the average inefficiency of irregular LDPC codes.
We fix an integer T ≥ 1. We consider a collection of disjoint symbol-nodes subsets S (t) d ⊆ S, indexed by t ∈ {1, . . . , T } and d ∈ {1, . . . d max }, such that: d contains only symbol-nodes of degree d) We denote by n The scheduled PEG algorithm works as follows: at time t, it connects progressively symbol-nodes within the subsets S

Algorithm 3 Scheduled Progressive Edge Growth algorithm
d do Determine C sj , given the current E; c i ←− C sj | min deg ; Add edge (s j , c i ) to E; end for end for end for end for We denote by G SPEG n, m, S (t) d the ensemble of all Tanner graphs constructed by using the SPEG algorithm. The average inefficiency ratio over all graphs in G SPEG n, m, S (t) d is defined as: When parameters n, m, S (t) d are implied, it will be simply denoted byμ SPEG . The corresponding standard deviation is denoted by σ SPEG .
In the simple case of T = 1, we have S (1) d = S d , and the SPEG algorithm is equivalent to the ModPEG algorithm. On the other hand, if T = n, each subset S (t) d contains one single symbol-node, and the SPEG algorithm is equivalent to the original PEG algorithm. For a general T value, the SPEG algorithm is in between these two extreme cases. It allows to explore the ensemble of LDPC codes with fixed codelength and degree distributions and, as explained shortly, is aimed at finding codes with very small average inefficiency. As observed in Section II-C, a lower average inefficiency corresponds to better performance of the code in the waterfall region. However, generally there is a tradeoff between waterfall and error floor regions. Hence, to prevent excessive degradation in the error floor region, the edges within each S (t) d subset are established in a degree-by-degree manner. The use of the SPEG algorithm can potentially improve the average inefficiency of the constructed LDPC code, as shown in the following example.
Example III.2. We consider non-binary LDPC codes with rate 1/2, defined over F 16 , whose node-perspective degree distribution polynomials are given in Table I. The asymptotic threshold is equal to p th = 0.4945, corresponding to an asymptotic inefficiency µ th = 1.011.
We want to construct a code with binary dimension K = 5000. Hence, the Tanner graph contains n = 2500 symbolnodes and m = 1250 constraint-nodes. We use the SPEG algorithm with T = 3, such that n (t1) d = n (t2) d , for any 1 ≤ t 1 , t 2 ≤ T . This means that each S d is partitioned into three subsets S (t) d , t = 1, 2, 3, of same cardinality. As in Example III.1, we estimated the average inefficiency ratio of the ensemble G SPEG n, m, S (t) d by simulating 100 SPEG-codes. We obtainedμ SPEG = 1.0536, which has to be compared withμ PEG = 1.0706 andμ ModPEG = 1.0834 from Table I. This example shows that an appropriate choice of the subsets S (t) d may improve the average inefficiency of the constructed code. In the following section we propose a method that allows to optimize this choice, by minimizing the average inefficiency of the corresponding ensemble of SPEGcodes.

A. Optimization algorithm
The main idea behind the SPEG algorithm is that different choices of the scheduling subsets S (t) d might lead to codes with different performance. Our purpose is to find scheduling subsets that minimize the average inefficiency of the corresponding ensemble of SPEG-codes. In order to properly formulate this optimization problem, we have to take into consideration only the "profile" of the scheduling subsets, which consists of the fractions of nodes within each subset. Precisely, let f (1) f Figure 3: Flowchart of the differential evolution optimization algorithm A family of parameters f satisfying the condition (2) before is called scheduling distribution. When parameters (n, m, f ) are fixed, we consider that the SPEG algorithm starts by randomly choosing a family of scheduling subsets S (t) d , according to the given scheduling distribution, and then it constructs a (random) Tanner graph as explained in the above section. We denote by G SPEG n, m, f (t) d the corresponding ensemble of SPEG Tanner graphs, and we define its average inefficiency by: When parameters n and m are fixed, it will be simply denoted byμ SPEG f Since our objective function cannot be expressed analytically, we address the optimization problem by using generic population-based metaheuristic optimization algorithms. More precisely, the differential evolution algorithm [17] is used, which optimizesμ SPEG f  Figure 3.
The algorithm maintains a population of candidate solutions, which is randomly initialized. At each iteration, the current population is evaluated, such as to find the best current solution. Then, a population of new candidate solutions is generated by combining existing candidates (mutation and recombination), and then keeping whichever candidate solution has the best score. In this way the objective function is treated as a black box that provides a measure of quality of the candidate solutions.

B. Simulation results
We consider four ensembles of irregular LDPC codes of rate 1/2, defined over the F 2 , F 4 , F 8 , F 16 , whose nodeperspective symbol-degree distributions are shown in Table I     (the constraint-node degree distributions are considered to be almost uniform).
We fixed the parameter T = 3 and, for each of the above ensembles, we used the differential evolution algorithm to find a scheduling distribution that minimizes the average inefficiency of the corresponding SPEG codes. We considered codes with binary dimension K = 5000; Hence, the binary code-length is N = 10000 and the non-binary codelength (number of symbol-nodes of the graph) is n = N/p, where p ∈ {1, 2, 3, 4}. The optimized scheduling distributions f  Table II. For comparison purposes, we have also displayed in Table II the average inefficiencies of the corresponding PEG, ModPEG, and random 5 ensembles. We can see that the SPEG algorithm significantly improves the Table II: Optimized scheduling distributions and corresponding inefficiency ratios, for irregular LDPC codes of rate 1/2, defined over F 2 , F 4 , F 8 and F 16 , with binary dimension K = 5000 average inefficiency ratios in comparison with those of the PEG and ModPEG algorithms. Moreover, we constructed several finite length codes over F 16 , using the same scheduling distribution that has been optimized for K = 5000. The average inefficiency of these codes is plotted in Figure 4. It can be observed that they significantly outperform codes constructed by the original PEG algorithm.
For K = 5000, Figure 5 displays the bit error rates of one PEG code, one ModPEG code, and one SPEG code with optimized scheduling distribution (these codes are chosen among the best codes of the corresponding ensembles). We can see that the SPEG algorithm significantly improves the waterfall region, at the expense of a slightly higher error floor.

V. CONCLUSION
The proposed Scheduled-PEG algorithm allows the enhancement of the classical PEG algorithm, by the introduction of a scheduling distribution that specifies the order in which edges are established in the graph. The scheduling distribution provides a way for exploring the ensemble of LDPC codes with fixed code-length and degree distributions, and is aimed at finding codes with very small average inefficiency.
We showed that the SPEG algorithm can be successfully combined with genetic optimization algorithms, which significantly improves the average inefficiency of the constructed LDPC codes over the classical-PEG construction. In terms of error rate curves, this translates into a significant improvement of the waterfall region.
Finally, we remark that the optimization of the scheduling distribution makes use of the specific channel model (through the use of the decoding inefficiency). Hence, LDPC codes constructed by using the SPEG algorithm together with an optimized scheduling distribution are channel dependent. However, the proposed algorithm could be generalized for more general channel models (e.g. by optimizing with respect to a target FER, or to the area under the FER curve.).