Decoding methods - Citizendia

In communication theory and coding theory, decoding is the process of translating received messages into codewords of a given code. There is much discussion in the academic world of Communication as to what actually constitutes communication Coding theory is one of the most important and direct applications of Information theory. In Telecommunication, a code word is an element of a Code. Each code word is a Sequence of symbols assembled in accordance with the specific rules of In Communications a code is a rule for converting a piece of Information (for example a letter, Word, Phrase, or 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. In Information theory, the noisy-channel coding theorem establishes that however contaminated with noise interference a communication channel may be it is possible to communicate A binary symmetric channel (or BSC is a common Communications channel model used in Coding theory and Information theory.

1 Notation
2 Ideal observer decoding
- 2.1 Decoding conventions
3 Maximum likelihood decoding
4 Minimum distance decoding
5 Syndrome decoding
6 See also
7 References

Notation

Henceforth $C \subset \mathbb{F}_2^n$ shall be a 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$ . In Communications a code is a rule for converting a piece of Information (for example a letter, Word, Phrase, or Examples The Hamming distance between 1011101 and 1001001 Note that $C$ is not necessarily linear. In Mathematics and Information theory, a linear code is an important type of Block code used in Error correction and detection schemes

Ideal observer decoding

Given a received message $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})$

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

Decoding conventions

Note that the probability for each codeword may not be unique: there may be more than one codeword with an equal likelihood of mutating into the received message. In such a case, the sender and receiver(s) must agree on a decoding convention. Popular conventions include:

Request that the codeword be resent
Choose any random codeword from the set of most likely codewords

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})$

i. Maximum likelihood estimation ( MLE) is a popular statistical method used for fitting a mathematical model to some data e. choose the codeword $y$ that was most likely to have been sent given that $x$ was received. Conditional probability is the Probability of some event A, given the occurrence of some other event B. 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 with ideal observer decoding, a convention must be agreed to for non-unique decoding.

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 \}$

i. Examples The Hamming distance between 1011101 and 1001001 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,\,$

then:

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

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. In Coding theory, a standard array (or Slepian array is a q^{n-k} by q^{k} array that lists all elements of a particular \mathbb{F}_q^n 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

Syndrome decoding is a highly efficient method of decoding a linear code over a noisy channel - ie one on which errors are made. In Mathematics and Information theory, a linear code is an important type of Block code used in Error correction and detection schemes 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$ . In Coding theory, a parity-check matrix of a linear block code C is a Generator matrix of the Dual code. 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. The column rank of a matrix A is the maximal number of Linearly independent columns of A.

References

Hill, Raymond. In Mathematics, Computer science, Telecommunication, and Information theory, error detection and correction has great practical importance in (1988). A First Course In Coding Theory, New York: Oxford University Press.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents