Questions on a modified FFT!

Hi,

Not long ago a friend of mine who works with digital amplifiers asked me I
knew of a special FFT (less demanding computation wise) that can analyze a
stream containing only ones and zeros. I guess he want's to analyze a
sampled PWM signal and as the amplifiers are working in the Ghz "area" of
sampling frequency, he needs to process heavy data.

Does such a FFT exits?

Thomas S.

it's called the fast hadamard transform -- a google search should give
you lots of results on the subject.

julius

On Sun, 30 Nov 2003, Heureka wrote:

> Hi,
>
> Not long ago a friend of mine who works with digital amplifiers asked me I
> knew of a special FFT (less demanding computation wise) that can analyze a
> stream containing only ones and zeros. I guess he want's to analyze a
> sampled PWM signal and as the amplifiers are working in the Ghz "area" of
> sampling frequency, he needs to process heavy data.
>
> Does such a FFT exits?
>
> Thomas S.
>
>
>
>

-- 
The most rigorous proofs will be shown by vigorous handwaving.
http://www.mit.edu/~kusuma

opinion of author is not necessarily of the institute

Yahooooo! great..thanks for your reply:)
"Julius Kusuma" <kusuma@mit.edu> wrote in message
news:Pine.GSO.4.55L.0311301140290.6629@mass-toolpike.mit.edu...
>
> it's called the fast hadamard transform -- a google search should give
> you lots of results on the subject.
>
> julius
>
> On Sun, 30 Nov 2003, Heureka wrote:
>
> > Hi,
> >
> > Not long ago a friend of mine who works with digital amplifiers asked me
I
> > knew of a special FFT (less demanding computation wise) that can analyze
a
> > stream containing only ones and zeros. I guess he want's to analyze a
> > sampled PWM signal and as the amplifiers are working in the Ghz "area"
of
> > sampling frequency, he needs to process heavy data.
> >
> > Does such a FFT exits?
> >
> > Thomas S.
> >
> >
> >
> >
>
> --
> The most rigorous proofs will be shown by vigorous handwaving.
> http://www.mit.edu/~kusuma
>
> opinion of author is not necessarily of the institute

Julius Kusuma wrote:
> 
> it's called the fast hadamard transform -- a google search should give
> you lots of results on the subject.

What's the domain of that transform?


Bob
-- 

"Things should be described as simply as possible, but no
simpler."

                                             A. Einstein

On Sun, 30 Nov 2003, Bob Cain wrote:
>
> Julius Kusuma wrote:
> >
> > it's called the fast hadamard transform -- a google search should give
> > you lots of results on the subject.
>
> What's the domain of that transform?
>

it's for GF(2), so either {0,1} additive modulo 2 or {-1,+1}
multiplicative.  i suspect that it can be generalized to other (finite)
fields, but hadamard matrices -- which this was named after -- have
entries {-1,+1}.

julius

-- 
The most rigorous proofs will be shown by vigorous handwaving.
http://www.mit.edu/~kusuma

opinion of author is not necessarily of the institute

Julius Kusuma <kusuma@mit.edu> wrote in message news:<Pine.GSO.4.55L.0311301140290.6629@mass-toolpike.mit.edu>...
> it's called the fast hadamard transform -- a google search should give
> you lots of results on the subject.


Ummmmm.....  The fast Hadamard transform does *not* require that
the input be zeroes and ones only: it works just as well with
real-valued or complex-valued inputs.  More to the point: is the
fast Hadamard transform a solution to the OP's problem -- which
presumably is the spectral analysis of PWM signals? What do the bins
mean in this case?

The convolution theorem for Hadamard transforms is different from
the convolution theorem for Fourier transforms.  If g and h are
sequences of length 2^n with Hadamard transforms G and H respectively,
then the inverse Hadamard transform of the term-by-term product of
G and H is a sequence x whose k-th term is

	x_k = sum from i = 0 to 2^n-1 (g_i).(h_{k.XOR.i})

where i and k are represented as n-bit binary numbers and k.XOR.i is
the bit-by-bit XOR of the representations of i and k.  This is sometimes
called a Poisson convolution, and is *not* the same as the usual cyclic
convolution

	sum from i = 0 to 2^n-1 (g_i).(h_{k-i})

with k-i being taken modulo 2^n.  Thus, the FHT **may** not serve
the OP's purpose.

A paper in the October 2003 issue of the Elsevier journal Signal
Processing gives a detailed theory of the spectrum of PWM signals
which might help in avoiding some of the computational issues of
calculating a transform at GHz rates.

On Sun, 30 Nov 2003, Dilip V. Sarwate wrote:

> Ummmmm.....  The fast Hadamard transform does *not* require that
> the input be zeroes and ones only: it works just as well with
> real-valued or complex-valued inputs.  More to the point: is the
> fast Hadamard transform a solution to the OP's problem -- which
> presumably is the spectral analysis of PWM signals? What do the bins
> mean in this case?
>
> The convolution theorem for Hadamard transforms is different from
> the convolution theorem for Fourier transforms.  If g and h are
> sequences of length 2^n with Hadamard transforms G and H respectively,
> then the inverse Hadamard transform of the term-by-term product of
> G and H is a sequence x whose k-th term is
>
> 	x_k = sum from i = 0 to 2^n-1 (g_i).(h_{k.XOR.i})
>
> where i and k are represented as n-bit binary numbers and k.XOR.i is
> the bit-by-bit XOR of the representations of i and k.  This is sometimes
> called a Poisson convolution, and is *not* the same as the usual cyclic
> convolution
>
> 	sum from i = 0 to 2^n-1 (g_i).(h_{k-i})
>
> with k-i being taken modulo 2^n.  Thus, the FHT **may** not serve
> the OP's purpose.
>
> A paper in the October 2003 issue of the Elsevier journal Signal
> Processing gives a detailed theory of the spectrum of PWM signals
> which might help in avoiding some of the computational issues of
> calculating a transform at GHz rates.
>

hi prof. sarwate,

oops, you're right about the convolution properties being different
between the two transforms.  my answer was incorrect....

sorry heureka,
julius

-- 
The most rigorous proofs will be shown by vigorous handwaving.
http://www.mit.edu/~kusuma

opinion of author is not necessarily of the institute