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

Electronics Letters

Iterative decoding using stochastic computation

Vincent Gaudet, Anthony Rapley

Published Feb 6, 2003• 199 citations
Publisher

Abstract

An iterative decoding architecture based on stochastic computational elements is proposed. Simulation results for a simple low-density parity-check code demonstrate near-optimal performance with respect to a maximum likelihood decoder. The proposed method provides an alternative to analogue decoding for high-speed/low-power applications.
DOI
10.1049/el:20030217

Related papers

Stochastic decoding of LDPC codes

Saeed Sharifi Tehrani, Warren J. Gross, Shie Mannor

This letter presents the first successful method for iterative stochastic decoding of state-of-the-art low-density parity-check (LDPC) codes. The proposed method shows the viability of the stochastic approach for decoding LDPC codes on factor graphs. In addition, simulation results for a 200 and a 1024 length LDPC code demonstrate the near-optimal performance of this method with respect to sum-product decoding. The proposed method has a significant potential for high-throughput and/or low complexity iterative decoding.

IEEE Communications Letters•Oct 1, 2006•165 citations

Efficient algorithms for stochastic decoding of LDPC codes

Kuo-Lun Huang

The expanding demand for high-speed communications has resulted in development of high-throughput error-correcting techniques required by emerging communication standards. Low-Density Parity-Check (LDPC) codes are a class of linear block codes that achieve near-capacity performance and have been selected as part of many digital communication standards. Stochastic computation has been proposed as a hardware efficient approach for decoding LDPC codes. Using stochastic computation, all messages in the iterative decoding process are represented by Bernoulli sequences. Computations on these sequences are performed bit-by-bit using simple logic operations. Furthermore, serial messages used in stochastic decoders help alleviate routing congestion in hardware implementation of decoder. These factors make stochastic decoding a low complexity alternative to implement LDPC decoders. In this dissertation, we analyze the characteristics of stochastic decoding and propose reduced-latency designs for stochastic LDPC decoders to achieve improved performance on various channel models.

•Jan 1, 2016•2 citations

Survey of Stochastic Computation on Factor Graphs

Saeed Sharifi Tehrani, Shie Mannor, Warren J. Gross

Stochastic computation is a new alternative approach for iterative computation on factor graphs. In this approach, the information is represented by the statistics of the bit stream which results in simple high-speed hardware implementation of graph-based algorithms. Despite the first purpose of its invention (i.e., low-precision digital circuits), the stochastic representation has recently been shown to be able to provide near-optimal decoding performance for practical Low-Density Parity- Check (LDPC) codes, with respect to Sum-Product Algorithm (SPA). This paper provides a survey of stochastic methods for graph-based iterative decoding, the state-of-the-art and, their possible new applications.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2007•29 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

A probabilistic computation method for the weight distribution of low-density parity-check codes

Masanori Hirotomo, Masami Mohri, Masakatu Morii

Low-density parity-check (LDPC) codes achieve outstanding performance by the sum-product decoder. Its performance approaches the maximum-likelihood (ML) decoding performance at high SNR region. Upper bounds on the error probability of the ML decoded LDPC codes can be computed using the weight distribution. Recently, X.-Y. Hu et al. presented an approximate algorithm for estimating the weight distribution of LDPC codes. However, the weight distribution computed by their method depends on the iterative decoding algorithm, and is not always estimated exactly. In this paper, we propose a probabilistic method for computing the low-part weight distribution of LDPC codes. Using our method, the approximate weight distribution of LDPC codes can be computed with high accuracy

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•30 citations

ML-performance of low-density parity check codes

Heidi Steendam, Marc Moeneclaey

In this paper, we derive the maximum likelihood (ML) performance for low-density parity check (LDPC) codes, considering BPSK and QPSK transmission over a Gaussian channel.We compare the theoretical ML performance with the performance of the iterative decoding algorithm.It turns out that the performance of the iterative decoding algorithm is close to the ML performance when the girth of the code is sufficiently high.When the girth of the code is equal to or smaller than 6, the decoding algorithm performs sub-optimal: the bit error rate (BER) obtained with the iterative decoding algorithm is much higher than the optimal BER that can be obtained when using ML decoding.

•Jan 1, 2002•5 citations
This letter presents the first successful method for iterative stochastic decoding of state-of-the-art low-density parity-check (LDPC) codes. The proposed method shows the viability of the stochastic approach for decoding LDPC codes on factor graphs. In addition, simulation results for a 200 and a 1024 length LDPC code demonstrate the near-optimal performance of this method with respect to sum-product decoding. The proposed method has a significant potential for high-throughput and/or low complexity iterative decoding.
The expanding demand for high-speed communications has resulted in development of high-throughput error-correcting techniques required by emerging communication standards. Low-Density Parity-Check (LDPC) codes are a class of linear block codes that achieve near-capacity performance and have been selected as part of many digital communication standards. Stochastic computation has been proposed as a hardware efficient approach for decoding LDPC codes. Using stochastic computation, all messages in the iterative decoding process are represented by Bernoulli sequences. Computations on these sequences are performed bit-by-bit using simple logic operations. Furthermore, serial messages used in stochastic decoders help alleviate routing congestion in hardware implementation of decoder. These factors make stochastic decoding a low complexity alternative to implement LDPC decoders. In this dissertation, we analyze the characteristics of stochastic decoding and propose reduced-latency designs for stochastic LDPC decoders to achieve improved performance on various channel models.
Stochastic computation is a new alternative approach for iterative computation on factor graphs. In this approach, the information is represented by the statistics of the bit stream which results in simple high-speed hardware implementation of graph-based algorithms. Despite the first purpose of its invention (i.e., low-precision digital circuits), the stochastic representation has recently been shown to be able to provide near-optimal decoding performance for practical Low-Density Parity- Check (LDPC) codes, with respect to Sum-Product Algorithm (SPA). This paper provides a survey of stochastic methods for graph-based iterative decoding, the state-of-the-art and, their possible new applications.
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.
Low-density parity-check (LDPC) codes achieve outstanding performance by the sum-product decoder. Its performance approaches the maximum-likelihood (ML) decoding performance at high SNR region. Upper bounds on the error probability of the ML decoded LDPC codes can be computed using the weight distribution. Recently, X.-Y. Hu et al. presented an approximate algorithm for estimating the weight distribution of LDPC codes. However, the weight distribution computed by their method depends on the iterative decoding algorithm, and is not always estimated exactly. In this paper, we propose a probabilistic method for computing the low-part weight distribution of LDPC codes. Using our method, the approximate weight distribution of LDPC codes can be computed with high accuracy
In this paper, we derive the maximum likelihood (ML) performance for low-density parity check (LDPC) codes, considering BPSK and QPSK transmission over a Gaussian channel.We compare the theoretical ML performance with the performance of the iterative decoding algorithm.It turns out that the performance of the iterative decoding algorithm is close to the ML performance when the girth of the code is sufficiently high.When the girth of the code is equal to or smaller than 6, the decoding algorithm performs sub-optimal: the bit error rate (BER) obtained with the iterative decoding algorithm is much higher than the optimal BER that can be obtained when using ML decoding.