DiscreteHadamardTransform
DiscreteHadamardTransform[list]
gives the discrete Hadamard transform of list.
Details and Options
- DiscreteHadamardTransform is also known as the Walsh transform and Walsh–Hadamard transform.
- The discrete Hadamard transform
of a list 
of length 
is by default defined to be 
, where 
, 
is the 
bit in the binary representation of the integer 
, and 
. - DiscreteHadamardTransform returns a list whose length is a power of 2. If the length of the input list is not a power of 2, it is zero padded to a length that is the smallest power of 2 greater than
. - DiscreteHadamardTransform takes a Method option, which specifies the sequency ordering (number of zero crossings in the Hadamard basis sequences) of the transform. Possible settings include:
-
"BitComplement" 
"GrayCode" Gray code reordering of "BitComplement" "Sequency" sequency increases with row and column index (default) - The bit complement ordering is also known as the Sylvester ordering.
- The sequency ordering is also known as the Walsh ordering.
- The Gray code ordering is also known as the dyadic ordering or Paley ordering.
- The forward and inverse Hadamard transforms are identical. »
Examples
open all close allBasic Examples (2)
Discrete Hadamard transform of a list:
DiscreteHadamardTransform[{1, 1, 1, 1, 0, 0, 0, 0}]Inverse discrete Hadamard transform:
DiscreteHadamardTransform[%]Discrete Hadamard transform of a 2D sequence that depicts a white rectangle on a black background:
PadRight[ConstantArray[1, {2, 2}], {4, 4}]//MatrixFormScope (1)
Options (1)
Method (1)
By default, a sequency-ordered Hadamard transform is used:
data = PadRight[ConstantArray[1, {5, 9}], {32, 32}];ListPlot3D[DiscreteHadamardTransform[data, Method -> "Sequency"], PlotRange -> All]Use the bit complement ordering for the Hadamard transform:
ListPlot3D[DiscreteHadamardTransform[data, Method -> "BitComplement"], PlotRange -> All]Use the Gray code ordering for the Hadamard transform:
ListPlot3D[DiscreteHadamardTransform[data, Method -> "GrayCode"], PlotRange -> All]Applications (1)
The two-dimensional Hadamard transform of an image:
t = DiscreteHadamardTransform[ImageData[[image]]];Truncate modes in each axis, effectively compressing by a factor of 
:
truncate[data_, f_] :=
Module[{i, j},
{i, j} = Floor[Dimensions[data] / Sqrt[f]];
PadRight[Take[data, i, j], Dimensions[data], 0.]
];Invert the Hadamard transform:
{Image[DiscreteHadamardTransform[truncate[t, 4]]], Image[DiscreteHadamardTransform[truncate[t, 16]]], Image[DiscreteHadamardTransform[truncate[t, 32]]]}Properties & Relations (3)
The discrete Hadamard transform is its own inverse (an involution):
data = RandomReal[1, 8];Chop[DiscreteHadamardTransform[DiscreteHadamardTransform[data]] - data]DiscreteHadamardTransform automatically pads with zeros to the nearest power of 2:
data = ConstantArray[1, 5];
DiscreteHadamardTransform[data]//NLength[%]DiscreteHadamardTransform[data] == DiscreteHadamardTransform[PadRight[data, 8]]Define a function for generating a bit-reversal permutation:
bitrevPermutation[n_] := IntegerReverse[Range[0, n - 1], 2, BitLength[n - 1]] + 1Define a function for generating a Gray code permutation:
grayPermutation[n_] := With[{r = Range[0, n - 1]}, BitXor[r, BitShiftRight[r]] + 1]Generate random data and take its discrete Hadamard transform for different sequency orderings:
data = RandomReal[1, 8];
hs = DiscreteHadamardTransform[data, Method -> "Sequency"];
hd = DiscreteHadamardTransform[data, Method -> "GrayCode"];
hb = DiscreteHadamardTransform[data, Method -> "BitComplement"];The Hadamard transform with Gray code ordering is equivalent to applying the Gray code permutation to the Hadamard transform with bit-complement sequency ordering:
hd == hb[[bitrevPermutation[8]]]The Hadamard transform with sequency ordering is equivalent to applying the bit-reversal permutation to the Hadamard transform with Gray code ordering:
hs == hd[[grayPermutation[8]]]The Hadamard transform with sequency ordering is equivalent to successively applying the bit-reversal permutation and Gray code permutation to the Hadamard transform with bit-complement sequency ordering:
hs == hb[[PermutationProduct[grayPermutation[8], bitrevPermutation[8]]]]Neat Examples (1)
Related Links
NKS|OnlineText
Wolfram Research (2012), DiscreteHadamardTransform, Wolfram Language function, https://reference.wolfram.com/language/ref/DiscreteHadamardTransform.html (updated 2024).
CMS
Wolfram Language. 2012. "DiscreteHadamardTransform." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2024. https://reference.wolfram.com/language/ref/DiscreteHadamardTransform.html.
APA
Wolfram Language. (2012). DiscreteHadamardTransform. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/DiscreteHadamardTransform.html