Content deleted Content added
LouScheffer (talk | contribs) →Low Density Parity Check codes: Change reference to standard format; link co-author |
LouScheffer (talk | contribs) →Low Density Parity Check codes: Add reference that explicitly states they were too complex at the time they were invented |
||
Line 83:
=== Low Density Parity Check codes ===
'''[[Low-density parity-check code]]s''', also known as '''LDPC''' or '''Gallager''' codes, are an example of an algorithm that was galactic when first developed, but became practical as computation improved. They were originally conceived by [[Robert G. Gallager]] 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> Although their performance was much better than other codes of that time, reaching the [[Gilbert–Varshamov bound for linear codes]], the codes were largely ignored as their iterative decoding algorithm was prohibitively computationally expensive for the hardware available.<ref>{{cite journal
|title=The development of turbo and LDPC codes for deep-space applications
|last1=Andrews |first1= Kenneth S |last2=Divsalar |first2= Dariush |last3=Dolinar |first3= Sam
|last4=Hamkins |first4= Jon |last5=Jones |first5=Christopher R |last6=Pollara |last5=Fabrizio
|journal=Proceedings of the IEEE
|volume=95
|number=11
|pages=2142--2156
|year=2007
|publisher=IEEE
|url=https://web.archive.org/web/20090620174506id_/http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf}}</ref>
Renewed interest in LDPC 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
| |||