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

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