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

arXiv:0810.2781 · IEEE Transactions on Information Theory

Linear Time Encoding of LDPC Codes

Jin Lu, José M. F. Moura

Published Jan 1, 2010• 19 citations
arXivHTMLPDF

Abstract

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.

DOI
10.1109/tit.2009.2034823

Related papers

Linear Time Encoding of LDPC Codes

Lu Jin, José M. F. Moura

Abstract—In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method “label-and-decide. ” We prove that the “label-and-decide ” method is applicable to Tanner graphs with a hierarchical structure—pseudo-trees—and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs—the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm—the “label-decide-recompute.” Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than 4 1 M 1 (k 0 1), where M is the number of independent rows in the parity-check matrix and k represents the mean row weight of the parity-check matrix. Index Terms—Encoding stopping set, low-density parity-check (LDPC) codes, linear complexity encoding, pseudo-tree, Tanner graphs.

•Feb 27, 2010•29 citations

Structured LDPC Codes with Linear Complexity Encoding

Vinay Bhardwaj, Nagendra Prasad Pathak, Arun R. Kumar

Low density parity check (LDPC) codes have stimulated a lot of interest in recent years due to their capacity approaching performance and availability of fast decoding algorithms. The existing encoding scheme for LDPC code usually incurs too high complexity and should be changed to encoding scheme with low complexity. An elementary turbo structured Tanner graph construction and encoding scheme for a family of regular LDPC codes attaining desired high girth is studied in this paper. The construction provides flexibility in choice of parameters like column weight (j > =2), row weight k and arbitrary girth g. Turbo structured low density parity check ( TS-LDPC) codes are regular LDPC codes with their Tanner graph consists of two trees connected by an interleaver. Linear complexity is attained with few alterations and restrictions of in Tanner graph of turbo structured LDPC codes. Simulation results demonstrates that not only the bit error rate (BER) performance of TSLDPC codes at low signal to noise ratio (SNR) is comparable with error performance of corresponding random LDPC codes, with better error performance at high SNR but linear encoding considerably reduces simulation time.

•Jan 1, 2009•3 citations

Systematic Modification of Parity-Check Matrices for Efficient Encoding of LDPC Codes

Mohammad Obaidah Shaqfeh, Norbert Goertz

An algorithm for efficient encoding of LDPC codes is presented that does not impose any restrictions on the construction of the parity-check matrices. The algorithm modifies the parity check matrix, without changing the subspace spanned by its rows, by removing linear dependent rows and adding a small number of new rows such that the graph-based message-passing encoder will not get stuck in a stopping set. The added rows are designed by a new algorithm which is based on the notion of the "key set". The encoder exploits the sparseness of the parity-check matrix, and the encoding complexity grows almost linear with the blocksize, because the number of added rows, which may not be sparse, is relatively small.

International Conference on Communications•Jun 1, 2007•3 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

Improved progressive edge-growth algorithm for fast encodable LDPC codes

Xueqin Jiang, Moon Ho Lee, Jinpeng Qi

The progressive edge-growth (PEG) algorithm is known to construct low-density parity-check (LDPC) codes at finite code lengths with large girths by establishing edges between symbol and check nodes in an edge-by-edge manner. The linear-encoding PEG (LPEG) algorithm, a simple variation of the PEG algorithm, can be applied to generate linear time encodable LDPC codes whose m parity bits p1, p2, ..., p m are computed recursively in m steps. In this article, we propose modifications of the LPEG algorithm to construct LDPC codes whose number of encoding steps is independent of the code length. The maximum degree of the symbol nodes in the Tanner graph is denoted by ; The m parity bits of the proposed LDPC codes are divided into subgroups and can be computed in only steps. Since , the number of encoding steps can be significantly reduced. It has also been proved that the PEG codes and the codes proposed in this article have similar lower bound on girth. Simulation results showed that the proposed codes perform very well over the AWGN channel with an iterative decoding.

EURASIP Journal on Wireless Communications and Networking•May 21, 2012•7 citations

On the Hardness of Approximating Stopping and Trapping Sets

Andrew McGregor, Olgica Milenković

We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes, based on stopping and trapping set enumeration, cannot provide accurate worst-case performance predictions for most codes.

IEEE Transactions on Information Theory•Mar 24, 2010•61 citations
In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.
Abstract—In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method “label-and-decide. ” We prove that the “label-and-decide ” method is applicable to Tanner graphs with a hierarchical structure—pseudo-trees—and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs—the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm—the “label-decide-recompute.” Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than 4 1 M 1 (k 0 1), where M is the number of independent rows in the parity-check matrix and k represents the mean row weight of the parity-check matrix. Index Terms—Encoding stopping set, low-density parity-check (LDPC) codes, linear complexity encoding, pseudo-tree, Tanner graphs.
Low density parity check (LDPC) codes have stimulated a lot of interest in recent years due to their capacity approaching performance and availability of fast decoding algorithms. The existing encoding scheme for LDPC code usually incurs too high complexity and should be changed to encoding scheme with low complexity. An elementary turbo structured Tanner graph construction and encoding scheme for a family of regular LDPC codes attaining desired high girth is studied in this paper. The construction provides flexibility in choice of parameters like column weight (j > =2), row weight k and arbitrary girth g. Turbo structured low density parity check ( TS-LDPC) codes are regular LDPC codes with their Tanner graph consists of two trees connected by an interleaver. Linear complexity is attained with few alterations and restrictions of in Tanner graph of turbo structured LDPC codes. Simulation results demonstrates that not only the bit error rate (BER) performance of TSLDPC codes at low signal to noise ratio (SNR) is comparable with error performance of corresponding random LDPC codes, with better error performance at high SNR but linear encoding considerably reduces simulation time.
An algorithm for efficient encoding of LDPC codes is presented that does not impose any restrictions on the construction of the parity-check matrices. The algorithm modifies the parity check matrix, without changing the subspace spanned by its rows, by removing linear dependent rows and adding a small number of new rows such that the graph-based message-passing encoder will not get stuck in a stopping set. The added rows are designed by a new algorithm which is based on the notion of the "key set". The encoder exploits the sparseness of the parity-check matrix, and the encoding complexity grows almost linear with the blocksize, because the number of added rows, which may not be sparse, is relatively small.
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.
The progressive edge-growth (PEG) algorithm is known to construct low-density parity-check (LDPC) codes at finite code lengths with large girths by establishing edges between symbol and check nodes in an edge-by-edge manner. The linear-encoding PEG (LPEG) algorithm, a simple variation of the PEG algorithm, can be applied to generate linear time encodable LDPC codes whose m parity bits p1, p2, ..., p m are computed recursively in m steps. In this article, we propose modifications of the LPEG algorithm to construct LDPC codes whose number of encoding steps is independent of the code length. The maximum degree of the symbol nodes in the Tanner graph is denoted by ; The m parity bits of the proposed LDPC codes are divided into subgroups and can be computed in only steps. Since , the number of encoding steps can be significantly reduced. It has also been proved that the PEG codes and the codes proposed in this article have similar lower bound on girth. Simulation results showed that the proposed codes perform very well over the AWGN channel with an iterative decoding.