Content deleted Content added
Citation bot (talk | contribs) Added volume. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Error detection and correction | #UCB_Category 48/128 |
|||
Line 7:
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==
| |||