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.
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.
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).
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.
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
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.
In this paper, two iterative message passing algorithms based on belief propagation proposed for the decoding of any binary linear block code are compared. The innovation of these algorithms lies in the fact that the structure of the graph of the parity check matrix is adaptively modified to render it suitable to belief propagation decoding. The modification is done such that the least reliable bits received from the channel are leaves of the graph. These algorithms perform favorably when compared with existing hard and iterative soft decision decoding algorithms in terms of error rate while maintaining a complexity polynomial in block length. It was found that while these two algorithms are conceptually similar, their performance in terms of word error rate (as a function of signal-to-noise ratio), decoding time (average number of iterations) and the updated bit reliabilities are very different
A novel belief propagation(BP) decoding algorithm for convolutional low-density parity-check codes is proposed.The proposed algorithm raises the efficiency of updating the variable information by applying feedback information at each decoding iteration and employs the weighting factor to reduce the error propagation caused by the cycles in the Tanner graph,thus yielding a faster convergence of the decoding.Simulation results show that an error performance better than that of the existing belief propagation algorithm can be achieved,while the 5/8 decoding delay and the computation complexity are effectively reduced.Compared with the existing BP,the proposed algorithm achieves a gain of 0.16dB at the BER of 10-6 with the same number of iterations.