Re: [boost] Request to contribute boost::FFT

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