Low-density parity-check code: Difference between revisions

Revision as of 08:18, 19 December 2024

Latest revision as of 20:28, 26 August 2025

(18 intermediate revisions by 7 users not shown)

Line 3:

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

'''Low-density parity-check (LDPC)''' codes are a class of [[Error correction code|error correction codescode]]s which (together with the closely- related [[Turboturbo code|turbo codes]]s) have gained prominence in [[coding theory]] and [[information theory]] insince 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>.

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 webjournal |title=Design of capacity-approaching irregular low-density parity-check codes |urljournal=https://ieeexploreIEEE Transactions on Information Theory |date=2001 |doi=10.ieee.org/document1109/18.910578 |archivelanguage=en-urlUS |last1=http://webRichardson |first1=T.archiveJ.org/web/20240909161749/https://ieeexplore.ieee.org/document/910578/ |archive-datelast2=2024-09-09Shokrollahi |access-datefirst2=2024-12-18M.A. |last3=Urbanke |websitefirst3=ieeexploreR.ieeeL.org |languagevolume=en-US47 |issue=2 |pages=619–637 |bibcode=2001ITIT...47..619R }}</ref> at low computation costs.

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.

This theoretical performance is made possible using a flexible design method that is based on sparse [[Tanner graph|Tanner graphs]]s (specialized [[bipartite graph|bipartite graphs]]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>

This theoretical performance is made possible using a flexible design method that is based on sparse [[Tanner graph|Tanner graphs]] (specialized [[bipartite graph|bipartite graphs]]).<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 inventedconceived by [[Robert G. Gallager]] (and are thus also known as Gallager codes). Gallager developeddevised the LDPC conceptcodes 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> HoweverThe codes were largely ignored at the time, as their iterative decoding algorithm (despite having linear complexity), was prohibitively computationally expensive atfor the timehardware 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
|title=Near Shannon limit performance of low density parity check codes
|last1=MacKay |first1=David JC |author1-link=David J. C. MacKay]]|last2=Neal and|first2=Radford M |author2-link=Radford M. Neal,
"Near Shannon|journal=Electronics LimitLetters
Performance of|volume=32
Low Density|number=18
Parity Check|pages=1645–1646
Codes," Electronics|year=1996
Letters, July|publisher=IET
1996 |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 also follows from thetheir amenability to theoreticalmathematical analysis. For example, 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. 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 |arxiv=1909.06430 |doi=10.1137/20M1365934 |s2cid=244549036}}</ref>

==Applications==

Line 38 ⟶ 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 133 ⟶ 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 210 ⟶ 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 217 ⟶ 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 228 ⟶ 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 254 ⟶ 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=[[IEEE]]https://etd.ohiolink.edu/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)