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)

    “We have been told over and over about the importance of bonding to our children. Rarely do we hear about the skill of letting go, or, as one parent said, “that we raise our children to leave us.” Early childhood, as our kids gain skills and eagerly want some distance from us, is a time to build a kind of adult-child balance which permits both of us room.”
    —Joan Sheingold Ditzion (20th century)