During the check node (CN) update, the elements of input message vectors are redundant for the output message vectors. Hence, in this paper, we exactly select from the input message vectors the elements, which really have contributions to the error-correction performance and constitute the minimum set for the CN update. With adoption of the forward and backward (FB) scheme, an adaptive minimum-set min-sum algorithm (AMSA) is proposed to reduce the computation complexity of the FB process. In order to concurrently update the output vectors belonging to the same CN, we present a parallel minimum-set min-sum algorithm (PMSA) with lower memory complexity than the AMSA. Compared with the min-sum algorithms, the two proposed minimum-set based algorithms introduce no error performance loss.

Belief Propagation (BP) decoding provides soft outputs and features high-level parallelism. In this paper, we propose an optimized software BP decoder for polar codes on graphics processing units (GPUs). A full-parallel decoding architecture for codes with length n ≤ 2048 is presented to simultaneously update n/2 processing elements (PEs) within each stage and achieve high on-chip memory utilization by using 8-bit quantization. And, for codes with length n > 2048, a partial-parallel decoding architecture is proposed to partly update PEs of each stage in parallel and coalesced global memory accesses are performed. Experimental results show that, with incorporation of the G-matrix based early termination criterion, more than 1 Gbps throughput for codes n ≤ 1024 can be achieved on NVIDIA TITAN Xp at 5 dB while the decoding latency is less than 1 ms. Compared with the state-of-the-art works, the proposed decoder achieves throughput speedups from 2.59× to 131× and provides good tradeoff between error performance and throughput.

Summary Nonbinary low‐density parity‐check (NB‐LDPC) codes are excellent error correcting codes and outperform their binary counterparts under the same code length. NB‐LDPC decoders are based on Belief Propagation Algorithm, which demands intensive message‐passing computation. Recently, to achieve both flexibility and good throughput performance, NB‐LDPC decoders have been ported from dedicated hardware solutions to multi/many‐core systems. In this paper, we propose an FFT‐based q‐ary Sum‐Product Algorithm (QSPA) decoding architecture for NB‐LDPC codes with layered and flooding schedules on a graphics processing unit (GPU). To improve the throughput performance of the proposed decoder, four optimization methods are presented to not only accelerate the decoding kernel execution but also improve the data transfer efficiency. The experiments are mainly accomplished on NVIDIA GTX580 and GTX Titan X. Throughputs up to 63 Mbps over GF(16) and 7.65 Mbps over GF(256) are achieved on GTX580 when executing 5 layered decoding iterations. Throughputs can reach up to 139 Mbps over GF(16) and17 Mbps over GF(256) on GTX Titan X. Experimental results show that the speedups of the decoding throughputs range from ×1.7 to ×16.8 by comparison with the existing FFT‐based QSPA decoders on GPU.