Parallelized Algorithm for Radix-2 Fast Hadamard Transform

The fast Hadamard transform (FHT) has extensive application in signal and image processing, communication systems, digital logic, and other fields. Faced with problems at a very large scale, the serial algorithms of the FHT are probably unable to meet the calculation time requirements. In this situation, parallelizing the algorithm is an effective solution. Based on compressed sensing image reconstruction of a single-pixel camera and by using the structural similarity between the FHT and the fast Fourier transform, we propose a task-level parallel algorithm for the general radix-2 FHT. We prove equivalence between the results of the serial and parallel algorithms by construction. The simulation result shows that for a problem scale with an input vector length less than 2²⁰ and subtasks fewer than 2¹⁰, the squared Euclidean distance error between the serial and parallel algorithms is less than 10^-18, which substantiates the correctness of the parallel algorithm. An experiment using POSIX threads on a PC with a multicore CPU demonstrates that on a specific platform and under a specific configuration the observed speedup is 1.33~1.42 for problem scales with an input vector length from 2²⁰ to 2²⁵. This implies the feasibility and effectiveness of the proposed method.