Fast Walsh–Hadamard–Fourier Transform Algorithm

An efficient fast Walsh-Hadamard-Fourier transform algorithm which combines the calculation of the Walsh-Hadamard transform (WHT) and the discrete Fourier transform (DFT) is introduced. This can be used in Walsh-Hadamard precoded orthogonal frequency division multiplexing systems (WHT-OFDM) to increase speed and reduce the implementation cost. The algorithm is developed through the sparse matrices factorization method using the Kronecker product technique, and implemented in an integrated butterfly structure. The proposed algorithm has significantly lower arithmetic complexity, shorter delays and simpler indexing schemes than existing algorithms based on the concatenation of the WHT and FFT, and saves about 70%-36% in computer run-time for transform lengths of 16-4096.