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

Telecommunication Engineering

Constructing and Decoding of LDPC Codes Based on Factor Graphs

Liang Zhao

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

Low Density Parity Check(LDPC) Codes are a kind of linear block codes approaching Shannon limit. They can be constructed either with spare parity-check matrix or with factor graphs. According to various constructing methods of the codes,several decoding algorithms have been proposed so far. In this paper the constructing method of LDPC codes based on factor graph is introduced at the beginning, then the sum-product decoding algorithm(SPA) is analyzed. Finally the decoding process of LDPC based on SPA algorithm is discussed.

Related papers

Low-Density Parity-Check Codes

Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.

Kluwer Academic Publishers eBooks•Dec 21, 2005•8 citations

A note on a decoding algorithm of codes on graphs with small loops

N. Kobayashi, Tomoko K. MATSUSHIMA, Shigeichi Hirasawa

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.

IEEE Information Theory Workshop (ITW)•Jan 1, 2005•1 citation

Construction of QC-LDPC Codes based on Cyclic Groups

Zhang Er-yang

Encoding of computer-generated random low-density parity-check(LDPC) codes can be rather complex.QC-LDPC codes have encoding advantage over random LDPC codes.Encoding of an QC-LDPC code can be implemented using shift-registers with linear complexity.The usual algorithm for the decoding of LDPC codes is the iterative sum-product algorithm(SPA),operating on a Tanner graph of the code.It is well known that cycle-free Tanner graph with SPA algorithm yeilds optimal decoding.The girth of the cycle -free Tanner graph is infinite.In this paper,we present an algebraic method for constructing binary QC-LDPC codes based on the rowcolumn constraint.The codes constructed by this method have girths at least 6.Experimental results show that the constructed LDPC codes decoded with SPA over the AWGN channel can perform as well as standard LDPC codes in terms of bit-error probability and block error probability.

Signal Processing•Jan 1, 2009•0 citations

Decoding of low-density parity-check codes based on noise soft-decision over finite-state Markov channels

He-Qin Zhou

An improved decoding algorithm for low-density parity-check code(LDPC) on finite-state Markov channels was presented and the corresponding factor graph representation was given.It consists of two parts: standard sum-product algorithm(SPA) for LDPC and forward-backward(FB) algorithm for Markov channel.After each iteration for SPA,FB re-estimated the channel likelihood ratio for the next iteration of SPA based on soft decisions for noise bits from SPA.Considering more cycles in the factor graph with the introduction of the Markov channel node,the probabilistic schedule was used to update the message during the iterations for decoding.Simulation results show that the algorithm not only performs much better than the standard sum-product algorithm,but also outperforms the algorithm based on hard decisions for noise bits.

•Jan 1, 2006•0 citations

Research on Encoding and Decoding Algorithms of LDPC Codes

Yifeng He, Zhemin Duan

The LDPC code, namely low density parity check code, is essentially a linear block code.Its decoding performance is closer to the Shannon limit than the Turbo code.The definition and description of LDPC codes are introduced in this paper.LDPC coding method includes the Algorithm of LU decomposable encoding and the algorithm of partitioned iterated encoding.the algorithm of message passing, the algorithm of minimum-sum decoding and the algorithm of bit-flipping decoding are the common decoding algorithms of the LDPC codes.The concept and features of the encoding and decoding algorithms are explored in this paper to provide some references for the relative researchers.

International Conference on Materials Science, Machinery and Energy Engineering (MSMEE)•Jan 1, 2017•1 citation

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•5 citations
Low Density Parity Check(LDPC) Codes are a kind of linear block codes approaching Shannon limit. They can be constructed either with spare parity-check matrix or with factor graphs. According to various constructing methods of the codes,several decoding algorithms have been proposed so far. In this paper the constructing method of LDPC codes based on factor graph is introduced at the beginning, then the sum-product decoding algorithm(SPA) is analyzed. Finally the decoding process of LDPC based on SPA algorithm is discussed.
Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.
The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.
Encoding of computer-generated random low-density parity-check(LDPC) codes can be rather complex.QC-LDPC codes have encoding advantage over random LDPC codes.Encoding of an QC-LDPC code can be implemented using shift-registers with linear complexity.The usual algorithm for the decoding of LDPC codes is the iterative sum-product algorithm(SPA),operating on a Tanner graph of the code.It is well known that cycle-free Tanner graph with SPA algorithm yeilds optimal decoding.The girth of the cycle -free Tanner graph is infinite.In this paper,we present an algebraic method for constructing binary QC-LDPC codes based on the rowcolumn constraint.The codes constructed by this method have girths at least 6.Experimental results show that the constructed LDPC codes decoded with SPA over the AWGN channel can perform as well as standard LDPC codes in terms of bit-error probability and block error probability.
An improved decoding algorithm for low-density parity-check code(LDPC) on finite-state Markov channels was presented and the corresponding factor graph representation was given.It consists of two parts: standard sum-product algorithm(SPA) for LDPC and forward-backward(FB) algorithm for Markov channel.After each iteration for SPA,FB re-estimated the channel likelihood ratio for the next iteration of SPA based on soft decisions for noise bits from SPA.Considering more cycles in the factor graph with the introduction of the Markov channel node,the probabilistic schedule was used to update the message during the iterations for decoding.Simulation results show that the algorithm not only performs much better than the standard sum-product algorithm,but also outperforms the algorithm based on hard decisions for noise bits.
The LDPC code, namely low density parity check code, is essentially a linear block code.Its decoding performance is closer to the Shannon limit than the Turbo code.The definition and description of LDPC codes are introduced in this paper.LDPC coding method includes the Algorithm of LU decomposable encoding and the algorithm of partitioned iterated encoding.the algorithm of message passing, the algorithm of minimum-sum decoding and the algorithm of bit-flipping decoding are the common decoding algorithms of the LDPC codes.The concept and features of the encoding and decoding algorithms are explored in this paper to provide some references for the relative researchers.
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.