Low-density parity-check code: Difference between revisions

Revision as of 21:14, 8 February 2025

Revision as of 12:35, 4 March 2025

Line 14:

LDPC codes were originally conceived by [[Robert G. Gallager]] (and are thus also known as Gallager codes). Gallager devised the codes 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> The codes were largely ignored at the time, as their iterative decoding algorithm (despite having linear complexity), was prohibitively computationally expensive for the hardware available.

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">[[{{cite journal
|title=Near Shannon limit performance of low density parity check codes
|last1=MacKay |first1=David JC |author1-link=David J. C. MacKay]]|last2=Neal and|first2=Radford M |author2-link=Radford M. Neal,
"Near Shannon|journal=Electronics Limitletters
Performance of|volume=32
Low Density|number=18
Parity Check|pages=1645--1646
Codes," Electronics|year=1996
Letters, July|publisher=IET
1996 |url=https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/MacKay96.pdf}}</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> Over 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.

Theoretical interest in LDPC codes also follows from their amenability to mathematical analysis. In his dissertation, Gallager showed that LDPC codes achieve the [[Gilbert–Varshamov bound for linear codes]] over binary fields with high probability. Over the [[binary erasure channel]], code sequences were designed at rates arbitrary close to channel capacity, with provably vanishing decoding error probability and linear decoding complexity.<ref>{{Cite journal |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-19 |journal=IEEE Transactions on Information Theory |date=2001 |doi=10.1109/18.910578 |language=en-US |last1=Richardson |first1=T.J. |last2=Shokrollahi |first2=M.A. |last3=Urbanke |first3=R.L. |volume=47 |issue=2 |pages=619–637 }}</ref> 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>