Prof. Dr.-Ing. Werner Henkel
Binary linear codes are one of the main tools for error-control coding over telecommunication channels and data storage devices. However, despite of having very simple encoder structures, their optimum decoding is usually a hard problem in practice. In 2003, Jon Feldman proposed a new general decoding method for binary linear codes. This method is based on linear programming relaxation of the ML-decoding problem of binary linear codes. Because of the well-known properties and efficient polynomial-time implementations for solving Linear Programming problems, this method has gained lots of attentions in the coding theory society. In this thesis, after a brief introduction to binary linear codes and LP decoding, we will propose some non-trivial upper and lower bounds for the performance of the LP-based decoders. Based on those bounds, we will investigate the performance of the LP-decoders on AWGN and BSC channels. Then, we will provide a new polynomial-time decoder (function of the length of the codes and number of the users) for decoding messages over a multiple-access channel (MAC) using LP-relaxation of the classical problem of decoding messages over a MAC channel and we will investigate the performance of the new decoder over an AWGN channel. Finally, we will propose a new approach for decoding linear codes over GF(2^m) and introduce a new subclass of non-binary LDPC codes, called HLDPC codes, and based on the LDPC decoding methods over binary domains, fast decoding algorithms for such codes will be concluded immediately. At the end, based on our approach of decoding linear codes over GF(2^m), we will introduce the LP-relaxation of the ML-decoding problem of linear codes over GF(2^m) based on Feldman’s relaxation method which yields a polynomial-time algorithm (function of the length of the code and m) for decoding codes over GF(2^m).
[Thesis] Some New Results on Linear Programming Decoding