Linear programming decoding

In information theory and coding theory, linear programming decoding (LP decoding) is a decoding method which uses concepts from linear programming (LP) theory to solve decoding problems. This approach was first used by Jon Feldman et al.[1] They showed how the LP can be used to decodes block codes.

The basic idea behind LP decoding is to first represent the maximum likelihood decoding of a linear code as an integer linear program, and then relax the integrality constraints on the variables into linear inequalities.

References

  1. ↑ "Using linear programming to Decode Binary linear codes," J. Feldman, M.J. Wainwright and D.R. Karger, IEEE Transactions on Information Theory, 51:954–972, March 2005.


This article is issued from Wikipedia - version of the 9/14/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.