Selmer Center: Coding Theory
The focus of my research is on experimental iterative, soft-in soft-out decoding of codes on graphs. Specific modifications to the message-passing algorithms, in combination with operations which act locally on the Tanner graph, are used to improve iterative decoding on high density parity check (HDPC) codes, i.e., small, non-random codes; typically, well-known ("classical") code constructions with strong structural properties are used. So far, three conference papers have been published, based on edge-local complementation (ELC) — a graph-local operation which preserves code. The initial paper uses ELC to produce isomorphic (Tanner) graphs, during decoding, which can be compared to applying permutations from the automorphism group of the code. The second paper uses ELC in an entirely random fashion, on extended quadratic residue codes, for the effect of producing non-isomorphic (Tanner) graphs.
The third paper further analyzes the properties of ELC, such that its effect on the Tanner graph may be predicted. For instance, we explore the subgraphs on which ELC has the effect of not increasing the weight of the Tanner graph beyond a specified threshold. We call this weight-bounding ELC.
The fourth paper proposes an adaptive application of ELC to affect the inferred error positions, by exploiting the effects of ELC on the Tanner graph. This effect, in short, is to make columns corresponding to weak positions weight-1 (systematic) in the corresponding parity-check matrix, such that the weaker positions may not take part in any cycles.
These papers comprise my 2010 PhD thesis, which joins them together in the common context of ELC and iterative SISO decoding of HDPC codes.
Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen, Matthew
G. Parker, and Eirik Rosnes,
Edge-Local Complementation With Applications to Iterative Decoding of
High-Density Parity-Check Codes", IEEE Transactions on
Communications 60 (10), pp. 2796 - 2808. Oct. 2012
Preprint version, Department of Informatics, University of Bergen, Norway, Tech. Report no. 395, Aug. 2010.
Lars Eirik Danielsen, Matthew G. Parker, Constanza Riera, and Joakim Grahl Knudsen. "On graphs and codes preserved by edge local complementation", submitted for publication 2010, (arXiv).
Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen, Matthew G. Parker, and Eirik Rosnes, "Improved Adaptive Belief Propagation Decoding Using Edge-Local Complementation", Proceedings of IEEE International Symposium on Information Theory (ISIT 2010), Austin, Texas, 2010.
Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen, Matthew G. Parker, and Eirik Rosnes, "On iterative decoding of HDPC codes using weight-bounding graph operations", Proceedings of 21st International Zürich Seminar on Communications (IZS 2010), Zürich, Switzerland, 2010.
Also presented at the HDPCC Workshop, Tel Aviv University, Israel, 2010.Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen, Matthew G. Parker, and Eirik Rosnes, "Iterative Decoding on Multiple Tanner Graphs Using Random Edge Local Complementation," Proceedings of IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, 2009.
Joakim Grahl Knudsen, Constanza Riera, Matthew G. Parker, and Eirik Rosnes, "Adaptive Soft-Decision Iterative Decoding Using Edge Local Complementation," Proceedings of The Second International Castle Meeting on Coding Theory and Applications (2ICMCTA), LNCS, Medina del Campo (Valladolid), Spain, 2008.
Joakim Grahl Knudsen, "On Iterative Decoding of High-Density Parity-Check Codes Using Edge-Local Complementation", Aug. 2010.
Masters thesis (MsC)
Joakim Grahl Knudsen," Randomised Construction and Dynamic Decoding of LDPC Codes," Nov. 2005.
Updated September 2013, J. G. Knudsen