Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the European Association for Theoretical Computer Science

Iterative Decoding of Low-Density Parity Check Codes

Venkatesan Guruswami

Published Jan 1, 2006• 11 citations
OpenAlex

Abstract

Much progress has been made on decoding algorithms for error-correcting codes in the last decade. In this article, we give an introduction to some fundamental results on iterative, message-passing algorithms for low-density parity check codes. For certain important stochastic channels, this line of work has enabled getting very close to Shannon capacity with algorithms that are extremely ecient (both in theory and practice).

Related papers

Iterative Decoding of Low-Density Parity Check Codes (A Survey)

Venkatesan Guruswami

Much progress has been made on decoding algorithms for error-correcting codes in the last decade. In this article, we give an introduction to some fundamental results on iterative, message-passing algorithms for low-density parity check codes. For certain important stochastic channels, this line of work has enabled getting very close to Shannon capacity with algorithms that are extremely efficient (both in theory and practice).

arXiv:cs/0610022•Oct 5, 2006•11 citations

Algorithms and VLSI Architectures for Low-Density Parity-Check Codes: Part 1-Low-Complexity Iterative Decoding

Kiran Gunnam, Joan Marc Català Pérez, Francisco García-Herrero

This article is the first of a two-part tutorial about low-density parity-check (LDPC) codes. These codes have been firmly established as error-correction coding techniques for communication and storage channels.

IEEE Solid-State Circuits Magazine•Jan 1, 2016•4 citations

A comprehensive Study of Decoding Algorithms for Low Density Parity-Check(LDPC)

C S Anil Kumar, M Vedhashri, L Vanditha +2 more

The near-capacity performance and effective decoding algorithms of Low-Density Parity-Check (LDPC) codes have made them a mainstay of contemporary error correction. With an emphasis on iterative techniques like the Belief Propagation (BP) algorithm, the Min-Sum algorithm, and their variations, this paper offers a thorough analysis of decoding algorithms for LDPC codes. We investigate the trade-offs between various algorithmic techniques’ computational complexity, decoding latency, and error correction performance. Particular focus is placed on new methods and hardware-friendly algorithms that are tailored for next-generation communication systems, such 5 G and beyond.

International Conference on Knowledge Engineering and Communication Systems (ICKECS)•Apr 28, 2025•0 citations

Iterative decoding of generalized low-density parity-check codes

Michael Lentmaier, K.S. Ziganfirov

A generalization of Gallager's low-density parity-check codes is introduced, where as component codes single-error correcting Hamming codes are used instead of single-error detecting parity-check codes. Low-density (LD) parity-check codes were first introduced by Gallager in 1963. These codes are, in combination with iterative decoding, very promising for achieving low error probabilities at a reasonable cost. Results of computer simulations for long LD codes show, that a performance close to the Shannon capacity limit can be achieved. In this work, we consider a generalized version of low-density parity-check codes, where the decoding procedure can be based on the decoding of Hamming component codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•43 citations

Message passing algorithms and improved LP decoding

Sanjeev Arora, Constantinos Daskalakis, David Steurer

Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding algorithms--- and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•53 citations

An overview of some efficient encoding and decoding algorithms for Low-Density Parity-Check Codes

Enrico Paolini, Gianluigi Liva, Marco Chiani

•Oct 10, 2003•0 citations
Much progress has been made on decoding algorithms for error-correcting codes in the last decade. In this article, we give an introduction to some fundamental results on iterative, message-passing algorithms for low-density parity check codes. For certain important stochastic channels, this line of work has enabled getting very close to Shannon capacity with algorithms that are extremely ecient (both in theory and practice).
The near-capacity performance and effective decoding algorithms of Low-Density Parity-Check (LDPC) codes have made them a mainstay of contemporary error correction. With an emphasis on iterative techniques like the Belief Propagation (BP) algorithm, the Min-Sum algorithm, and their variations, this paper offers a thorough analysis of decoding algorithms for LDPC codes. We investigate the trade-offs between various algorithmic techniques’ computational complexity, decoding latency, and error correction performance. Particular focus is placed on new methods and hardware-friendly algorithms that are tailored for next-generation communication systems, such 5 G and beyond.
A generalization of Gallager's low-density parity-check codes is introduced, where as component codes single-error correcting Hamming codes are used instead of single-error detecting parity-check codes. Low-density (LD) parity-check codes were first introduced by Gallager in 1963. These codes are, in combination with iterative decoding, very promising for achieving low error probabilities at a reasonable cost. Results of computer simulations for long LD codes show, that a performance close to the Shannon capacity limit can be achieved. In this work, we consider a generalized version of low-density parity-check codes, where the decoding procedure can be based on the decoding of Hamming component codes.
Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding algorithms--- and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.