## Walsh-Hadamard Transform

The Walsh-Hadamard transform is a non-sinusoidal, orthogonal
transformation technique that decomposes a signal into a set of basis
functions. These basis functions are Walsh functions, which are rectangular
or square waves with values of +1 or –1. Walsh-Hadamard transforms
are also known as Hadamard (see the `hadamard`

function
in the MATLAB software), Walsh, or Walsh-Fourier transforms.

The first eight Walsh functions have these values:

Index | Walsh Function Values |
---|---|

0 | 1 1 1 1 1 1 1 1 |

1 | 1 1 1 1 -1 -1 -1 -1 |

2 | 1 1 -1 -1 -1 -1 1 1 |

3 | 1 1 -1 -1 1 1 -1 -1 |

4 | 1 -1 -1 1 1 -1 -1 1 |

5 | 1 -1 -1 1 -1 1 1 -1 |

6 | 1 -1 1 -1 -1 1 -1 1 |

7 | 1 -1 1 -1 1 -1 1 -1 |

The Walsh-Hadamard transform returns sequency values. Sequency is a more generalized notion of frequency and is defined as one half of the average number of zero-crossings per unit time interval. Each Walsh function has a unique sequency value. You can use the returned sequency values to estimate the signal frequencies in the original signal.

Three different ordering schemes are used to store Walsh functions: sequency, Hadamard, and dyadic. Sequency ordering, which is used in signal processing applications, has the Walsh functions in the order shown in the table above. Hadamard ordering, which is used in controls applications, arranges them as 0, 4, 6, 2, 3, 7, 5, 1. Dyadic or gray code ordering, which is used in mathematics, arranges them as 0, 1, 3, 2, 6, 7, 5, 4.

The Walsh-Hadamard transform is used in a number of applications,
such as image processing, speech processing, filtering, and power
spectrum analysis. It is very useful for reducing bandwidth storage
requirements and spread-spectrum analysis. Like the FFT, the Walsh-Hadamard
transform has a fast version, the fast Walsh-Hadamard transform (`fwht`

). Compared to the FFT, the FWHT
requires less storage space and is faster to calculate because it
uses only real additions and subtractions, while the FFT requires
complex values. The FWHT is able to represent signals with sharp discontinuities
more accurately using fewer coefficients than the FFT. Both the FWHT
and the inverse FWHT (`ifwht`

)
are symmetric and thus, use identical calculation processes. The FWHT
and IFWHT for a signal *x*(*t*) of
length *N* are defined as:

$$\begin{array}{l}{y}_{n}=\frac{1}{N}{\displaystyle \sum _{i=0}^{N-1}{x}_{i}}\mathrm{WAL}(n,i),\\ {x}_{i}={\displaystyle \sum _{i=0}^{N-1}{y}_{n}\mathrm{WAL}(n,i)},\end{array}$$

where *i* = 0,1, …, *N* – 1 and WAL(*n*,*i*) are
Walsh functions. Similar to the Cooley-Tukey algorithm for the FFT,
the *N* elements are decomposed into two sets of *N*/2
elements, which are then combined using a butterfly structure to form
the FWHT. For images, where the input is typically a 2-D signal, the
FWHT coefficients are calculated by first evaluating across the rows
and then evaluating down the columns.

For the following simple signal, the resulting FWHT shows that `x`

was
created using Walsh functions with sequency values of 0, 1, 3, and
6, which are the nonzero indices of the transformed `x`

.
The inverse FWHT recreates the original signal.

x = [4 2 2 0 0 2 -2 0] y = fwht(x)

x = 4 2 2 0 0 2 -2 0 y = 1 1 0 1 0 0 1 0

x1 = ifwht(y)

x1 = 4 2 2 0 0 2 -2 0