maximum likelihood decoding, since if then: 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: The probability 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, i.e. one on which errors are made. In essence, syndrome decoding is minimum distance decoding using a reduced lookup table. This is allowed by the linearity of the code. Suppose that is a linear code of length and minimum distance with parity-check matrix . Then clearly is capable of correcting up to errors made by the channel (since if no more than errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword). Now suppose that a codeword is sent over the channel and the error pattern occurs. Then is received. Ordinary minimum distance decoding would lookup the vector in a table of size for the nearest match - i.e. an element (not necessarily unique) with for all . Syndrome decoding takes advantage of the property of the parity matrix that: for all . The syndrome of the received is defined to be: To perform ML decoding in a binary symmetric channel, one has to look-up a precomputed table of size , mapping to . Note that this is already of significantly less complexity than that of a standard array decoding. However, under the assumption that no more than errors were made during transmission, the receiver can look up the value in a further reduced table of size List decoding Information set decoding This is a family of Las Vegas-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to