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:1607.05647

Design of LDPC Codes using Multipath EMD Strategies and Progressive Edge Growth

Cornelius T. Healy, Rodrigo C. de Lamare

Published Jul 19, 2016• 0 citations
arXivHTMLPDF

Abstract

Low-density parity-check (LDPC) codes are capable of achieving excellent performance and provide a useful alternative for high performance applications. However, at medium to high signal-to-noise ratios (SNR), an observable error floor arises from the loss of independence of messages passed under iterative graph-based decoding. In this paper, the error floor performance of short block length codes is improved by use of a novel candidate selection metric in code graph construction. The proposed Multipath EMD approach avoids harmful structures in the graph by evaluating certain properties of the cycles which may be introduced in each edge placement. We present Multipath EMD based designs for several structured LDPC codes including quasi-cyclic and irregular repeat accumulate codes. In addition, an extended class of diversity-achieving codes on the challenging block fading channel is proposed and considered with the Multipath EMD design. This combined approach is demonstrated to provide gains in decoder convergence and error rate performance. A simulation study evaluates the performance of the proposed and existing state-of-the-art methods.

DOI
10.48550/arxiv.1607.05647

Related papers

Design of LDPC Codes Based on Multipath EMD Strategies for Progressive Edge Growth

Cornelius T. Healy, Rodrigo C. de Lamare

Low-density parity-check (LDPC) codes are capable of achieving excellent performance and provide a useful alternative for the high-performance applications. However, at medium to high signal-to-noise ratios, an observable error floor arises from the loss of independence of messages passed under iterative graph-based decoding. In this paper, the error floor performance of the short block length codes is improved by the use of a novel candidate selection metric in code graph construction. The proposed multipath extrinsic message degree (EMD) approach avoids harmful structures in the graph by evaluating certain properties of the cycles introduced in each edge placement. We present multipath EMD-based designs for several structured LDPC codes, including quasi-cyclic and the irregular repeat accumulate codes. In addition, an extended class of the diversity-achieving codes on the challenging block fading channel is proposed and considered with the multipath EMD design. This combined approach is demonstrated to provide the gains in decoder convergence and error rate performance. A simulation study evaluates the performance of the proposed and existing state-of-the-art methods.

IEEE Transactions on Communications•Jun 10, 2016•52 citations

Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

Cornelius T. Healy

Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.

•Jul 1, 2014•4 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

Design of nested protograph-based LDPC codes with low error-floors

Matthew L. Grimes, David G. M. Mitchell

In this paper, we propose a method to design nested protograph-based low-density parity-check (LDPC) codes for network communications with low error-floors via a graph modification procedure. Lowering the error-floor of nested LDPC codes is essential for certain applications that require very low decoded error rates in moderate to high signal-to-noise-ratios (SNRs) like optical communication and data storage. The multilevel method we propose improves upon existing state-of-the-art algebraic designs by the identification and removal of harmful graph structures from nested LDPC codes, effectively improving the performance of each of the nested codes in their error-floor region. Simulation results are provided that confirm the expected performance improvement.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)•Jan 1, 2018•3 citations

The design of structured LDPC codes with algorithmic graph construction

Wojciech Sułek

Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.

Bulletin of the Polish Academy of Sciences Technical Sciences•May 30, 2022•0 citations

Decoder-Optimised Progressive Edge Growth Algorithms for the Design of LDPC Codes with Low Error Floors

Cornelius T. Healy, Rodrigo C. de Lamare

A novel construction for irregular low-density parity-check (LDPC) codes based on a modification of the Progressive Edge Growth (PEG) algorithm is presented. Edge placement of the PEG algorithm is enhanced by use of the Sum-Product algorithm in the design of the parity-check matrix. The proposed algorithm is highly flexible in block length and rate. The codes constructed by the proposed methods are tested in the AWGN channel and significant performance improvements are achieved. The flexibility of the proposed decoder optimisation operation is then shown by its use in modifying the Improved PEG (IPEG) algorithm to achieve further performance gains.

IEEE Communications Letters•Apr 27, 2012•51 citations
Low-density parity-check (LDPC) codes are capable of achieving excellent performance and provide a useful alternative for high performance applications. However, at medium to high signal-to-noise ratios (SNR), an observable error floor arises from the loss of independence of messages passed under iterative graph-based decoding. In this paper, the error floor performance of short block length codes is improved by use of a novel candidate selection metric in code graph construction. The proposed Multipath EMD approach avoids harmful structures in the graph by evaluating certain properties of the cycles which may be introduced in each edge placement. We present Multipath EMD based designs for several structured LDPC codes including quasi-cyclic and irregular repeat accumulate codes. In addition, an extended class of diversity-achieving codes on the challenging block fading channel is proposed and considered with the Multipath EMD design. This combined approach is demonstrated to provide gains in decoder convergence and error rate performance. A simulation study evaluates the performance of the proposed and existing state-of-the-art methods.
Low-density parity-check (LDPC) codes are capable of achieving excellent performance and provide a useful alternative for the high-performance applications. However, at medium to high signal-to-noise ratios, an observable error floor arises from the loss of independence of messages passed under iterative graph-based decoding. In this paper, the error floor performance of the short block length codes is improved by the use of a novel candidate selection metric in code graph construction. The proposed multipath extrinsic message degree (EMD) approach avoids harmful structures in the graph by evaluating certain properties of the cycles introduced in each edge placement. We present multipath EMD-based designs for several structured LDPC codes, including quasi-cyclic and the irregular repeat accumulate codes. In addition, an extended class of the diversity-achieving codes on the challenging block fading channel is proposed and considered with the multipath EMD design. This combined approach is demonstrated to provide the gains in decoder convergence and error rate performance. A simulation study evaluates the performance of the proposed and existing state-of-the-art methods.
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.
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.
In this paper, we propose a method to design nested protograph-based low-density parity-check (LDPC) codes for network communications with low error-floors via a graph modification procedure. Lowering the error-floor of nested LDPC codes is essential for certain applications that require very low decoded error rates in moderate to high signal-to-noise-ratios (SNRs) like optical communication and data storage. The multilevel method we propose improves upon existing state-of-the-art algebraic designs by the identification and removal of harmful graph structures from nested LDPC codes, effectively improving the performance of each of the nested codes in their error-floor region. Simulation results are provided that confirm the expected performance improvement.
Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.
A novel construction for irregular low-density parity-check (LDPC) codes based on a modification of the Progressive Edge Growth (PEG) algorithm is presented. Edge placement of the PEG algorithm is enhanced by use of the Sum-Product algorithm in the design of the parity-check matrix. The proposed algorithm is highly flexible in block length and rate. The codes constructed by the proposed methods are tested in the AWGN channel and significant performance improvements are achieved. The flexibility of the proposed decoder optimisation operation is then shown by its use in modifying the Improved PEG (IPEG) algorithm to achieve further performance gains.