View source for Low-density parity-check code

{{Short description|Linear error correcting code}}
{{Use American English|date = March 2019}}
{{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>

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 |url=https://ieeexplore.ieee.org/document/910578 |archive-url=http://web.archive.org/web/20240909161749/https://ieeexplore.ieee.org/document/910578/ |archive-date=2024-09-09 |access-date=2024-12-18 |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 }}</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]]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 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.

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">[[David J.C. MacKay]] and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996</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 their amenability to mathematical analysis.   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 |url=https://ieeexplore.ieee.org/document/910578 |archive-url=http://web.archive.org/web/20240909161749/https://ieeexplore.ieee.org/document/910578/ |archive-date=2024-09-09 |access-date=2024-12-19 |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 }}</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==
In 2003, an [[Repeat-accumulate code#Irregular Repeat Accumulate Codes|irregular repeat accumulate]] (IRA) style LDPC code beat six turbo codes to become the error-correcting code in the new [[DVB-S2]] standard for [[digital television]].<ref name="hughesdvb">[http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf Presentation by Hughes Systems] {{webarchive|url=https://web.archive.org/web/20061008053124/http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf |date=2006-10-08 }}</ref> The DVB-S2 selection committee made decoder complexity estimates for the turbo code proposals using a much less efficient serial decoder architecture rather than a parallel decoder architecture. This forced the turbo code proposals to use frame sizes on the order of one half the frame size of the LDPC proposals.{{Citation needed|date=May 2023}}

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.

For example:
The [[Reed-Solomon code]] with LDPC Coded Modulation (RS-LCM) uses a Reed-Solomon outer code.<ref>
Chih-Yuan Yang, Mong-Kai Ku.
http://123seminarsonly.com/Seminar-Reports/029/26540350-Ldpc-Coded-Ofdm-Modulation.pdf
"LDPC coded OFDM modulation for high spectral efficiency transmission"
</ref> The DVB-S2, the DVB-T2 and the DVB-C2 standards all use a [[BCH code]] outer code to mop up residual errors after LDPC decoding.<ref>
Nick Wells.
[http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf "DVB-T2 in relation to the DVB-x2 Family of Standards"] {{webarchive|url=https://web.archive.org/web/20130526003113/http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf |date=2013-05-26 }}
</ref>

[[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 venders. 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==
{{More citations needed section|date=May 2023}}
LDPC codes functionally are defined by a sparse [[parity-check matrix]]. This [[sparse matrix]] is often randomly generated, subject to the [[sparsity]] constraints—[[#Code construction|LDPC code construction]] is discussed [[#Code construction|later]]. These codes were first designed by Robert Gallager in 1960.<ref name="G1962" />

Below is a graph fragment of an example LDPC code using [[factor graph|Forney's factor graph notation]]. In this graph, ''n'' variable nodes in the top of the graph are connected to (''n''&minus;''k'') constraint nodes in the bottom of the graph.

This is a popular way of graphically representing an (''n'',&nbsp;''k'') LDPC code. The bits of a valid message, when placed on the '''T's''' at the top of the graph, satisfy the graphical constraints. Specifically, all lines connecting to a variable node (box with an '=' sign) have the same value, and all values connecting to a factor node (box with a '+' sign) must sum, [[modular arithmetic|modulo]] two, to zero (in other words, they must sum to an even number; or there must be an even number of odd values).

[[Image:ldpc code fragment factor graph.svg|none]]
Ignoring any lines going out of the picture, there are eight possible six-bit strings corresponding to valid codewords: (i.e., 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). This LDPC code fragment represents a three-bit message encoded as six bits. Redundancy is used, here, to increase the chance of recovering from channel errors. This is a (6,&nbsp;3) [[linear code]], with ''n''&nbsp;=&nbsp;6 and ''k''&nbsp;=&nbsp;3.

Again ignoring lines going out of the picture, the parity-check matrix representing this graph fragment is

:<math>
\mathbf{H} = 
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}.
</math>

In this matrix, each row represents one of the three parity-check constraints, while each column represents one of the six bits in the received codeword.

In this example, the eight codewords can be obtained by putting the [[parity-check matrix]] '''H''' into this form <math>\begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}</math> through basic [[row operations]] in [[GF(2)]]:
:<math>\mathbf{H}
=
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}_1
\sim
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 & 0 \\
\end{pmatrix}_2
\sim
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 \\
\end{pmatrix}_3
\sim
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 \\
\end{pmatrix}_4.
</math>

Step 1: H.

Step 2: Row 1 is added to row 3.

Step 3: Row 2 and 3 are swapped.

Step 4: Row 1 is added to row 3.

From this, the [[generator matrix]] '''G''' can be obtained as <math>\begin{bmatrix} I_{k} | P \end{bmatrix}</math> (noting that in the special case of this being a binary code <math>P = -P</math>), or specifically:

:<math>\mathbf{G}
=
\begin{pmatrix}
1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 \\
\end{pmatrix}.
</math>

Finally, by multiplying all eight possible 3-bit strings by '''G''', all eight valid codewords are obtained. For example, the codeword for the bit-string '101' is obtained by:

:<math>
\begin{pmatrix}
1 & 0 & 1 \\
\end{pmatrix} 
\odot
\begin{pmatrix}
1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 \\
\end{pmatrix}
=
\begin{pmatrix}
1 & 0 & 1 & 0 & 1 & 1 \\
\end{pmatrix}
</math>,

where <math>\odot</math> is symbol of mod 2 multiplication.

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

The bit-string '101' is found in as the first 3 bits of the codeword '101011'.

== Example encoder ==
{{Unreferenced section|date=May 2023}}
[[File:LDPC encoder Figure.png|thumb|none|500px|LDPC encoder]]

During the encoding of a frame, the input data bits (D) are repeated and distributed to a set of constituent encoders. The constituent encoders are typically accumulators and each accumulator is used to generate a parity symbol. A single copy of the original data (S<sub>0,K-1</sub>) is transmitted with the parity bits (P) to make up the code symbols. The S bits from each constituent encoder are discarded.

The parity bit may be used within another constituent code.

In an example using the DVB-S2 rate 2/3 code the encoded block size is 64800 symbols (N=64800) with 43200 data bits (K=43200) and 21600 parity bits (M=21600). Each constituent code (check node) encodes 16 data bits except for the first parity bit which encodes 8 data bits. The first 4680 data bits are repeated 13 times (used in 13 parity codes), while the remaining data bits are used in 3 parity codes (irregular LDPC code).

For comparison, classic turbo codes typically use two constituent codes configured in parallel, each of which encodes the entire input block (K) of data bits. These constituent encoders are recursive convolutional codes (RSC) of moderate depth (8 or 16 states) that are separated by a code interleaver which interleaves one copy of the frame.

The LDPC code, in contrast, uses many low depth constituent codes (accumulators) in parallel, each of which encode only a small portion of the input frame. The many constituent codes can be viewed as many low depth (2 state) "[[convolutional codes]]" that are connected via the repeat and distribute operations. The repeat and distribute operations perform the function of the interleaver in the turbo code.

The ability to more precisely manage the connections of the various constituent codes and the level of redundancy for each input bit give more flexibility in the design of LDPC codes, which can lead to better performance than turbo codes in some instances. Turbo codes still seem to perform better than LDPCs at low code rates, or at least the design of well performing low rate codes is easier for turbo codes.

As a practical matter, the hardware that forms the accumulators is reused during the encoding process. That is, once a first set of parity bits are generated and the parity bits stored, the same accumulator hardware is used to generate a next set of parity bits.

==Decoding==
{{Unreferenced section|date=May 2023}}
As with other codes, the [[maximum likelihood decoding]] of an LDPC code on the [[binary symmetric channel]] is an [[NP-complete]] problem,<ref>{{cite journal |title=On the Inherent Intractability of Certain Coding Problems |author= Robert McEliece, [[Elwyn Berlekamp|E. R. Berlekamp]] and H. Van Tilborg |journal=IEEE Trans. Inf. Theory |year=1978 |pages=384–386 |publisher=IEEE |doi=10.1109/TIT.1978.1055873|url= https://resolver.caltech.edu/CaltechAUTHORS:BERieeetit78 }}</ref> shown by reduction from [[3-dimensional matching]]. So assuming [[P versus NP problem|P != NP]], which is widely believed, then performing optimal decoding for an arbitrary code of any useful size is not practical.

However, sub-optimal techniques based on iterative [[belief propagation]] decoding give excellent results and can be practically implemented. The sub-optimal decoding techniques view each parity check that makes up the LDPC as an independent single parity check (SPC) code. Each SPC code is decoded separately using [[Soft-in soft-out decoder|soft-in-soft-out]] (SISO) techniques such as [[Soft output Viterbi algorithm|SOVA]], [[BCJR algorithm|BCJR]], [[Maximum a posteriori estimation|MAP]], and other derivates thereof. The soft decision information from each SISO decoding is cross-checked and updated with other redundant SPC decodings of the same information bit. Each SPC code is then decoded again using the updated soft decision information. This process is iterated until a valid codeword is achieved or decoding is exhausted. This type of decoding is often referred to as sum-product decoding.

The decoding of the SPC codes is often referred to as the "check node" processing, and the cross-checking of the variables is often referred to as the "variable-node" processing.

In a practical LDPC decoder implementation, sets of SPC codes are decoded in parallel to increase throughput.

In contrast, belief propagation on the [[binary erasure channel]] is particularly simple where it consists of iterative constraint satisfaction.

For example, consider that the valid codeword, 101011, from the example above, is transmitted across a binary erasure channel and received with the first and fourth bit erased to yield ?01?11. Since the transmitted message must have satisfied the code constraints, the message can be represented by writing the received message on the top of the factor graph.

In this example, the first bit cannot yet be recovered, because all of the constraints connected to it have more than one unknown bit. In order to proceed with decoding the message, constraints connecting to only one of the erased bits must be identified. In this example, only the second constraint suffices. Examining the second constraint, the fourth bit must have been zero, since only a zero in that position would satisfy the constraint.

This procedure is then iterated. The new value for the fourth bit can now be used in conjunction with the first constraint to recover the first bit as seen below. This means that the first bit must be a one to satisfy the leftmost constraint.

[[Image:ldpc code fragment factor graph w erasures decode step 2.svg|none]]

Thus, the message can be decoded iteratively. For other channel models, the messages passed between the variable nodes and check nodes are [[real number]]s, which express probabilities and likelihoods of belief.

This result can be validated by multiplying the corrected codeword '''r''' by the parity-check matrix '''H''':

:<math>\mathbf{z} = \mathbf{H \odot r}
= 
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}
\odot
\begin{pmatrix}
1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\
\end{pmatrix}

=
\begin{pmatrix}
0 \\ 0 \\ 0 \\
\end{pmatrix}.
</math>

Because the outcome '''z''' (the [[Decoding methods#Syndrome decoding|syndrome]]) of this operation is the three × one zero vector, the resulting codeword '''r''' is successfully validated.

After the decoding is completed, the original message bits '101' can be extracted by looking at the first 3 bits of the codeword.

While illustrative, this erasure example does not show the use of soft-decision decoding or soft-decision message passing, which is used in virtually all commercial LDPC decoders.

=== 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 |first1=A.I.V. |last1=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 Annual Allerton Conference on Communication Control and Computing |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 |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}}</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}}

*Pseudorandom approaches
*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 }}</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}}

Some LDPC codes are based on [[Reed–Solomon code]]s, such as the RS-LDPC code used in the [[10 Gigabit Ethernet]] standard.<ref>
Ahmad Darabiha, Anthony Chan Carusone, Frank R. Kschischang.
[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 |first1=Z. |last1=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 |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 |citeseerx=10.1.1.100.3023 }}</ref>

== Compared to turbo codes ==
LDPC codes can be compared with other powerful coding schemes, e.g. [[turbo code]]s.<ref>{{cite conference |first1=B. |last1=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 ==

=== People ===
*[[Richard Hamming]]
*[[Claude Shannon]]
*[[David J. C. MacKay]]
*[[Irving S. Reed]]
*[[Michael Luby]]

=== Theory ===
*[[Graph theory]]
*[[Hamming code]]
*[[Sparse graph code]]
*[[Expander code]]

=== Applications ===

*[[G.hn|G.hn/G.9960]] (ITU-T Standard for networking over power lines, phone lines and coaxial cable)
*[[802.3an]] or 10GBASE-T (10 gigabit/s Ethernet over twisted pair)
*[[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 |last=Dill |first=Jeffery |last2=Li |first2=Huanlin |date=June 27, 2011 |editor-last=Cao |editor-first=Yanyan |title=Studies on Lowering the Error Floors of Finite Length LDPC codes |url=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)
*[[DOCSIS]] 3.1
*[[ATSC 3.0]] (Next generation North America digital terrestrial broadcasting)
*[[3GPP]] (5G-NR data channel)

=== Other capacity-approaching codes ===
*[[Fountain codes]]
*[[LT codes]]
*[[Online codes]]
*[[Raptor codes]]
*[[Repeat-accumulate code]]s (a class of simple turbo codes)
*[[Serial concatenated convolutional codes]]
*[[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 ==
{{reflist|33em}}

== External links ==
* [https://www.researchgate.net/profile/Sarah-Johnson-64/publication/228977165_Introducing_Low-Density_Parity-Check_Codes/links/0deec51c7c8f92e602000000/Introducing-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 }}
* {{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 arXiv |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)]
* [http://community.wvu.edu/~mcvalenti/documents/TurboLDPCTutorial.pdf Turbo and LDPC Codes: Implementation, Simulation, and Standardization (West Virginia University)]
* [http://www5.tu-ilmenau.de/nt/de/teachings/vorlesungen/itsc_master/folien/script.pdf Information theory and coding (Marko Hennhöfer, 2011, TU Ilmenau)] - discusses LDPC codes at pages 74–78.
* [http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html LDPC codes and performance results]
* [https://www.mathworks.com/help/comm/examples/dvb-s-2-link-including-ldpc-coding.html?s_tid=srchtitle DVB-S.2 Link, Including LDPC Coding (MatLab)]
*Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations:
** [http://www.cs.utoronto.ca/~radford/ldpc.software.html Binary LDPC codes] in [[C (programming language)|C]]
** [http://freshmeat.net/projects/pycodes/ Binary LDPC codes] for [[Python (programming language)|Python]] (core algorithm in C)
** [https://web.archive.org/web/20090926035703/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcenc.html LDPC encoder] and [https://web.archive.org/web/20090217170744/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcdec.html LDPC decoder] in [[MATLAB]]
** [https://aff3ct.github.io A Fast Forward Error Correction Toolbox] (AFF3CT) in [[C++11]] for fast LDPC simulations

{{CCSDS|state=collapsed}}

{{DEFAULTSORT:Low-Density Parity-Check Code}}
[[Category:Error detection and correction]]
[[Category:Coding theory]]
[[Category:Capacity-approaching codes]]