Linear programming decoding: Difference between revisions

Content deleted Content added

Inline

Revision as of 23:34, 14 September 2013

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

^ "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.

[feldman-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.

[1]

Revision as of 04:26, 12 August 2012 edit FrescoBot (talk \| contribs) Bots 1,150,735 edits m Bot: link syntax/spacing ← Previous edit		Revision as of 23:34, 14 September 2013 edit undo Duoduoduo (talk \| contribs) Extended confirmed users, Pending changes reviewers 11,085 edits spell out acronym once more Next edit →
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 code]] as an [[Integer_linear_programming\|integer linear program]], and then [[Linear_programming_relaxation\|relax]] the integrality constraints on the variables into linear inequalities.		The basic idea behind LP decoding is to first represent the [[Maximum_likelihood_decoding#Maximum_likelihood_decoding\|maximum likelihood decoding]] of a [[linear code]] as an [[Integer_linear_programming\|integer linear program]], and then [[Linear_programming_relaxation\|relax]] the integrality constraints on the variables into linear inequalities.