Low-density parity-check code: Difference between revisions

Revision as of 22:13, 6 May 2024

Latest revision as of 20:28, 26 August 2025

(38 intermediate revisions by 11 users not shown)

Line 3:

{{Use mdy dates|date = March 2019}}

'''Low-density parity-check (LDPC)''' codes are a class of [[error correction code]]s which (together with the closely related [[turbo code]]s) have gained prominence in [[coding theory]] and [[information theory]] since the late 1990s. The codes today are widely used in applications ranging from wireless communications to flash-memory storage. Together with turbo codes, they sparked a revolution in coding theory, achieving order-of-magnitude improvements in performance compared to traditional error correction codes.<ref>{{Cite web |title=Turbo Codes Explained: History, Examples, and Applications - IEEE Spectrum |url=https://spectrum.ieee.org/turbo-codes |access-date=2024-12-18 |website=spectrum.ieee.org |language=en}}</ref>

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>{{citation |author=Amin Shokrollahi |url=http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |title=LDPC Codes: An Introduction |archive-url=https://web.archive.org/web/20170517034849/http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |archive-date=2017-05-17}}</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.

Central to the performance of LDPC codes is their adaptability to the iterative [[belief propagation]] decoding algorithm. Under this algorithm, they can be designed to approach theoretical limits ([[Channel capacity|capacities]]) of many channels<ref>{{Cite journal |title=Design of capacity-approaching irregular low-density parity-check codes |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 |bibcode=2001ITIT...47..619R }}</ref> at low computation costs.

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.

Theoretically, analysis of LDPC codes focuses on sequences of codes of fixed [[code rate]] and increasing [[block length]]. These sequences are typically tailored to a set of channels. For appropriately designed sequences, the decoding error under belief propagation can often be proven to be vanishingly small (approaches zero with the block length) at rates that are very close to the capacities of the channels. Furthermore, this can be achieved at a complexity that is linear in the block length.

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

This theoretical performance is made possible using a flexible design method that is based on sparse [[Tanner graph]]s (specialized [[bipartite graph]]s).<ref>{{citation |author=Amin Shokrollahi |url=http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |title=LDPC Codes: An Introduction |archive-url=https://web.archive.org/web/20170517034849/http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |archive-date=2017-05-17}}</ref>

==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 }}</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.

Impractical to implement when first developed by [[Robert G. Gallager|Gallager]] in 1963,<ref>{{Cite book |first=Robert G. |last=Gallager |title= Low Density Parity Check Codes |publisher= M.I.T. Press |year= 1963 |url= http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/ldpc.pdf |access-date= August 7, 2013 }}</ref> LDPC codes were forgotten until his work was rediscovered in 1996.<ref name=MacKay96>[[David J.C. MacKay]] and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996</ref> [[Turbo code]]s, another class of capacity-approaching codes discovered in 1993, became the coding scheme of choice in the late 1990s, used for applications such as the [[Deep Space Network]] and [[satellite communication]]s. LDPC codes then received renewed interest as a patent-free alternative of similar performance.<ref name="Closing"/> Since then, advances in low-density parity-check 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>

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 |first2=Radford M |author2-link=Radford M. Neal

|journal=Electronics Letters

|volume=32

|number=18

|pages=1645–1646

|year=1996

|publisher=IET

|doi=10.1049/el:19961141 |bibcode=1996ElL....32.1645M |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 havealso beenfollows shownfrom totheir haveamenability idealto combinatorialmathematical propertiesanalysis. 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 |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 |bibcode=2001ITIT...47..619R }}</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 |datearxiv=20201909.06430 |doi=10.1137/20M1365934 |s2cid=244549036 }}</ref>

==Applications==

Line 17 ⟶ 32:

In 2008, LDPC beat convolutional turbo codes as the [[forward error correction]] (FEC) system for the [[ITU-T]] [[G.hn]] standard.<ref>[http://homepnablog.typepad.com/my_weblog/2008/12/ghn-a-phy-for-all-seasons.html HomePNA Blog: G.hn, a PHY For All Seasons]</ref> G.hn chose LDPC codes over turbo codes because of their lower decoding complexity (especially when operating at data rates close to 1.0&nbsp;Gbit/s) and because the proposed turbo codes exhibited a significant [[error floor]] at the desired range of operation.<ref>[http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html IEEE Communications Magazine paper on G.hn] {{webarchive|url=https://web.archive.org/web/20091213012126/http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html |date=2009-12-13 }}</ref>

LDPC codes are also used for [[10GBASE-T]] Ethernet, which sends data at 10 gigabits per second over twisted-pair cables. As of 2009, LDPC codes are also part of the [[Wi-Fi]] 802.11 standard as an optional part of [[802.11n]] and [[802.11ac]], in the High Throughput (HT) PHY specification.<ref>IEEE Standard, section 20.3.11.6 [https://web.archive.org/web/20100704235707/http://standards.ieee.org/getieee802/download/802.11n-2009.pdf "802.11n-2009"], IEEE, October 29, 2009, accessed March 21, 2011.</ref> LDPC is a mandatory part of [[802.11ax]] (Wi-Fi 6).<ref>{{cite web |title=IEEE SA - IEEE 802.11ax-2021 |url=https://standards.ieee.org/ieee/802.11ax/7180/ |website=IEEE Standards Association |access-date=22 May 2022 |language=en}}</ref>

Some [[OFDM]] systems add an additional outer error correction that fixes the occasional errors (the "error floor") that get past the LDPC correction inner code even at low [[bit error rate]]s.

Line 33 ⟶ 48:

[[5G NR]] uses [[Polar code (coding theory)|polar code]] for the control channels and LDPC for the data channels.<ref>{{cite web|url=https://accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|title=5G Channel Coding|access-date=January 6, 2019|archive-url=https://web.archive.org/web/20181206003124/https://www.accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|archive-date=December 6, 2018|url-status=dead}}</ref><ref>{{cite web|url=https://accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|title=A Vision for 5G Channel Coding|last=Maunder|first=Robert|date=September 2016|access-date=January 6, 2019|archive-url=https://web.archive.org/web/20181206003124/https://www.accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|archive-date=December 6, 2018|url-status=dead}}</ref>

Although LDPC code has had its success in commercial hard disk drives, to fully exploit its error correction capability in [[SSD]]s demands unconventional fine-grained flash memory sensing, leading to an increased memory read latency. LDPC-in-SSD<ref>{{Cite conference |author= Kai Zhao |author2=Wenzhe Zhao |author3=Hongbin Sun |author4=Tong Zhang |author5=Xiaodong Zhang |author6=Nanning Zheng | title=LDPC-in-SSD: Making Advanced Error Correction Codes Work Effectively in Solid State Drives |conference= FAST' 13| pages=243–256|year=2013|url=https://www.usenix.org/system/files/conference/fast13/fast13-final125.pdf}}</ref> is an effective approach to deploy LDPC in SSD with a very small latency increase, which turns LDPC in SSD into a reality. Since then, LDPC has been widely adopted in commercial SSDs in both customer-grades and enterprise-grades by major storage vendersvendors. Many TLC (and later) SSDs are using LDPC codes. A fast hard-decode (binary erasure) is first attempted, which can fall back into the slower but more powerful soft decoding.<ref>{{cite web|url= https://www.eetimes.com/soft-decoding-in-ldpc-based-ssd-controllers/|website=EE Times|date=2015|title= Soft-Decoding in LDPC based SSD Controllers}}</ref>

==Operational use==

Line 128 ⟶ 143:

As a check, the row space of '''G''' is orthogonal to '''H''' such that <math> G \odot H^T = 0 </math>

The input bit-string '101' is found in as the first 3 bits of the codeword '101011', due to the presence of the identity matrix <math>I_{k}</math>. The trailing three bits '011' of the codeword are the parity bits.

== Example encoder ==

Line 205 ⟶ 220:

== 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 |first1=T.J. |last1=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|bibcode=2001ITIT...47..619R |url=http://infoscience.epfl.ch/record/95795 }}</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 ⟶ 227:

*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 |first1=T.J. |last1=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 |bibcode=2001ITIT...47..638R |url=http://infoscience.epfl.ch/record/95793 }}</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 223 ⟶ 238:

</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 |first1=Y. |last1=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 |bibcode=2001ITIT...47.2711K |citeseerx=10.1.1.100.3023 }}</ref>

== Compared to turbo codes ==

Line 249 ⟶ 264:

*[[CMMB]] (China Multimedia Mobile Broadcasting)

*[[DVB-S2]] / [[DVB-T2]] / [[DVB-C2]] (digital video broadcasting, 2nd generation)

*[[DMB-T/H]] (digital video broadcasting)<ref>{{cite web |urllast1=https://spectrum.ieee.org/consumerDill |first1=Jeffery |last2=Li |first2=Huanlin |date=June 27, 2011 |editor-electronics/standards/does-china-have-the-best-digital-television-standard-on-thelast=Cao |editor-planet/2first=Yanyan |title=IEEEStudies Spectrum: Does Chinaon HaveLowering the BestError DigitalFloors Televisionof StandardFinite onLength theLDPC Planet?codes |websiteurl=spectrumhttps://etd.ieeeohiolink.orgedu/acprod/odb_etd/ws/send_file/send?accession=ohiou1305126490&disposition=inline |url-status=dead |archive-url=https://web.archive.org/web/20091212140917/http://spectrum.ieee.org/consumer-electronics/standards/does-china-have-the-best-digital-television-standard-on-the-planet/2 |archive-date=2009-12-12 |website=[[IEEE]] |publisher=Ohio University, Electrical Engineering (Engineering and Technology)}}</ref>

*[[WiMAX]] (IEEE 802.16e standard for microwave communications)

* [[IEEE 802.11n-2009]] ([[Wi-Fi]] standard)

Line 265 ⟶ 280:

*[[Tornado code]]s (LDPC codes designed for [[binary erasure channel|erasure decoding]])

*[[Turbo code]]s

=== Capacity-achieving codes ===

So far there is only one capacity achieving code by design and proof.

*[[Polar code (coding theory)|Polar codes]]

== References ==

Line 270 ⟶ 289:

== External links ==

* [httphttps://sigpromuwww.orgresearchgate.net/profile/Sarah-Johnson-64/publication/228977165_Introducing_Low-Density_Parity-Check_Codes/links/sarah0deec51c7c8f92e602000000/SJohnsonLDPCintroIntroducing-Low-Density-Parity-Check-Codes.pdf Introducing Low-Density Parity-Check Codes (by Sarah J Johnson, 2010)]

* [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 }}