Linear Programming Based Decoding Algorithms for Binary Linear Block Codes
Project Description
The optimization research group works on integer programming methods for coding algorithms in the framework of the project "Computational Mathematical Modelling for advanced System-On-Chip Design" of the Center for Mathematical and Computational Modelling.
In coding theory we are concerned with the following problem: a sender transmits information to a receiver over a channel which may cause some random errors on the information. Main tasks in this process are encoding at the sender side and decoding at the receiver side. Coding theory makes use of mathematics and especially optimization in various research areas.
Research Team
PIs:
- Prof. Dr. Horst Hamacher (AG Optimization)
- Prof. Dr. Norbert Wehn (Microelectronic System Design Group)
Members:
- Dr. Frank Kienle (Microelectronic System Design Group)
- Jun.-Prof. Dr. Stefan Ruzika (AG Optimization)
- Dipl.-Math. Michael Helmling (AG Optimization)
- Dipl.-Ing. Stefan Scholl (Microelectronic System Design Group)
Former Members:
- Dr. Akin Tanatmis (AG Optimization)
Integration in Teaching
- Selected topics have been discussed in seminars in winter semester 08/09, summer semester 2009, and winter semester 11/12.
- State examination, thesis: S. Heupel, Cycle polytopes and their application in coding theory, July 2009.
- Reading Course WS 2009/10: K. Kalda, Duality in Mathematical Programming Based Decoding and Relationship to Message Passing Algorithms, March 2010.
- State examination, thesis: B. Thome, Ein spezialisierter LP-Löser für Maximum-Likelihood-Dekodierung binärer linearer Codes, April 2010.
- MSc, thesis: K. Kalda, Message Passing, Duality, and LP Decoding, October 2010.
- Diploma thesis: M. Helmling, Band Matrix Constrained Optimization Problems with Applications in Coding Theory, January 2011.
- PhD., thesis: A. Tanatmis, Mathematical Programming Approaches for Decoding of Linear Block Codes, January 2011.
- Diploma thesis: A. Hiller, Constructing Efficient LP-Formulations for Maximum Likelihood Decoding, October 2011
- Diploma thesis: F. Gensheimer, Quadratic Network Flow Problems, April 2012
- Diploma thesis: P. Vijakumar: Belief Propagation in Combinatorial Optimization, April 2012
- One PhD thesis and one diploma thesis are currently in progress.
Students interested in writing a thesis within this project may contact Stefan Ruzika.
Workshops and Talks
S. Ruzika, A Separation Algorithm for Improved Linear Programming-Decoding of Linear Block Codes, 5th International Symposium on Turbo Codes & Related Topics, September 1 - 5 2008, Lausanne.
A. Tanatmis, New Valid Inequalities for the LP Decoding of Binary Linear Block Codes, IEEE International Symposium on Information Theory, June 28-July 3 2009, Seoul.
M. Punekar and A. Tanatmis, Mathematical optimization based decoding, (CM)2- seminar winter semester 09/10, December 12, Kaiserslautern.
A. Tanatmis, Numerical comparison of IP formulations in ML decoding and minimum distance calculation, Workshop „Linear Programming and Message-Passing Approaches to High-Density Parity-Check Codes and High-Density Graphical Models“, March 1-2 2010, Tel Aviv.
- M. Helmling: On the computation of „distance properties“ of 3D turbo codes, November 22 2010, University of Bergen, Norway.
M. Helmling, S. Scholl, Mathematical Optimization Based Channel Coding: Current Achievements and Future Challenges, (CM)² Young Researcher Symposium, February 15 2011, Kaiserslautern.
Workshop (Co-)Organization
- Yair Be'ery, Michael Chertkov, Stefan Ruzika, Pascal O. Vontobel, Organization of „International Workshop on Linear Programming and Message-Passing Approaches to High-Density Parity-Check Codes and High-Density Graphical Models“, March 1-2 2010, Tel Aviv
Publications
- A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn, A separation algorithm for improved LP-decoding of linear block codes, Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, September 1 - 5 2008.
- A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn, New Valid Inequalities for the LP Decoding of Binary Linear Block Codes, IEEE International Symposium on Information Theory, Seoul, June 28-July 3 2009.
- A. Tanatmis, S. Ruzika, M. Punekar and F. Kienle, Numerical Comparison of IP Formulations as ML decoders, accepted, International Conference on Communications, Cape Town, May 23 - 27 2010. Complementary numerical experiments
- A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn, A separation algorithm for improved LP-decoding of linear block codes, accepted, IEEE Transactions on Information Theory, 2010.
- A. Tanatmis, S. Ruzika and F. Kienle, A Lagrangian relaxation based decoding algorithm for LTE Turbo codes, accepted, 6th International Symposium on Turbo Codes and Related Topics, in Brest, France on 6-10 September 2010.
- M. Punekar, F. Kienle, N. Wehn, A. Tanatmis, S. Ruzika and H.W. Hamacher, Calculating the Minimum Distance of Linear Block Codes via Integer Programming, accepted, 6th International Symposium on Turbo Codes and Related Topics, in Brest, France on 6-10 September 2010.
- E. Rosnes, M. Helmling, A. Graell i Amat: „Pseudocodewords of Linear Programming Decoding of 3-Dimensional Turbo Code“. Proc. IEEE Int. Symp. Inf. Theory, Saint Petersburg, Russia, July/Aug. 2011. Preprint: arXiv:1103.1559v1 [cs.IT]
- M. Helmling, S. Ruzika and A. Tanatmis: „Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms“, IEEE Transactions on Information Theory, accepted for publication. Preprint: arXiv:1107.3715v2 [cs.IT]
Contact
Prof. Dr. Horst W. Hamacher
|
AG Optimization
Department of Mathematics
67663 Kaiserslautern, Germany
University of Kaiserslautern Paul-Ehrlich-Str. 14 - 457 |
|
Junior Prof. Dr. Stefan Ruzika
|
AG Optimization
Department of Mathematics
67663 Kaiserslautern, Germany
University of Kaiserslautern Paul-Ehrlich-Str. 14 - 445 |
|