© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1204.0334 · IEEE Transactions on Parallel and Distributed Systems

Implementation of Decoders for LDPC Block Codes and LDPC Convolutional Codes Based on GPUs

Yue Zhao, Francis C. M. Lau

Published Oct 28, 2013• 35 citations

Abstract

In this paper, efficient LDPC block-code decoders/simulators which run on graphics processing units (GPUs) are proposed. We also implement the decoder for the LDPC convolutional code (LDPCCC). The LDPCCC is derived from a predesigned quasi-cyclic LDPC block code with good error performance. Compared to the decoder based on the randomly constructed LDPCCC code, the complexity of the proposed LDPCCC decoder is reduced due to the periodicity of the derived LDPCCC and the properties of the quasicyclic structure. In our proposed decoder architecture, Γ (Γ is a multiple of a warp) codewords are decoded together, and hence, the messages of Γ codewords are also processed together. Since all the Γ codewords share the same Tanner graph, messages of the Γ distinct codewords corresponding to the same edge can be grouped into one package and stored linearly. By optimizing the data structures of the messages used in the decoding process, both the read and write processes can be performed in a highly parallel manner by the GPUs. In addition, a thread hierarchy minimizing the divergence of the threads is deployed, and it can maximize the efficiency of the parallel execution. With the use of a large number of cores in the GPU to perform the simple computations simultaneously, our GPU-based LDPC decoder can obtain hundreds of times speedup compared with a serial CPU-based simulator and over 40 times speedup compared with an eight-thread CPU-based simulator.

DOI: 10.1109/tpds.2013.52

Related papers

A Scalable LDPC Decoder on GPU

Kiran Kumar Abburi

A flexible and scalable approach for LDPC decoding on CUDA based Graphics Processing Unit (GPU) is presented in this paper. Layered decoding is a popular method for LDPC decoding and is known for its fast convergence. However, efficient implementation of the layered decoding algorithm on GPU is challenging due to the limited amount of data-parallelism available in this algorithm. To overcome this problem, a kernel execution configuration that can decode multiple codewords simultaneously on GPU is developed. This paper proposes a compact data packing scheme to reduce the number of global memory accesses and parity-check matrix representation to reduce constant memory latency. Global memory bandwidth efficiency is improved by coalescing simultaneous memory accesses of threads in a half-warp into a single memory transaction. Asynchronous data transfers are used to hide host memory latency by overlapping kernel execution with data transfers between CPU and GPU. The proposed implementation of LDPC decoder on GPU performs two orders of magnitude faster than the LDPC decoder on a CPU and four times faster than the previously reported LDPC decoder on GPU. This implementation achieves a throughput of 160Mbps, which is comparable to dedicated hardware solutions.

International Conference on VLSI Design•Jan 1, 2011•23 citations

Parallel decoding of LDPC convolutional codes using OpenMP and GPU

Chi Ho Chan, Francis C. M. Lau

Recently, there have been different applications, namely 10GBase-T Ethernet, video broadcasting and satellite communication, utilizing low-density parity-check (LDPC) codes as the forward-error-correction codes. The main reason is that the error performance of LDPC codes can be very close to the Shannon limit. LDPC codes can be further categorized into LDPC block codes (LDPC-BCs) and LDPC convolutional codes (LDPC-CCs). It has also been discovered that LDPC-CCs usually outperform LDPC-BCs. Simulation of LDPC-BCs and LDPC-CCs can take a lot of time because the decoding algorithms are relatively complex. Fortunately, the decoding steps can be performed in parallel. In this paper, we create three different platforms for simulating the error performance of LDPC-CCs. The first two platforms are run on a Central Processing Unit (CPU) while the third one involves the use of a Graphics Processing Unit (GPU). We show that using GPU can improve the simulation speed substantially.

IEEE Symposium on Computers and Communications (ISCC)•Jul 1, 2012•7 citations

High Throughput Pipeline Decoder for LDPC Convolutional Codes on GPU

Yi Hou, Rongke Liu, Hao Peng +1 more

In this letter, we present a graphics processing unit (GPU)-based LDPC convolutional code (LDPC-CC) pipeline decoder with optimized parallelism. The proposed decoder exploits different granularities of decoding parallelism for both the compute unified device architecture (CUDA) kernel execution stage and the data transfer stage. Moreover, the parameter selection criteria for decoder implementation are designed to avoid exhaustive search of all the combinations of parameters. The experiments are carried out on Nvidia GTX460 and GTX580 platforms. The results demonstrate the proposed decoder achieves about 3 times speedup compared to the existing GPU-based work.

IEEE Communications Letters•Oct 5, 2015•9 citations

Simulation of LDPC convolutional decoders with CPU and GPU

Chi Ho Chan, Francis C. M. Lau

In this paper, the Sum Product Algorithm (SPA) and the Min-Sum Algorithm (MSA) are used for decoding low-density parity-check convolutional codes (LDPC-CCs). The two algorithms have been implemented and run on three different computing environments. The first environment is a single-threading Central Processing Unit (CPU); the second one is the multi-threading CPU based on OpenMP (Open Multi-Processing); and the third one is the multi-threading Graphics Processing Unit (GPU). The error performance of the LDPC-CCs and the simulation time taken under the three specific computing environments and the two decoding algorithms are evaluated and compared. It is found that the different computing environments produce very similar error results. It is also concluded that using the GPU computing platform can reduce the simulation time substantially.

International Conference on Consumer Electronics, Communications and Networks (CECNet)•Apr 1, 2012•2 citations

Massive parallel LDPC decoding on GPU

Gabriel Falcão, Leonel A. Sousa, Vitor M. M. da Silva

Low-Density Parity-Check (LDPC) codes are powerful error correcting codes (ECC). They have recently been adopted by several data communication standards such as DVB-S2 and WiMax. LDPCs are represented by bipartite graphs, also called Tanner graphs, and their decoding demands very intensive computation. For that reason, VLSI dedicated architectures have been investigated and developed over the last few years. This paper proposes a new approach for LDPC decoding on graphics processing units (GPUs). Efficient data structures and an new algorithm are proposed to represent the Tanner graph and to perform LDPC decoding according to the stream-based computing model. GPUs were programmed to efficiently implement the proposed algorithms by applying data-parallel intensive computing. Experimental results show that GPUs perform LDPC decoding nearly three orders of magnitude faster than modern CPUs. Moreover, they lead to the conclusion that GPUs with their tremendous processing power can be considered as a consistent alternative to state-of-the-art hardware LDPC decoders.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming•Feb 20, 2008•48 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

In this paper, efficient LDPC block-code decoders/simulators which run on graphics processing units (GPUs) are proposed. We also implement the decoder for the LDPC convolutional code (LDPCCC). The LDPCCC is derived from a predesigned quasi-cyclic LDPC block code with good error performance. Compared to the decoder based on the randomly constructed LDPCCC code, the complexity of the proposed LDPCCC decoder is reduced due to the periodicity of the derived LDPCCC and the properties of the quasicyclic structure. In our proposed decoder architecture, Γ (Γ is a multiple of a warp) codewords are decoded together, and hence, the messages of Γ codewords are also processed together. Since all the Γ codewords share the same Tanner graph, messages of the Γ distinct codewords corresponding to the same edge can be grouped into one package and stored linearly. By optimizing the data structures of the messages used in the decoding process, both the read and write processes can be performed in a highly parallel manner by the GPUs. In addition, a thread hierarchy minimizing the divergence of the threads is deployed, and it can maximize the efficiency of the parallel execution. With the use of a large number of cores in the GPU to perform the simple computations simultaneously, our GPU-based LDPC decoder can obtain hundreds of times speedup compared with a serial CPU-based simulator and over 40 times speedup compared with an eight-thread CPU-based simulator.

A flexible and scalable approach for LDPC decoding on CUDA based Graphics Processing Unit (GPU) is presented in this paper. Layered decoding is a popular method for LDPC decoding and is known for its fast convergence. However, efficient implementation of the layered decoding algorithm on GPU is challenging due to the limited amount of data-parallelism available in this algorithm. To overcome this problem, a kernel execution configuration that can decode multiple codewords simultaneously on GPU is developed. This paper proposes a compact data packing scheme to reduce the number of global memory accesses and parity-check matrix representation to reduce constant memory latency. Global memory bandwidth efficiency is improved by coalescing simultaneous memory accesses of threads in a half-warp into a single memory transaction. Asynchronous data transfers are used to hide host memory latency by overlapping kernel execution with data transfers between CPU and GPU. The proposed implementation of LDPC decoder on GPU performs two orders of magnitude faster than the LDPC decoder on a CPU and four times faster than the previously reported LDPC decoder on GPU. This implementation achieves a throughput of 160Mbps, which is comparable to dedicated hardware solutions.

Recently, there have been different applications, namely 10GBase-T Ethernet, video broadcasting and satellite communication, utilizing low-density parity-check (LDPC) codes as the forward-error-correction codes. The main reason is that the error performance of LDPC codes can be very close to the Shannon limit. LDPC codes can be further categorized into LDPC block codes (LDPC-BCs) and LDPC convolutional codes (LDPC-CCs). It has also been discovered that LDPC-CCs usually outperform LDPC-BCs. Simulation of LDPC-BCs and LDPC-CCs can take a lot of time because the decoding algorithms are relatively complex. Fortunately, the decoding steps can be performed in parallel. In this paper, we create three different platforms for simulating the error performance of LDPC-CCs. The first two platforms are run on a Central Processing Unit (CPU) while the third one involves the use of a Graphics Processing Unit (GPU). We show that using GPU can improve the simulation speed substantially.

In this letter, we present a graphics processing unit (GPU)-based LDPC convolutional code (LDPC-CC) pipeline decoder with optimized parallelism. The proposed decoder exploits different granularities of decoding parallelism for both the compute unified device architecture (CUDA) kernel execution stage and the data transfer stage. Moreover, the parameter selection criteria for decoder implementation are designed to avoid exhaustive search of all the combinations of parameters. The experiments are carried out on Nvidia GTX460 and GTX580 platforms. The results demonstrate the proposed decoder achieves about 3 times speedup compared to the existing GPU-based work.

In this paper, the Sum Product Algorithm (SPA) and the Min-Sum Algorithm (MSA) are used for decoding low-density parity-check convolutional codes (LDPC-CCs). The two algorithms have been implemented and run on three different computing environments. The first environment is a single-threading Central Processing Unit (CPU); the second one is the multi-threading CPU based on OpenMP (Open Multi-Processing); and the third one is the multi-threading Graphics Processing Unit (GPU). The error performance of the LDPC-CCs and the simulation time taken under the three specific computing environments and the two decoding algorithms are evaluated and compared. It is found that the different computing environments produce very similar error results. It is also concluded that using the GPU computing platform can reduce the simulation time substantially.

Low-Density Parity-Check (LDPC) codes are powerful error correcting codes (ECC). They have recently been adopted by several data communication standards such as DVB-S2 and WiMax. LDPCs are represented by bipartite graphs, also called Tanner graphs, and their decoding demands very intensive computation. For that reason, VLSI dedicated architectures have been investigated and developed over the last few years. This paper proposes a new approach for LDPC decoding on graphics processing units (GPUs). Efficient data structures and an new algorithm are proposed to represent the Tanner graph and to perform LDPC decoding according to the stream-based computing model. GPUs were programmed to efficiently implement the proposed algorithms by applying data-parallel intensive computing. Experimental results show that GPUs perform LDPC decoding nearly three orders of magnitude faster than modern CPUs. Moreover, they lead to the conclusion that GPUs with their tremendous processing power can be considered as a consistent alternative to state-of-the-art hardware LDPC decoders.

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.