Decoding methods: Difference between revisions

Revision as of 02:29, 25 February 2008

Latest revision as of 20:11, 7 July 2025

(119 intermediate revisions by 80 users not shown)

Line 1:

{{Short description|Algorithms to decode messages}}

{{Cleanup|date=November 2007}}

{{use dmy dates|date=December 2020|cs1-dates=y}}

In [[communication theory]] and [[coding theory]], '''decoding''' is the process of translating received messages into [[Code word (communication)|codewords]] of a given [[code]]. ThisThere articlehave discussesbeen many common methods of mapping messages to codewords. These methods are often used to recover messages sent over a [[noisy channel]], such as a [[binary symmetric channel]].

==Notation==

Henceforth <math>C \subset \mathbb{F}_2^n</math> shallis beconsidered a [[binary code]] ofwith 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> shall representis the [[Hamming distance]] between <math>x,y</math>.those Note that <math>C</math> is not necessarily [[linear code|linear]]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:

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>

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

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 codewordvector <math>x \in \mathbb{F}_2^n</math> '''[[maximum likelihood]] decoding''' picks a codeword <math>y \in C</math> tothat [[maximizationOptimization (mathematics)|maximisemaximize]]:s

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

-that is, the codeword <math>y</math> that wasmaximizes mostthe likelyprobability tothat have<math>x</math> beenwas sentreceived, [[conditional probability|given that]] <math>xy</math> was receivedsent. Note that ifIf all codewords are equally likely to be sent during ordinary use, 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})} \\.

& {} = \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 for ''ideal observer decoding'', a convention must be agreed for non-unique decoding. Again, popular such conventions are:

<math>\mathbb{P}(y \mbox{ sent})</math> is constant as all codewords are equally likely to be sent.

:# Request that the codeword be resent;

Therefore,

:# Choose any one of the possible decodings at random.

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

==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>

-thei.e. codewordchoose (or athe codeword) <math>y \in C</math> that is as close as possible to <math> x \in \mathbb{F}_2^n</math>.

NoticeNote 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>

Line 56 ⟶ 71:

:<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>

Line 63 ⟶ 78:

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:

As for other decoding methods, a convention is agreed for non-unique decoding. Popular such conventions are:

:# Request that the codeword be resent;

:#The probability <math>p</math> that an error occurs is independent of the position of the symbol.

:# Choose any one of the possible decodings at random.

:#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'' - ie 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.

'''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 name="Beutelspacher-Rosenbaum_1998"/>

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 76 ⟶ 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 - i.e. an element (not necessarily unique) <math>c \in C</math> with

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

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>

== List decoding ==

(for a binary code) 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:

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

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

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

Notice that this will always give a unique (but not necessarily accurate) decoding result since

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) ==

: <math>Hx = Hy</math>

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>

==See also==

if and only if <math>x=y</math>. This is because the parity check matrix <math>H</math> is a generator matrix for the dual code <math>C^\perp</math> and hence is of full [[rank (linear algebra)|rank]].

* [[Don't care alarm]]

* [[Error detection and correction]]

* [[Forbidden input]]

==References==

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

[[Category:coding theory]]

* {{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:Coding theory]]

[[fr:Méthode de décodage]]