Adaptable Low Density Parity Check (LDPC) Engine

Student: Sahil Hassan

Algorithmic Contribution: We introduced a new algorithm called Probabilistic Gallagher B (PGaB) by applying a probabilistic stimulation functionover the iterative decoding process, conduct detailed experimental evaluations with respect to other decoders and show that our algorithm not only improves the decoding performance with respect to GaB by four orders of magnitude, but also requires fewest amountof hardware resources with respect to other comparable decoding algorithms GDBF and PGDBF while achieving equivalent or better decoding performance. We present the details of our incremental approach to designing and implementing the GaB and PGaB hardware architecture.

Architecture Specific Contribution: The connection intensive bipartite graph based LDPC decoder hardware architecture creates routing stress when implemented on the FPGA for longer codewords that are utilized in today's communications systems and standards. From FPGA point of view, even though there is sufficient amount of computing resources that would match the degree of parallelism desired by the design, implementation is less likely to pass the routing stage of the synthesis as the number of connections in the implementation increase with the code length, which in turn increases the stress on FPGA routing resources. Another contributor to the routing stress is the number of parity bits used by the communication medium, which has direct impact on the number of connections between each iteration of the decoding process since increasing the ratio of parity bit to data from 0.5 to 0.75 would mean increasing number of connections by a factor of 4 for a given codeword. Therefore for implementations of longer codewords and/or higher code rates, designers resort to reducing the degree of parallelism in their implementations.

Publications

• Burak Unal, Ali Akoglu, Fakhreddine Ghaffari, Bane Vasic, “Hardware Implementation and Performance Analysis of Resource Efficient Stochastic Hard Decision LDPC Decoders,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 65, issue: 9, pp. 3074-3084, September 2018.
• Fakhreddine Ghaffari, Burak Unal, Ali Akoglu, Khoa Le, David Declercq and Bane Vasic, “Efficient FPGA Implementation of Probabilistic Gallager B LDPC Decoder,” 24th IEEE International Conference on Electronics, Circuits and Systems (ICECS), Batumi, Georgia, December 5-8 2017, pp. 1-4.
• Fakhreddine Ghaffari, Ali Akoglu, Bane Vasic, “Multi-mode Low-latency Software-defined Error Correction for Data Centers,” IEEE 26th International Conference on Computer Communications and Networks (ICCCN 2017), Vancouver, Canada, July 31 -August 3, 2017, pp. 1-8. (Invited Paper)
• Burak Unal, Fakhreddine Ghaffari, Ali Akoglu, Bane Vasic, “Analysis and Implementation of Resource Efficient Probabilistic Gallager B LDPC Decoder,” 2017 15th IEEE International New Circuits and Systems Conference (NEWCAS), Strasbourg, 2017, pp. 333-336. (Best Paper Nominee)
• Gregory Striemer, Ali Akoglu, "An Adaptable Low Density Parity Check (LDPC) Engine for Space Based Communication Systems", IEEE NASA/ESA Conference on Adaptive Hardware and Systems (AHS 2010) June 15-18, 2010 Anaheim California