Low-density parity-check code: Difference between revisions

Revision as of 15:31, 20 February 2024

Revision as of 22:30, 25 April 2024

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

==History==

Impractical to implement when first developed by [[Robert G. Gallager|Gallager]] in 1963,<ref>{{Cite book |first=Robert G. |last=Gallager |title= Low Density Parity Check Codes |publisher= M.I.T. Press |year= 1963 |url= http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/ldpc.pdf |access-date= August 7, 2013 }}</ref> LDPC codes were forgotten until his work was rediscovered in 1996.<ref name=MacKay96>[[David J.C. MacKay]] and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996</ref> [[Turbo code]]s, another class of capacity-approaching codes discovered in 1993, became the coding scheme of choice in the late 1990s, used for applications such as the [[Deep Space Network]] and [[satellite communication]]s. LDPC codes then received renewed interest as a patent-free alternative of similar performance.<ref name="Closing"/> Since then, advances in low-density parity-check codes have seen them surpass turbo codes in terms of [[error floor]] and performance in the higher [[code rate]] range, leaving turbo codes better suited for the lower code rates only.<ref>[http://deepspace.jpl.nasa.gov/dsndocs/810-005/208/208B.pdf Telemetry Data Decoding, Design Handbook]</ref>

==Applications==

In 2003, an [[Repeat-accumulate code#Irregular Repeat Accumulate Codes|irregular repeat accumulate]] (IRA) style LDPC code beat six turbo codes to become the error-correcting code in the new [[DVB-S2]] standard for [[digital television]].<ref name="hughesdvb">[http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf Presentation by Hughes Systems] {{webarchive|url=https://web.archive.org/web/20061008053124/http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf |date=2006-10-08 }}</ref> The DVB-S2 selection committee made decoder complexity estimates for the turbo code proposals using a much less efficient serial decoder architecture rather than a parallel decoder architecture. This forced the turbo code proposals to use frame sizes on the order of one half the frame size of the LDPC proposals.{{Citation needed|date=May 2023}}

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 &nbsp;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 [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>

Line 150:

==Decoding==

{{Unreferenced section|date=May 2023}}

As with other codes, the [[maximum likelihood decoding]] of an LDPC code on the [[binary symmetric channel]] is an [[NP-complete]] problem,<ref>{{cite journal |title=On the Inherent Intractability of Certain Coding Problems |author= Robert McEliece, [[Elwyn Berlekamp|E. R. Berlekamp]] and H. Van Tilborg |journal=IEEE Trans. Inf. Theory |year=1978 |pages=384–386 |publisher=IEEE |doi=10.1109/TIT.1978.1055873|url= https://resolver.caltech.edu/CaltechAUTHORS:BERieeetit78 }}</ref> shown by reduction from [[3-dimensional matching]]. So assuming [[P versus NP problem|P != NP]], which is widely believed, then performing optimal decoding for an arbitrary code of any useful size is not practical.

However, sub-optimal techniques based on iterative [[belief propagation]] decoding give excellent results and can be practically implemented. The sub-optimal decoding techniques view each parity check that makes up the LDPC as an independent single parity check (SPC) code. Each SPC code is decoded separately using [[Soft-in soft-out decoder|soft-in-soft-out]] (SISO) techniques such as [[Soft output Viterbi algorithm|SOVA]], [[BCJR algorithm|BCJR]], [[Maximum a posteriori estimation|MAP]], and other derivates thereof. The soft decision information from each SISO decoding is cross-checked and updated with other redundant SPC decodings of the same information bit. Each SPC code is then decoded again using the updated soft decision information. This process is iterated until a valid codeword is achieved or decoding is exhausted. This type of decoding is often referred to as sum-product decoding.