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.
Contents
Notation
Ideal observer decoding
One may be given the message
For example, a person can choose the codeword
Decoding conventions
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
Maximum likelihood decoding
Given a received codeword
that is, the codeword
Upon fixing
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.
Minimum distance decoding
Given a received codeword
i.e. choose the codeword
Note that if the probability of error on a discrete memoryless channel
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
p 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
errors made by the channel (since if no more than
Now suppose that a codeword
for all
for all
To perform ML decoding in a Binary symmetric channel, one has to look-up a precomputed table of size
Note that this is already of significantly less complexity than that of a Standard array decoding.
However, under the assumption that no more than
only (for a binary code). The table is against pre-computed values of
Knowing what
Partial response maximum likelihood
Partial response maximum likelihood (PRML) is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal.
Viterbi decoder
A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using forward error correction based on a convolutional code. The Hamming distance is used as a metric for hard decision Viterbi decoders. The squared Euclidean distance is used as a metric for soft decision decoders.