Decoding methods: Difference between revisions

Revision as of 12:42, 3 July 2008

Latest revision as of 20:11, 7 July 2025

(110 intermediate revisions by 77 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==

GivenOne amay receivedbe given the message <math>x \in \mathbb{F}_2^n</math>, then '''ideal observer decoding''' picksgenerates athe codeword <math>y \in C</math>. The process results in tothis maximisesolution:

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

NoteEach thatcodeword thedoes probabilitynot forhave each codeword may notan beexpected uniquepossibility: 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 ahead of time 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 -- [[automatic repeat-request]]

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

{{mainFurther|maximumMaximum 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>,

i.e.that chooseis, 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 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>

& {} = \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>

Line 64 ⟶ 80:

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.

Line 73 ⟶ 89:

==Syndrome decoding==

<!-- [[Syndrome decoding]] redirects here -->

'''Syndrome decoding''' is a highly efficient method of decoding a [[linear code]] over a ''noisy channel'', - iei.e. one on which errors are made. In essence, syndrome decoding is ''minimum distance decoding'' using a reduced lookup table. ItThis is allowed by the linearity of the code.<ref which allows for the lookup table to be reduced in size.name="Beutelspacher-Rosenbaum_1998"/>

The simplest kind of syndrome decoding is [[Hamming code]].

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 83 ⟶ 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 - iei.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 96 ⟶ 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]].

UnderHowever, under the assumption that no more than <math>t</math> errors were made during transmission, the receiver lookscan 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 ==

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

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.

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

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.

: <math>Hx = Hy</math>

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

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

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

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

{{mainMain|viterbiViterbi decoder}}

A viterbiViterbi decoder uses the viterbiViterbi 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 viterbiViterbi decoders. The ''squared'' [[Euclidean distance]] is used as a metric for soft decision 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>

== See also ==

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

* Hill, Raymond. (1988). ''A First Course In Coding Theory'', New York: Oxford University Press.

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

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

[[ja:復号手法]]