Decoding methods
Encyclopedia
In communication theory
and 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
.
could have been considered a code
with the length
; 
shall be elements of 
; and 
would be representing the Hamming distance
between
. Note that 
is not necessarily linear
.
, 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.
maximum likelihood
decoding picks a codeword
to maximize
:
i.e. choose the codeword
that maximizes the probability that 
was received, given that
was sent. Note that if all codewords are equally likely to be sent then this scheme is equivalent to ideal observer decoding.
In fact, by Bayes Theorem we have
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 ML decoding problem can also be modeled as an integer programming
problem.
, 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:
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:
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.
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. It is the linearity of the code which allows for the lookup table to be reduced in size.
The simplest kind of syndrome decoding is Hamming 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:
Under the assumption that no more than
errors were made during transmission, the receiver looks up the value 
in a table of size
(for a binary code) against pre-computed values of
for all possible error patterns 
. Knowing what 
is, it is then trivial to decode 
as:
) is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal.
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.
Communication theory
Communication theory is a field of information and mathematics that studies the technical process of information and the human process of human communication.- History :- Origins :...
and coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, decoding is the process of translating received messages into codewords of a given code
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
. 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
Binary symmetric channel
A binary symmetric channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit , and the receiver receives a bit. It is assumed that the bit is usually transmitted correctly, but that it will be "flipped" with a...
.
Notation
Henceforth, could have been considered a codeCode
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
with the length
; shall be elements of ; and would be representing the Hamming distanceHamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
between
. Note that is not necessarily linearLinear code
In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...
.
Ideal observer decoding
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.Decoding conventions
Each codeword does not have a 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.
Maximum likelihood decoding
Given a received codeword maximum likelihoodMaximum likelihood
In statistics, maximum-likelihood estimation is a method of estimating the parameters of a statistical model. When applied to a data set and given a statistical model, maximum-likelihood estimation provides estimates for the model's parameters....
decoding picks a codeword
to maximizeMaximization
The profit motive is the concept in economics that refers to individuals being provided incentive to relinquish something for deployment to a productive purpose. If humans are rational and self-interested , then they should only divert some of their personal resource toward production for others...
:
i.e. choose the codeword
that maximizes the probability that was received, given thatConditional probability
In probability theory, the "conditional probability of A given B" is the probability of A if B is known to occur. It is commonly notated P, and sometimes P_B. P can be visualised as the probability of event A when the sample space is restricted to event B...
was sent. Note that if all codewords are equally likely to be sent then this scheme is equivalent to ideal observer decoding.In fact, by Bayes Theorem we have
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 whenis maximised, and the claim follows.
As with ideal observer decoding, a convention must be agreed to for non-unique decoding.
The ML decoding problem can also be modeled as an integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
problem.
Minimum distance decoding
Given a received codeword, minimum distance decoding picks a codeword to minimise the Hamming distanceHamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
:
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 ifthen:
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
- The probability
These assumptions may be reasonable for transmissions over a binary symmetric channel
Binary symmetric channel
A binary symmetric channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit , and the receiver receives a bit. It is assumed that the bit is usually transmitted correctly, but that it will be "flipped" with a...
. 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 codeLinear code
In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...
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. It is the linearity of the code which allows for the lookup table to be reduced in size.
The simplest kind of syndrome decoding is Hamming code
Hamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
.
Suppose that
is a linear code of length and minimum distance with parity-check matrixParity-check matrix
In coding theory, a parity-check matrix of a linear block code Cis a generator matrix of the dual code. As such, a codeword c is in C if and only if the matrix-vector product Hc=0....
. Then clearly is capable of correcting up toerrors 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) withfor all
. Syndrome decoding takes advantage of the property of the parity matrix that:for all
. The syndrome of the received is defined to be:Under the assumption that no more than
errors were made during transmission, the receiver looks up the value in a table of size(for a binary code) against pre-computed values of
for all possible error patterns . Knowing what is, it is then trivial to decode as:Partial response maximum likelihood
Partial response maximum likelihood (PRMLPRML
In computer data storage, Partial Response Maximum Likelihood is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal. PRML attempts to correctly interpret even small changes in the analog signal, whereas peak detection relies on fixed...
) 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
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
is used as a metric for hard decision viterbi decoders.
The squared Euclidean distance
Euclidean distance
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
is used as a metric for soft decision decoders.