In communication theory and coding theory, decoding is the process of translating received messages into codewords of a given code. This article discusses common methods of mapping messages to codewords. These methods are often used to recover messages sent over a noisy channel, such as a binary symmetric channel.

Notation

Ideal observer decoding

:$\backslash mathbb\{P\}(y\; \backslash mbox\{\; sent\}\; \backslash mid\; x\; \backslash mbox\{\; received\})$

i.e. choose the codeword $y$ that is most likely to be received as the message $x$ after transmission.

Decoding conventions

Maximum likelihood decoding

Given a received codeword $x\; \backslash in\; \backslash mathbb\{F\}\_2^n$ maximum likelihood decoding picks a codeword $y\; \backslash in\; C$ to maximize:

:$\backslash mathbb\{P\}(x\; \backslash mbox\{\; received\}\; \backslash mid\; y\; \backslash mbox\{\; sent\})$

i.e. choose the codeword $y$ that maximizes the probability that $x$ was received, given that $y$ was sent. Note that if all codewords are equally likely to be sent then this scheme is equivalent to ''ideal observer decoding''. In fact, by Bayes Theorem we have

:

Now, note that $\backslash mathbb\{P\}(x\; \backslash mbox\{\; received\})$ is fixed as $x$ is fixed and $\backslash mathbb\{P\}(y\; \backslash mbox\{\; sent\})$ is constant as all codewords are equally likely to be sent. Therefore $\backslash mathbb\{P\}(x\; \backslash mbox\{\; received\}\; \backslash mid\; y\; \backslash mbox\{\; sent\})$ is maximised as a function of the variable $y$ precisely when $\backslash mathbb\{P\}(y\; \backslash mbox\{\; sent\}\backslash mid\; x\; \backslash mbox\{\; received\}\; )$ is maximised, and the claim follows.

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

The ML decoding problem can also be modeled as an integer programming problem.

Minimum distance decoding

:$d(x,y)\; =\; \backslash \#\; \backslash \{i\; :\; x\_i\; \backslash not\; =\; y\_i\; \backslash \}$

i.e. choose the codeword $y$ that is as close as possible to $x$.

Note that if the probability of error on a discrete memoryless channel $p$ is strictly less than one half, then ''minimum distance decoding'' is equivalent to ''maximum likelihood decoding'', since if

:$d(x,y)\; =\; d,\backslash ,$

then:

:

which (since ''p'' is less than one half) is maximised by minimising ''d''.

Minimum distance decoding is also known as ''nearest neighbour decoding''. It can be assisted or automated by using a standard array. Minimum distance decoding is a reasonable decoding method when the following conditions are met:

:#The probability $p$ that an error occurs is independent of the position of the symbol :#Errors are independent events - an error at one position in the message does not affect other positions

These assumptions may be reasonable for transmissions over a binary symmetric channel. They may be unreasonable for other media, such as a DVD, where a single scratch on the disk can cause an error in many neighbouring symbols or codewords.

As with other decoding methods, a convention must be agreed to for non-unique decoding.

Syndrome decoding

The simplest kind of syndrome decoding is Hamming code.

Suppose that $C\backslash subset\; \backslash mathbb\{F\}\_2^n$ is a linear code of length $n$ and minimum distance $d$ with parity-check matrix $H$. Then clearly $C$ is capable of correcting up to

:$t\; =\; \backslash left\backslash lfloor\backslash frac\{d-1\}\{2\}\backslash right\backslash rfloor$

errors made by the channel (since if no more than $t$ errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword).

Now suppose that a codeword $x\; \backslash in\; \backslash mathbb\{F\}\_2^n$ is sent over the channel and the error pattern $e\; \backslash in\; \backslash mathbb\{F\}\_2^n$ occurs. Then $z=x+e$ is received. Ordinary minimum distance decoding would lookup the vector $z$ in a table of size $|C|$ for the nearest match - i.e. an element (not necessarily unique) $c\; \backslash in\; C$ with

:$d(c,z)\; \backslash leq\; d(y,z)$

for all $y\; \backslash in\; C$. Syndrome decoding takes advantage of the property of the parity matrix that:

:$Hx\; =\; 0$

for all $x\; \backslash in\; C$. The ''syndrome'' of the received $z=x+e$ is defined to be:

:$Hz\; =\; H(x+e)\; =Hx\; +\; He\; =\; 0\; +\; He\; =\; He$

Under the assumption that no more than $t$ errors were made during transmission, the receiver looks up the value $He$ in a table of size

:

(for a binary code) against pre-computed values of $He$ for all possible error patterns $e\; \backslash in\; \backslash mathbb\{F\}\_2^n$. Knowing what $e$ is, it is then trivial to decode $x$ as:

:$x\; =\; z\; -\; e$

Partial response maximum likelihood

Partial response maximum likelihood (PRML) is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal.

Viterbi decoder

A Viterbi decoder uses the viterbi algorithm for decoding a bitstream that has been encoded using forward error correction based on a convolutional code. The Hamming distance is used as a metric for hard decision viterbi decoders. The ''squared'' Euclidean distance is used as a metric for soft decision decoders.

See also

References

Category:Coding theory