[sdiy] Reverse Walsh?

[Magnus Danielson]

From: Ethan Duni <eduni at ucsd.edu>
Subject: Re: [sdiy] Reverse Walsh?
Date: Thu, 14 Mar 2002 13:44:31 -0800 (PST)

> At 12:03 PM 3/14/2002, you wrote:
> >Is there something like FFT for Walsh that given an
> >input curve, the ouput is a set of Walsh function
> >coefficients?
> 
> -Yes! Its full name is the "Walsh-Hadamard Transform" or WHT for short. the
> analysis equation for the WHT is (hopefully you can read my ascii-math
> notation):
> 
> S[k] = (1/sqrt(N))*sum(s[n]*(-1)^b(k,n)), where the sum is over n from 0 to
> N-1 and the results would be computed for coefficients k=0 through N-1. The
> function b(k,n) controls the "sequency" of the basis function, and so its
> value is the number of transitions basis vector k would have made at time n.
> For more detailed info, look for books on transform coding. Also, the WHT
> is, happily, a "fast" transform, like the FFT.

In my ASCII math notation that would be

            N-1
            ---
        1   \            b(k,n)
S(k) = ---   >  s(n)*(-1)
         -  /
       \/N  ---
            n=0

Indeed, the Walsh-Hadamard is indeed a "fast" transform, it is even
the fastest, since the butterfly form only contains add's and sub's
and no multiplications. Making Walsh-Hadamard butterflies in software
or digital hardware is a good little exercise in order before doing
the real FFT (which is just sligthly more complex).

It is a pitty that they do not perform as well as DCTs on picture and
audio material.

Cheers,
Magnus