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

Low-density Parity-Check decoding Algorithms

Florent Pirou

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.

Related papers

Parallel algorithms and architectures for LDPC Decoding

Gabriel Falcão

Low-Density Parity-Check (LDPC) codes have recaptured the attention of the scientific community a few years after Turbo codes were invented in the early nineties. Originally proposed in the 1960s at MIT by R. Gallager, LDPC codes represent powerful error correcting codes that allow working very close to the Shannon limit and achieve excellent Bit Error Rate (BER) due to computationally intensive algorithms on the decoder side of the system. Advances in microelectronics introduced small process technologies that allowed developing complex designs incorporating a high number of transistors in Very Large Scale Integration (VLSI) systems. Recently, these processes have been used to develop architectures able of performing LDPC decoding in real-time and delivering considerably high throughputs. Mainly for these reasons and naturally because the patent has expired, they have been adopted by modern communication standards which triggered their popularity, showing how actual they are. Due to the increase of transistor density in VLSI systems, and also to the fact that recently processing speed has risen faster than bandwidth, power and memory walls have created a new paradigm in computer architectures: rather than just increasing the frequency of operation supported by smaller process designs, the introduction of multiple cores on a single chip has become the new trend to provide augmented computational power. This thesis proposes new approaches for these computationally intensive algorithms, by performing parallel LDPC decoding based on ubiquitous multi-core architectures and achieves efficient throughputs that compare well with dedicated VLSI systems. We extensively address the challenges faced in the investigation and development of these programmable solutions, with focus mainly given on flexibility and scalability of the proposed algorithms, throughput and BER performance, and general efficiency of the programmable solutions here presented, that also achieve results more than an order of magnitude superior to those obtained with conventional CPUs. Furthermore, the investigation herein described follows a methodology that analyzes in detail the computational complexity of these decoding algorithms in order to propose strategies to accelerate their processingwhich, if conveniently transposed to other areas of computer science, can demonstrate that in this new multi-core era we may be in the presence of valid alternatives to non-reprogrammable dedicated VLSI hardware that requires non-recurring engineering.

•Dec 6, 2010•8 citations

Design of VLSI implementation-oriented LDPC codes

Hao Zhong, Tong Zhang

Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error-correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of an LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in real applications. In this paper, following the joint code and decoder design philosophy, we propose a semi-random design scheme to construct the LDPC codes that not only exhibit very good error-correcting performance but also effectively fit to partially parallel VLSI decoder implementations. The corresponding partially parallel decoder has a very regular structure and simple control mechanism. Our computer simulations show that such LDPC codes achieve very good performance comparable to their counterparts constructed in a fully random scheme, which however have little chance of fitting to partially parallel decoder implementations.

IEEE Vehicular Technology Conference•Jan 1, 2003•47 citations

Techniques for the decoding of low density parity check codes: efficient simulation, algorithm improvement and implementation

Babak Daneshrad, Enver Çavuş

After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.

•Jan 1, 2007•2 citations

VLSI implementation-oriented (3, k)-regular low-density parity-check codes

Tong Zhang, Keshab K. Parhi

In the past few years, Gallager's low-density parity-check (LDPC) codes received a lot of attention and many efforts have been devoted to analyzing and improving their error-correcting performance. However, little consideration has been given to the LDPC decoder VLSI implementation. The straightforward fully parallel decoder architecture usually incurs too high complexity for many practical purposes and should be transformed to a partly parallel realization. Unfortunately, due to the randomness of LDPC codes, it is nearly impossible to develop an effective transformation for an arbitrarily given LDPC code. We propose a joint code and decoder design approach to construct a class of (3, k)-regular LDPC codes which exactly fit a partly parallel decoder implementation and have a very good performance. Moreover, for such LDPC codes, we propose a systematic, efficient encoding scheme by effectively exploiting the sparseness of its parity check matrix.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Nov 13, 2002•71 citations

Linear-time encoding and decoding of low-density parity-check codes

Mikael Simberg

Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.

•Jan 20, 2015•0 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
Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.
Low-Density Parity-Check (LDPC) codes have recaptured the attention of the scientific community a few years after Turbo codes were invented in the early nineties. Originally proposed in the 1960s at MIT by R. Gallager, LDPC codes represent powerful error correcting codes that allow working very close to the Shannon limit and achieve excellent Bit Error Rate (BER) due to computationally intensive algorithms on the decoder side of the system. Advances in microelectronics introduced small process technologies that allowed developing complex designs incorporating a high number of transistors in Very Large Scale Integration (VLSI) systems. Recently, these processes have been used to develop architectures able of performing LDPC decoding in real-time and delivering considerably high throughputs. Mainly for these reasons and naturally because the patent has expired, they have been adopted by modern communication standards which triggered their popularity, showing how actual they are. Due to the increase of transistor density in VLSI systems, and also to the fact that recently processing speed has risen faster than bandwidth, power and memory walls have created a new paradigm in computer architectures: rather than just increasing the frequency of operation supported by smaller process designs, the introduction of multiple cores on a single chip has become the new trend to provide augmented computational power. This thesis proposes new approaches for these computationally intensive algorithms, by performing parallel LDPC decoding based on ubiquitous multi-core architectures and achieves efficient throughputs that compare well with dedicated VLSI systems. We extensively address the challenges faced in the investigation and development of these programmable solutions, with focus mainly given on flexibility and scalability of the proposed algorithms, throughput and BER performance, and general efficiency of the programmable solutions here presented, that also achieve results more than an order of magnitude superior to those obtained with conventional CPUs. Furthermore, the investigation herein described follows a methodology that analyzes in detail the computational complexity of these decoding algorithms in order to propose strategies to accelerate their processingwhich, if conveniently transposed to other areas of computer science, can demonstrate that in this new multi-core era we may be in the presence of valid alternatives to non-reprogrammable dedicated VLSI hardware that requires non-recurring engineering.
Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error-correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of an LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in real applications. In this paper, following the joint code and decoder design philosophy, we propose a semi-random design scheme to construct the LDPC codes that not only exhibit very good error-correcting performance but also effectively fit to partially parallel VLSI decoder implementations. The corresponding partially parallel decoder has a very regular structure and simple control mechanism. Our computer simulations show that such LDPC codes achieve very good performance comparable to their counterparts constructed in a fully random scheme, which however have little chance of fitting to partially parallel decoder implementations.
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.
In the past few years, Gallager's low-density parity-check (LDPC) codes received a lot of attention and many efforts have been devoted to analyzing and improving their error-correcting performance. However, little consideration has been given to the LDPC decoder VLSI implementation. The straightforward fully parallel decoder architecture usually incurs too high complexity for many practical purposes and should be transformed to a partly parallel realization. Unfortunately, due to the randomness of LDPC codes, it is nearly impossible to develop an effective transformation for an arbitrarily given LDPC code. We propose a joint code and decoder design approach to construct a class of (3, k)-regular LDPC codes which exactly fit a partly parallel decoder implementation and have a very good performance. Moreover, for such LDPC codes, we propose a systematic, efficient encoding scheme by effectively exploiting the sparseness of its parity check matrix.
Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.