Fast Walsh-Hadamard Transform

The function implement the sequency(Walsh) ordered fast Walsh-Hadamard transform.

Description

The function implement the 1D sequency(Walsh) ordered fast Walsh-Hadamard transform which can be used in signal processing, pattern recongnition and Genetic alogorithms.
This algorithm uses a Cooley-Tukey type signal flow graph and is implemented in N log2 N additions and subtractions. Data sequence length must be an integer power of 2.
The inverse transform is the same as the forward transform except for the multiplication factor N. This can be easily achieved by deleting the last line i.e. x=inv(N)*x;
Example:
x=[1 2 1 1];
W=FWHT(x);

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Walsh Transform(1D)

• MATLAB release: MATLAB 6.5 (R13)

[Larry Kenney]

Excellent compact implementation

[Jiang Anyou]

Hello,
      How can know the full detail of the algorithm of Fast Walsh Hadamard transformation?

[fras hafeid]

how to get fwht from wht?

[jeissonjavier rey duque]

 

[Baojun Qi]

Very good!

[sin r]

i'm interested to know more bout the natural ordered hadamard transforms. could u give us more info?

[f f]

 

[Nedunuri krishna]

 

[Laszlo Hars]

The Hadamard transform is useful outside of signal processing, too, so it is unfortunate that this nice little function requires the Signal Processing Toolbox. However, the need is only a three-line function:
function R = bitrevorder(X)
% rearrange vector X to reverse bit order, upto max 2^k size <= length(X)
[f,e] = log2(length(X));
I = dec2bin(0:pow2(0.5,e)-1);
R = X(bin2dec(I(:,e-1:-1:1))+1);

If you save it under the filename bitrevorder.m, FWHT works without the signal processing toolbox. If you change the first few lines of FWHT to
x = bitrevorder(data);
N = length(x);
k1 = N; k2 = 1; k3 = N/2;
for i1=1:log2(N) %Iteration stage …

the input data vector will be truncated to the largest power of two size, not exceeding the length of data, so you need not worry about odd lengths.

[Jaseem Mohamed]

 

[Ranga Dias]

 

[Mayra V]

 

[Sumit Jha007]

The code was good but the file name & function command name has to be same.

[Saifuldeen A-Mohammed]

 

[Stephen Becker]

As of R2008b, Matlab's Signal Processing toolbox has the functions "fwht" and "ifwht" for the Fast Walsh-Hadamard (aka Hadamard) Transform, and you can choose among three different orderings. This builtin code doesn't work on very large vectors though, whereas I know it is possible to operate on these large vectors because a friend gave me some mex code that does just that. I haven't compared with the file posted here.