Linear programming decoding: Difference between revisions
Content deleted Content added
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
In [[information theory]] and [[coding theory]], '''linear programming decoding (LP decoding)''' is a [[Decoding methods|decoding]] method which uses concepts from [[Linear programming|LP]] theory to solve decoding problems. This approach was first used by Jon Feldman ''et al.''<ref name = feldman> "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.</ref> They showed how the LP can be used to decodes block codes. |
In [[information theory]] and [[coding theory]], '''linear programming decoding (LP decoding)''' is a [[Decoding methods|decoding]] method which uses concepts from [[Linear programming|LP]] theory to solve decoding problems. This approach was first used by Jon Feldman ''et al.''<ref name = feldman> "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.</ref> 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#Maximum_likelihood_decoding|maximum likelihood decoding]] of a linear error-correcting code as an [[Integer_linear_programming|integer linear program]], and then [[Linear_programming_relaxation|relax]] the integrality constraints on the variables into linear inequalities. |
|||
== References == |
== References == |
||
Revision as of 18:21, 1 August 2012
In information theory and coding theory, linear programming decoding (LP decoding) is a decoding method which uses concepts from 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 error-correcting code as an integer linear program, and then relax the integrality constraints on the variables into linear inequalities.
References
- ^ "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 applied mathematics–related article is a stub. You can help Wikipedia by expanding it. |