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

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

Ideal observer decoding

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

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

-the codeword (or a codeword) ${\displaystyle y\in C}$  that is most likely to be received as ${\displaystyle 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 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$  maximum likelihood decoding picks a codeword ${\displaystyle y\in C}$  to maximise:

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

-the codeword that was most likely to have been sent given that ${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ , minimum distance decoding picks a codeword ${\displaystyle y\in C}$  to minimise the Hamming distance :

${\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}}$ 

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

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

${\displaystyle d(x,y)=d}$ 

then:

${\displaystyle {\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 ${\displaystyle p}$  is less than one half) is maximised by minimising ${\displaystyle 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 ${\displaystyle C\subset \mathbb {F} _{2}^{n}}$  is a linear code of length ${\displaystyle n}$  and minimum distance ${\displaystyle d}$  with parity-check matrix ${\displaystyle H}$ . Then clearly ${\displaystyle C}$  is capable of correcting up to

${\displaystyle t=\lfloor {\frac {d-1}{2}}\rfloor }$ 

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

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

${\displaystyle d(c,z)\leq d(y,z)}$ 

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

${\displaystyle Hx=0}$ 

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

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$ 

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

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

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

${\displaystyle x=z-e}$ 

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

${\displaystyle Hx=Hy}$ 

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