View source for Decoding methods

{{Short description|Algorithms to decode messages}}{{Expert needed|Coding theory
| ex2 = Information theory
| date = December 2018
}}

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]].

==Notation==
<math>C \subset \mathbb{F}_2^n</math> is considered a [[binary code]] with the length <math>n</math>; <math>x,y</math> shall be elements of <math>\mathbb{F}_2^n</math>; and <math>d(x,y)</math> is the distance between those elements.

==Ideal observer decoding==
One may be given the message <math>x \in \mathbb{F}_2^n</math>, then '''ideal observer decoding''' generates the codeword <math>y \in C</math>. The process results in this solution:

:<math>\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})</math>

For example, a person can choose the codeword <math>y</math> that is most likely to be received as the message <math>x</math> after transmission.

===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{{snd}} [[automatic repeat-request]].
:# Choose any random codeword from the set of most likely codewords which is nearer to that.
:# If [[Concatenated error correction code|another code follows]], mark the ambiguous bits of the codeword as erasures and hope that the outer code disambiguates them.

==Maximum likelihood decoding==
{{Further|Maximum likelihood}}

Given a received codeword <math>x \in \mathbb{F}_2^n</math> '''[[maximum likelihood]] decoding''' picks a codeword <math>y \in C</math> that [[Optimization (mathematics)|maximize]]s

:<math>\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})</math>,

that is, the codeword <math>y</math> that maximizes the probability that <math>x</math> was received, [[conditional probability|given that]] <math>y</math> 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]],

:<math>
\begin{align}
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) & {} = \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent} )} \\
& {} = \mathbb{P}(y \mbox{ sent} \mid x \mbox{ received}) \cdot \frac{\mathbb{P}(x \mbox{ received})}{\mathbb{P}(y \mbox{ sent})}.
\end{align}
</math>

Upon fixing <math>\mathbb{P}(x \mbox{ received})</math>, <math>x</math> is restructured and
<math>\mathbb{P}(y \mbox{ sent})</math> is constant as all codewords are equally likely to be sent.
Therefore, 
<math>
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) 
</math>
is maximised as a function of the variable <math>y</math> precisely when
<math>
\mathbb{P}(y \mbox{ sent}\mid x \mbox{ received} ) 
</math>
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.<ref name = feldman>{{cite news | title=Using Linear Programming to Decode Binary Linear Codes | first1=Jon | last1=Feldman |first2=Martin J. | last2=Wainwright | first3=David R. | last3=Karger | journal=IEEE Transactions on Information Theory | volume=51 | issue=3 | pages=954–972 |date=March 2005 | doi=10.1109/TIT.2004.842696}}</ref>

The maximum likelihood decoding algorithm is an instance of the "marginalize a product function" problem which is solved by applying the [[generalized distributive law]].<ref name=GenDistLaw>{{cite journal | last1=Aji | first1=Srinivas M. | last2=McEliece | first2=Robert J. | title=The Generalized Distributive Law | journal=IEEE Transactions on Information Theory |date=March 2000 | volume=46 | issue=2 | pages=325–343 | doi=10.1109/18.825794}}</ref>

==Minimum distance decoding==
Given a received codeword <math>x \in \mathbb{F}_2^n</math>, '''minimum distance decoding''' picks a codeword <math>y \in C</math> to minimise the [[Hamming distance]]:

:<math>d(x,y) = \# \{i : x_i \not = y_i \}</math>

i.e. choose the codeword <math>y</math> that is as close as possible to <math>x</math>.

Note that if the probability of error on a [[discrete memoryless channel]] <math>p</math> is strictly less than one half, then ''minimum distance decoding'' is equivalent to ''maximum likelihood decoding'', since if

:<math>d(x,y) = d,\,</math>

then:

:<math>
\begin{align}
\mathbb{P}(y \mbox{ received} \mid x \mbox{ sent}) & {} = (1-p)^{n-d} \cdot p^d \\
& {} = (1-p)^n \cdot \left( \frac{p}{1-p}\right)^d \\
\end{align}
</math>

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 <math>p</math> that an error occurs is independent of the position of the symbol.
:#Errors are independent events{{snd}} 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]] redirects here -->
'''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.<ref>[[Albrecht Beutelspacher]] & Ute Rosenbaum (1998) ''Projective Geometry'', page 190, [[Cambridge University Press]]  {{ISBN|0-521-48277-1}}
</ref>

Suppose that <math>C\subset \mathbb{F}_2^n</math> is a linear code of length <math>n</math> and minimum distance <math>d</math> with [[parity-check matrix]] <math>H</math>. Then clearly <math>C</math> is capable of correcting up to

:<math>t = \left\lfloor\frac{d-1}{2}\right\rfloor</math>

errors made by the channel (since if no more than <math>t</math> errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword).

Now suppose that a codeword <math>x \in \mathbb{F}_2^n</math> is sent over the channel and the error pattern <math>e \in \mathbb{F}_2^n</math> occurs. Then <math>z=x+e</math> is received. Ordinary minimum distance decoding would lookup the vector <math>z</math> in a table of size <math>|C|</math> for the nearest match - i.e. an element (not necessarily unique) <math>c \in C</math> with

:<math>d(c,z) \leq d(y,z)</math>

for all <math>y \in C</math>. Syndrome decoding takes advantage of the property of the parity matrix that:

:<math>Hx = 0</math>

for all <math>x \in C</math>. The ''syndrome'' of the received <math>z=x+e</math> is defined to be:

:<math>Hz = H(x+e) =Hx + He = 0 + He = He</math>

To perform [[#Maximum_likelihood_decoding|ML decoding]] in a [[binary symmetric channel]], one has to look-up a precomputed table of size <math>2^{n-k}</math>, mapping <math>He</math> to <math>e</math>.

Note that this is already of significantly less complexity than that of a [[standard array|standard array decoding]].

However, under the assumption that no more than <math>t</math> errors were made during transmission, the receiver can look up the value <math>He</math> in a further reduced table of size

:<math>
\begin{matrix}
\sum_{i=0}^t \binom{n}{i} < |C| \\
\end{matrix}
</math>

only (for a binary code). The table is against pre-computed values of <math>He</math> for all possible error patterns <math>e \in \mathbb{F}_2^n</math>.

Knowing what <math>e</math> is, it is then trivial to decode <math>x</math> as:

:<math>x = z - e </math>

For '''Binary''' codes, if both <math>k</math> and <math>n-k</math> are not too big, and assuming the code generating matrix is in standard form, syndrome decoding can be computed using 2 precomputed lookup tables and 2 XORs only. <ref>[[Jack Keil Wolf ]] (2008) ''An Introduction to Error Correcting Codes'', Course: Communication Systems III, [[UCSD]], http://circuit.ucsd.edu/~yhk/ece154c-spr17/pdfs/ErrorCorrectionI.pdf</ref>

Let <math>z</math> be the received noisy codeword, i.e. <math>z=x\oplus e</math>. Using the encoding lookup table of size <math>2^k</math>, the codeword <math>z'</math> that corresponds to the first <math>k</math> bits of <math>z</math> is found. 

The syndrome is then computed as the last <math>n-k</math> bits of <math>s=z\oplus z'</math> (the first <math>k</math> bits of the XOR are zero [since the generating matrix is in standard form] and discarded). Using the syndrome, the error <math>e</math> is computed using the syndrome lookup table of size <math>2^{n-k}</math>, and the decoding is then computed via <math>x = z \oplus e</math> (for the codeword, or the first <math>k</math> bits of <math>x</math> for the original word).

The number of entries in the two lookup tables is <math>2^k+2^{n-k}</math>, which is significantly smaller than <math>2^n</math> required for [[standard array|standard array decoding]] that requires only <math>1</math> lookup. Additionally, the precomputed encoding lookup table can be used for the encoding, and is thus often useful to have.

==Partial response maximum likelihood==
{{Main|PRML}}

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==
{{Main|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.

==See also==
* [[Error detection and correction]]

==Sources==
* {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | publisher=[[Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | year=1986 | isbn=978-0-19-853803-5 }}
* {{cite book | last = Pless | first = Vera | authorlink=Vera Pless | title = Introduction to the theory of error-correcting codes | publisher = [[John Wiley & Sons]]|series = Wiley-Interscience Series in Discrete Mathematics | year = 1982| isbn = 978-0-471-08684-0 }}
* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | year=1992 | isbn=978-3-540-54894-2 }}

==References==
{{reflist}}

[[Category:Coding theory]]