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 Conference on Computer and Information Technology (CIT)

Overview of LDPC Codes

Zongjie Tu, Shiyong Zhang

Published Oct 1, 2007• 21 citations
Publisher

Abstract

In light of the history of LDPC codes and relevant research advances in recent years, this paper probes into the encoding and decoding techniques related to this capacity-approaching error-correction technology. Besides the general expression as an equation, LDPC codes can also be examined with a Tanner graph. The encoding of LDPC codes comprises two tasks: construct a sparse parity-check matrix, and generate codewords with the matrix. The decoding of LDPC codes can be divided into three phases: initialization, message update, and validation. With a conventional model of communication systems, common decoding algorithms of LDPC codes are scrutinized. In particular, the sum-product algorithm is analyzed in an elaborate fashion. The logarithmic sum- product algorithm and the min-sum algorithm are two important variations of the sum-product algorithm. The logarithmic sum-product algorithm reduces multiplication to addition by introducing logarithmic likelihood ratio while the latter simplifies computation at the cost of precision.

DOI
10.1109/cit.2007.7

Related papers

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooks•Nov 19, 2009•6 citations

Comprehensive Algorithmic Review and Analysis of LDPC Codes

Waheed Ullah, Abid Yahya

Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel

Indonesian Journal of Electrical Engineering and Computer Science•Oct 1, 2015•8 citations

Comprehensive Algorithmic Review and Analysis of LDPC Codes

Waheed Ullah, Abid Yahya

Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel

TELKOMNIKA Indonesian Journal of Electrical Engineering•Oct 1, 2015•10 citations

Reduced-Complexity Decoding of LDPC Codes

Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.

IEEE Transactions on Communications•Jul 1, 2005•32 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

Reduced-Complexity Decoding of LDPC Codes

J. Chen, Ajay Dholakia, Evangelos S. Eleftheriou +2 more

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

IEEE Transactions on Communications•Aug 1, 2005•964 citations
In light of the history of LDPC codes and relevant research advances in recent years, this paper probes into the encoding and decoding techniques related to this capacity-approaching error-correction technology. Besides the general expression as an equation, LDPC codes can also be examined with a Tanner graph. The encoding of LDPC codes comprises two tasks: construct a sparse parity-check matrix, and generate codewords with the matrix. The decoding of LDPC codes can be divided into three phases: initialization, message update, and validation. With a conventional model of communication systems, common decoding algorithms of LDPC codes are scrutinized. In particular, the sum-product algorithm is analyzed in an elaborate fashion. The logarithmic sum- product algorithm and the min-sum algorithm are two important variations of the sum-product algorithm. The logarithmic sum-product algorithm reduces multiplication to addition by introducing logarithmic likelihood ratio while the latter simplifies computation at the cost of precision.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel
Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.
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.
Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.