# Can the Walsh Hadamard transform be computed for non power of 2 sizes?

Can the walsh hadamard transform be calculated for odd image block sizes such as 5x5 or 7x7? Most of the examples I've seen are for 4x4 and 8x8?

I fear it probably can't from the description I read on Wikipedia ( though I'm still trying to fully digest that page).

-
I know this is not answering your question, but how about padding your block with zeros? Working with powers of 2 is always comforting! –  Atul Ingle Feb 23 at 23:20
@AtulIngle That is a very bad idea in the context of the Walsh-Hadamard transform. –  Dilip Sarwate Feb 24 at 3:39
Just for completeness @dilip, why would it be a bad idea? –  trican Feb 24 at 11:34
The DFT method of computing a convolution always gives the cyclic or circular convolution of the input sequences. It is adapted to compute the linear convolution of sequences of lengths $L$ and $M$, say, by zero-padding the sequences to common length $N \geq L+M-1$ where $N$ is chosen so as to be able to use the FFT algorithm for the DFT most efficiently. The Walsh-Hadmard transform supports a different convolution, and cannot be used to compute linear convolutions via zero-padding. So, you could zero-pad, and use the FHT, but is $\mathbf xH$ really useful for anything? –  Dilip Sarwate Feb 25 at 3:12
add comment

## 1 Answer

The Walsh-Hadamard transform requires a Hadamard matrix -- which has entries $\pm 1$ and whose rows are orthogonal vectors. A $n \times n$ Hadamard matrix is known to exist for $n = 2$. Larger Hadamard matrices can exist only if $n$ is a multiple of $4$, though it is not known if there is a Hadamard matrix for every multiple of $4$. However, there is a recursive construction that can be used to construct a $2^m \times 2^m$ Hadamard matrix from a $2^{m-1}\times 2^{m-1}$ Hadamard matrix, and this structure allows for the use of the Fast Hadamard Transform algorithm, which reduces the computational cost from $2^{2m}$ additions and subtractions to $m2^m$ additions and subtractions (just like the $N$-FFT reduces the number of multiplications from $O(N^2)$ to $O(N\log N)$.

With this as background, the answer is Yes, you can use a Walsh-Hadamard transform of length $N$ if you can find a $N\times N$ Hadamard matrix, but your choices for $N$ are necessarily restricted. Also, fast algorithms may not exist for your choice of $N$, though some speed-up is usually possible.

Note that Walsh-Hadamard transforms (WHTs) do not support cyclic convolutions, but they do support what is sometimes called Poisson convolution. If $H$ denotes a $2^m\times 2^m$ Hadamard matrix and $\mathbf x$ and $\mathbf y$ are vectors of length $2^m$ with \WHTs $\mathbf xH$ and $\mathbf yH$, then the inverse WHT of the term-by-term multiplication of the entries in $\mathbf xH$ and $\mathbf yH$ can be described as follows. Suppose that the entries in $\mathbf x$ and $\mathbf y$ etc are indexed not by integers $0$ through $2^m-1$ but rather by the $m$-bit representations of these numbers. Thus, we talk not of $x[k]$ as the $k$-th entry in $\mathbf x$ but rather of $x[\mathbf k]$ where $\mathbf k$ is the $m$-bit representation of $k$. Then, the iWHT of the term-by-term product of the entries in $\mathbf xH$ and $\mathbf yH$ has $\mathbf k$-th entry $$\sum_{\mathbf i} x[\mathbf i]y[\mathbf k\oplus \mathbf i]$$ which is eerily reminiscent of $$\sum_i x[i]y[k-i]$$ and even more so if one notes that modulo two, addition and subtraction are the same and so that $\mathbf k\oplus \mathbf i$ could as well have been written as $\mathbf k\ominus \mathbf i$.

-
Many thanks for the extremely detailed response –  trican Feb 24 at 11:11
I never knew these things about the WHT. Thanks! –  Atul Ingle Feb 25 at 20:07
add comment