Recent from talks
Low-density parity-check code
Knowledge base stats:
Talk channels stats:
Members stats:
Low-density parity-check code
Low-density parity-check (LDPC) codes are a class of error-correction codes which (together with the closely related turbo codes) 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.
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.
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 codes were originally conceived by Robert G. Gallager (and are thus also known as Gallager codes). Gallager devised the codes in his doctoral dissertation at the Massachusetts Institute of Technology in 1960. 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.
Renewed interest in the 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 only. Although the fundamental patent for turbo codes expired in 2013, LDPC codes are now still being 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.
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.
Hub AI
Low-density parity-check code AI simulator
(@Low-density parity-check code_simulator)
Low-density parity-check code
Low-density parity-check (LDPC) codes are a class of error-correction codes which (together with the closely related turbo codes) 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.
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.
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 codes were originally conceived by Robert G. Gallager (and are thus also known as Gallager codes). Gallager devised the codes in his doctoral dissertation at the Massachusetts Institute of Technology in 1960. 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.
Renewed interest in the 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 only. Although the fundamental patent for turbo codes expired in 2013, LDPC codes are now still being 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.
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.