Decoding methods

Decoding methods are the family of procedures in coding theory for turning a received message, which may have been corrupted on a noisy channel such as a binary symmetric channel, back into a codeword of a chosen code. They differ in the rule they apply to choose that codeword. Ideal observer decoding picks the codeword that is most probable given what was received. Maximum likelihood decoding picks the codeword that makes the received word most probable, and it gives the same answer when every codeword is equally likely to have been sent. Minimum distance decoding, also called nearest neighbour decoding, picks the closest codeword and is reasonable when errors are independent, as on a binary symmetric channel, though less so on a scratched DVD where one flaw damages many neighbouring symbols. Syndrome decoding speeds this up for linear codes with a reduced lookup table. Further methods include list decoding, information set decoding, partial response maximum likelihood, Viterbi decoders and the optimal decision decoding algorithm. When several codewords tie, sender and receiver must agree in advance on a convention, such as asking for a resend, choosing at random, marking erasures for an outer code or reporting a failure.