IEEE International Conference on Electronics, Circuits and Systems (ICECS)

Efficient FPGA implementation of probabilistic gallager B LDPC decoder

Fakhreddine Ghaffari, Burak Ünal, Ali Akoglu, Khoa Le, David Declercq, Bane V. Vasic

Published Dec 1, 2017• 6 citations

Abstract

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.

DOI: 10.1109/icecs.2017.8292048

Related papers

Hardware Implementation and Performance Analysis of Resource Efficient Probabilistic Hard Decision LDPC Decoders

Burak Ünal, Ali Akoglu, Fakhreddine Ghaffari +1 more

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.

IEEE Transactions on Circuits and Systems I Regular PapersApr 3, 201823 citations

Analysis and implementation of resource efficient probabilistic Gallager B LDPC decoder

Burak Ünal, Fakhreddine Ghaffari, Ali Akoglu +2 more

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.

IEEE International New Circuits and Systems Conference (NEWCAS)Jun 1, 20177 citations

High Performance and Resource Efficient Low Density Parity Check Decoder Design

Burak Ünal

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.

Signal Processing and Communications Applications Conference (SIU)Jun 25, 20250 citations

A New Probabilistic Gradient Descent Bit Flipping Decoder for LDPC Codes

Hangxuan Cui, Jun Ting Lin, Suwen Song +1 more

Probabilistic gradient descent bit-flipping (PGDBF) is the state-of-the-art hard-decision algorithm for decoding low-density parity-check (LDPC) codes on binary symmetric channel (BSC). However, there still exists a considerable performance gap between the PGDBF algorithm and soft-decision algorithms, especially in the error-floor region. To bridge this performance gap, a tabu-list aided PGDBF (T-PGDBF) algorithm is proposed in this paper. In the T-PGDBF algorithm, a tabu-list is employed to help the decoding escape from trapping sets, which is the main cause of the error-floor phenomenon. The bits which are flipped in the current iteration will be added to the tabu-list to prevent them being flipped in the next iteration. Simulation results show that the T-PGDBF algorithm offers a significant performance gain when compared to the PGDBF algorithm, which can reach that of soft-decision algorithms. We also present the hardware architecture to implement the T-PGDBF algorithm. Synthesis results show that the improved performance offered by the T-PGDBF algorithm can be obtained with a small hardware overhead.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20198 citations

FPGA Implementations of Layered MinSum LDPC Decoders Using RCQ Message Passing

Caleb Terrill, Linfang Wang, Sean Chen +4 more

Non-uniform message quantization techniques such as reconstruction-computation-quantization (RCQ) improve error-correction performance and decrease hardware complexity of low-density parity-check (LDPC) decoders that use a flooding schedule. Layered MinSum RCQ (L-msRCQ) enables message quantization to be utilized for layered decoders and irregular LDPC codes. We investigate field-programmable gate array (FPGA) implementations of L-msRCQ decoders. Three design methods for message quantization are presented, which we name the Lookup, Broadcast, and Dribble methods. The decoding performance and hardware complexity of these schemes are compared to a layered offset MinSum (OMS) decoder. Simulation results on a (16384, 8192) protograph-based raptor-like (PBRL) LDPC code show that a 4-bit L-msRCQ decoder using the Broadcast method can achieve a 0.03 dB improvement in error-correction performance while using 12% fewer registers than the OMS decoder. A Broadcast-based 3-bit L-msRCQ decoder uses 15% fewer lookup tables, 18% fewer registers, and 13% fewer routed nets than the OMS decoder, but results in a 0.09 dB loss in performance.

arXiv:2104.09480GlobecomDec 1, 20215 citations

Field programmable gate arrays implementations of low complexity soft-input soft-output low-density parity-check decoders

Leonardo J. Arnone, J. Castiñeira Moreira, Patrick Guy Farrell

Low-density parity-check (LDPC) codes are very efficient error control codes that are being considered for use in many next-generation communication systems. In this study low complexity soft-input, soft-output (SISO) field programmable gate arrays (FPGA) implementations of a novel logarithmic sum-product (LogSP) iterative LDPC decoder and a recently proposed simplified soft Euclidean distance (SSD) iterative LDPC decoder are presented, and their complexities and performance are compared. These implementations operate over any choice of parity check matrix (including those randomly generated, structurally generated and either systematic or non-systematic) and can be parametrically adapted for any code rate. The proposed implementations are both of very low complexity, because they operate using only sums, subtractions, comparisons and look-up tables, which makes them particularly suitable for FPGA realisation. The SSD decoder has a lower implementation complexity than the LogSP LDPC decoder and it also offers the advantage of not requiring knowledge of the channel signal-to-noise ratio, unlike most other LDPC decoders.

IET CommunicationsAug 14, 20125 citations