Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Iterative and Maximum-Likelihood Decoding of LDPC Codes

Enrico Paolini, Gianluigi Liva, Balázs Matuz, Marco Chiani

Published Feb 25, 2026• 0 citations
Publisher

Abstract

Decoding of LDPC codes on the erasure channel: In Chapter 6, we illustrate different decoding algorithms for LDPC codes over erasure channels, namely, iterative (IT) and maximum likelihood (ML) decoding. Decoding on the erasure channel can be strongly simplified with respect to decoding on other channels, since whenever a symbol is not erased, we know its value with full certainty. We illustrate that iterative decoding can be done by a peeling process which resolves one unknown per iteration. ML decoding can be performed efficiently by solving a sparse system of equations by variants of the Gaussian elimination algorithm.

DOI
10.1017/9781316443354.007

Related papers

Pivoting Algorithms for Maximum Likelihood Decoding of LDPC Codes over Erasure Channels

Gianluigi Liva, Balázs Matuz, Enrico Paolini +1 more

This paper investigates efficient maximum-likelihood (ML) decoding algorithms for low-density parity-check (LDPC) codes over erasure channels. In particular, enhancements to a previously proposed structured Gaussian elimination approach are presented. The improvements are achieved by developing a set of algorithms, here referred to as pivoting algorithms, aiming to limit the average number of reference variables (or pivots) from which the erased symbols can be recovered. Four pivoting algorithms are compared, which exhibit different trade-offs between the complexity of the pivoting phase and the average number of pivots. Numerical results on the performance of LDPC codes under ML erasure decoding complete the analysis, confirming that a near-optimum performance can be obtained with an affordable decoding complexity, up to very high data rates. For example, for one of the presented algorithms, a software implementation has been developed, which is capable to provide data rates above 1.5 Gbps on a commercial computing platform.

Globecom•Nov 1, 2009•22 citations

On Decoding of Low-Density Parity-Check Codes Over the Binary Erasure Channel

Hossein Pishro-Nik, Faramarz Fekri

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.

IEEE Transactions on Information Theory•Mar 1, 2004•147 citations

An Efficient Maximum-Likelihood Decoding of LDPC Codes Over the Binary Erasure Channel

David Burshtein, G. Miller

We propose an efficient maximum-likelihood (ML) decoding algorithm for decoding low-density parity-check (LDPC) codes over the binary-erasure channel (BEC). We also analyze the computational complexity of the proposed algorithm.

IEEE Transactions on Information Theory•Oct 26, 2004•97 citations

Iterative LDPC Decoder Analysis

Enrico Paolini, Gianluigi Liva, Balázs Matuz +1 more

Performance analysis for iterative decoders: In Chapter 7, we discuss the behavior of LDPC codes under iterative erasure decoding. When the blocklength goes to infinity, for many LDPC codes, the symbol error probability exhibits a so-called threshold phenomenon that is, there exists a certain channel erasure probability below which error-free communication is possible, while this is not guaranteed above it. We discuss how to compute this threshold for ensembles of LDPC codes on memoryless erasure channels. In the finite-length setting, one may observe a flattening of the symbol error rate curve owing to stopping sets – specific structures in the code’s bipartite graph. Knowing their number and size allows predicting this so-called error floor. Based on our findings, we discuss how to design good LDPC for memoryless erasure channels with extension to channels with memory.

Cambridge University Press eBooks•Feb 25, 2026•0 citations

Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC

Luis Salamanca, Pablo M. Olmos, Juan José Murillo-Fuentes +1 more

We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels.

IEEE Transactions on Communications•Feb 1, 2013•10 citations

A decoding algorithm for LDPC codes over erasure channels with sporadic errors

Gianluigi Liva, Enrico Paolini, Balázs Matuz +1 more

An efficient decoding algorithm for low-density parity-check (LDPC) codes on erasure channels with sporadic errors (i.e., binary error-and-erasure channels with error probability much smaller than the erasure probability) is proposed and its performance analyzed. A general single-error multiple-erasure (SEME) decoding algorithm is first described, which may be in principle used with any binary linear block code. The algorithm is optimum whenever the non-erased part of the received word is affected by at most one error, and is capable of performing error detection of multiple errors. An upper bound on the average block error probability under SEME decoding is derived for the linear random code ensemble. The bound is tight and easy to implement. The algorithm is then adapted to LDPC codes, resulting in a simple modification to a previously proposed efficient maximum likelihood LDPC erasure decoder which exploits the parity-check matrix sparseness. Numerical results reveal that LDPC codes under efficient SEME decoding can closely approach the average performance of random codes.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2010•11 citations
Decoding of LDPC codes on the erasure channel: In Chapter 6, we illustrate different decoding algorithms for LDPC codes over erasure channels, namely, iterative (IT) and maximum likelihood (ML) decoding. Decoding on the erasure channel can be strongly simplified with respect to decoding on other channels, since whenever a symbol is not erased, we know its value with full certainty. We illustrate that iterative decoding can be done by a peeling process which resolves one unknown per iteration. ML decoding can be performed efficiently by solving a sparse system of equations by variants of the Gaussian elimination algorithm.
This paper investigates efficient maximum-likelihood (ML) decoding algorithms for low-density parity-check (LDPC) codes over erasure channels. In particular, enhancements to a previously proposed structured Gaussian elimination approach are presented. The improvements are achieved by developing a set of algorithms, here referred to as pivoting algorithms, aiming to limit the average number of reference variables (or pivots) from which the erased symbols can be recovered. Four pivoting algorithms are compared, which exhibit different trade-offs between the complexity of the pivoting phase and the average number of pivots. Numerical results on the performance of LDPC codes under ML erasure decoding complete the analysis, confirming that a near-optimum performance can be obtained with an affordable decoding complexity, up to very high data rates. For example, for one of the presented algorithms, a software implementation has been developed, which is capable to provide data rates above 1.5 Gbps on a commercial computing platform.
This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.
Performance analysis for iterative decoders: In Chapter 7, we discuss the behavior of LDPC codes under iterative erasure decoding. When the blocklength goes to infinity, for many LDPC codes, the symbol error probability exhibits a so-called threshold phenomenon that is, there exists a certain channel erasure probability below which error-free communication is possible, while this is not guaranteed above it. We discuss how to compute this threshold for ensembles of LDPC codes on memoryless erasure channels. In the finite-length setting, one may observe a flattening of the symbol error rate curve owing to stopping sets – specific structures in the code’s bipartite graph. Knowing their number and size allows predicting this so-called error floor. Based on our findings, we discuss how to design good LDPC for memoryless erasure channels with extension to channels with memory.
We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels.
An efficient decoding algorithm for low-density parity-check (LDPC) codes on erasure channels with sporadic errors (i.e., binary error-and-erasure channels with error probability much smaller than the erasure probability) is proposed and its performance analyzed. A general single-error multiple-erasure (SEME) decoding algorithm is first described, which may be in principle used with any binary linear block code. The algorithm is optimum whenever the non-erased part of the received word is affected by at most one error, and is capable of performing error detection of multiple errors. An upper bound on the average block error probability under SEME decoding is derived for the linear random code ensemble. The bound is tight and easy to implement. The algorithm is then adapted to LDPC codes, resulting in a simple modification to a previously proposed efficient maximum likelihood LDPC erasure decoder which exploits the parity-check matrix sparseness. Numerical results reveal that LDPC codes under efficient SEME decoding can closely approach the average performance of random codes.