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.
Notation
<math>C \subset \mathbb{F}_2^n</math> is considered a binary code with the length <math>n</math>; <math>x,y</math> shall be elements of <math>\mathbb{F}_2^n</math>; and <math>d(x,y)</math> is the distance between those elements.
Ideal observer decoding
One may be given the message <math>x \in \mathbb{F}_2^n</math>, then ideal observer decoding generates the codeword <math>y \in C</math>. The process results in this solution:
:<math>\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})</math>
For example, a person can choose the codeword <math>y</math> that is most likely to be received as the message <math>x</math> after transmission.
Decoding conventions
Each codeword does not have an expected possibility: there may be more than one codeword with an equal likelihood of mutating into the received message. In such a case, the sender and receiver(s) must agree ahead of time on a decoding convention. Popular conventions include:
:# Request that the codeword be resent automatic repeat-request.
:# Choose any random codeword from the set of most likely codewords which is nearer to that.
:# If another code follows, mark the ambiguous bits of the codeword as erasures and hope that the outer code disambiguates them
:# Report a decoding failure to the system
Maximum likelihood decoding
Given a received vector <math>x \in \mathbb{F}_2^n</math> maximum likelihood decoding picks a codeword <math>y \in C</math> that maximizes
:<math>\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})</math>,
that is, the codeword <math>y</math> that maximizes the probability that <math>x</math> was received, given that <math>y</math> was sent. If all codewords are equally likely to be sent then this scheme is equivalent to ideal observer decoding.
In fact, by Bayes' theorem,
:<math>
\begin{align}
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) & {} = \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent} )} \\
& {} = \mathbb{P}(y \mbox{ sent} \mid x \mbox{ received}) \cdot \frac{\mathbb{P}(x \mbox{ received})}{\mathbb{P}(y \mbox{ sent})}.
\end{align}
</math>
Upon fixing <math>\mathbb{P}(x \mbox{ received})</math>, <math>x</math> is restructured and
<math>\mathbb{P}(y \mbox{ sent})</math> is constant as all codewords are equally likely to be sent.
Therefore,
<math>
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})
</math>
is maximised as a function of the variable <math>y</math> precisely when
<math>
\mathbb{P}(y \mbox{ sent}\mid x \mbox{ received} )
</math>
is maximised, and the claim follows.
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.
See also
- Don't care alarm
- Error detection and correction
- Forbidden input
References
</references>