• Author or source: Timo H Tossavainen
• Type: wavelet transform
• Created: 2002-01-17 01:54:52
notes
```IIRC, They're also called walsh-hadamard transforms.
Basically like Fourier, but the basis functions are squarewaves with different sequencies.
I did this for a transform data compression study a while back.
Here's some code to do a walsh hadamard transform on long ints in-place (you need to
divide by n to get transform) the order is bit-reversed at output, IIRC.
The inverse transform is the same as the forward transform (expects bit-reversed input).
i.e. x = 1/n * FWHT(FWHT(x)) (x is a vector)
```
code
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37``` ```void inline wht_bfly (long& a, long& b) { long tmp = a; a += b; b = tmp - b; } // just a integer log2 int inline l2 (long x) { int l2; for (l2 = 0; x > 0; x >>=1) { ++ l2; } return (l2); } //////////////////////////////////////////// // Fast in-place Walsh-Hadamard Transform // //////////////////////////////////////////// void FWHT (std::vector& data) { const int log2 = l2 (data.size()) - 1; for (int i = 0; i < log2; ++i) { for (int j = 0; j < (1 << log2); j += 1 << (i+1)) { for (int k = 0; k < (1<