Decoding methods

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

Notation

Throughout this article, $C\subset \mathbb {F} _{2}^{n}$ shall be a (not necessarily linear) code of length $n$.

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} (x{\mbox{ received}}\mid y{\mbox{ sent}})$

-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:

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

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} (y{\mbox{ sent}}\mid x{\mbox{ received}})$

-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:

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

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:

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

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:

$Hx=0$

for all $x\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

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

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

$x=z-e$

Notice that this will always give a unique (but not necessarily accurate) decoding result since

$Hx=Hy$

if and only if $x=y$. This is because the parity check matrix $H$ is a generator matrix for the dual code $C^{\perp }$ and hence is of full rank.