Decoding Methods - Minimum Distance Decoding

Given a received codeword, minimum distance decoding picks a codeword to minimise the Hamming distance :

i.e. choose the codeword that is as close as possible to .

Note that if the probability of error on a discrete memoryless channel is strictly less than one half, then minimum distance decoding is equivalent to maximum likelihood decoding, since if

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. Minimum distance decoding is a reasonable decoding method when the following conditions are met:

  1. The probability that an error occurs is independent of the position of the symbol
  2. 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.

Read more about this topic:  Decoding Methods

Famous quotes containing the words minimum and/or distance:

    “There are ... two minimum conditions necessary and sufficient for the existence of a legal system. On the one hand those rules of behavior which are valid according to the system’s ultimate criteria of validity must be generally obeyed, and on the other hand, its rules of recognition specifying the criteria of legal validity and its rules of change and adjudication must be effectively accepted as common public standards of official behavior by its officials.”
    —H.L.A. (Herbert Lionel Adolphus)

    “A petty reason perhaps why novelists more and more try to keep a distance from journalists is that novelists are trying to write the truth and journalists are trying to write fiction.”
    —Graham Greene (1904–1991)