• search hit 42 of 106
Back to Result List

Advances in mathematical programming-based error-correction decoding

  • The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Michael Helmling
Referee:Stefan Ruzika, Øyvind Ytrehus, Pascal O. Vontobel
Document Type:Doctoral Thesis
Date of completion:2015/07/24
Date of publication:2015/07/24
Publishing institution:Universität Koblenz-Landau, Campus Koblenz, Universitätsbibliothek
Granting institution:Universität Koblenz, Fachbereich 3
Date of final exam:2015/07/17
Release Date:2015/07/24
GND Keyword:Decodierung; Kanalcodierung; Mathematik; Optimierung
Number of pages:ix, 219
Institutes:Fachbereich 3 / Mathematisches Institut
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoEs gilt das deutsche Urheberrecht: § 53 UrhG