Decoding methods: Difference between revisions

Revision as of 18:27, 2 February 2021

Latest revision as of 20:11, 7 July 2025

(13 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Algorithms to decode messages}}

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

In [[coding theory]], '''decoding''' is the process of translating received messages into [[Code word (communication)|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==

Line 18 ⟶ 19:

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

:# 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> 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' Theoremtheorem]],

:<math>

Line 118 ⟶ 120:

\end{matrix}

</math>

(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 name="Wolf_2008"/>

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.

== List decoding ==

Line 142 ⟶ 130:

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"/>

Line 156 ⟶ 144:

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

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

Line 164 ⟶ 155:

==References==

{{reflist|refs=

<ref name="Feldman_2005">{{cite newsjournal |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="Wolf_2008">{{cite web |author-first=Jack Keil |author-last=Wolf |author-link=Jack Keil Wolf |date=2008 |title=An Introduction to Error Correcting Codes |work=Course: Communication Systems III |publisher=[[UCSD]] |url=http://circuit.ucsd.edu/~yhk/ece154c-spr17/pdfs/ErrorCorrectionI.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 |title=Cryptanalysis of the Original McEliece Cryptosystem |journal=Advances in Cryptology — ASIACRYPT'98 |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>

}}