The Gallager B (GaB), among the hard-decision class of low-density-parity-check (LDPC) algorithms, is an ideal candidate for designing high-throughput decoder hardware. However, GaB suffers from poor error-correction performance. We introduce a probabilistic GaB (PGaB) algorithm that disturbs the decisions made during the decoding iterations randomly with a probability value determined based on experimental studies. We propose a heuristic that switches the decoding from GaB to PGaB after certain number of iterations and show that our heuristic reduces the average iteration count by up to 62% compared with GaB. We evaluate the hardware performance and resource requirement trends of PGaB over three quasicyclic codes using the Xilinx Virtex-6 field programmable gate array. We extend this analysis to performance comparison over our implementations of gradient descent bit flipping (GDBF) and probabilistic GDBF (PGDBF) algorithms for each code studied in this paper. We achieve up to four orders of magnitude better error correction performance than the GaB with less than 1% loss in throughput performance. Our heuristic consistently results with an improvement in maximum operational clock rate across all codes compared with the GDBF and PGDBF.
The Gallager B (GaB), among the hard-decision class of low-density-parity-check (LDPC) algorithms, is an ideal candidate for designing high-throughput decoder hardware. However, GaB suffers from poor error-correction performance. We introduce a probabilistic GaB (PGaB) algorithm that disturbs the decisions made during the decoding iterations randomly with a probability value determined based on experimental studies. We propose a heuristic that switches the decoding from GaB to PGaB after certain number of iterations and show that our heuristic reduces the average iteration count by up to 62% compared with GaB. We evaluate the hardware performance and resource requirement trends of PGaB over three quasicyclic codes using the Xilinx Virtex-6 field programmable gate array. We extend this analysis to performance comparison over our implementations of gradient descent bit flipping (GDBF) and probabilistic GDBF (PGDBF) algorithms for each code studied in this paper. We achieve up to four orders of magnitude better error correction performance than the GaB with less than 1% loss in throughput performance. Our heuristic consistently results with an improvement in maximum operational clock rate across all codes compared with the GDBF and PGDBF.
Low-Density-Parity-Check (LDPC) codes have gained popularity in communication systems and standards due to their capacity-approaching error-correction performance. In this paper, we first expose the tradeoff between decoding performance and hardware performance across three LDPC hard-decision decoding algorithms: Gallager B (GaB), Gradient Descent Bit Flipping (GDBF), and Probabilistic Gradient Descent Bit Flipping (PGDBF). We show that GaB architecture delivers the best throughput while using fewest Field Programmable Gate Array (FPGA) resources, however performs the worst in terms of decoding performance. We then modify the GaB architecture, introduce a new Probabilistic stimulation function (PGaB), and achieve dramatic decoding performance improvement over the GaB, exceeding the performance of GDBF, without sacrificing its superior maximum operating frequency.
Low Density Parity Check (LDPC) codes have gained popularity in communication systems due to their capacity-approaching error correction performance. In this study, a high-performance LDPC decoding algorithm with extremely low resource usage is proposed. Among the hard decision class of LDPC decoders, Gallager B (GaB) provides high-performance hardware due to its computational simplicity. However, GaB suffers from poor error-correction performance. In this study, a new intrinsic computation technique for GaB called Intrinsic Gallager B (IGaB) is introduced to improve error correction performance. Our simulation results show that the IGaB algorithm provides better error correction performance compared with GaB. GaB and IGaB algorithms are implemented on Field Programmable Gate Array (FPGA) to compare hardware performance.
This paper presents the performance evaluation of the Probabilistic Gallager B (PGaB), a hard decision message passing Low Density Parity Check (LDPC) Decoder, with respect to the soft decision based decoders MinSum (MS) and Offset-MinSum (OMS). PGaB algorithm relies on introducing deliberate and controlled randomness to some of the exchanged messages of the GaB decoder such that it is able to escape from local minima associated with dominant trapping sets. We show that PGaB delivers higher decoding throughput than soft decision based decoders MS and OMS while using much fewer amount of Field Programmable Gate Array (FPGA) resources. Our Monte-Carlo simulation results show that the decoding performance of the PGaB on Binary Symmetric Channel (BSC) is far better than the deterministic GaB and very close to MS and OMS performances especially in error floor region.
This paper deals with the hardware implementation of the recently introduced Probabilistic Gradient-Descent Bit-Flipping (PGDBF) decoder. The PGDBF is a new type of hard-decision decoder for Low-Density Parity-Check (LDPC) code, with improved error correction performance thanks to the introduction of deliberate random perturbation in the computing units. In the PGDBF, the random perturbation operates during the bit-flipping step, with the objective to avoid the attraction of so-called trapping-sets of the LDPC code. In this paper, we propose an efficient hardware architecture which minimizes the resource overhead needed to implement the random perturbations of the PGDBF. Our architecture is based on the use of a Short Random Sequence (SRS) that is duplicated to fully apply the PGDBF decoding rules, and on an optimization of the maximum finder unit. The generation of good SRS is crucial to maintain the outstanding decoding performance of PGDBF, and we propose two different methods with equivalent hardware overheads, but with different behaviors on different LDPC codes. Our designs show that the improved PGDBF performance gains can be obtained with a very small additional complexity, therefore providing a competitive hard-decision LDPC decoding solution for current standards.
Hard-decision LDPC decoders are widely used in communication and storage systems due to their simple circuits. However, existing hard decision LDPC decoding circuits lead to slow decoding convergence due to flipping according to the maximum energy value, reducing decoding performance. This paper proposes the Dual-Energy Probabilistic Gradient Descent Bit-Flipping (DPGDBF) hard-decision algorithm. If the energy value of the variable node reaches the threshold, all nodes with the threshold energy will be flipped, and the node with the sub-maximum threshold energy will be flipped with a certain probability. otherwise, only all variable nodes with the maximum energy value are flipped. The simulation results show that, in a limited iterative range, compared with Tabu-list Random-Penalty Gradient Descent Bit-Flipping (TRGDBF), for (2048, 1024) codes, the average number of decoding iterations of the algorithm is reduced by 12%, and the decoding performance is improved to a certain extent; for (9216,7680) codes, the average number of decoding iterations of the DPGDBF algorithm is reduced by 18%, and the decoding performance is improved by 4 times. In addition, this paper proposes a hardware implementation of the DPGDBF algorithm for (2048, 1024) codes, with a maximum clock frequency of 305.53MHz and a through-put of 19.52Gbps.
Low-complexity and high-performance low-density parity-check (LDPC) decoders are highly demanded in various modern communication and storage systems. In this paper, a novel hard-decision decoding algorithm, called tabu-list random-penalty gradient descent bit-flipping (TRGDBF) algorithm, is proposed. Compared to the state-of-the-art hard-decision algorithms, the TRGDBF algorithm has much better error-correction performance due to several algorithmic improvements. First, a random-penalty term is introduced to the inversion function to help the decoder escape from trapping sets, which are the main causes of the error-floor phenomenon. Second, a tabu-list is employed to improve the decoding efficiency. Numerical results show that the TRGDBF algorithm can achieve up to two orders of magnitude better error-correction performance than the probabilistic gradient descent bit-flipping (PGDBF) algorithm and reduce the average iteration count by about 15%. In addition, a well-optimized hardware architecture is developed to implement the TRGDBF algorithm. Algorithmic transformation and architecture optimization are well explored to reduce the hardware complexity and latency. Synthesis results show that the TRGDBF decoder can work at a higher frequency and offer a larger throughput than the PGDBF decoder.