4.10.2 LDPC Codes

LDPC codes—Gallager codes—are block codes with a sparse parity-check matrix meaning that only a small fraction of the matrix elements are 1 (“low density”). First proposed by Robert G. Gallager in 1963, LDPC codes were computationally impractical at the time and were largely forgotten until they were re-introduced by MacKay and Neal in the mid-1990s, when advances in processing made iterative decoding feasible.

An LDPC code can be represented by a sparse parity-check matrix of dimension (n–k)×n, where each parity equation involves only a few codeword bits. This structure can also be represented as a Tanner graph, a bipartite graph connecting variable nodes (bits) and check nodes (parity equations).

Decoding is performed iteratively using message passing (belief propagation), in which nodes exchange reliability information until the parity constraints are satisfied.

LDPC codes are often described by their degree distribution (n,c,p), where n is the codeword length, c is the number of variable nodes connected to each check node, and p is the number of parity checks per variable node.

LDPC codes can be viewed as compound or “graph-based” codes because the sparse parity structure acts as a set of many shallow constituent codes (accumulators) operating in parallel—an interpretation that explains their excellent iterative-decoding performance.

LDPC codes offer several advantages and trade-offs relative to Turbo codes:

Lower decoding complexity for large block sizes due to sparse message passing.
No low-weight codewords (Turbo codes may exhibit error floors due to such codewords).
Excellent performance at high code rates (e.g., ¾, ⅚, ⅞).

They do, however, have a number of disadvantages:

More complex encoding for large block lengths requires matrix inversion or specialized encoders.
Less effective than Turbo codes at very low code rates (e.g., ⅙, ⅓, ½).
Slower than Turbo codes to converge, often requiring more than 100 iterations, although typically only 20-30.

LDPC codes now dominate modern HTS systems, such as DVB-S2/S2X and CCSDS 131.0-B-4, and are standard in 5G NR, Wi-Fi 6/7, and deep-space missions, where they operate within ≈ 1 dB of the Shannon limit.