Content deleted Content added
Reverting edit(s) by 37.160.180.127 (talk) to rev. 984983545 by WikiCleanerBot: Vandalism (RW 16) |
Matthiaspaul (talk | contribs) CE, improved refs |
||
Line 1:
{{use dmy dates|date=December 2020|cs1-dates=y}}
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]].
Line 49 ⟶ 50:
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
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=
==Minimum distance decoding==
Line 86 ⟶ 87:
==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
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 125:
:<math>x = z - e </math>
For '''
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.
Line 141:
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}</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==
Line 187 ⟶ 158:
* [[Error detection and correction]]
* [[Forbidden input]]
* {{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 | url-access=registration | url=https://archive.org/details/firstcourseincod0000hill }}▼
* {{cite book | last = Pless | first = Vera | authorlink=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 | 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 | url-access=registration | url=https://archive.org/details/introductiontoco0000lint }}▼
==References==
{{reflist
<ref name="Feldman_2005">{{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>
<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 |author-last=Keil 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 |last1=Ohta |first1=Kazuo |last2=Pei |first2=Dingyi |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}}</ref>
}}
==Further reading==
▲* {{cite book |
▲* {{cite book |
▲* {{cite book |
[[Category:Coding theory]]
| |||