Parallel-Pipeline Fast Walsh-Hadamard Transform Implementation Using HLS

Walsh Hadamard Transform (WHT) is an orthogonal, symmetric, involutional, and linear operation used in data encryption, data compression, and quantum computing. The WHT belongs to a generalized class of Fourier transforms, which allows that many algorithms developed for the fast Fourier transform (FFT) work for fast WHT implementations (FWHT). This paper employs this property and uses a parallel-pipeline FFT well-known strategy for VLSI implementation to build parallel-pipeline architectures for FWHT. We apply the FFT parallel-pipeline approach on a Fast WHT and use the High-Level Synthesis (HLS) tool from Xilinx Vitis to generate an FPGA solution. We also provide an open-source code with the basic blocks to build any model with any parallelization level. The parallel-pipeline proposed solutions achieve a latency reduction of up to 3.57% compared to a pipeline approach on a 256-long signal using 32 bit floating-point numbers.

I. Introduction

The Walsh-Hadamard Transform (WHT) decomposes any signal into a series of basis functions called Walsh functions, which are rectangular or square with values of +1 and –1. The WHT of a signal with samples can be computed by the matrix multiplication with the Hadamard matrix. This Hadamard matrix can be defined recursively by

$$\begin{equation*}{H_k} = {\frac{1} {\sqrt2 }}\left[ \begin{array}{lcl}{{H_{k - 1}}} & {{H_{k - 1}}} \\ {{H_{k - 1}}} & {{H_{k - 1}}} \\ \end{array} \right]\tag{1}\end{equation*}$$ with , or using the Kronecker product by: $$\begin{equation*}{H_k} = {H_1} \otimes {H_{k - 1}}.\tag{2}\end{equation*}$$