Low-density parity-check code

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.