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.
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.
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.
Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency, and soft output with a high hardware cost. Stochastic computing, as a form of approximate computing, provides a potential low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. By utilizing the frozen bits of polar codes and stochastic computing, multiple novel optimization methods are presented to further speed up convergence and increase the hardware efficiency.
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.
Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency and soft output with a high hardware cost. A form of approximate computing called stochastic computing provides a low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. Multiple methods at the algorithm and architecture levels are presented to further speed up convergence and hardware efficiency.
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
Low-Density Parity-Check (LDPC) codes are one of the most popular codes used in nowadays’ communication due to their high coding efficiency at low decoding complexity. With these characteristics, LDPC codes are suitable for high-speed information transmission systems. The widely used decoding algorithm for LDPC codes is Belief Propagation (BP) decoding with which the performance of LDPC codes can approach the Shannon limit. With the development of 5G, a lot of attention is given to the so-called ultra-reliable low latency communication scenario which needs the short code to transmit. However, short codes will not have a very good performance with BP decoding. To solve this problem, investigations have been done such as multiple-bases BP decoding. Although this decoding method has a better performance than BP decoding, it will cause a high complexity in the hardware implementation. Besides, an investigation on the stochastic decoding for shortcodes was proposed in 2003. This decoding method is hardware friendly, but its performance can only approach BP decoding. Inspired by multiple-bases BP decoding and stochastic decoding, binary stochastic decoding with parallel decoders is proposed in this thesis firstly. It represents stochastic sequences with multiple parallel Tanner graphs and uses hard-decision decoding in the iterative part because of the binary input bits. However, this decoding method has a severe performance loss compared to BP decoding. To avoid this problem, the enhancement method is used to make the binary sequences be non-binary sequences that can form more powerful parallel decoders. Then the non-binary symbols of these new sequences are transformed to their corresponding log-likelihood ratio which enables the iterative part to use BP decoding. In addition, combining with the ML decision of list decoding, the decision part of our stochastic decoder can fully utilize the output to increase the efficiency of the decoding method. After ensuring the performance of our non-binary stochastic decoding to be better than BP decoding, the complexity of the decoder is reduced to save the computational resources. Finally, with constant adjustments, the bit width of each non-binary symbol is determined to be 15, and the sequence length is reduced to 20 which can let the non-binary stochastic decoding has an acceptable complexity while keeping good performance.