This paper presents a stochastic algorithm for iterative error control decoding. We show that the stochastic decoding algorithm is an approximation of the sum-product algorithm. When the code's factor graph is a tree, as with trellises, the algorithm approaches maximum a-posteriori decoding. We also demonstrate a stochastic approximations to the alternative update rule successive relaxation. Stochastic decoders have very simple digital implementations which have almost no RAM requirements. We present example stochastic decoders for a trellis-based Hamming code, and for a block turbo code constructed from Hamming codes
This paper presents a stochastic algorithm for iterative error control decoding. We show that the stochastic decoding algorithm is an approximation of the sum-product algorithm. When the code's factor graph is a tree, as with trellises, the algorithm approaches maximum a-posteriori decoding. We also demonstrate a stochastic approximations to the alternative update rule successive relaxation. Stochastic decoders have very simple digital implementations which have almost no RAM requirements. We present example stochastic decoders for a trellis-based Hamming code, and for a block turbo code constructed from Hamming codes
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.
Low-density parity-check codes, a class of capacity-approaching linear codes, are particularly recognized for their efficient decoding scheme. The decoding scheme, known as the sum-product, is an iterative algorithm consisting of passing messages between variable and check nodes of the factor graph. The sum-product algorithm is fully parallelizable, owing to the fact that all messages can be update concurrently. However, since it requires extensive number of highly interconnected wires, the fully-parallel implementation of the sum-product on chips is exceedingly challenging. Stochastic decoding algorithms, which exchange binary messages, are of great interest for mitigating this challenge and have been the focus of extensive research over the past decade. They significantly reduce the required wiring and computational complexity of the message-passing algorithm. Even though stochastic decoders have been shown extremely effective in practice, the theoretical aspect and understanding of such algorithms remains limited at large. Our main objective in this paper is to address this issue. We first propose a novel algorithm referred to as the Markov based stochastic decoding. Then, we provide concrete quantitative guarantees on its performance for tree-structured as well as general factor graphs. More specifically, we provide upper-bounds on the first and second moments of the error, illustrating that the proposed algorithm is an asymptotically consistent estimate of the sum-product algorithm. We also validate our theoretical predictions with experimental results, showing we achieve comparable performance to other practical stochastic decoders.
Iterative decoding techniques have become a viable alternative for constructing high performance coding systems. In particular, the recent success of turbo codes indicates that performance close to the Shannon limit may be achieved. In this thesis, it is showed that many iterative decoding algorithms are special cases of two generic algorithms, the min-sum and sum-product algorithms, which also include non-iterative algorithms such as Viterbi decoding. The min-sum and sum-product algorithms are developed and presented as generalized trellis algorithms, where the time axis of the trellis is replaced by an arbitrary graph, the "Tanner graph". With cycle-free Tanner graphs, the resulting decoding algorithms (e.g., Viterbi decoding) are maximum-likelihood but suffer from an exponentially increasing complexity. Iterative decoding occurs when the Tanner graph has cycles (e.g., turbo codes); the resulting algorithms are in general suboptimal, but significant complexity reductions are possible compared to the cycle-free case. Several performance estimates for iterative decoding are developed, including a generalization of the union bound used with Viterbi decoding and a characterization of errors that are uncorrectable after infinitely many decoding iterations.
Being one of the most efficient solutions to implement forward error correction (FEC) decoders based on belief propagation, stochastic processing is thus a method worthy of consideration when addressing the decoding of emerging codes such as Cortex codes. This code family offers short block codes with large Hamming distances. Unfortunately, their construction introduces many hidden variables making them difficult to be efficiently decoded with digital circuits implementing the Sum-Product algorithm. With the introduction of multiple stochastic streams, the proposed solution alleviates the hidden variables problem thus yielding decoding performances close to optimal. Morevover, this new stochastic architecture is more efficient in terms of complexity-throughput ratio compared to recently published stochastic decoders using either edge or tracking forecast memories.
Despite the outstanding performance of non-binary low-density parity-check (LDPC) codes over many communication channels, they are not in widespread use yet. This is due to the high implementation complexity of their decoding algorithms, even those that compromise performance for the sake of simplicity. In this paper, we present three algorithms based on stochastic computation to reduce the decoding complexity. The first is a purely stochastic algorithm with error-correcting performance matching that of the sum-product algorithm (SPA) for LDPC codes over Galois fields with low order and a small variable node degree. We also present a modified version which reduces the number of decoding iterations required while remaining purely stochastic and having a low per-iteration complexity. The second algorithm, relaxed half-stochastic (RHS) decoding, combines elements of the SPA and the stochastic decoder and uses successive relaxation to match the error-correcting performance of the SPA. Furthermore, it uses fewer iterations than the purely stochastic algorithm and does not have limitations on the field order and variable node degree of the codes it can decode. The third algorithm, NoX, is a fully stochastic specialization of RHS for codes with a variable node degree 2 that offers similar performance, but at a significantly lower computational complexity. We study the performance and complexity of the algorithms; noting that all have lower per-iteration complexity than SPA and that RHS can have comparable average per-codeword computational complexity, and NoX a lower one.
This paper presents a Relaxed Half-Stochastic (RHS) low-density parity-check (LDPC) decoding algorithm that uses some elements of the sum-product algorithm (SPA) in its variable nodes, but maintains the low-complexity interleaver and check node structures characteristic of stochastic decoders. The algorithm relies on the principle of successive relaxation to convert binary stochastic streams to a log-likelihood ratio (LLR) representation. Simulations of a (2048, 1723) RS-LDPC code show that the RHS algorithm can outperform 100-iterations floating-point SPA decoding. We describe approaches for low-complexity implementation of the RHS algorithm. Furthermore, we show how the stochastic nature of the belief representation can be exploited to lower the error floor.