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:

    “After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.”
    —Barbara Ehrenreich (20th century)

    “Morality without religion is only a kind of dead reckoning—an endeavor to find our place on a cloudy sea by measuring the distance we have run, but without any observation of the heavenly bodies.”
    —Henry Wadsworth Longfellow (1807–1882)