On iterative decoding of high-density parity-check codes using edge-local complementation
MetadataShow full item record
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
Paper I: Lecture Notes in Computer Science 5228, Knudsen, J. G., Riera, C., Parker, M. G., Rosnes, E., Adaptive soft-decision decoding using edge local complementation, pp. 82-94. Copyright 2008 Springer. All rights reserved. Accepted version. The published version is available at: http://dx.doi.org/10.1007/978-3-540-87448-5_10Paper II: Knudsen, J. G.; Riera, C.; Danielsen, L. E.; Parker, M. G;, Rosnes, E., Iterative decoding on multiple Tanner graphs using random edge local complementation, pp. 899–903. In IEEE International Symposium on Information Theory, ISIT, Seoul, Korea, Jun./Jul. 2009. Copyright 2009 IEEE. All rights reserved. Accepted version. The published version is available at: http://dx.doi.org/10.1109/ISIT.2009.5205625Paper III: Knudsen, J. G.; Riera, C.; Danielsen, L. E.; Parker, M. G.; Rosnes, E. (2010), Random edge-local complementation with applications to iterative decoding of HDPC codes. Technical Report no. 395, Department of Informatics, University of Bergen, Norway, Aug. 2010. Submitted version. Submitted to IEEE Trans. Inform. Theory, 2010.Paper IV: Knudsen, J. G.; Riera, C.; Danielsen, L. E.; Parker, M. G.; Rosnes, E., Improved adaptive belief propagation decoding using edge-local complementation. pp. 774–778. In IEEE International Symposium on Information Theory Proceedings (ISIT). Austin,Texas, Jul. 2010. Copyright 2010 IEEE. All rights reserved. Accepted version. The published version is available at: http://dx.doi.org/10.1109/ISIT.2010.5513625Paper V: Danielsen, L. E.; Parker, M. G.; Riera, C;, Knudsen, J. G. (2010), On graphs and codes preserved by edge local complementation, 2010. arXiv:1006.5802. This paper was presented at the 10th Nordic Combinatorial Conference (NORCOM 2010), Reykjavik, Iceland, May 2010. Draft version.