Low-density parity-check (LDPC) codes, also known as Gallager codes, are a class of error-correction codes first proposed in 1960. Together with the closely related turbo codes, they 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.

LDPC codes were originally conceived by Robert G. Gallager in 1960. Gallager devised the codes in his doctoral dissertation at the Massachusetts Institute of Technology. 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. They came back into favor in the mid 1990s, both because improved hardware made them practical, and because they provided a high performance and patent-free alternative to turbo codes.

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 (capacities) of many channels at low computation costs.

History Renewed interest in LDPC codes emerged following the invention of the closely related turbo codes (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently rediscovered in 1996. Initial industry preference for LDPC codes over turbo codes stemmed from patent-related constraints on the latter. "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." 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.Telemetry Data Decoding, Design Handbook Although the fundamental patent for turbo codes expired in 2013, in many cases LDPC codes are still 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 arbitrarily close to channel capacity, with provably vanishing decoding error probability and linear decoding complexity. 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.

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 graphs (specialized bipartite graphs).

LDPC code ensembles have also been analyzed using methods from statistical physics. Murayama, Kabashima, Saad, and Vicente studied regular LDPC codes through a spin-system analogy and the replica method, and later work extended this analysis to LDPC codes over Galois fields.

Since 2013, LDPC codes have also been proposed as a means of correcting errors in quantum computers, as they require few additional qubits to correct errors, as demonstrated by Gottesman, the University of Strasburg, Alice & Bob, and others. A 2025 study reported LDPC-CSS quantum codes for the quantum depolarizing channel whose numerical decoding performance approached the hashing bound, while retaining decoding complexity linear in the number of physical qubits.

Applications In 2003, an 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.Presentation by Hughes Systems The decision was based on technical factors such as ease of parallelization and error floors, plus the patent-free status of LDPC. "LDPC codes can achieve higher throughputs than turbo codes, if parallel decoding architectures are allowed. Also, turbo codes are patented while LDPC codes are not patented."

In 2008, LDPC beat convolutional turbo codes as the forward error correction (FEC) system for the ITU-T G.hn standard.HomePNA Blog: G.hn, a PHY For All Seasons G.hn chose LDPC codes over turbo codes because of their lower decoding complexity (especially when operating at data rates close to 1.0 Gbit/s) and because the proposed turbo codes exhibited a significant error floor at the desired range of operation.IEEE Communications Magazine paper on G.hn

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.IEEE Standard, section 20.3.11.6 "802.11n-2009", IEEE, October 29, 2009, accessed March 21, 2011. LDPC is a mandatory part of 802.11ax (Wi-Fi 6).

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 rates. For example, the Reed-Solomon code with LDPC Coded Modulation (RS-LCM) uses a Reed-Solomon outer code.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" 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.Nick Wells. "DVB-T2 in relation to the DVB-x2 Family of Standards"

5G NR uses polar code for the control channels and LDPC for the data channels.

Although LDPC code has had its success in commercial hard disk drives, to fully exploit its error correction capability in SSDs demands unconventional fine-grained flash memory sensing, leading to an increased memory read latency. LDPC-in-SSD is an effective approach to deploy LDPC in SSDs 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 vendors. 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.

Operational use LDPC codes functionally are defined by a sparse parity-check matrix. This sparse matrix is often randomly generated, subject to the sparsity constraints—LDPC code construction is discussed later. These codes were first designed by Robert Gallager in 1960.

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

This is a popular way of graphically representing an (n, k) LDPC code. The bits of a valid message, when placed on the Ts 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, modulo two, to zero (in other words, they must sum to an even number, or there must be an even number of odd values).

Ignoring any lines going out of the picture, there are eight possible six-bit strings corresponding to valid codewords: (i.e., 000000, 001110, 010111, 011001, 100101, 101011, 110010, 111100). 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, 3) linear code, with n = 6 and k = 3.

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

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 through basic row operations in GF(2):

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 (noting that in the special case of this being a binary code ), or specifically:

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

,

where is symbol of mod 2 multiplication.

As a check, the row space of G is orthogonal to H such that .

The input bit-string "101" is found as the first 3 bits of the codeword "101011", due to the presence of the identity matrix . The trailing three bits "011" of the codeword are the parity bits.

Example encoder Each bit of all possible messages can be generated by direct multiplication with the G matrix defined in the previous section. However, this method is seldom used in practice, where codes are picked for ease of encoding. In practice this means the input bits are copied straight to the output, and the check bits computed with a series of encoders. In theory there can be one encoder required for each check bit, but in practice the hardware cost is reduced by picking encoders that can be re-used.

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 (S0,K-1) 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.