spyrit.misc.walsh_hadamard.fwht

spyrit.misc.walsh_hadamard.fwht(x, order=True)

Fast Walsh-Hadamard transform of x

Args:

x (np.ndarray): n-by-1 input signal, where n is a power of two. order (bool, optional): True for sequency (default), False for natural. order (list, optional): permutation indices.

Returns:

np.ndarray: n-by-1 transformed signal

Example 1:

Fast sequency-ordered (i.e., Walsh) Hadamard transform

>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2])
>>> y = wh.fwht(x)
>>> print(y)

Example 2:

Fast Hadamard transform

>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2])
>>> y = wh.fwht(x, False)
>>> print(y)

Example 3:

Permuted fast Hadamard transform

>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2])
>>> ind = [1, 0, 3, 2, 7, 4, 5, 6]
>>> y = wh.fwht(x, ind)
>>> print(y)

Example 4:

Comparison with Walsh-Hadamard transform via matrix-vector product

>>> from spyrit.misc.walsh_hadamard import fwht, walsh_matrix
>>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2])
>>> y1 = fwht(x)
>>> H = walsh_matrix(8)
>>> y2 = H @ x
>>> print(f"Diff = {np.linalg.norm(y1-y2)}")

Example 5:

Comparison with the fast Walsh-Hadamard transform from sympy >>> import spyrit.misc.walsh_hadamard as wh >>> import sympy as sp >>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2]) >>> y1 = wh.fwht(x) >>> y2 = sp.fwht(x) >>> y3 = wh.sequency_perm(np.array(y2)) >>> print(f”Diff = {np.linalg.norm(y1-y3)}”)

Example 6:

Computation times for a signal of length 2**12

>>> import timeit
>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = np.random.rand(2**12,1)
>>> t = timeit.timeit(lambda: wh.fwht(x), number=10)
>>> print(f"Fast Walsh transform, no ind (10x): {t:.3f} seconds")
>>> ind = wh.sequency_perm_ind(len(x))
>>> t = timeit.timeit(lambda: wh.fwht(x,ind), number=10)
>>> print(f"Fast Walsh transform, with ind (10x): {t:.3f} seconds")
>>> t = timeit.timeit(lambda: wh.fwht(x,False), number=10)
>>> print(f"Fast Hadamard transform (10x): {t:.3f} seconds")
>>> import sympy as sp
>>> t = timeit.timeit(lambda: sp.fwht(x), number=10)
>>> print(f"Fast Hadamard transform from sympy (10x): {t:.3f} seconds")