Concept

# Decoding methods

Summary
In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel. is considered a binary code with the length ; shall be elements of ; and is the distance between those elements. One may be given the message , then ideal observer decoding generates the codeword . The process results in this solution: For example, a person can choose the codeword that is most likely to be received as the message after transmission. Each codeword does not have an expected possibility: there may be more than one codeword with an equal likelihood of mutating into the received message. In such a case, the sender and receiver(s) must agree ahead of time on a decoding convention. Popular conventions include: Request that the codeword be resent - automatic repeat-request. Choose any random codeword from the set of most likely codewords which is nearer to that. If another code follows, mark the ambiguous bits of the codeword as erasures and hope that the outer code disambiguates them Given a received vector maximum likelihood decoding picks a codeword that maximizes that is, the codeword that maximizes the probability that was received, given that was sent. If all codewords are equally likely to be sent then this scheme is equivalent to ideal observer decoding. In fact, by Bayes Theorem, Upon fixing , is restructured and is constant as all codewords are equally likely to be sent. Therefore, is maximised as a function of the variable precisely when is maximised, and the claim follows. As with ideal observer decoding, a convention must be agreed to for non-unique decoding. The maximum likelihood decoding problem can also be modeled as an integer programming problem. The maximum likelihood decoding algorithm is an instance of the "marginalize a product function" problem which is solved by applying the generalized distributive law.