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 Transactions on Communications

Constructing LDPC codes by error minimization progressive edge growth

E. Sharon, Simon N. Litsyn

Published Mar 1, 2008• 24 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2008.050658

Related papers

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

Generating Good Finite Length LDPC Codes Based on Lifted Graphs

Eran Sharon, Simon N. Litsyn

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.

•Sep 27, 2006•0 citations

A PEG Construction of Finite-Length LDPC Codes with Low Error Floor

Sina Khazraie, Reza Asvadi, Amir H. Banihashemi

The progressive-edge-growth (PEG) algorithm of Hu et al. is modified to improve the error floor performance of the constructed low-density parity-check (LDPC) codes. To improve the error floor, the original PEG algorithm is equipped with an efficient algorithm to find the dominant elementary trapping sets (ETS's) that are added to the Tanner graph of the under-construction code by the addition of each variable node and its adjacent edges. The aim is to select the edges, among the candidates available at each step of the original PEG algorithm, that prevent the creation of dominant ETS's. The proposed method is applicable to both regular and irregular variable node degree distributions. Simulation results are presented to demonstrate the superior ETS distribution and error floor performance of the constructed codes compared to similar codes constructed by the original and other modifications of the PEG algorithm.

IEEE Communications Letters•Jun 5, 2012•43 citations

New PEG algorithm with low error floor for construction of irregular LDPC codes

Feijin Shi, Shuangshuang Han

The progressive-edge-growth (PEG) algorithm for constructing Tanner graphs with large girth by progressively establishing edges/connections between symbol nodes and check nodes in an edge-by-edge way is highly known to construct low-density parity-check (LDPC) codes at short block lengths for achieving good performance. This paper proposed an improved PEG construction for irregular codes, which heuristically selects good codes from random graphs for short block lengths. The simulation results are given to demonstrate that the proposed algorithm gians better BER performance for high signal-to-noise (SNR) ratios without performance loss for low-SNR region, i.e. low error floor.

IEEE International Conference on Computer and Communications (ICCC)•Oct 1, 2015•1 citation

Regular and irregular progressive edge-growth tanner graphs

Xiao-Yu Hu, Evangelos S. Eleftheriou, Donald M. Arnold

We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2005•1,489 citations

An improved algorithm for constructing QC-LDPC codes based on the PEG algorithm

Zhiyong Fan, Weibo Zhang, Xingcheng Liu +1 more

The Progressive edge-growth (PEG) algorithm was proven to be a simple and effective approach in designing Low-density parity-check (LDPC) codes. However, the Tanner graph constructed with the PEG algorithm is non-structured, which leads to random distributions of the positions of 1's in the corresponding parity-check matrix. In this paper, an improved algorithm based on the PEG algorithm for constructing quasi-cyclic (QC) LDPC codes is proposed. The proposed algorithm can eliminate short cycles efficiently and gain low error-floors. What is more important, the proposed QC-LDPC codes construction method is hardware-friendly because of its quasi-cyclic structure. Our simulation results demonstrate that the codes constructed with the proposed algorithm has better performance than the PEG algorithm over the additive white Gaussian noise (AWGN) channel and Rayleigh flat fading channel.

International Conference on Communications and Networking in China (ChinaCom)•Aug 1, 2009•5 citations
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.
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.
The progressive-edge-growth (PEG) algorithm of Hu et al. is modified to improve the error floor performance of the constructed low-density parity-check (LDPC) codes. To improve the error floor, the original PEG algorithm is equipped with an efficient algorithm to find the dominant elementary trapping sets (ETS's) that are added to the Tanner graph of the under-construction code by the addition of each variable node and its adjacent edges. The aim is to select the edges, among the candidates available at each step of the original PEG algorithm, that prevent the creation of dominant ETS's. The proposed method is applicable to both regular and irregular variable node degree distributions. Simulation results are presented to demonstrate the superior ETS distribution and error floor performance of the constructed codes compared to similar codes constructed by the original and other modifications of the PEG algorithm.
The progressive-edge-growth (PEG) algorithm for constructing Tanner graphs with large girth by progressively establishing edges/connections between symbol nodes and check nodes in an edge-by-edge way is highly known to construct low-density parity-check (LDPC) codes at short block lengths for achieving good performance. This paper proposed an improved PEG construction for irregular codes, which heuristically selects good codes from random graphs for short block lengths. The simulation results are given to demonstrate that the proposed algorithm gians better BER performance for high signal-to-noise (SNR) ratios without performance loss for low-SNR region, i.e. low error floor.
We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.
The Progressive edge-growth (PEG) algorithm was proven to be a simple and effective approach in designing Low-density parity-check (LDPC) codes. However, the Tanner graph constructed with the PEG algorithm is non-structured, which leads to random distributions of the positions of 1's in the corresponding parity-check matrix. In this paper, an improved algorithm based on the PEG algorithm for constructing quasi-cyclic (QC) LDPC codes is proposed. The proposed algorithm can eliminate short cycles efficiently and gain low error-floors. What is more important, the proposed QC-LDPC codes construction method is hardware-friendly because of its quasi-cyclic structure. Our simulation results demonstrate that the codes constructed with the proposed algorithm has better performance than the PEG algorithm over the additive white Gaussian noise (AWGN) channel and Rayleigh flat fading channel.