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
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 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
fwht(X,1) is allowed but
These functions compute the WHT normalized similarly to the
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
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
- Instead of sequency order, one can also compute the WHT in the natural
(Hadamard) ordering with
ifwht_natural, or in the dyadic (Paley) ordering with
ifwht_dyadic. These functions take the same arguments as
ifwhtand have the same normalizations, respectively. The natural-order transforms also have in-place variants
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
For many sizes, the Hadamard matrix is not unique; the
function returns an arbitrary choice. For power-of-two sizes, the
choice is equivalent to
You can pretty-print a Hadamard matrix as a table of
(characters indicating the signs of the entries) via
Hadamard.printsigns(hadamard(28)) for the 28×28 Hadamard matrix.
This package was written by Steven G. Johnson.