In this thesis, we propose a new stochastic decoding algorithm for non-binary LDPC codes with d_v = 2, which is based on the concept of a mutliset, a generalization of the set that allows for multiple occurrences of the same element. The algorithm is called Adaptive Multiset Stochastic Algorithm (AMSA) and represents probability mass functions as multisets, which simplifies the structure of the variable node. AMSA reduces the run-time complexity of one decoding cycle to O(q) for regular memory architectures, and to O(1) if a custom SRAM architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two versions of a (192,96) (2,4)-regular code, one over GF(64) and the other over GF(256), both achieving a maximum clock frequency of 108 MHz and a throughput of 65 Mbit/s at E_b/N_0 = 2.4 dB. We also propose an SRAM architecture for ASIC implementations that reduces the run-time complexity of a decoding cycle to O(1) and achieves a throughput of 698 Mbit/s at the same noise level. The algorithm has a frame error rate (FER) of 3.5 x 10^-7 at E_b/N_0 = 2.4 dB when using the GF(256) version of the code. To the best of our knowledge, the implemented decoders are the first fully-parallel non-binary LDPC decoders over GF(64) and GF(256) reported in the literature.
In this thesis, we propose a new stochastic decoding algorithm for non-binary LDPC codes with d_v = 2, which is based on the concept of a mutliset, a generalization of the set that allows for multiple occurrences of the same element. The algorithm is called Adaptive Multiset Stochastic Algorithm (AMSA) and represents probability mass functions as multisets, which simplifies the structure of the variable node. AMSA reduces the run-time complexity of one decoding cycle to O(q) for regular memory architectures, and to O(1) if a custom SRAM architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two versions of a (192,96) (2,4)-regular code, one over GF(64) and the other over GF(256), both achieving a maximum clock frequency of 108 MHz and a throughput of 65 Mbit/s at E_b/N_0 = 2.4 dB. We also propose an SRAM architecture for ASIC implementations that reduces the run-time complexity of a decoding cycle to O(1) and achieves a throughput of 698 Mbit/s at the same noise level. The algorithm has a frame error rate (FER) of 3.5 x 10^-7 at E_b/N_0 = 2.4 dB when using the GF(256) version of the code. To the best of our knowledge, the implemented decoders are the first fully-parallel non-binary LDPC decoders over GF(64) and GF(256) reported in the literature.
We propose a non-binary stochastic decoding algorithm for low-density parity-check (LDPC) codes over GF(q) with degree two variable nodes, called Adaptive Multiset Stochastic Algorithm (AMSA). The algorithm uses multisets, an extension of sets that allows multiple occurrences of an element, to represent probability mass functions that simplifies the structure of the variable nodes. The run-time complexity of one decoding cycle using AMSA is O(q) for conventional memory architectures, and O(1) if a custom memory architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two (192,96) (2,4)-regular codes over GF(64) and GF(256), both achieving a maximum clock frequency of 108 MHz. The GF(64) decoder has a coded throughput of 65 Mb/s at Eb/N0=2.4 dB when using conventional memory, while a decoder using the custom memory version can achieve 698 Mb/s at the same Eb/N0. At a frame error rate (FER) of 2×10-6the GF(64) version of the algorithm is only 0.04 dB away from the floating-point SPA performance, and for the GF(256) code the difference is 0.2 dB. To the best of our knowledge, this is the first fully parallel non-binary LDPC decoder over GF(256) reported in the literature.
Stochastic decoding is a new approach to iterative decoding on graphs. This paper presents a hardware architecture for fully parallel stochastic low-density parity-check (LDPC) decoders. To obtain the characteristics of the proposed architecture, we apply this architecture to decode an irregular state-of-the-art (1056,528) LDPC code on a Xilinx Virtex-4 LX200 field-programmable gate-array (FPGA) device. The implemented decoder achieves a clock frequency of 222 MHz and a throughput of about 1.66 Gb/s atEb/N0=4.25dB(a bit error rate of10−8). It provides decoding performance within 0.5 and 0.25 dB of the floating-point sum-product algorithm with 32 and 16 iterations, respectively, and similar error-floor behavior. The decoder uses less than 40% of the lookup tables, flip-flops, and IO ports available on the FPGA device. The results provided in this paper validate the potential of stochastic LDPC decoding as a practical and competitive fully parallel decoding approach.
This paper concerns a new and powerful Low-Density Parity-Check (LDPC) stochastic decoding algorithm, called Controlled Start-up Stochastic (CSS) decoding, to implement fully parallel LDPC decoders. The proposed algorithm uses a clever starting point computing method to improve the convergence as well as to reduce the latency of the decoding process, without a significant hardware complexity cost. Using this stochastic method, in low signal-to-noise ratio (SNR) region, a short LDPC code can outperforms the fixed point state-of-the-art (2048, 1723) LDPC code. To validate the performance of the proposed algorithm, a (48, 24) LDPC code are implemented on Xilinx Virtex-6 VLX240T field programmable gate array device, with and without the CSS method. The new algorithm provides a decoding speed seven times faster and a Bit Error Rate (BER) hundred times better at E3/N0=4.5 dB. In addition, the results provide a BER better than the 6 bits offset min-sum algorithm (OMSA) and better than the 6 bits sum-product algorithm (SPA) for the (2048, 1723) LDPC code, below E3/N0=3.9 dB and Eb/N0=4.3 dB respectively. The obtained results show that, the proposed algorithm is the first stochastic algorithm which can outperform the OMSA and SPA algorithms, with less hardware complexity.
A new stochastic decoding algorithm, called Delayed Stochastic (DS) decoding, is introduced to implement low-density-parity-check (LDPC) decoders. The delayed stochastic decoding uses an alternative method to track probability values, which results in reduction of hardware complexity and memory requirement of the stochastic decoders. It is therefore suitable for fully-parallel implementation of long LDPC codes with applications in optical communications. Two decoders are implemented using the DS algorithm for medium (2048, 1723) and long (32768, 26624) LDPC codes. The decoders occupy 3.93- mm2and 56.5- mm2silicon area using 90-nm CMOS technology and provide maximum core throughputs of 172.4 and 477.7 Gb/s at [(Eb)/(No)]=5.5 and 4.8 dB, respectively.
During the check node (CN) update, the elements of input message vectors are redundant for the output message vectors. Hence, in this paper, we exactly select from the input message vectors the elements, which really have contributions to the error-correction performance and constitute the minimum set for the CN update. With adoption of the forward and backward (FB) scheme, an adaptive minimum-set min-sum algorithm (AMSA) is proposed to reduce the computation complexity of the FB process. In order to concurrently update the output vectors belonging to the same CN, we present a parallel minimum-set min-sum algorithm (PMSA) with lower memory complexity than the AMSA. Compared with the min-sum algorithms, the two proposed minimum-set based algorithms introduce no error performance loss.
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.