Low-density parity-check code: Difference between revisions

Revision as of 12:38, 4 March 2025

Revision as of 12:49, 4 March 2025

Line 12:

==History==

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<ref>{{cite thesis |last=Gallager |first=Robert G. |date= 1960 |title=Low density parity check codes |url=https://dspace.mit.edu/bitstream/handle/1721.1/11804/32786367-MIT.pdf |degree=Ph.D |publisher=Massachusetts Institute of Technology }}</ref> 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 |url=https://dspace.mit.edu/bitstream/handle/1721.1/11804/32786367-MIT.pdf}}</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