FFTs for microcontrollers
Retroactively posted April 8, 2005
At a recent talk on the FFTW library, it was mentioned in passing that alternate algorithms have been developed which play with the operation count to optimize certain things.
The most interesting is a technique due to Winograd which gives you O(n) multiplications and O(n log n) additions, as opposed to the classic treatment which is O(n log n) for both. On a modern processor, this is pretty much useless, since both operations are single-cycle (or better, in the case of multi-operand instructions or the ever-popular multiply-and-accumulate).
On a simple microcontroller, however, where a full multiply instruction might even be a subroutine, let alone a many-cycle operation, it looks like this could be a substantial savings. The AWare guys likely won't care since the AVRs they're using are beefy enough to have a good hardware multiply, but other folks still in PIC purgatory might want to have a look.
The original paper that tends to get referenced is Winograd in "Mathematics of Computation", v32 n1 p175-199, January 1978. The MIT library has it on the shelves and in electronic form too. There may be more recent papers or even FFT library routines that take advantage of it already out there.