Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Telecommunications Forum (TELFOR)

Flexible parallel implementation of LLR BP decoding simulation on multicores using OpenCL

Igor Volkov, Aleksei Kharin, Aleksei Dryakhlov, Evgeny Mirokhin, Konstantin Terekhov, Konstantin Zavertkin, Aleksei Ovinnikov, Evgeny A. Likhobabin, Vladimir V. Vityazev

Published Nov 1, 2017• 8 citations
Publisher

Abstract

In this paper we explore acceleration of the logarithmic likelihood ratio (LLR) belief propagation (BP) algorithm for LDPC codes decoding simulation, using parallel computation on graphics processing units (GPUs) with OpenCL technology. The proposed parallel implementation of the LLR BP algorithm includes parallel version of all decoding steps: decoder initialization, check and variable nodes update, a posteriori LLR calculation and decoding termination check. Decoder throughput was measured by simulating data transmission system with LDPC coding for DVB-T2/S2 (64800, 32400) and PEG (1008, 504) codes.

DOI
10.1109/telfor.2017.8249334

Related papers

Parallel Implementation of GPU-Based LDPC Enhanced Quasi-Maximum Likelihood Decoder

KONG Feiyue, JIANG Xueqin, WAN Xuefen, CHEN Sijing, CUI Jian, YANG Yi

The Enhanced Quasi-Maximum Likelihood(EQML) decoder has better decoding performance for short Low Density Parity Check(LDPC) codes than traditional Belief Propagation(BP) decoder,and can meet the high reliability requirements of 5G mobile communication.However,its decoding speed is greatly reduced due to its complex computational structure.To address the problem,this paper proposes a parallel acceleration scheme based on Graphics Processing Unit(GPU) for EQML decoder.The scheme compresses and stores the parity check matrix of irregular LDPC codes,and resorts the traditional BP decoding algorithms to maximize the utilization of threads in Kernel.Then parallel decoding is implemented for multi-code words in each stage of reprocessing,so as to realize memory access optimization and parallel decoding of streams.Experimental results show that the GPU-based EQML decoder improves the speed by two orders of magnitude compared with the CPU-based decoder,while keeping the error correction performance.

•May 1, 2020•0 citations

Sequential decoding of non-binary LDPC codes on graphics processing units

David L. Romero, Nicholas B. Chang

Non-binary low-density parity-check (LDPC) codes have been shown to attain near capacity error correcting performance in noisy wireless communication channels. It is well known that these codes require a very large number of operations per-bit to decode. This high computational complexity along with a parallel decoder structure makes graphics processing units (GPUs) an attractive platform for acceleration of the decoding algorithm. The seemingly random memory access patterns associated with decoding are generally beneficial to error-correcting performance but present a challenge to designers who want to leverage the computational capabilities of the GPU. In this paper we describe the design of an efficient decoder implementation based on GPUs and a corresponding set of powerful non-binary LDPC codes. Using the belief propagation algorithm with a sequential message updating scheme it is shown that we are able to exploit parallelism inherent in the decoding algorithm while decreasing the number of decoding iterations required for convergence.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2012•10 citations

Parallel Algorithmic Optimization for Enhanced Quasi-Maximum Likelihood Decoding on GPU

Kong Fei-Yue, Sijing Chen, Xue-fen Wan +1 more

The Enhanced quasi-maximum likelihood (EQML) decoder has better decoding performance than the traditional belief propagation (BP) decoder, but its decoding speed is greatly reduced due to its complicated computational structure. Therefore, an efficient graphics processing unit (GPU) implementation structure for EQML decoder of low-density parity-check (LDPC) code is proposed. Intra-codeword parallel and inter-codeword parallel decoding schemes on GPU are adopted instead of serial decoding on CPU. Several optimization methods have also been employed to enhance the decoder throughput, such as compressed storing and Kernel thread arrangement scheme, which improve the decoding speed without degrading the decoding performance of the decoder. Experiment results show that our GPU based implementation structure which is about two orders of magnitude faster than that of CPU implementation.

IEEE International Conference on Electronics and Communication Engineering (ICECE)•Dec 1, 2019•0 citations

Program realization of simulation tools of low-density codecs: effective architecture of a decoder for massive parallel computations on graphic processors

А В Башкиров, А. А. Пирогов, O Y Makarov +3 more

Abstract The article deals with the peculiarities of modeling the characteristics of low-density parity-check codes (LDPC) in terms of their decoding. When decoding low-density parity-check codes in various communication standards, the iterative belief propagation algorithm (BP) and its various modifications - Pearl’s algorithm, sum-of-products algorithm - are widely used. In the article, special attention is given to this algorithm. The BP algorithm is a message-passing algorithm on a graphical model and consists of two basic messaging procedures between the nodes in the Tanner graph for LDPC code. The issues of constructing an effective architecture for an iterative decoder operating on the belief propagation algorithm in a heterogeneous system with massively parallel computing on a graphics processing unit are considered. It is shown that the use of the GPU allows to achieve a significant gain in decoding time with a sufficient size of the test matrix (a sufficient number of code and test nodes), obtained due to the parallelism of the architecture. Expressions for calculation of the size of the “working group” are given. The benefit of using a modified decoder architecture is estimated.

Journal of Physics Conference Series•Oct 1, 2019•0 citations

Modified Belief Propagation Decoding Algorithm for Low-Density Parity Check Code Based on Oscillation

Satoshi Gounai, Tomoaki Otsuki Ohtsuki, T. Kaneko

A low-density parity check (LDPC) code with the belief propagation (BP) or the log-likelihood ratio belief propagation (LLR-BP) can achieve good bit error rate (BER) performance approaching the Shannon limit. When a parity check matrix of the LDPC code has the cycle, the BP and LLR-BP decoding algorithms achieve approximate maximum a posterior probability (MAP) decoding. Although the decoding algorithms are approximate MAP decoding, LDPC codes can achieve very good BER. For the short and middle length LDPC codes, BER and block error rate (BLER) performances are affected by cycle largely. In each iteration, the magnitudes of a posterior LLRs of some bits oscillate owing to cycles. The oscillation is the dominant error factor in the high Eb/Noregion for short and middle length LDPC codes. In this paper, we extend the definition of oscillation to extrinsic LLR (ex-LLR) derived in the bit node process and propose the modified LLR-BP and the modified UMP-BP decoding algorithms. To reduce effects of oscillating ex-LLRs on decoding, for oscillating ex-LLRs, we add the previous ex-LLR to the current ex-LLR. From the computer simulation, we show that for short and middle length LDPC codes, with a simple modification, our proposed decoding algorithms can improve the conventional LLR-BP and UMP-BP decoding algorithms. In particular, we show that the modified UMP-BP decoding algorithm with low complexity can achieve better BER and BLER than the conventional LLR-BP decoding algorithm

IEEE Vehicular Technology Conference•Sep 8, 2006•15 citations

Reduced-Complexity Decoding of LDPC Codes

Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.

IEEE Transactions on Communications•Jul 1, 2005•27 citations
In this paper we explore acceleration of the logarithmic likelihood ratio (LLR) belief propagation (BP) algorithm for LDPC codes decoding simulation, using parallel computation on graphics processing units (GPUs) with OpenCL technology. The proposed parallel implementation of the LLR BP algorithm includes parallel version of all decoding steps: decoder initialization, check and variable nodes update, a posteriori LLR calculation and decoding termination check. Decoder throughput was measured by simulating data transmission system with LDPC coding for DVB-T2/S2 (64800, 32400) and PEG (1008, 504) codes.
The Enhanced Quasi-Maximum Likelihood(EQML) decoder has better decoding performance for short Low Density Parity Check(LDPC) codes than traditional Belief Propagation(BP) decoder,and can meet the high reliability requirements of 5G mobile communication.However,its decoding speed is greatly reduced due to its complex computational structure.To address the problem,this paper proposes a parallel acceleration scheme based on Graphics Processing Unit(GPU) for EQML decoder.The scheme compresses and stores the parity check matrix of irregular LDPC codes,and resorts the traditional BP decoding algorithms to maximize the utilization of threads in Kernel.Then parallel decoding is implemented for multi-code words in each stage of reprocessing,so as to realize memory access optimization and parallel decoding of streams.Experimental results show that the GPU-based EQML decoder improves the speed by two orders of magnitude compared with the CPU-based decoder,while keeping the error correction performance.
Non-binary low-density parity-check (LDPC) codes have been shown to attain near capacity error correcting performance in noisy wireless communication channels. It is well known that these codes require a very large number of operations per-bit to decode. This high computational complexity along with a parallel decoder structure makes graphics processing units (GPUs) an attractive platform for acceleration of the decoding algorithm. The seemingly random memory access patterns associated with decoding are generally beneficial to error-correcting performance but present a challenge to designers who want to leverage the computational capabilities of the GPU. In this paper we describe the design of an efficient decoder implementation based on GPUs and a corresponding set of powerful non-binary LDPC codes. Using the belief propagation algorithm with a sequential message updating scheme it is shown that we are able to exploit parallelism inherent in the decoding algorithm while decreasing the number of decoding iterations required for convergence.
The Enhanced quasi-maximum likelihood (EQML) decoder has better decoding performance than the traditional belief propagation (BP) decoder, but its decoding speed is greatly reduced due to its complicated computational structure. Therefore, an efficient graphics processing unit (GPU) implementation structure for EQML decoder of low-density parity-check (LDPC) code is proposed. Intra-codeword parallel and inter-codeword parallel decoding schemes on GPU are adopted instead of serial decoding on CPU. Several optimization methods have also been employed to enhance the decoder throughput, such as compressed storing and Kernel thread arrangement scheme, which improve the decoding speed without degrading the decoding performance of the decoder. Experiment results show that our GPU based implementation structure which is about two orders of magnitude faster than that of CPU implementation.
Abstract The article deals with the peculiarities of modeling the characteristics of low-density parity-check codes (LDPC) in terms of their decoding. When decoding low-density parity-check codes in various communication standards, the iterative belief propagation algorithm (BP) and its various modifications - Pearl’s algorithm, sum-of-products algorithm - are widely used. In the article, special attention is given to this algorithm. The BP algorithm is a message-passing algorithm on a graphical model and consists of two basic messaging procedures between the nodes in the Tanner graph for LDPC code. The issues of constructing an effective architecture for an iterative decoder operating on the belief propagation algorithm in a heterogeneous system with massively parallel computing on a graphics processing unit are considered. It is shown that the use of the GPU allows to achieve a significant gain in decoding time with a sufficient size of the test matrix (a sufficient number of code and test nodes), obtained due to the parallelism of the architecture. Expressions for calculation of the size of the “working group” are given. The benefit of using a modified decoder architecture is estimated.
A low-density parity check (LDPC) code with the belief propagation (BP) or the log-likelihood ratio belief propagation (LLR-BP) can achieve good bit error rate (BER) performance approaching the Shannon limit. When a parity check matrix of the LDPC code has the cycle, the BP and LLR-BP decoding algorithms achieve approximate maximum a posterior probability (MAP) decoding. Although the decoding algorithms are approximate MAP decoding, LDPC codes can achieve very good BER. For the short and middle length LDPC codes, BER and block error rate (BLER) performances are affected by cycle largely. In each iteration, the magnitudes of a posterior LLRs of some bits oscillate owing to cycles. The oscillation is the dominant error factor in the high Eb/Noregion for short and middle length LDPC codes. In this paper, we extend the definition of oscillation to extrinsic LLR (ex-LLR) derived in the bit node process and propose the modified LLR-BP and the modified UMP-BP decoding algorithms. To reduce effects of oscillating ex-LLRs on decoding, for oscillating ex-LLRs, we add the previous ex-LLR to the current ex-LLR. From the computer simulation, we show that for short and middle length LDPC codes, with a simple modification, our proposed decoding algorithms can improve the conventional LLR-BP and UMP-BP decoding algorithms. In particular, we show that the modified UMP-BP decoding algorithm with low complexity can achieve better BER and BLER than the conventional LLR-BP decoding algorithm
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.