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

Generating Good Finite Length LDPC Codes Based on Lifted Graphs

Eran Sharon, Simon N. Litsyn

Published Sep 27, 2006• 0 citations
OpenAlex

Abstract

A method for generating good finite length Low-Density Parity-Check (LDPC) codes based on lifted graphs is described.The codes are constructed using a progressive edge growth technique by taking into account the influence that every introduced edge has on the error floor and waterfall threshold of the code.The generated code can be tailored according to prescribed specification, achieving the desirable error floor versus waterfall threshold trade-off.For the constructed codes, an analytical upper bound on the expected block error probability of the code over the Binary Erasure Channel (BEC) in the error floor region and an asymptotic Density Evolution (DE) waterfall threshold are obtained.

Related papers

Constructing LDPC codes by error minimization progressive edge growth

E. Sharon, Simon N. Litsyn

A novel approach to constructing Tanner graphs using progressive edge growth (PEG) is introduced. It yields LDPC codes providing minimized block error probability in Binary Erasure Channels (BEC). The constructed codes exhibit superior performance over codes generated by previously known algorithms, both for BEC and AWGN channels. Furthermore, an upper bound on the expected block error probability in the error floor region of the generated codes is derived. This allows analytical prediction of the codes' error floor performance. Finally, the method is generalized for generating simple in implementation LDPC codes based on lifted graphs.

IEEE Transactions on Communications•Mar 1, 2008•24 citations

An Improvement of the PEG Algorithm for LDPC Codes in the Waterfall Region

Gerd Richter

There exist many different algorithms to construct good low-density parity-check (LDPC) codes. To maximize the girth of the bipartite graph, which represents the LDPC code, the progressive edge-growth (PEG) algorithm was introduced. This construction methods leads for irregular LDPC codes to a lower error floor, but also to a performance loss in the waterfall region compared with randomly constructed LDPC codes. In this paper, we describe a modification of the PEG algorithm that improves the performance in the waterfall region. Furthermore, this modified PEG algorithm yields codes with lower error floors and a slightly better performance in the waterfall region than randomly constructed LDPC codes

IEEE EUROCON - International Conference on Computer as a Tool (EUROCON)•Jan 1, 2005•9 citations

A Method for Constructing LDPC Codes with Low Error Floor

Eran Sharon, Simon N. Litsyn

This paper describes a novel progressive edge growth (PEG) algorithm for constructing LDPC codes with minimized block error probability over the binary erasure channel (BEC). The constructed codes provide superior performance and lower error floor compared to codes generated by previously known algorithms. Furthermore, an upper bound on the expected block error probability in the error floor region of the generated code is derived

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•4 citations

Design of Finite-Length Irregular Protograph Codes with Low Error Floors over the Binary-Input AWGN Channel Using Cyclic Liftings

Reza Asvadi, Amir H. Banihashemi, Mahmoud Ahmadian‐Attari

We propose a technique to design finite-length irregular low-density parity-check (LDPC) codes over the binary-input additive white Gaussian noise (AWGN) channel with good performance in both the waterfall and the error floor region. The design process starts from a protograph which embodies a desirable degree distribution. This protograph is then lifted cyclically to a certain block length of interest. The lift is designed carefully to maximize the components of the approximate cycle extrinsic message degree (ACE) spectrum of the code's Tanner graph in a greedy fashion. As a consequence, the designed code would perform well in the error floor region. Moreover, the proposed construction results in quasi-cyclic codes which are attractive in practice due to simple encoder and decoder implementation. Simulation results are provided to demonstrate the effectiveness of the proposed construction in comparison with similar existing constructions.

arXiv:1102.0424•IEEE Transactions on Communications•Mar 13, 2012•24 citations

Constructing LDPC Codes by 2-Lifts

Xudong Ma, En‐hui Yang

With the motivation of constructing Low-Density Parity-Check (LDPC) codes with low error floors, we propose a new code construction scheme based on random 2-lifts. An analysis on stopping set distributions of the proposed code ensembles is presented. The analysis shows that low-weight stopping sets in the resulting codes are typically the results of stopping sets with weak graph expansion properties in the base graphs. Based on this analysis, we propose a set of design criteria for constructing codes with low error floors. According to the design criteria, stopping sets with weak graph expansion properties should be avoided in the base graphs. We present numerical results on constructing capacity-approaching codes over Binary Erasure Channels (BEC). The numerical results show that the codes by the proposed scheme have significantly lower error floors compared with the codes by the standard construction.

arXiv:cs/0609117•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•3 citations

A novel algorithm of constructing LDPC codes with graph theory

Yan Cui, Xinhui Si, Yanan Shen

There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.

IEEE Conference on Cybernetics and Intelligent Systems•Sep 1, 2008•2 citations
A method for generating good finite length Low-Density Parity-Check (LDPC) codes based on lifted graphs is described.The codes are constructed using a progressive edge growth technique by taking into account the influence that every introduced edge has on the error floor and waterfall threshold of the code.The generated code can be tailored according to prescribed specification, achieving the desirable error floor versus waterfall threshold trade-off.For the constructed codes, an analytical upper bound on the expected block error probability of the code over the Binary Erasure Channel (BEC) in the error floor region and an asymptotic Density Evolution (DE) waterfall threshold are obtained.
A novel approach to constructing Tanner graphs using progressive edge growth (PEG) is introduced. It yields LDPC codes providing minimized block error probability in Binary Erasure Channels (BEC). The constructed codes exhibit superior performance over codes generated by previously known algorithms, both for BEC and AWGN channels. Furthermore, an upper bound on the expected block error probability in the error floor region of the generated codes is derived. This allows analytical prediction of the codes' error floor performance. Finally, the method is generalized for generating simple in implementation LDPC codes based on lifted graphs.
There exist many different algorithms to construct good low-density parity-check (LDPC) codes. To maximize the girth of the bipartite graph, which represents the LDPC code, the progressive edge-growth (PEG) algorithm was introduced. This construction methods leads for irregular LDPC codes to a lower error floor, but also to a performance loss in the waterfall region compared with randomly constructed LDPC codes. In this paper, we describe a modification of the PEG algorithm that improves the performance in the waterfall region. Furthermore, this modified PEG algorithm yields codes with lower error floors and a slightly better performance in the waterfall region than randomly constructed LDPC codes
We propose a technique to design finite-length irregular low-density parity-check (LDPC) codes over the binary-input additive white Gaussian noise (AWGN) channel with good performance in both the waterfall and the error floor region. The design process starts from a protograph which embodies a desirable degree distribution. This protograph is then lifted cyclically to a certain block length of interest. The lift is designed carefully to maximize the components of the approximate cycle extrinsic message degree (ACE) spectrum of the code's Tanner graph in a greedy fashion. As a consequence, the designed code would perform well in the error floor region. Moreover, the proposed construction results in quasi-cyclic codes which are attractive in practice due to simple encoder and decoder implementation. Simulation results are provided to demonstrate the effectiveness of the proposed construction in comparison with similar existing constructions.
With the motivation of constructing Low-Density Parity-Check (LDPC) codes with low error floors, we propose a new code construction scheme based on random 2-lifts. An analysis on stopping set distributions of the proposed code ensembles is presented. The analysis shows that low-weight stopping sets in the resulting codes are typically the results of stopping sets with weak graph expansion properties in the base graphs. Based on this analysis, we propose a set of design criteria for constructing codes with low error floors. According to the design criteria, stopping sets with weak graph expansion properties should be avoided in the base graphs. We present numerical results on constructing capacity-approaching codes over Binary Erasure Channels (BEC). The numerical results show that the codes by the proposed scheme have significantly lower error floors compared with the codes by the standard construction.
There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.