Boost logo

Boost :

Subject: Re: [boost] Request to contribute boost::FFT
From: Pekka Seppänen (pekka.seppanen_at_[hidden])
Date: 2013-06-03 10:55:28

On 3.6.2013 16:48, Mario Mulansky wrote:
> afaik fft methods need temporary working space. this might already be a strong
> enough argument to encapsulate methods into classes. I dont think "just a few
> functions" is enough here.

Actually, no, you don't need any temporary space for FFT/IFFT. There might be
some implementations that require this, but by all means that doesn't cover
all FFT implementations.

At least with the basic radix-2 implementations there's even no need for
separate input and output buffers; All you need is one (complex) buffer of
size N, where N is your FFT size and everything happens in place.

(If you're doing some contiguous/real life signal processing, obviously you
can't have a buffer of an unlimited size. Then you need to split your input
buffer into blocks and this is where overlap add/save etc. techniques step in;
And these need temporary buffers between blocks. However, the temporary
buffers needed for these are "outside" the FFT/IFFT calculation.)

It's not that I would need a Boost.FFT, but I completely agree with the "few
just won't cut it" ideology. Mostly because there are so many free, tested and
ready implementations around that work on the POD/trivial complex types.
100-200 lines worth of good ole copy-paste and you're ready to go.

However, what the most - if all - lack is the ability to use actually complex
(not complex as in complex number) types that would reveal and enable one to
test how many bits are used or required to implement a FFT of a certain precision.

That might not be a good use case for a rainy day project, but if you're
implementing FFT related things (say, a digital filter; FFT, filter, IFFT) on
a embedded system you don't just start directly writing code for that
particular device. What you do is first verify (protype) your plans with eg.
Matlab, then write a C/C++ version that runs on your desktop and only after
that port the code for the device.

As it could be, that you don't know until you have your PoC running that what
kind of embedded platform you do need for your implementation to be feasible.
Do you need a DSP chip, 16bit or 32bit, floating or fixed point or does a
multi purpose micro controller cut it.

And that's the point where you'd like stick your custom complex number class
in; That tells you at what kind of level (as in how many bits) precision it
operates and what kind of operations it makes. This is a bit what Matlab's
Fixed Point toolbox does (I have used it a bit) but still I find a bit lacky
for real life problems.

I'd say that in the end you'll write your FFT completely by hand as that's
where all the processing time counts. But! You don't want to start by doing
yet another FFT implementation that is off-by-one bug etc. ridden for the
first few days.

As I'm not the one doing the implementation, please do regard this as a
comment coming from the back row - easier said than done, that is. Just liked
to share some thoughts on FFT matters that I've encountered during the years.

-- Pekka

Boost list run by bdawes at, gregod at, cpdaniel at, john at