[boost] Re: ffts

From: Benedikt Weber (weber_at_[hidden])
Date: 2002-09-22 06:03:18

"Jason D Schmidt" <jd.schmidt_at_[hidden]> wrote in message
news:20020921.174919.1648.1.jd.schmidt_at_juno.com...

> The prototype is:
> template <const size_t cPoints, class value_type>
> std::valarray<std::complex<value_type> > fft(const
> std::valarray<std::complex<value_type> >& data).
>
> When one performs an n-point fft, the first thing that has to be done is
> to calculate the bit-reversal of the indices (it's the critical part of
> the algorithm).  The bit-reversed indices are different for each
> different fft size.  With my code, a 128-point fft is a different
> function from a 256-point function (because the size is a template
> parameter).  The bit-reversed indices are stored in a static valarray
> object, which is initialized the first time the fft function is called,
> and it's never modified again.
> [...]
> The drawback to this design is that the size of the fft has to be known
> at compile time (because it's a template parameter), and it makes other
> computations (psd, correlation, convolution, etc.) that depend on the fft
> very cumbersome.

I don't think you need the size of the fft to be a template parameter. You
could have a static map<size_t,valarray<size_t> that holds the different
bit-reversed indices.

>Plus, the fft size has to be a power of 2.

Why that?

> Also, the above prototype shows that my fft function can't handle any
> container generically.  I implemented it for only the std::valarray
> because valarray has functionality that makes it much faster than any
> other standard container.  For example, inside the fft function if I want
> to write code like
>
> static const std::valarray<size_t> bit_reversed
> indices(do_bit_reversal<cPoints>());
> const std::valarray<value_type> bit_reversed_data[bit_reversed_indices] =
> data;
>
> there's no container-generic way to do it.  I can't assume that every
> container will have an operator[] that takes a generic container of
> size_t variables.  In fact, valarray is the only standard container with
> that capability (along with std::slice & std::gslice capabilities).
>
> Ok, you might say that I should write my fft implementation as if it's
> operating on an STL container or a range of generic iterators.  However,
> then it wouldn't work with valarray, because valarray doesn't have
> iterators, and it wouldn't have the performance gain that it makes with
> valarray's operator[] and slicing capabilities.

Valarray's operator[](valarray<size_t>)  ist just a convenience which allows
you to write compact code. You could write a loop using operator[](size_t).
Then you could support at least use all containers that provide operator[].

> You can also see from the prototype above that my fft function takes a
> complex argument and returns complex values.  I have a function that
> transforms real data and returns complex values, too.  As long as both
> functions have the same prototype, then my code can transform both real &
> complex data.  I just always make sure to return complex values because,
> in general, the return value of an fft is complex, and you can't overload
> functions by return type.

One commonly used setup in signal analysis is to use an fft that takes an
array of real data and returns an array of complex data of half the size +1.
The inverse transform works the other way around. You can always use
different names for the function if the return type cannot be determined by
the arguments.

Benedikt