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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

PWG: Progressive Weight-Growth Algorithm for LDPC Codes

Xiangxue Li, Qingji Zheng, Haifeng Qian, Dong Zheng, Kefei Chen

Published Jan 1, 2014• 0 citations
Publisher

Abstract

Given specified parameters, the number of check nodes, the expected girth and the variable node degrees, the Progressive Weight-Growth (PWG) algorithm is proposed to generate high rate low-density parity-check (LDPC) codes. Based on the theoretic foundation that is to investigate the girth impact by adding/removing variable nodes and edges of the Tanner graph, the PWG progressively increases column weights of the parity check matrix without violating the constraints defined by the given parameters. The analysis of the computational complexity and the simulation of code performance show that the LDPC codes by the PWG provide better or comparable performance in comparison with LDPC codes by some well-known methods (e.g., Mackay's random constructions, the PEG algorithm, and the bit-filling algorithm).

DOI
10.1587/transfun.e97.a.685

Related papers

Extended PEG Algorithm for High Rate LDPC Codes

Zhiheng Zhou, Xiangxue Li, Dong Zheng +2 more

Progressive Edge-Growth(PEG) Algorithm is a good candidate to generate Tanner Graphs with a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner. In this paper, we propose an extended PEG algorithm for constructing Low-Density Parity-Check (LDPC) codes with very high rate when given a lower bound of girth. Simulation results show the bit error rates of constructed LDPC codes with very high rate or large girth.

IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)•Jan 1, 2009•5 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

Progressive edge-growth Tanner graphs

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

We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.

Globecom•Nov 13, 2002•496 citations

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

Efficient Progressive Edge-Growth Algorithm Based on Chinese Remainder Theorem

Xueqin Jiang, Xiang‐Gen Xia, Moon Ho Lee

Progressive edge-growth (PEG) algorithm construction builds a Tanner graph, or equivalently a parity-check matrix, for an LDPC code by establishing edges between the symbol nodes and the check nodes in an edge-by-edge manner and maximizing the girth in a greedy fashion. This approach is simple but the complexity of the PEG algorithm scale is O(nm), where n is the number of symbol nodes and m is the number of check nodes. We deal with this problem by construct a base matrix Hbof size mb× nbwith the PEG algorithm and simultaneously expand this base matrix into a parity-check matrix H of size mx n via the the Chinese remainder theorem (CRT), where m ≫ mband n ≥ nb. The size of the base matrix is expanded without decreasing the girth. For convenience, the PEG and CRT combined algorithm is referred to as the PEG-CRT algorithm in this paper. Since a smaller matrix is constructed with the PEG algorithm and the complexity of the CRT computation is negligible compared to the PEG algorithm, the complexity of the whole code construction process is reduced. Furthermore, the proposed algorithm has a potential advantage of saving storage space by storing a smaller matrix Hband expanding it to H "on-the-fly" in hardware. The expanded matrix H preserves the important properties of base matrix such as large girth, flexible code rate and low density. The complexity analysis shows that the complexity of the PEG-CRT algorithm does not grow with the code length n. Simulation results show that compared with the PEG LDPC codes of length nb, the expanded PEG-CRT LDPC codes have better bit error rate (BER) performance with the iterative decoding. It is also shown that compared with PEG LDPC codes of length n, which constructed with higher complexities, the PEG-CRT codes have similar BER performance.

IEEE Transactions on Communications•Jan 31, 2014•19 citations

Quasi-Cyclic Low-Density Parity-Check Codes Based on Progressive Cycle Growth Algorithm

Yuanhua Liu, Meiling Zhang, Niu Xin-Liang

Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2016•1 citation
Given specified parameters, the number of check nodes, the expected girth and the variable node degrees, the Progressive Weight-Growth (PWG) algorithm is proposed to generate high rate low-density parity-check (LDPC) codes. Based on the theoretic foundation that is to investigate the girth impact by adding/removing variable nodes and edges of the Tanner graph, the PWG progressively increases column weights of the parity check matrix without violating the constraints defined by the given parameters. The analysis of the computational complexity and the simulation of code performance show that the LDPC codes by the PWG provide better or comparable performance in comparison with LDPC codes by some well-known methods (e.g., Mackay's random constructions, the PEG algorithm, and the bit-filling algorithm).
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.
We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.
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.
Progressive edge-growth (PEG) algorithm construction builds a Tanner graph, or equivalently a parity-check matrix, for an LDPC code by establishing edges between the symbol nodes and the check nodes in an edge-by-edge manner and maximizing the girth in a greedy fashion. This approach is simple but the complexity of the PEG algorithm scale is O(nm), where n is the number of symbol nodes and m is the number of check nodes. We deal with this problem by construct a base matrix Hbof size mb× nbwith the PEG algorithm and simultaneously expand this base matrix into a parity-check matrix H of size mx n via the the Chinese remainder theorem (CRT), where m ≫ mband n ≥ nb. The size of the base matrix is expanded without decreasing the girth. For convenience, the PEG and CRT combined algorithm is referred to as the PEG-CRT algorithm in this paper. Since a smaller matrix is constructed with the PEG algorithm and the complexity of the CRT computation is negligible compared to the PEG algorithm, the complexity of the whole code construction process is reduced. Furthermore, the proposed algorithm has a potential advantage of saving storage space by storing a smaller matrix Hband expanding it to H "on-the-fly" in hardware. The expanded matrix H preserves the important properties of base matrix such as large girth, flexible code rate and low density. The complexity analysis shows that the complexity of the PEG-CRT algorithm does not grow with the code length n. Simulation results show that compared with the PEG LDPC codes of length nb, the expanded PEG-CRT LDPC codes have better bit error rate (BER) performance with the iterative decoding. It is also shown that compared with PEG LDPC codes of length n, which constructed with higher complexities, the PEG-CRT codes have similar BER performance.
Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.