Mathematical Sciences

Lund University

  • Title: Linear programming methods for decoding
  • Short description:

    The goal of the project is to compare different methods of decoding binary linear codes and find out how well they work on certain classes of codes.

  • Long description:

    One way to decode (in the sense of finding among the code words the one most likely to result in the received word) a linear error correcting code is to use integer linear programming. The decoding problem is NP-hard, so we cannot hope to find a general efficient and exact decoding algorithm. One way to handle this problem is to change the problem a bit (by a method called relaxation) into a linear programming problem that can be efficiently solved. The price we have to pay is that we sometimes get an output that is not a codeword. (Called a pseudocodeword.) A suggestion for project here is to study different ways of relaxing the problem and how that works for some well know types of binary linear codes. Depending on the interests of the student this could be done by implementing and comparing the performance of a couple of methods or by learning more about the theoretical properties of codes for which the relaxation method works well.

  • Contact: Anna Torstensson