Re: Fast approximate FFT

From: George Bush (george.w.bush_at_whitehouse.com)
Date: 11/28/04 

Date: Sun, 28 Nov 2004 19:23:49 GMT

1. It's probably more useful to you if you ask this question in comp.dsp.

2. There were a couple of articles on approximate FFTs in the IEEE
Transactions on Signal Processing in the last two or three years.

3. There have been several papers in the last fifteen in the IEEE
Transactions on Signal Processing on FFT pruning. The problem for you is the
additional computation involved in pruning the FFT very quickly exceeds the
computation saved. I think the number is around 10% but don't hold me to
that.

In article <coct9p$pvp$2@mercury.leidenuniv.nl>, mathar@mpia.de wrote:
>In article <2f066762.0411261304.46d7200@posting.google.com>,
> spasmous@yahoo.com (spasmous) writes:
>>Is there an FFT algorithm that is faster than Nlog(N) - presumably
>>with a trade off against accuracy?
>>
>>I know there is a fast method for extracting a single frequency (ie. a
>>fast & inaccurate FFT) but I was thinking more like one that gives all
>>frequencies within ~25%, or one that returns good estimates of the
>>large amplitude components but poor estimates of the small ones.
> In the standard radix-2 or radix-4 implementations one could imagine doing
>the "butterfly" sorting first and then ignore after log_2(k) of these
>steps some of the "branches" of the "tree" of values. This would appear
>in the output as not computing a fraction (1/2 or 1/4 or 1/8 etc) of the
>values that the full algorithm would bring, but compute the rest to
>their "full" precision.

Quantcast