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

IEEE International Symposium on Information Theory (ISIT)

LDPC decoding and code design on extrinsic trees

Eric T. Psota, Lance C. Pérez

Published Jun 1, 2009• 6 citations
Publisher

Abstract

Extrinsic tree decoding of low-density parity-check codes operates on modified, finite computation trees created from the Tanner graph of the code. The goal of the extrinsic tree algorithm is to maintain or improve the performance of existing iterative decoders, while providing a decoding algorithm for which upper bounds can be computed. The extrinsic tree algorithm is examined, along with the design of parity-check matrices on which the extrinsic tree decoder performs well.

DOI
10.1109/isit.2009.5205794

Related papers

Extrinsic tree decoding

Eric T. Psota, Lance C. Pérez

A new decoding method, called extrinsic tree decoding, is presented for decoding low-density parity-check codes on modified finite computation trees. The proposed method maintains similar performance to that of existing iterative decoders, while providing a decoding method for which realistic upper bounds can be computed for practical codes.

Conference on Information Sciences and Systems•Mar 1, 2009•5 citations

Tree Matrix Algorithm of LDPC Codes

Huanming Zhang

LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth. An LDPC code is defined by a sparse parity-check matrix and can be described by a bipartite graph called Tanner graph. Loops in Tanner graph prevent the sum-product algorithm from converging. Further, loops, especially short loops, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. This paper, by graph theory, deduces cut-node tree graph of LDPC code, and depicts it with matrix. On the basis of tree matrix algorithm, whole depictions of loops can be figured out, providing of foundation for further research of relations between loops and LDPC codes’ performance.

Journal of Signal and Information Processing•Jan 1, 2014•0 citations

Low-Density Parity-Check Codes

W.E. Ryan, Shu Lin

Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.

Cambridge University Press eBooks•Sep 17, 2009•6 citations

Finite tree-based decoding of low-density parity-check codes

Eric T. Psota

Low-density parity-check codes are commonly decoded using iterative message-passing decoders, such as the min-sum and sum-product decoders. Computer simulations demonstrate that these suboptimal decoders are capable of achieving low probability of bit error at signal-to-noise ratios close to capacity. However, current methods for analyzing the behavior of the min-sum and sum-product decoders fails to produce usable bounds on the probability of bit error. Thus, the resulting probability of bit error when using these decoders remains largely unknown for signal-to-noise ratios beyond the reach of simulation. For this reason, it is worth considering alternative methods for decoding low-density parity-check codes. New methods for decoding low-density parity-check codes, known as finite tree-based decoders, are presented as alternative decoders for low-density parity-check codes. The goal of the finite tree-based decoders is to achieve probability of bit error comparable to that of the min-sum and sum-product decoders, while allowing for computationally tractable performance analysis. Finite tree-based decoding requires the construction of finite trees derived from the Tanner graph of the low-density parity-check code. The resulting size of the finite trees allows for current analytical techniques, such as deviation bounds and density evolution, to be used to predict the probability of bit error of finite tree-based decoding of short-to-moderate length low-density parity-check codes. Simulation results show that finite tree-based decoders are capable of outperforming current iterative decoders at high signal-to-noise ratios. Examples are also given where finite tree-based decoding provably approaches maximum-likelihood performance as the signal-to-noise ratio grows large. A new method is also presented for lower bounding the minimum distance of low-density parity-check codes. This new lower bound is used as a cost criteria for the construction of low-density parity-check codes with both large girth and minimum-distance properties. Codes generated with this new construction technique are shown in simulations to outperform codes generated with the progressive edge-growth algorithm, using both iterative decoding and finite tree-based decoding.

•Jan 1, 2010•3 citations

Low-Density Parity-Check Lattices: Construction and Decoding Analysis

Mohammad‐Reza Sadeghi, Amir H. Banihashemi, Daniel Panario

Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands

IEEE Transactions on Information Theory•Sep 29, 2006•95 citations

A Differential Binary Message-Passing LDPC Decoder

Nastaran Mobini, Amir H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

Globecom•Nov 1, 2007•16 citations
Extrinsic tree decoding of low-density parity-check codes operates on modified, finite computation trees created from the Tanner graph of the code. The goal of the extrinsic tree algorithm is to maintain or improve the performance of existing iterative decoders, while providing a decoding algorithm for which upper bounds can be computed. The extrinsic tree algorithm is examined, along with the design of parity-check matrices on which the extrinsic tree decoder performs well.
LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth. An LDPC code is defined by a sparse parity-check matrix and can be described by a bipartite graph called Tanner graph. Loops in Tanner graph prevent the sum-product algorithm from converging. Further, loops, especially short loops, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. This paper, by graph theory, deduces cut-node tree graph of LDPC code, and depicts it with matrix. On the basis of tree matrix algorithm, whole depictions of loops can be figured out, providing of foundation for further research of relations between loops and LDPC codes’ performance.
Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.
Low-density parity-check codes are commonly decoded using iterative message-passing decoders, such as the min-sum and sum-product decoders. Computer simulations demonstrate that these suboptimal decoders are capable of achieving low probability of bit error at signal-to-noise ratios close to capacity. However, current methods for analyzing the behavior of the min-sum and sum-product decoders fails to produce usable bounds on the probability of bit error. Thus, the resulting probability of bit error when using these decoders remains largely unknown for signal-to-noise ratios beyond the reach of simulation. For this reason, it is worth considering alternative methods for decoding low-density parity-check codes. New methods for decoding low-density parity-check codes, known as finite tree-based decoders, are presented as alternative decoders for low-density parity-check codes. The goal of the finite tree-based decoders is to achieve probability of bit error comparable to that of the min-sum and sum-product decoders, while allowing for computationally tractable performance analysis. Finite tree-based decoding requires the construction of finite trees derived from the Tanner graph of the low-density parity-check code. The resulting size of the finite trees allows for current analytical techniques, such as deviation bounds and density evolution, to be used to predict the probability of bit error of finite tree-based decoding of short-to-moderate length low-density parity-check codes. Simulation results show that finite tree-based decoders are capable of outperforming current iterative decoders at high signal-to-noise ratios. Examples are also given where finite tree-based decoding provably approaches maximum-likelihood performance as the signal-to-noise ratio grows large. A new method is also presented for lower bounding the minimum distance of low-density parity-check codes. This new lower bound is used as a cost criteria for the construction of low-density parity-check codes with both large girth and minimum-distance properties. Codes generated with this new construction technique are shown in simulations to outperform codes generated with the progressive edge-growth algorithm, using both iterative decoding and finite tree-based decoding.
Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.