Fast multidimensional Walsh-Hadamard transforms

This package provides functions to compute fast Walsh-Hadamard transforms in Julia, for arbitrary dimensions and arbitrary power-of-two transform sizes, with the three standard orderings: natural (Hadamard), dyadic (Paley), and sequency (Walsh) ordering.

It works by calling Julia's interface to the FFTW library, and can often be orders of magnitude faster than the corresponding fwht functions in the Matlab signal-processing toolbox.

Within Julia, just use the package manager to run Pkg.add("Hadamard") to install the files.

After installation, the using Hadamard statement will import the names in the Hadamard module so that you can call the function below.

• The function fwht(X) computes the fast Walsh-Hadamard transform (WHT) of the multidimensional array X (of real or complex numbers), returning its output in sequency order. The inverse transform is ifwht(X).

By default, fwht and ifwht compute the multidimensional WHT, which consists of the ordinary (one-dimensional) WHT performed along each dimension of the input. To perform only the 1d WHT along dimension d, you can can instead use fwht(X, d) and ifwht(X, d) functions. More generally, d can be a tuple or array or dimensions to transform.

The sizes of the transformed dimensions must be powers of two, or an exception is thrown. The non-transformed dimensions are arbitrary. For example, given a 16x20 array X, fwht(X,1) is allowed but fwht(X,2) is not.

These functions compute the WHT normalized similarly to the fwht and ifwht functions in Matlab. Given the Walsh functions, which have values of +1 or -1, fwht multiplies its input by the Walsh functions and divides by n (the length of the input) to obtain the coefficients of each Walsh function in the input. ifwht multiplies its inputs by the Walsh functions and sums them to recover the signal, with no n factor.

• Instead of sequency order, one can also compute the WHT in the natural (Hadamard) ordering with fwht_natural and ifwht_natural, or in the dyadic (Paley) ordering with fwht_dyadic and ifwht_dyadic. These functions take the same arguments as fwht and ifwht and have the same normalizations, respectively. The natural-order transforms also have in-place variants fwht_natural! and ifwht_natural!.

We also provide a a function hadamard(n) which returns a Hadamard matrix of order n, similar to the Matlab function of the same name. The known Hadamard matrices up to size 256 are currently supported (via a lookup table), along with any size that factorizes into products of these known sizes and/or powers of two.

The return value of hadamard(n) is a matrix of Int8 values. If you are planning to do matrix computations with this matrix, you may want to convert to Float64 first via float(hadamard(n)).

For many sizes, the Hadamard matrix is not unique; the hadamard function returns an arbitrary choice. For power-of-two sizes, the choice is equivalent to ifwht_natural(eye(n), 1).

You can pretty-print a Hadamard matrix as a table of + and - (characters indicating the signs of the entries) via Hadamard.printsigns, e.g. Hadamard.printsigns(hadamard(28)) for the 28×28 Hadamard matrix.

You can also obtain a Walsh matrix (sequency-ordered Hadamard matrix) of order n by using the function walsh(n); the order n must be powers of two. This function is related to the Hadamard matrix hadamard(n) by a bit-reversal permutation followed by a Gray-code permutation of the rows.

This package was written by Steven G. Johnson.