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).

Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have a natural application in quantum information theory, where they correspond to ternary quantum error-correcting codes. However, these codes have so far received far less interest from coding theorists than self-dual additive codes over GF(4), which correspond to binary quantum codes. Self-dual additive codes over GF(9) have been classified up to length 8, and in this paper we extend the complete classification to codes of lengths 9 and 10. The classification is obtained by using a new algorithm that combines two graph representations of self-dual additive codes. The search space is first reduced by the fact that every code can be mapped to a weighted graph, and a different graph is then introduced that transforms the problem of code equivalence into a problem of graph isomorphism. By an extension technique, we are able to classify all optimal codes of lengths 11 and 12. There are 56 005 876 (11, 311, 5) codes and 6493 (12, 312, 6) codes. We also find the smallest codes with trivial automorphism group.

We show that (n, 2 n ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 n ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.

Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have previously been classified up to length 8. In this paper, all codes of length 9 and 10 are classified, using a new algorithm that combines two graph representations of codes. First, the search space is reduced by the fact that every self-dual additive code can be mapped to a weighted graph. Then a different graph is described that transforms the problem of code equivalence into a problem of graph isomorphism.

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.