Decoding methods

From Wikipedia, the free encyclopedia

This article discusses common methods in communication theory for decoding codewords sent over a noisy channel (such as a binary symmetric channel).

1 Notation
2 Ideal observer decoding
3 Maximum likelihood decoding
4 Minimum distance decoding
5 Syndrome decoding

[edit] Notation

Henceforth $C \subset \mathbb{F}_2^n$ shall be a (not necessarily linear) code of length $n$ ; $x, y$ shall be elements of $\mathbb{F}_2^n$ ; and $d (x, y)$ shall represent the Hamming distance between $x, y$ .

[edit] Ideal observer decoding

Given a received codeword $x \in \mathbb{F}_2^n$ , ideal observer decoding picks a codeword $y \in C$ to maximise:

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

-the codeword (or a codeword) $y \in C$ that is most likely to be received as $x$ .

Where this decoding result is non-unique a convention must be agreed. Popular such conventions are:

Request that the codeword be resent;
Choose any one of the possible decodings at random.

[edit] Maximum likelihood decoding

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

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

-the codeword that was most likely to have been sent given that $x$ was received. Note that if all codewords are equally likely to be sent during ordinary use, then this scheme is equivalent to ideal observer decoding:

$\begin{matrix} \mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) & = & \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent} )} \\ && \\ & = & \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent})} \frac{\mathbb{P}(y \mbox{ sent})}{\mathbb{P}(x \mbox{ sent})} \\ && \\ & = & \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent})} \\ && \\ & = & \mathbb{P}(y \mbox{ received} \mid x \mbox{ sent}) \\ \end{matrix}$

As for ideal observer decoding, a convention must be agreed for non-unique decoding. Again, popular such conventions are:

Request that the codeword be resent;
Choose any one of the possible decodings at random.

[edit] Minimum distance decoding

Given a received codeword $x \in \mathbb{F}_2^n$ , minimum distance decoding picks a codeword $y \in C$ to minimise the Hamming distance :

$d(x,y) = \# \{i : x_i \not = y_i \}$

-the codeword (or a codeword) $y \in C$ that is as close as possible to $x \in \mathbb{F}_2^n$ .

Notice 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 likelhood decoding since if

d (x, y) = d

then:

$\begin{matrix} \mathbb{P}(y \mbox{ received} \mid x \mbox{ sent}) & = & (1-p)^{n-d}p^d \\ && \\ & = & (1-p)^n \left( \frac{p}{1-p}\right)^d \\ \end{matrix}$

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

As for other decoding methods, a convention is agreed for non-unique decoding. Popular such conventions are:

Request that the codeword be resent;
Choose any one of the possible decodings at random.

[edit] Syndrome decoding

Syndrome decoding is a highly efficient method of decoding a linear code over a noisy channel - ie one on which errors are made. In essence, syndrome decoding is minimum distance decoding using a reduced lookup table. It is the linearity of the code which allows for the lookup table to be reduced in size.

Suppose that $C\subset \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 upto

$t=\lfloor\frac{d-1}{2}\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 \in \mathbb{F}_2^n$ is sent over the channel and the error pattern $e \in \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 - ie an element (not necessarily unique) $c \in C$ with

$d(c,z) \leq d(y,z)$

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

H x = 0

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

H z = H (x + e) = H x + H e = 0 + H e = H e

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

$\begin{matrix} \sum_{i=0}^t \binom{n}{i} < |C| \\ \end{matrix}$

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