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

On iterative decoding of high-density parity-check codes using edge-local complementation

Joakim Grahl Knudsen

Published Nov 24, 2010• 0 citations
OpenAlex

Abstract

The overall topic of this work is a graph operation known as edgelocal complementation (ELC) and its applications to iterative decoding of classical codes. Although these legacy codes are arguably not well-suited for graph-based decoding, they have other desirable properties resulting in much current research on the general problem of forging this alloy. From this perspective, these codes are typically referred to as highdensity parity-check codes. Our approach is to gain diversity by means of ELC. Based on the known link between ELC and the information sets of a code, C, we identify a one-to-one relationship between ELC operations and the automorphism group of a code, Aut(C). With respect to a specific parity-check matrix, H, we classify these code-preserving permutations into trivial and nontrivial permutations, based on whether the matrix is preserved (under ELC) up to row permutations, or not. The corresponding iso-ELC operations preserve the structure of the graph, and simulation data are presented on the performance benefit of using iso-ELC operations as a source of diversity. Generalizing this to random (noniso) ELC, we explore the benefits of a simplified, entirely graph-local (i.e., distributive) implementation of ELC-based decoding. Special codes are chosen, which are structurally well-suited for this type of random ELC decoding. At an extreme, certain codes are ELCpreserved, in that any ELC operation is an iso-ELC operation. Although less useful from a coding perspective, the corresponding graphs are interesting to determine and classify. However, in the general case, we observe negative effects of random ELC, which causes the weight of the graph to increase. Based on this, we explore the specific structural properties which determine which ELC operations (i.e., which edges of a graph) are desirable for ELC, from a decoding perspective. This is dominated by the weight increase (in terms of number of new edges) resulting from ELC, which also causes detrimental short cycles, so we identify the graphical conditions (i.e., subgraphs) for which ELC is weight-bounding ELC (WB-ELC). These operations are used to reduce the weight of a systematic H (given a code), and also used in a proposed decoder based on WB-ELC. At a slightly different approach, we also apply ELC operations in an adaptive decoding scheme. As ELC is a local operation, we can, to a certain extent, target the (inferred) least reliable positions specifically. This is a well-known technique to improve decoding, normally implemented via Gaussian elimination, which we improve by using beneficial properties of the ELC operation

Related papers

Random Edge-Local Complementation with Applications to Iterative Decoding of High-Density Parity-Check Codes

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen +2 more

We describe the application of edge-local complementation (ELC) to a Tanner graph associated with a binary linear code, C. Various properties of ELC are described, mainly the special case of isomorphic ELC operations and the relationship to the automorphism group of the code, Aut(C), and the generalization of ELC to weight-bounding ELC (WB-ELC) operations under which the number of edges remains upper-bounded. ELC generates all systematic parity-check matrices (the orbit) of the code, so WB-ELC facilitates a restriction to low-weight matrices of this orbit. We propose using ELC and WB-ELC as a source of diversity, to improve iterative soft-input soft-output decoding of high-density parity-check (HDPC) codes, with the sum-product algorithm (SPA). A motivation of ELC-enhanced SPA decoding is locality; that diversity is achieved by local graph action, and is well-suited to the local actions that constitute the SPA and allows for parallel software implementation. Simulation data on the error-rate performance of the proposed SPA-ELC and SPA-WBELC iterative decoding algorithms is shown for several HDPC codes. A gain is reported over SPA decoding, and over a recently proposed algorithm to decode HDPC codes using permutations from Aut(C). ELC-enhanced decoding extends the scope of iterative decoding to codes with trivial Aut(C).

IEEE Transactions on Communications•Aug 13, 2012•0 citations

On iterative decoding of HDPC codes using weight-bounding graph operations

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen +2 more

Abstract—In this paper, we extend our work on iterative softinput soft-output (SISO) decoding of high density parity check (HDPC) codes. Edge-local complementation (ELC) is a graph operationwhichcanbeusedtogivestructuralredundancyduring decoding with the sum-product algorithm (SPA). We describe the specific subgraphs required for ELC to not increase the weight of the Tanner graph beyond a specified upper bound. We call this controlled operation weight-bounding ELC (WB-ELC). A generalized iterative SISO HDPC decoder is described, which can be configured to employ different operations; most importantly, ‘flooding ’ SPA, and iterative ‘permutation decoding. ’ The latter is a state-of-the-art decoding algorithm for HDPC codes, using permutations from the automorphism group of the code. We observe performance improvements when the SISO HDPC decoder is configured to use WB-ELC, as compared to using ELC, or even permutation decoding. I.

•Jan 1, 2010•3 citations

Improved adaptive belief propagation decoding using edge-local complementation

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen +2 more

This work is an extension of our previous work on an iterative soft-decision decoder for high-density parity-check codes, using a graph-local operation known as edge-local complementation (ELC). Inferred least reliable codeword positions are targeted by an ELC stage in between sum-product algorithm iterations. A gain is shown over related iterative decoding algorithms - mainly due to an improved heuristic to determine optimum ELC locations in the Tanner graph - both in error-rate performance, as well as complexity in terms of a significant reduction in the required number of ELC operations. We also present a novel damping operation, generalized to the graph-local setting where extrinsic information remains on edges not affected by ELC.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•2 citations

Iterative decoding on multiple tanner graphs using random edge local complementation

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen +2 more

In this paper, we propose to enhance the performance of the sum-product algorithm (SPA) by interleaving SPA iterations with a random local graph update rule. This rule is known as edge local complementation (ELC), and has the effect of modifying the Tanner graph while preserving the code. We have previously shown how the ELC operation can be used to implement an iterative permutation group decoder (SPA-PD)-one of the most successful iterative soft-decision decoding strategies at small blocklengths. In this work, we exploit the fact that ELC can also give structurally distinct parity-check matrices for the same code. Our aim is to describe a simple iterative decoder, running SPA-PD on distinct structures, based entirely on random usage of the ELC operation. This is called SPA-ELC, and we focus on small blocklength codes with strong algebraic structure. In particular, we look at the extended Golay code and two extended quadratic residue codes. Both error rate performance and average decoding complexity, measured by the average total number of messages required in the decoding, significantly outperform those of the standard SPA, and compares well with SPA-PD. However, in contrast to SPA-PD, which requires a global action on the Tanner graph, we obtain a performance improvement via local action alone. Such localized algorithms are of mathematical interest in their own right, but are also suited to parallel/distributed realizations.

arXiv:0905.4164•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•8 citations

On iterative decoding of short codes

Shacham Nimrod, Ofer Amrani

This paper is concerned with iterative decoding of short error correcting codes having high density parity check matrices (HDPC Codes). There is a need for reliable graph-based iterative decoding of short codes; for instance this is beneficial in the framework of a newly introduced random version of OFDMA (R-OFDMA) [1]. We first note how the structure of the parity check matrix can alter an iterative decoder's performance. Specifically we focus on the allowable redundancies in the matrices, where it is possible to benefit from inserting redundant parity checks without altering the code properties. We then employ computation tree analysis and density evolution which both support simulation results showing a performance improvement.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2016•0 citations

Iterative Decoding of Codes on Graphs

Sundararajan Sankaranarayanan

The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.

•Jan 1, 2006•0 citations
The overall topic of this work is a graph operation known as edgelocal complementation (ELC) and its applications to iterative decoding of classical codes. Although these legacy codes are arguably not well-suited for graph-based decoding, they have other desirable properties resulting in much current research on the general problem of forging this alloy. From this perspective, these codes are typically referred to as highdensity parity-check codes. Our approach is to gain diversity by means of ELC. Based on the known link between ELC and the information sets of a code, C, we identify a one-to-one relationship between ELC operations and the automorphism group of a code, Aut(C). With respect to a specific parity-check matrix, H, we classify these code-preserving permutations into trivial and nontrivial permutations, based on whether the matrix is preserved (under ELC) up to row permutations, or not. The corresponding iso-ELC operations preserve the structure of the graph, and simulation data are presented on the performance benefit of using iso-ELC operations as a source of diversity. Generalizing this to random (noniso) ELC, we explore the benefits of a simplified, entirely graph-local (i.e., distributive) implementation of ELC-based decoding. Special codes are chosen, which are structurally well-suited for this type of random ELC decoding. At an extreme, certain codes are ELCpreserved, in that any ELC operation is an iso-ELC operation. Although less useful from a coding perspective, the corresponding graphs are interesting to determine and classify. However, in the general case, we observe negative effects of random ELC, which causes the weight of the graph to increase. Based on this, we explore the specific structural properties which determine which ELC operations (i.e., which edges of a graph) are desirable for ELC, from a decoding perspective. This is dominated by the weight increase (in terms of number of new edges) resulting from ELC, which also causes detrimental short cycles, so we identify the graphical conditions (i.e., subgraphs) for which ELC is weight-bounding ELC (WB-ELC). These operations are used to reduce the weight of a systematic H (given a code), and also used in a proposed decoder based on WB-ELC. At a slightly different approach, we also apply ELC operations in an adaptive decoding scheme. As ELC is a local operation, we can, to a certain extent, target the (inferred) least reliable positions specifically. This is a well-known technique to improve decoding, normally implemented via Gaussian elimination, which we improve by using beneficial properties of the ELC operation
We describe the application of edge-local complementation (ELC) to a Tanner graph associated with a binary linear code, C. Various properties of ELC are described, mainly the special case of isomorphic ELC operations and the relationship to the automorphism group of the code, Aut(C), and the generalization of ELC to weight-bounding ELC (WB-ELC) operations under which the number of edges remains upper-bounded. ELC generates all systematic parity-check matrices (the orbit) of the code, so WB-ELC facilitates a restriction to low-weight matrices of this orbit. We propose using ELC and WB-ELC as a source of diversity, to improve iterative soft-input soft-output decoding of high-density parity-check (HDPC) codes, with the sum-product algorithm (SPA). A motivation of ELC-enhanced SPA decoding is locality; that diversity is achieved by local graph action, and is well-suited to the local actions that constitute the SPA and allows for parallel software implementation. Simulation data on the error-rate performance of the proposed SPA-ELC and SPA-WBELC iterative decoding algorithms is shown for several HDPC codes. A gain is reported over SPA decoding, and over a recently proposed algorithm to decode HDPC codes using permutations from Aut(C). ELC-enhanced decoding extends the scope of iterative decoding to codes with trivial Aut(C).
Abstract—In this paper, we extend our work on iterative softinput soft-output (SISO) decoding of high density parity check (HDPC) codes. Edge-local complementation (ELC) is a graph operationwhichcanbeusedtogivestructuralredundancyduring decoding with the sum-product algorithm (SPA). We describe the specific subgraphs required for ELC to not increase the weight of the Tanner graph beyond a specified upper bound. We call this controlled operation weight-bounding ELC (WB-ELC). A generalized iterative SISO HDPC decoder is described, which can be configured to employ different operations; most importantly, ‘flooding ’ SPA, and iterative ‘permutation decoding. ’ The latter is a state-of-the-art decoding algorithm for HDPC codes, using permutations from the automorphism group of the code. We observe performance improvements when the SISO HDPC decoder is configured to use WB-ELC, as compared to using ELC, or even permutation decoding. I.
This work is an extension of our previous work on an iterative soft-decision decoder for high-density parity-check codes, using a graph-local operation known as edge-local complementation (ELC). Inferred least reliable codeword positions are targeted by an ELC stage in between sum-product algorithm iterations. A gain is shown over related iterative decoding algorithms - mainly due to an improved heuristic to determine optimum ELC locations in the Tanner graph - both in error-rate performance, as well as complexity in terms of a significant reduction in the required number of ELC operations. We also present a novel damping operation, generalized to the graph-local setting where extrinsic information remains on edges not affected by ELC.
In this paper, we propose to enhance the performance of the sum-product algorithm (SPA) by interleaving SPA iterations with a random local graph update rule. This rule is known as edge local complementation (ELC), and has the effect of modifying the Tanner graph while preserving the code. We have previously shown how the ELC operation can be used to implement an iterative permutation group decoder (SPA-PD)-one of the most successful iterative soft-decision decoding strategies at small blocklengths. In this work, we exploit the fact that ELC can also give structurally distinct parity-check matrices for the same code. Our aim is to describe a simple iterative decoder, running SPA-PD on distinct structures, based entirely on random usage of the ELC operation. This is called SPA-ELC, and we focus on small blocklength codes with strong algebraic structure. In particular, we look at the extended Golay code and two extended quadratic residue codes. Both error rate performance and average decoding complexity, measured by the average total number of messages required in the decoding, significantly outperform those of the standard SPA, and compares well with SPA-PD. However, in contrast to SPA-PD, which requires a global action on the Tanner graph, we obtain a performance improvement via local action alone. Such localized algorithms are of mathematical interest in their own right, but are also suited to parallel/distributed realizations.
This paper is concerned with iterative decoding of short error correcting codes having high density parity check matrices (HDPC Codes). There is a need for reliable graph-based iterative decoding of short codes; for instance this is beneficial in the framework of a newly introduced random version of OFDMA (R-OFDMA) [1]. We first note how the structure of the parity check matrix can alter an iterative decoder's performance. Specifically we focus on the allowable redundancies in the matrices, where it is possible to benefit from inserting redundant parity checks without altering the code properties. We then employ computation tree analysis and density evolution which both support simulation results showing a performance improvement.
The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.