Optimized Fast Walsh–Hadamard Transform on GPUs for non-binary LDPC decoding

• We analyse the role of the FWHT under the non-binary LDPC decoding problem.
• We quantify the trade-off between memory bank conflicts and the throughput on GPUs.
• The FWHT employs radix-n approaches tuned to the number of shared memory banks.
• The FWHT was tuned for both 16 and 32 shared memory bank GPU architectures.

The Fourier Transform Sum-Product Algorithm (FT-SPA) used in non-binary Low-Density Parity-Check (LDPC) decoding makes extensive use of the Walsh–Hadamard Transform (WHT). We have developed a massively parallel Fast Walsh–Hadamard Transform (FWHT) which exploits the Graphics Processing Unit (GPU) pipeline and memory hierarchy, thereby minimizing the level of memory bank conflicts and maximizing the number of returned instructions per clock cycle for different generations of graphics processors, with considerable speedup gains in FT-SPA based non-binary LDPC decoding.