Regular and irregular progressive edge-growth tanner graphs

2005/01/01 by Xiao-Yu Hu, Xiaoyu Hu, Evangelos Eleftheriou +3 · 62 citations
Computer Science · Engineering · Biochemistry, Genetics and Molecular Biology · #Error Correcting Code Techniques #Advanced Wireless Communication Techniques #DNA and Biological Computing

paper · doi:10.1109/tit.2004.839541

Abstract

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.

Cited by

• Deterministic Constructions of Compressed Sensing Matrices From Unitary Geometry
• PEG-Like Design of Binary QC-LDPC Codes Based on Detecting and Avoiding Generating Small Cycles
• On the Intractability of the Minimum Distance Problem for Regular LDPC Codes
• Message-Passing Algorithms for Counting Short Cycles in a Graph
• A Survey on Trapping Sets and Stopping Sets
• Windowed Decoding of Spatially Coupled Codes
• Design of regular (2,d/sub c/)-LDPC codes over GF(q) using their binary images
• Extended Non-Binary Low-Density Parity-Check Codes over Erasure Channels
• Multi-Edge type Unequal Error Protection LDPC codes
• Study of Structured Root-LDPC Codes and PEG Techniques for Block-Fading Channels
• Protograph-Based Raptor-Like LDPC Codes
• LDPC Codes from Latin Squares Free of Small Trapping Sets
• Rate-Adaptive Protograph-Based MacKay-Neal Codes
• Joint Detection/Decoding Algorithms for Nonbinary LDPC Codes over ISI Channels
• Polarized Low-Density Parity-Check Codes on the BSC
• Sparse Signatures with Forward Error Correction Coding for Non-Orthogonal Massive Access
• Code Annealing and the Suppressing Effect of the Cyclically Lifted LDPC Code Ensemble
• Girth-12 Quasi-Cyclic LDPC Codes with Consecutive Lengths
• Efficient Probabilistic Parity Shaping for Irregular Repeat-Accumulate LDPC Codes
• Efficient Encoding Algorithm of Binary and Non-Binary LDPC Codes Using Block Triangulation
• Structured LDPC Codes from Permutation Matrices Free of Small Trapping\n Sets
• Circulant Arrays on Cyclic Subgroups of Finite Fields: Rank Analysis and Construction of Quasi-Cyclic LDPC Codes
• Design of Irregular SC-LDPC Codes With Non-Uniform Degree Distributions by Linear Programing
• OTFS Signaling for Uplink NOMA of Heterogeneous Mobility Users
• A Branch-and-Cut Algorithm to Design LDPC Codes without Small Cycles in Communication Systems
• Scheduled-PEG construction of LDPC codes for Upper-Layer FEC
• Optimized Rate-Adaptive Protograph-Based LDPC Codes for Source Coding with Side Information
• GF(2^m) Low-Density Parity-Check Codes Derived from Cyclotomic Cosets
• Structured sublinear compressive sensing via belief propagation
• High Girth Spatially-Coupled LDPC Codes with Hierarchical Structure
• Counting Short Cycles in Bipartite Graphs: A Fast Technique/Algorithm and a Hardness Result
• Rate-Compatible LDPC Codes Based on Puncturing and Extension Techniques for Short Block Lengths
• Deterministic Constructions of Binary Measurement Matrices from Finite Geometry
• Repeat Accumulate Based Designs for LDPC Codes on Fading Channels
• Compressive Sensing Using Low Density Frames
• Reliable communication over non-binary insertion/deletion channels
• Joint Network and LDPC Coding for Bi-directional Relaying
• Quasi Cyclic LDPC Codes Based on Finite Set Systems
• Lattice Index Codes from Algebraic Number Fields
• Some problems of Graph Based Codes for Belief Propagation decoding
• Quasi-cyclic LDPC codes with high girth
• Study of Knowledge-Aided Iterative Detection and Decoding for Multiuser MIMO Systems
• DNA Barcoding through Quaternary LDPC Codes. [europepmc]
• Trellis Tone Modulation Multiple-Access for Peer Discovery in D2D Networks. [europepmc]
• High speed error correction for continuous-variable quantum key distribution with multi-edge type LDPC code. [europepmc]
• Adaptive Rate-Compatible Non-Binary LDPC Coding Scheme for the B5G Mobile System. [europepmc]
• Design of a Labeling Scheme for 32-QAM Delayed Bit-Interleaved Coded Modulation. [europepmc]
• High-throughput GPU layered decoder of quasi-cyclic multi-edge type low density parity check codes in continuous-variable quantum key distribution systems. [europepmc]
• Constructing LDPC Codes with Any Desired Girth. [europepmc]
• High-Efficient Syndrome-Based LDPC Reconciliation for Quantum Key Distribution. [europepmc]
• A Nonbinary LDPC-Coded Probabilistic Shaping Scheme for a Rayleigh Fading Channel. [europepmc]
• Protograph Designing of P-LDPC Codes via M 3 Method. [europepmc]
• Lossy P-LDPC Codes for Compressing General Sources Using Neural Networks. [europepmc]
• Design and Analysis of Joint Group Shuffled Scheduling Decoding Algorithm for Double LDPC Codes System. [europepmc]
• Analysis and Optimization of a General Linking Matrix for JSCC Scheme Based on Double LDPC Codes. [europepmc]
• Design and Optimization of Linking Matrix for a JSCC System Based on DP-LDPC Codes. [europepmc]
• Design of Low-Density Parity-Check Code Pair for Joint Source-Channel Coding Systems Based on Graph Theory. [europepmc]
• Improved PEG-Based Construction of Analog Fountain Codes. [europepmc]
• LDPC Codes on Balanced Incomplete Block Designs: Construction, Girth, and Cycle Structure Analysis. [europepmc]
• An Efficient Two-Stage Decoding Scheme for LDPC-CRC Concatenated Codes. [europepmc]
• High-Efficiency Lossy Source Coding Based on Multi-Layer Perceptron Neural Network. [europepmc]
• Construction of Efficient High-Rate Protograph QC-LDPC Codes by Joint EXIT Chart, PEG, AWD, and QC-NLACE Techniques [europepmc]

Related

• A Unifying Framework to Construct QC-LDPC Tanner Graphs of Desired Girth
• Necessary and Sufficient Girth Conditions for LDPC Tanner Graphs with\n Denser Protographs
• Necessary and Sufficient Girth Conditions for Tanner Graphs of\n Quasi-Cyclic LDPC Codes
• Edge Coloring Technique to Remove Small Elementary Trapping Sets from Tanner Graph of QC-LDPC Codes with Column Weight 4
• On the Intractability of the Minimum Distance Problem for Regular LDPC Codes