Decoding methods: Difference between revisions

Revision as of 16:17, 12 July 2015

Revision as of 09:12, 5 August 2015

Line 1:

{{Expert-verifysubject|date=June 2010}}

In [[coding theory]], '''decoding''' is the process of translating received messages into [[codewords]] of a given [[code]]. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a [[noisy channel]], such as a [[binary symmetric channel]].

Line 21:

==Maximum likelihood decoding==

{{SeeFurther|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> that [[Optimization (mathematics)|maximize]]s

Line 51:

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

The maximum likelihood decoding problem can also be modeled as an [[integer programming]] problem.<ref name = feldman>{{cite articlenews | title=Using Linear Programming to Decode Binary Linear Codes | first1=Jon | last1=Feldman |first2=Martin J. | last2=Wainwright | first3=David R. | last3=Karger | journal=IEEE Transactions on Information Theory | volume=51 | issue=3 | pages=954–972 |date=March 2005 | doi=10.1109/TIT.2004.842696}}</ref>

The maximum likelihood decoding algorithm is an instance of the "marginalize a product function" problem which is solved by applying the [[generalized distributive law]].<ref name=GenDistLaw>{{cite journal | last1=Aji | first1=Srinivas M. | last2=McEliece | first2=Robert J. | title=The Generalized Distributive Law | journal=IEEE Transactions on Information Theory |date=March 2000 | volume=46 | issue=2 | pages=325–343 | doi=10.1109/18.825794}}</ref>

Line 139:

* {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | publisher=[[Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | year=1986 | isbn=0-19-853803-0 }}

* {{cite book | last = Pless | first = Vera | authorlink=Vera Pless | title = Introduction to the theory of error-correcting codes | publisher = [[John Wiley & Sons]]|series = Wiley-Interscience Series in Discrete Mathematics | year = 1982| isbn = 0-471-08684-3 }}

* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | year=1992 | isbn=3-540-54894-7 }}

== References ==