Decoding methods

From Wikipedia, the free encyclopedia

(Redirected from Minimum distance decoding)

This article may require cleanup to meet Wikipedia's quality standards.
Please improve this article if you can. (November 2007)

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

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$ .

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.

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{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})} \\ & {} = \mathbb{P}(y \mbox{ sent} \mid x \mbox{ received}). \end{align}$

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.

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 likelihood decoding since if

$d(x,y) = d,\,$

then:

$\begin{align} \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{align}$

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.

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 up to

$t = \left\lfloor\frac{d-1}{2}\right\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:

x = z - e

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

H x = H y

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.

Retrieved from "http://en.wikipedia.org/wiki/Decoding_methods"

Categories: Cleanup from November 2007 | All pages needing cleanup | Coding theory

Searching reference...

Reference

Sources

Decoding methods

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Searching reference...

Reference

Sources

Decoding methods

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.