Skip to content
Back to search results

Low-Density Parity-Check Codes (LDPC)

Introduced by
Robert Gallager
Year
1962
Type
linear error-correcting code
Family
Coding theory
Font size

What does it do?

LDPC codes, invented by Robert Gallager in 1962 and rediscovered in the 1990s by MacKay, are linear error-correcting codes defined by sparse parity-check matrices.

They achieve performance within 0.4 dB of the Shannon limit with iterative belief-propagation decoding and have become the standard for modern wireless (WiFi-6, 5G NR, Digital Video Broadcasting). Unlike turbo codes, LDPC codes have a more elegant graph-theoretic structure and more mature theoretical analysis.

The intuition behind the method

Standard linear codes use dense parity-check matrices, making decoding computationally intensive. LDPC codes flip this: the parity-check matrix is sparse (most entries are zero), so each parity check involves only a handful of bits. At the receiver, a bipartite graph is constructed where variable nodes represent transmitted bits and check nodes represent parity constraints. Decoding becomes iterative message passing on this graph: each variable node gathers information from its neighbors, updates its belief about the bit value, and sends refined estimates back. The sparsity ensures fast convergence and near-Shannon performance.

History

Gallager invented LDPC codes in 1962, but the theory lagged behind practical implementation. In 1995, MacKay rediscovered them and showed their near-Shannon performance via simulations. Extensive research in the 2000s developed efficient encoding, decoding, and graph construction algorithms. LDPC codes were adopted in WiFi-6 (802.11ax, 2021) and 5G NR standard (2018). They have become more prevalent than turbo codes in new systems due to better performance and cleaner structure.

When to use it

LDPC codes are preferred over turbo codes in modern systems due to better performance and simpler architecture. Use LDPC for wide SNR ranges (no threshold cliff); they work well from low to high SNR. LDPC is the standard for WiFi-6, satellite, and 5G NR. Avoid LDPC only if legacy compatibility requires turbo codes. LDPC is also suitable for very short packets (>30 bits) as the code structure is separable.

Limitations and considerations

  • Graph construction and matrix storage become complex for very long codes (>10k bits)
  • Performance sensitive to small-scale graph structures (girths, absorbing sets); requires careful design
  • Belief propagation assumes loopy graph, but graphs have cycles; convergence to optimal solution not guaranteed
  • Decoding latency (iterations) grows logarithmically with SNR; not zero-latency like some classical codes
  • Quantization of messages (in fixed-point hardware) affects performance; careful bit allocation needed

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Performance within 0.4 dB of Shannon limit (slightly better than turbo codes)
  • Simpler graph-theoretic structure; cleaner theoretical analysis than turbo codes
  • Iterative decoding avoids cliff-like threshold behavior (unlike turbo)
  • Flexible code design via graph construction; easy to tailor to specific applications
  • Efficient parallel decoding hardware; message-passing suits VLSI/GPU implementation
  • Works well for both long and moderately short codewords

Applications

  • WiFi-6 (802.11ax): high-throughput wireless local area networks with LDPC providing reliable data delivery
  • 5G NR: channel coding for both data and control channels, replacing turbo codes from 4G
  • Satellite communications: digital video broadcasting (DVB-S2) and deep space missions using long-codeword LDPC
  • Power line communications (PLC): robust data transmission over noisy electrical grids
  • Flash memory systems: error correction for NAND flash storage without wear-down from frequent refresh

How it works

How it works

1

Information bits are encoded using a sparse parity-check matrix H; encoded bits are the solution to H*c = 0 (mod 2), where c is the codeword.

2

The parity-check matrix H is structured to be sparse (e.g., each row/column has constant low weight 3-5). This structure is exploited for efficient encoding.

3

Encoded bits are transmitted over a noisy channel; received bits are soft values (likelihood ratios or log-likelihood ratios).

4

A bipartite graph is constructed: left nodes = variable nodes (bits), right nodes = check nodes (parity equations). Edges connect variables to the checks they appear in.

5

Iterative belief propagation: variable nodes aggregate messages from check nodes, update bit estimates, and send refined messages back. After iterations, hard decisions are made; if parity checks are satisfied, decoding is successful.

Common pitfalls

  • Using a poorly designed sparse graph with short cycles; small cycles cause belief propagation to oscillate
  • Over-iterating beyond convergence; unnecessary iterations waste power without improvement
  • Assuming min-sum decoding is as good as sum-product; approximations have performance loss, especially at low SNR
  • Neglecting finite-length effects; graphs designed for asymptotic analysis may underperform on short packets
  • Not accounting for quantization in hardware implementation; floating-point simulation differs from fixed-point reality

Frequently asked questions

What makes LDPC decoding so efficient compared to general linear codes?

The sparsity of the parity-check matrix means each bit participates in only a few parity checks. At decoding, message-passing on the bipartite graph is linear in the number of edges, not the code length. For dense codes, decoding would require matrix inversion, which is cubic in code length. Sparsity makes decoding quasi-linear and practical for long codes.

What is an absorbing set and why does it matter?

An absorbing set is a small subset of the graph that can trap belief propagation decoding, preventing convergence to the correct solution. They are a primary source of error floor (the non-exponential decrease in BER at low SNR). Code designers avoid short absorbing sets through careful graph construction; analysis tools (e.g., stopping set analysis) identify problematic structures.

How does LDPC compare to polar codes?

Both achieve near-Shannon performance. Polar codes have a recursive structure and provable optimality under successive cancellation decoding at infinite code length. LDPC codes are more flexible and have better finite-length performance empirically. 5G NR uses polar codes for control channels (short packets) and LDPC for data channels (long packets), exploiting each code's strengths.

Why is the graph girth important in LDPC codes?

The girth is the length of the shortest cycle in the bipartite graph. Short cycles (girth < 6) cause belief propagation to use correlated information (messages loop back), degrading performance. High-girth codes (girth ≥ 6) break correlations better. Codes are often designed to maximize girth subject to sparsity constraints.

Related methods

Sources

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    Open DOI reference
    Copied.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    Open DOI reference
    Copied.