Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
GreenC bot (talk | contribs) Rescued 2 archive links; Move 2 urls. Wayback Medic 2.5 per WP:URLREQ#ieee.org |
||
Line 5:
In [[information theory]], a '''low-density parity-check''' ('''LDPC''') '''code''' is a [[Linear code|linear]] [[error correcting code]], a method of transmitting a message over a [[signal noise|noisy]] transmission channel.<ref>{{cite book |author-link=David J.C. MacKay |first=David J. |last=MacKay |title=Information theory, Inference and Learning Algorithms |publisher=Cambridge University Press |date=2003 |isbn=0-521-64298-1 |pages= |url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html}}</ref><ref>{{cite book |author-link=Todd K. Moon |first=Todd K. |last=Moon |title=Error Correction Coding, Mathematical Methods and Algorithms |publisher=Wiley |date=2005 |isbn=0-471-64800-0 |pages= |url=}} (Includes code)</ref> An LDPC code is constructed using a sparse [[Tanner graph]] (subclass of the [[bipartite graph]]).<ref>{{citation |author=Amin Shokrollahi |url=http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |title=LDPC Codes: An Introduction |archive-url=https://web.archive.org/web/20170517034849/http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |archive-date=2017-05-17}}</ref> LDPC codes are [[:Category:capacity-approaching codes|capacity-approaching codes]], which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum (the [[Shannon–Hartley theorem|Shannon limit]]) for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative [[belief propagation]] techniques, LDPC codes can be decoded in time linear in their block length.
LDPC codes are also known as '''Gallager codes''', in honor of [[Robert G. Gallager]], who developed the LDPC concept in his doctoral dissertation at the [[Massachusetts Institute of Technology]] in 1960.<ref>{{Cite news |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |title=Explained: Gallager codes |first=L. |last=Hardesty |journal=MIT News |date= January 21, 2010 |access-date= August 7, 2013 }}</ref><ref name="G1962">{{cite journal |first=R.G. |last=Gallager |title=Low density parity check codes |journal=IRE Trans. Inf. Theory |volume=8 |issue=1 |pages=21–28 |date=January 1962 |doi=10.1109/TIT.1962.1057683 |hdl=1721.1/11804/32786367-MIT|s2cid=260490814 }}</ref> However, LDPC codes require computationally expensive iterative decoding, so they went unused for decades. In 1993 the newly invented [[turbo code]]s demonstrated that codes with iterative decoding could far outperform other codes used at that time, but turbo codes were patented and required a fee for use. This raised renewed interest in LDPC codes, which were shown to have similar performance, but were much older and patent-free.<ref name="Closing">{{cite journal |author=Erico Guizzo |title=CLOSING IN ON THE PERFECT CODE |journal=IEEE Spectrum |date=Mar 1, 2004 |url=https://spectrum.ieee.org/closing-in-on-the-perfect-code|archive-url=https://web.archive.org/web/20210902170851/https://spectrum.ieee.org/closing-in-on-the-perfect-code|url-status=dead|archive-date=September 2, 2021}} "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."</ref> Now that the fundamental patent for turbo codes has expired (on August 29, 2013),<ref>{{cite patent |url=https://www.google.com/patents/US5446747 |country=US |number=5446747}}</ref><ref>{{cite journal |journal=New Scientist |title=Communication speed nears terminal velocity |first=D. |last=Mackenzie |date=9 July 2005}}</ref> LDPC codes are still used for their technical merits.
LDPC codes have been shown to have ideal combinatorial properties. In his dissertation, Gallager showed that LDPC codes achieve the [[Gilbert–Varshamov bound for linear codes]] over binary fields with high probability. In 2020 it was shown that Gallager's LDPC codes achieve [[list decoding]] capacity and also achieve the [[Gilbert–Varshamov bound for linear codes]] over general fields.<ref name="MRRSW20">{{cite journal |last1=Mosheiff |first1=J. |last2=Resch |first2=N. |last3=Ron-Zewi |first3=N. |last4=Silas |first4=S. |last5=Wootters |first5=M. |title=Low-Density Parity-Check Codes Achieve List-Decoding Capacity |journal=SIAM Journal on Computing |issue=FOCS 2020 |pages=38–73 |date=2020 |doi=10.1137/20M1365934 |s2cid=244549036 |arxiv=1909.06430 }}</ref>
Line 17:
In 2008, LDPC beat convolutional turbo codes as the [[forward error correction]] (FEC) system for the [[ITU-T]] [[G.hn]] standard.<ref>[http://homepnablog.typepad.com/my_weblog/2008/12/ghn-a-phy-for-all-seasons.html HomePNA Blog: G.hn, a PHY For All Seasons]</ref> G.hn chose LDPC codes over turbo codes because of their lower decoding complexity (especially when operating at data rates close to 1.0 Gbit/s) and because the proposed turbo codes exhibited a significant [[error floor]] at the desired range of operation.<ref>[http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html IEEE Communications Magazine paper on G.hn] {{webarchive|url=https://web.archive.org/web/20091213012126/http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html |date=2009-12-13 }}</ref>
LDPC codes are also used for [[10GBASE-T]] Ethernet, which sends data at 10 gigabits per second over twisted-pair cables. As of 2009, LDPC codes are also part of the [[Wi-Fi]] 802.11 standard as an optional part of [[802.11n]] and [[802.11ac]], in the High Throughput (HT) PHY specification.<ref>IEEE Standard, section 20.3.11.6 [https://web.archive.org/web/20100704235707/http://standards.ieee.org/getieee802/download/802.11n-2009.pdf "802.11n-2009"], IEEE, October 29, 2009, accessed March 21, 2011.</ref> LDPC is a mandatory part of [[802.11ax]] (Wi-Fi 6).<ref>{{cite web |title=IEEE SA - IEEE 802.11ax-2021 |url=https://standards.ieee.org/ieee/802.11ax/7180/ |website=IEEE Standards Association |access-date=22 May 2022 |language=en}}</ref>
Some [[OFDM]] systems add an additional outer error correction that fixes the occasional errors (the "error floor") that get past the LDPC correction inner code even at low [[bit error rate]]s.
Line 249:
*[[CMMB]] (China Multimedia Mobile Broadcasting)
*[[DVB-S2]] / [[DVB-T2]] / [[DVB-C2]] (digital video broadcasting, 2nd generation)
*[[DMB-T/H]] (digital video broadcasting)<ref>{{cite web |url=https://spectrum.ieee.org/consumer-electronics/standards/does-china-have-the-best-digital-television-standard-on-the-planet/2 |title=IEEE Spectrum: Does China Have the Best Digital Television Standard on the Planet? |website=
*[[WiMAX]] (IEEE 802.16e standard for microwave communications)
* [[IEEE 802.11n-2009]] ([[Wi-Fi]] standard)
| |||