LDPC code

A low-density parity-check (LDPC) code is a linear error-correcting code defined by a sparse parity-check matrix. The sparsity enables efficient decoding via iterative message-passing algorithms such as belief propagation, which approach the Shannon limit with linear-time complexity. Invented by Robert Gallager in 1960 and rediscovered in the 1990s, LDPC codes now underpin modern communication standards from Wi-Fi to deep-space telemetry.

The deeper significance of LDPC codes is structural: they demonstrate that local constraints, when arranged with the right topology, produce globally optimal behavior. This is the same principle that underlies quantum LDPC codes and probabilistic graphical models.