Content deleted Content added
Add →See also: section |
|||
| (115 intermediate revisions by 80 users not shown) | |||
Line 1:
{{Short description|Algorithms to decode messages}}
{{use dmy dates|date=December 2020|cs1-dates=y}}
In
==Notation==
==Ideal observer decoding==
▲Given a received message <math>x \in \mathbb{F}_2^n</math>, '''ideal observer decoding''' picks a codeword <math>y \in C</math> to maximise:
:<math>\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})</math>
===
:# Request that the codeword be resent{{snd}} [[automatic repeat-request]].▼
▲Note that the probability for each codeword may not be unique: 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 on a decoding convention. Popular conventions include:
:# Choose any random codeword from the set of most likely codewords which is nearer to that.▼
▲:# Request that the codeword be resent
:# 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
▲:# Choose any random codeword from the set of most likely codewords
:# Report a decoding failure to the system
==Maximum likelihood decoding==
{{Further|Maximum likelihood}}
Given a received
:<math>\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})</math>,
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})}
& {} = \mathbb{P}(y \mbox{ sent} \mid x \mbox{ received}).▼
\end{align}
</math>
Upon fixing <math>\mathbb{P}(x \mbox{ received})</math>, <math>x</math> is restructured and
As with ''ideal observer decoding'', a convention must be agreed to for non-unique decoding.▼
<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>
</math>
is maximised, and the claim follows.
==Minimum distance decoding==▼
The maximum likelihood decoding problem can also be modeled as an [[integer programming]] problem.<ref name="Feldman_2005"/>
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]] :▼
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="Aji-McEliece_2000"/>
▲==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>
Line 61 ⟶ 78:
which (since ''p'' is less than one half) is maximised by minimising ''d''.
Minimum distance decoding is also known as ''nearest neighbour decoding''.
:#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'',
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
Line 74 ⟶ 97:
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 -
▲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 - ie an element (not necessarily unique) <math>c \in C</math> with
:<math>d(c,z) \leq d(y,z)</math>
Line 87 ⟶ 109:
:<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>.
Under the assumption that no more than <math>t</math> errors were made during transmission the receiver looks up the value <math>He</math> in a table of size▼
Note that this is already of significantly less complexity than that of a [[standard array|standard array decoding]].
▲
:<math>
\begin{matrix}
\sum_{i=0}^t \binom{n}{i}
\end{matrix}
</math>
== List decoding ==
{{Main|List decoding}}
== Information set decoding ==
This is a family of [[Las Vegas algorithm|Las Vegas]]-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to guess all the error-positions.
The simplest form is due to Prange: Let <math>G</math> be the <math>k \times n</math> generator matrix of <math>C</math> used for encoding. Select <math>k</math> columns of <math>G</math> at random, and denote by <math>G'</math> the corresponding submatrix of <math>G</math>. With reasonable probability <math>G'</math> will have full rank, which means that if we let <math>c'</math> be the sub-vector for the corresponding positions of any codeword <math>c = mG</math> of <math>C</math> for a message <math>m</math>, we can recover <math>m</math> as <math>m = c' G'^{-1}</math>. Hence, if we were lucky that these <math>k</math> positions of the received word <math>y</math> contained no errors, and hence equalled the positions of the sent codeword, then we may decode.
If <math>t</math> errors occurred, the probability of such a fortunate selection of columns is given by <math>\textstyle\binom{n-t}{k}/\binom{n}{k}\approx \exp(-tk/n)</math>.
This method has been improved in various ways, e.g. by Stern<ref name="Stern_1989"/> and [[Anne Canteaut|Canteaut]] and Sendrier.<ref name="Ohta_1998"/>
==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.
== Optimal decision decoding algorithm (ODDA) ==
== See also ==▼
Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system.{{Clarify|date=January 2023}}<ref>{{Citation |title= Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system; |author1=Siamack Ghadimi|publisher=Universal Journal of Electrical and Electronic Engineering|date=2020}}</ref>
* [[Don't care alarm]]
* [[Error detection and correction]]
* [[Forbidden input]]
==
{{reflist|refs=
<ref name="Feldman_2005">{{cite journal |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|s2cid=3120399 |citeseerx=10.1.1.111.6585 }}</ref>
<ref name="Beutelspacher-Rosenbaum_1998">{{cite book |author-first1=Albrecht |author-last1=Beutelspacher |author-link1=Albrecht Beutelspacher |author-first2=Ute |author-last2=Rosenbaum |date=1998 |title=Projective Geometry |page=190 |publisher=[[Cambridge University Press]] |isbn=0-521-48277-1}}</ref>
<ref name="Aji-McEliece_2000">{{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 |url=https://authors.library.caltech.edu/1541/1/AJIieeetit00.pdf}}</ref>
<ref name="Stern_1989">{{cite book |author-first=Jacques |author-last=Stern |date=1989 |chapter=A method for finding codewords of small weight |title=Coding Theory and Applications |series=Lecture Notes in Computer Science |publisher=[[Springer-Verlag]] |volume=388 |pages=106–113 |doi=10.1007/BFb0019850 |isbn=978-3-540-51643-9}}</ref>
<ref name="Ohta_1998">{{cite book |date=1998 |editor-last1=Ohta |editor-first1=Kazuo |editor-first2=Dingyi |editor-last2=Pei |series=Lecture Notes in Computer Science |volume=1514 |pages=187–199 |doi=10.1007/3-540-49649-1 |isbn=978-3-540-65109-3 |s2cid=37257901 |title=Advances in Cryptology — ASIACRYPT'98 }}</ref>
}}
==Further reading==
* {{cite book |author-last=Hill |author-first=Raymond |title=A first course in coding theory |publisher=[[Oxford University Press]] |series=Oxford Applied Mathematics and Computing Science Series |date=1986 |isbn=978-0-19-853803-5 |url-access=registration |url=https://archive.org/details/firstcourseincod0000hill}}
* {{cite book |author-last=Pless |author-first=Vera |author-link=Vera Pless |title=Introduction to the theory of error-correcting codes |title-link=Introduction to the Theory of Error-Correcting Codes |publisher=[[John Wiley & Sons]] |series=Wiley-Interscience Series in Discrete Mathematics |date=1982 |isbn=978-0-471-08684-0}}
* {{cite book |author-first=Jacobus H. |author-last=van Lint |title=Introduction to Coding Theory |edition=2 |publisher=[[Springer-Verlag]] |series=[[Graduate Texts in Mathematics]] (GTM) |volume=86 |date=1992 |isbn=978-3-540-54894-2 |url-access=registration |url=https://archive.org/details/introductiontoco0000lint}}
[[Category:
| |||