Decoding methods: Difference between revisions

Revision as of 10:33, 7 June 2015

Revision as of 18:51, 1 July 2015

Line 23:

{{See|Maximum likelihood}}

Given a received codeword <math>x \in \mathbb{F}_2^n</math> '''[[maximum likelihood]] decoding''' picks a codeword <math>y \in C</math> tothat [[Optimization (mathematics)|maximize]]:s

:<math>\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})</math>,

i.e.that chooseis, the codeword <math>y</math> that maximizes the probability that <math>x</math> was received, [[conditional probability|given that]] <math>y</math> was sent. Note that ifIf all codewords are equally likely to be sent then this scheme is equivalent to ''ideal observer decoding''.

In fact, by [[Bayes Theorem]] we have,

:<math>

Line 49:

is maximised, and the claim follows.

As with ''ideal observer decoding'', a convention must be agreed to for non-unique decoding.

The MLmaximum likelihood decoding problem can also be modeled as an [[integer programming]] problem.<ref name = feldman>"{{cite article | title=Using linearLinear programmingProgramming to Decode Binary linearLinear codes,"Codes J.| first1=Jon | last1=Feldman, M.|first2=Martin J. | last2=Wainwright and| first3=David D.R. | last3=Karger, | journal=IEEE Transactions on Information Theory, | volume=51:954-972, | issue=3 | pages=954–972 | month=March | year=2005 | doi=10.1109/TIT.2004.842696}}</ref>

The MLmaximum likelihood decoding algorithm has been found to beis an instance of the MPF"marginalize a product function" problem which is solved by applying the [[generalized distributive law]]. <ref name=GenDistLaw>{{cite journal |last last1=Aji |first first1=S.Srinivas M. |author2 last2=McEliece, R.| first2=Robert J. | title=The generalizedGeneralized distributiveDistributive Law law| journal=Information Theory, IEEE Transactions on Information Theory |date month=MarMarch | year=2000 | volume=46 | issue=2 | pages=325–343 | doi=10.1109/18.825794|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=825794&isnumber=17872}}</ref>

==Minimum distance decoding==