Selmer Center: Coding Theory

Foto: Jørgen Barth

Joakim Grahl Knudsen was born in Bergen, Norway, in 1979. He received B.Sc. (2004) degree in informatics, and M.Sc. (2006) and Ph.D. (2010) degrees in coding theory at the Selmer Center, Dept. of Informatics, University of Bergen, Norway. Following this, he worked as a researcher at the Dept. of Informatics until Aug. 2011. Currently, he is working in the software industry, with Webstep. His research interests are coding theory, iterative decoding algorithms, graph theory, and codes on graphs.

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.

Publications

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen, Matthew G. Parker, and Eirik Rosnes, "Random 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

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.

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.

PhD thesis

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.

Supervising Comittee

Matthew G. Parker, Eirik Rosnes and Øyvind Ytrehus