Low-density parity-check code: Difference between revisions

Revision as of 19:38, 18 December 2024

Revision as of 19:54, 18 December 2024

Line 5:

LDPC codes are a class of [[Error correction code|error correction codes]] which (together with the closely-related [[Turbo code|turbo codes]]) have gained prominence in [[coding theory]] and [[information theory]] in the late 1990s. The codes today are widely used in applications ranging from wireless communications to flash-memory storage. Together with turbo codes, they sparked a revolution in coding theory, achieving order-of-magnitude improvements in performance compared to traditional error correction codes<ref>{{Cite web |title=Turbo Codes Explained: History, Examples, and Applications - IEEE Spectrum |url=https://spectrum.ieee.org/turbo-codes |access-date=2024-12-18 |website=spectrum.ieee.org |language=en}}</ref>.

Theoretically, sequences of LDPC codes exist at rates that approach theoretical limits ([[Channel capacity|capacities]]) of many channels<ref>{{Cite web |title=Design of capacity-approaching irregular low-density parity-check codes |url=https://ieeexplore.ieee.org/document/910578 |archive-url=http://web.archive.org/web/20240909161749/https://ieeexplore.ieee.org/document/910578/ |archive-date=2024-09-09 |access-date=2024-12-18 |website=ieeexplore.ieee.org |language=en-US}}</ref>. Codes within each such sequence, have increasing block length (at the same [[code rate]]). Most importantly, when appropriately designed, the codes in the sequence can be decoded using aan iterative [[belief propagation]] algorithm, to achieve vanishingly small decoding error, at a complexity that is linear in the block length.

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 are alsooriginally knowninvented as '''Gallager codes''', in honor ofby [[Robert G. Gallager]], who(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 |title=Explained: Gallager codes |first=L. |last=Hardesty |journal=MIT News |date= January 21, 2010 |access-date= August 7, 2013 |journal=MIT News}}</ref><ref name="G1962">{{cite journal |last=Gallager |first=R.G. |lastdate=GallagerJanuary 1962 |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 |s2cid=260490814 |hdl=1721.1/11804/32786367-MIT|s2cid=260490814 }}</ref> However, LDPCtheir codesiterative requiredecoding computationallyalgorithm expensive(despite iterativehaving decodinglinear complexity), sowas theyprohibitively wentcomputationally unusedexpensive forat decadesthe time. In 1993Renewed interest in the newlycodes inventedemerged following the invention of the closely-related [[turbo code]]s demonstrated(1993), that codeswhose withsimilarly iterative decoding couldalgorithm far outperformoutperformed other codes used at that time,. but turboLDPC codes were patentedsubsequently andrediscovered requiredin a1996.<ref feename="MacKay96">[[David forJ.C. useMacKay]] and Radford M. ThisNeal, raised"Near renewedShannon interestLimit inPerformance LDPCof codesLow Density Parity Check Codes," whichElectronics wereLetters, shownJuly to1996</ref> have similar performance,Initial butindustry werepreference muchfor olderLDPC andcodes over turbo codes stemmed from patent-free.related constraints on the latter<ref name="Closing">{{cite journal |author=Erico Guizzo |date=Mar 1, 2004 |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 |url-status=dead |journal=IEEE Spectrum |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 In the time that has elapsed, 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 |country=US |number=5446747}}</ref><ref>{{cite journal |journallast=NewMackenzie Scientist|first=D. |date=9 July 2005 |title=Communication speed nears terminal velocity |firstjournal=D.New |last=Mackenzie |date=9 July 2005Scientist}}</ref> LDPC codes are now still usedbeing 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 |datearxiv=2020 |volume=531909.06430 |doi=10.1137/20M1365934 |s2cid=244549036 |arxiv=1909.06430 }}</ref>

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 |volume=53 |doi=10.1137/20M1365934 |s2cid=244549036 |arxiv=1909.06430 }}</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==