Low-density parity-check code: Difference between revisions

Revision as of 21:08, 28 November 2023

Revision as of 08:08, 1 December 2023

Line 5:

In [[information theory]], a '''low-density parity-check''' ('''LDPC''') '''code''' is a [[Linear code|linear]] [[error correcting code]], a method of transmitting a message over a [[signal noise|noisy]] transmission channel.<ref>{{cite book |author-link=David J.C. MacKay |first=David J. |last=MacKay |title=Information theory, Inference and Learning Algorithms |publisher=Cambridge University Press |date=2003 |isbn=0-521-64298-1 |pages= |url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html}}</ref><ref>{{cite book |author-link=Todd K. Moon |first=Todd K. |last=Moon |title=Error Correction Coding, Mathematical Methods and Algorithms |publisher=Wiley |date=2005 |isbn=0-471-64800-0 |pages= |url=}} (Includes code)</ref> An LDPC code is constructed using a sparse [[Tanner graph]] (subclass of the [[bipartite graph]]).<ref>[[Amin Shokrollahi]] (2003) LDPC Codes: An Introduction</ref> LDPC codes are [[:Category:capacity-approaching codes|capacity-approaching codes]], which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum (the [[Shannon–Hartley theorem|Shannon limit]]) for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative [[belief propagation]] techniques, LDPC codes can be decoded in time linear in their block length.

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}} "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 |lastlast1=Mosheiff |firstfirst1=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 |doi=10.1137/20M1365934 |s2cid=244549036 }}</ref>

==History==

Line 197:

=== Updating node information ===

In recent years{{When|date=May 2023}}, there has also been a great deal of work spent studying the effects of alternative schedules for variable-node and constraint-node update. The original technique that was used for decoding LDPC codes was known as ''flooding''. This type of update required that, before updating a variable node, all constraint nodes needed to be updated and vice versa. In later work by Vila Casado ''et al.'',<ref name=Vila07>{{cite conference |firstfirst1=A.I.V. |lastlast1=Casado |first2=M. |last2=Griot |first3=R.D. |last3=Wesel |title=Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes |conference=2007 IEEE International Conference on Communications, Glasgow, UK |volume= |issue= |pages=932–7 |date=2007 |doi=10.1109/ICC.2007.158|arxiv=cs/0702111 }}</ref> alternative update techniques were studied, in which variable nodes are updated with the newest available check-node information.{{Citation needed|date=May 2023}}

The intuition behind these algorithms is that variable nodes whose values vary the most are the ones that need to be updated first. Highly reliable nodes, whose [[log-likelihood ratio]] (LLR) magnitude is large and does not change significantly from one update to the next, do not require updates with the same frequency as other nodes, whose sign and magnitude fluctuate more widely.{{Citation needed|date=May 2023}}

These scheduling algorithms show greater speed of convergence and lower error floors than those that use flooding. These lower error floors are achieved by the ability of the Informed Dynamic Scheduling (IDS)<ref name=Vila07/> algorithm to overcome trapping sets of near codewords.<ref name=Richardson03>{{cite journal |first=T. |last=Richardson |title=Error floors of LDPC codes |journal=Proceedings of the annualAnnual Allerton conferenceConference on communicationCommunication controlControl and computingComputing |volume=41 |issue=3 |pages=1426–35 |date=October 2003 |doi= |url=https://www.academia.edu/download/83908330/Error_floors_of_LDPC_codes20220411-30673-13qgho0.pdf |issn=0732-6181}}</ref>

When nonflooding scheduling algorithms are used, an alternative definition of iteration is used. For an (''n'',&nbsp;''k'') LDPC code of rate ''k''/''n'', a full ''iteration'' occurs when ''n'' variable and ''n''&nbsp;&minus;&nbsp;''k'' constraint nodes have been updated, no matter the order in which they were updated.{{Citation needed|date=May 2023}}

== Code construction ==

For large block sizes, LDPC codes are commonly constructed by first studying the behaviour of decoders. As the block size tends to infinity, LDPC decoders can be shown to have a noise threshold below which decoding is reliably achieved, and above which decoding is not achieved,<ref name=richardson01>{{cite journal |firstfirst1=T.J. |lastlast1=Richardson |first2=M.A. |last2=Shokrollahi |first3=R.L. |last3=Urbanke |title=Design of capacity-approaching irregular low-density parity-check codes |journal=IEEE Transactions on Information Theory |volume=47 |issue=2 |pages=619–637 |date=February 2001 |doi=10.1109/18.910578}}</ref> colloquially referred to as the [[cliff effect]]. This threshold can be optimised by finding the best proportion of arcs from check nodes and arcs from variable nodes. An approximate graphical approach to visualising this threshold is an [[EXIT chart]].{{Citation needed|date=May 2023}}

The construction of a specific LDPC code after this optimization falls into two main types of techniques:{{Citation needed|date=May 2023}}

Line 212:

*Combinatorial approaches

Construction by a pseudo-random approach builds on theoretical results that, for large block size, a random construction gives good decoding performance.<ref name=MacKay96/> In general, pseudorandom codes have complex encoders, but pseudorandom codes with the best decoders can have simple encoders.<ref name=richardson01b>{{cite journal |firstfirst1=T.J. |lastlast1=Richardson |first2=R.L. |last2=Urbanke |title=Efficient encoding of low-density parity-check codes |journal=IEEE Transactions on Information Theory |volume=47 |issue=2 |pages=638–656 |date=February 2001 |doi=10.1109/18.910579 }}</ref> Various constraints are often applied to help ensure that the desired properties expected at the theoretical limit of infinite block size occur at a finite block size.{{Citation needed|date=May 2023}}

Combinatorial approaches can be used to optimize the properties of small block-size LDPC codes or to create codes with simple encoders.{{Citation needed|date=May 2023}}

Line 220:

[http://www.eecg.toronto.edu/~tcc/darabiha_jssc08.pdf "Power Reduction Techniques for LDPC Decoders"]

</ref> Compared to randomly generated LDPC codes, structured LDPC codes—such as the LDPC code used in the [[DVB-S2]] standard—can have simpler and therefore lower-cost hardware—in particular, codes constructed such that the H matrix is a [[circulant matrix]].<ref>

{{cite journal |firstfirst1=Z. |lastlast1=Zhang |first2=V. |last2=Anantharam |first3=M.J. |last3=Wainwright |first4=B. |last4=Nikolic |title=An Efficient 10GBASE-T Ethernet LDPC Decoder Design With Low Error Floors |journal=IEEE Journal of Solid-State Circuits |volume=45 |issue=4 |pages=843–855 |date=April 2010 |doi=10.1109/JSSC.2010.2042255 |bibcode=2010IJSSC..45..843Z |s2cid=10431486 |url=http://people.eecs.berkeley.edu/~wainwrig/Papers/ZhangEtAl10.pdf}}

</ref>

Yet another way of constructing LDPC codes is to use [[finite geometry|finite geometries]]. This method was proposed by Y. Kou ''et al.'' in 2001.<ref name=Kou1>{{cite journal |firstfirst1=Y. |lastlast1=Kou |first2=S. |last2=Lin |first3=M.P.C. |last3=Fossorier |title=Low-density parity-check codes based on finite geometries: a rediscovery and new results |journal=IEEE Transactions on Information Theory |volume=47 |issue=7 |pages=2711–36 |date=November 2001 |doi=10.1109/18.959255 }}</ref>

== LDPC codes vs. turbo codes ==

LDPC codes can be compared with other powerful coding schemes, e.g. [[turbo code]]s.<ref>{{cite conference |firstfirst1=B. |lastlast1=Tahir |first2=S. |last2=Schwarz |first3=M. |last3=Rupp |title=BER comparison between Convolutional, Turbo, LDPC, and Polar codes |conference=2017 24th International Conference on Telecommunications (ICT), Limassol, Cyprus |volume= |issue= |pages=1–7 |date=2017 |doi=10.1109/ICT.2017.7998249 |url=}}</ref> In one hand, [[Bit error rate|BER]] performance of turbo codes is influenced by low codes limitations.<ref>{{cite book |first=K. |last=Moon Todd |title=Error correction coding: mathematical methods and algorithms |publisher=Wiley |___location= |date=2005 |isbn=0-471-64800-0 |pages=614 |url=}}</ref> LDPC codes have no limitations of minimum distance,<ref>{{harvnb|Moon Todd|2005|p=653}}</ref> that indirectly means that LDPC codes may be more efficient on relatively large [[code rate]]s (e.g. 3/4, 5/6, 7/8) than turbo codes. However, LDPC codes are not the complete replacement: turbo codes are the best solution at the lower code rates (e.g. 1/6, 1/3, 1/2).<ref>Andrews, Kenneth S., et al. "The development of turbo and LDPC codes for deep-space applications." Proceedings of the IEEE 95.11 (2007): 2142-2156.</ref><ref>Hassan, A.E.S., Dessouky, M., Abou Elazm, A. and Shokair, M., 2012. [https://www.researchgate.net/profile/Mona_Shokair/publication/234051399_Evaluation_of_Complexity_Versus_Performance_for_Turbo_Code_and_LDPC_Under_Different_Code_Rates/links/56b7b68908ae44bb330bc82f.pdf Evaluation of complexity versus performance for turbo code and LDPC under different code rates]. Proc. SPACOMM, pp.93-98.</ref>

== See also ==

Line 275:

* [http://bernh.net/media/download/papers/ldpc.pdf LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)]

* [https://www.nt.tuwien.ac.at/wp-content/uploads/2016/10/DC2-16_Ch7_LDPC.pdf LDPC Codes (TU Wien)] {{Webarchive|url=https://web.archive.org/web/20190228003946/https://www.nt.tuwien.ac.at/wp-content/uploads/2016/10/DC2-16_Ch7_LDPC.pdf |date=February 28, 2019 }}

* {{cite book |url=http://www.inference.phy.cam.ac.uk/mackay/itila/ |title=Information Theory, Inference, and Learning Algorithms |author-link=David J.C. MacKay |first=David J.C. |last=MacKay |publisher=Cambridge University Press |isbn=9780521642989 |date= September 25, 2003|pages=557–573 |chapter=47. Low-Density Parity-Check Codes |chapter-url={{GBurl|AKuMj4PN_EMC|p=557}} }}

* {{cite arxivarXiv |eprint=cs/0610022 |title=Iterative Decoding of Low-Density Parity Check Codes |first=Venkatesan |last=Guruswami |date=2006}}

* [http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf LDPC Codes: An Introduction (by Amin Shokrollahi, 2003)]

* [http://www.tsc.uc3m.es/~fernando/BP_LDPC.pdf Belief-Propagation Decoding of LDPC Codes (by Amir Bennatan, Princeton University)]