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. 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. 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. The decision was based on technical factors such as ease of parallelization and error floors, plus the patent-free status of LDPC. In 2008, LDPC beat convolutional turbo codes as the forward error correction (FEC) system for the ITU-T G.hn standard. 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. 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. 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. 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. 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.
… excerpt ends here. Continue reading the full article.
