Low-density parity-check code: Difference between revisions

Revision as of 07:19, 19 December 2024

Revision as of 07:28, 19 December 2024

Line 11:

This theoretical performance is made possible using a flexible design method that is based on sparse [[Tanner graph|Tanner graphs]] (specialized [[bipartite graph|bipartite graphs]]).<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>

==History==

LDPC codes were originally invented by [[Robert G. Gallager]] (and are thus also known as Gallager codes). Gallager developed the LDPC concept in his doctoral dissertation at the [[Massachusetts Institute of Technology]] in 1960.<ref>{{Cite news |last=Hardesty |first=L. |date=January 21, 2010 |title=Explained: Gallager codes |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |access-date=August 7, 2013 |journal=MIT News}}</ref><ref name="G1962">{{cite journal |last=Gallager |first=R.G. |date=January 1962 |title=Low density parity check codes |journal=IRE Trans. Inf. Theory |volume=8 |issue=1 |pages=21–28 |doi=10.1109/TIT.1962.1057683 |s2cid=260490814 |hdl=1721.1/11804/32786367-MIT}}</ref> However, their iterative decoding algorithm (despite having linear complexity), was prohibitively computationally expensive at the time.

Renewed interest in the codes emerged following the invention of the closely-related [[turbo code]]s (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently 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> Initial industry preference for LDPC codes over turbo codes stemmed from patent-related constraints on the latter<ref name="Closing">{{cite journal |author=Erico Guizzo |date=Mar 1, 2004 |title=CLOSING IN ON THE PERFECT CODE |url=https://spectrum.ieee.org/closing-in-on-the-perfect-code |url-status=dead |journal=IEEE Spectrum |archive-url=https://web.archive.org/web/20210902170851/https://spectrum.ieee.org/closing-in-on-the-perfect-code |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>. InOver the time that has elapsed since their discovery, advances in LDPC 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> Although the fundamental patent for turbo codes has expired (on August 29, 2013),<ref>{{cite patent|country=US|number=5446747|url=https://www.google.com/patents/US5446747}}</ref><ref>{{cite journal |last=Mackenzie |first=D. |date=9 July 2005 |title=Communication speed nears terminal velocity |journal=New Scientist}}</ref> LDPC codes are now still being preferred 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. |date=2020 |title=Low-Density Parity-Check Codes Achieve List-Decoding Capacity |journal=SIAM Journal on Computing |volume=53 |issue=FOCS 2020 |pages=38–73 |arxiv=1909.06430 |doi=10.1137/20M1365934 |s2cid=244549036}}</ref>