FFT Structure optimization

Hi!
I want to ask for your advice about a problem i have. I need to perform an
FFT every specified amount of time but the FFT calculation takes more time
than i can afford. as an optimization step i want to throw half of the
output bins of the FFT but on the FFT structures that i know it'll only
save half of the last stage butterflies calculation. 
is there any other FFT structure that i can use so I'll save more cycles
and I'll be able to work on only half of the spectrum? (1..N samples on
the input  => bins 1..(N/2-1) on the output)

abramovs wrote:
> Hi!
> I want to ask for your advice about a problem i have. I need to perform an
> FFT every specified amount of time but the FFT calculation takes more time
> than i can afford. as an optimization step i want to throw half of the
> output bins of the FFT but on the FFT structures that i know it'll only
> save half of the last stage butterflies calculation. 
> is there any other FFT structure that i can use so I'll save more cycles
> and I'll be able to work on only half of the spectrum? (1..N samples on
> the input  => bins 1..(N/2-1) on the output)

If you need only half the number of bins, compute an FFT using half as 
many samples. That won't cut the time in half, but it will help.

Use a faster processor if you can.

Jerry
-- 
        "The rights of the best of men are secured only as the
        rights of the vilest and most abhorrent are protected."
            - Chief Justice Charles Evans Hughes, 1927
���������������������������������������������������������������������

abramovs wrote:
> I want to ask for your advice about a problem i have. I need to perform an
> FFT every specified amount of time but the FFT calculation takes more time
> than i can afford. as an optimization step i want to throw half of the
> output bins of the FFT but on the FFT structures that i know it'll only
> save half of the last stage butterflies calculation.
> is there any other FFT structure that i can use so I'll save more cycles
> and I'll be able to work on only half of the spectrum? (1..N samples on
> the input  => bins 1..(N/2-1) on the output)

This is an intrinsic problem.  What you are describing is known as a
"pruned" FFT, and in general with N inputs and K outputs the complexity
is O(N log K); i.e. you only save a small factor in the log.  As Jerry
pointed out, you could also cut down your sampling rate if you are
willing to use only half of your input data.

However, it sounds like you are using a textbook radix-2 algorithm, and
this is probably the first thing you should change, assuming you are
using a general-purpose CPU.  It turns out that different FFT
implementations can vary in performance by a factor of 10, and textbook
radix-2 codes are usually at the bottom of the heap (contrary to the
claims made by some textbooks, *cough* Numerical Recipes *cough*).  A
number of FFT codes are freely available that will do much, much
better. (See e.g. our benchmarks at fftw.org/speed).

Regards,
Steven G. Johnson

>abramovs wrote:
>> I want to ask for your advice about a problem i have. I need to perform
an
>> FFT every specified amount of time but the FFT calculation takes more
time
>> than i can afford. as an optimization step i want to throw half of the
>> output bins of the FFT but on the FFT structures that i know it'll
only
>> save half of the last stage butterflies calculation.
>> is there any other FFT structure that i can use so I'll save more
cycles
>> and I'll be able to work on only half of the spectrum? (1..N samples
on
>> the input  => bins 1..(N/2-1) on the output)
>
>This is an intrinsic problem.  What you are describing is known as a
>"pruned" FFT, and in general with N inputs and K outputs the complexity
>is O(N log K); i.e. you only save a small factor in the log.  As Jerry
>pointed out, you could also cut down your sampling rate if you are
>willing to use only half of your input data.
>
>However, it sounds like you are using a textbook radix-2 algorithm, and
>this is probably the first thing you should change, assuming you are
>using a general-purpose CPU.  It turns out that different FFT
>implementations can vary in performance by a factor of 10, and textbook
>radix-2 codes are usually at the bottom of the heap (contrary to the
>claims made by some textbooks, *cough* Numerical Recipes *cough*).  A
>number of FFT codes are freely available that will do much, much
>better. (See e.g. our benchmarks at fftw.org/speed).
>
>Regards,
>Steven G. Johnson
>
>

the problem is that i need the frequency resolution generated by the 2*n
FFT but i don't need all the information of the spectrum (only the first n
bins). cutting doun the FFT order will harm my frequency resolution. the
sampling frequency is fixed and cant be changed.
i'll look in the benchmarks to see if there is more efficiant algorithm.

regards,
benny abramovsky

I think you ought look at FFTW.  I've benchmarked several FFTs and found that 
FFTW was the best algorithm for general purpose processors written in a high 
livel language.  If you're working on DSPs or writing in assembler, there are 
likely to be other choices that will be faster.  

If you have too much data, maybe you should reduce your sample rate and use a 
smaller FFT.  Halfband filter/decimaters might be a good choice if they fit 
your data requirements.

In article <a6udnUg8qqdqDILYnZ2dnUVZ_oOdnZ2d@giganews.com>, "abramovs" 
<bennyab@gmail.com> wrote:
>>abramovs wrote:
>>> I want to ask for your advice about a problem i have. I need to perform
>an
>>> FFT every specified amount of time but the FFT calculation takes more
>time
>>> than i can afford. as an optimization step i want to throw half of the
>>> output bins of the FFT but on the FFT structures that i know it'll
>only
>>> save half of the last stage butterflies calculation.
>>> is there any other FFT structure that i can use so I'll save more
>cycles
>>> and I'll be able to work on only half of the spectrum? (1..N samples
>on
>>> the input  => bins 1..(N/2-1) on the output)
>>
>>This is an intrinsic problem.  What you are describing is known as a
>>"pruned" FFT, and in general with N inputs and K outputs the complexity
>>is O(N log K); i.e. you only save a small factor in the log.  As Jerry
>>pointed out, you could also cut down your sampling rate if you are
>>willing to use only half of your input data.
>>
>>However, it sounds like you are using a textbook radix-2 algorithm, and
>>this is probably the first thing you should change, assuming you are
>>using a general-purpose CPU.  It turns out that different FFT
>>implementations can vary in performance by a factor of 10, and textbook
>>radix-2 codes are usually at the bottom of the heap (contrary to the
>>claims made by some textbooks, *cough* Numerical Recipes *cough*).  A
>>number of FFT codes are freely available that will do much, much
>>better. (See e.g. our benchmarks at fftw.org/speed).
>>
>>Regards,
>>Steven G. Johnson
>>
>>
>
>the problem is that i need the frequency resolution generated by the 2*n
>FFT but i don't need all the information of the spectrum (only the first n
>bins). cutting doun the FFT order will harm my frequency resolution. the
>sampling frequency is fixed and cant be changed.
>i'll look in the benchmarks to see if there is more efficiant algorithm.
>
>regards,
>benny abramovsky
>

abramovs wrote:
> the problem is that i need the frequency resolution generated by the 2*n
> FFT but i don't need all the information of the spectrum (only the first n
> bins). cutting doun the FFT order will harm my frequency resolution. the
> sampling frequency is fixed and cant be changed.

No, don't take the first half of your data.  Take every other data
point.  This halves the sampling rate, and gives you the same frequency
"resolution" (i.e. the same size bins) as the full DFT.  Of course, it
discards half of your data, too, so if you can make the full FFT fast
enough by switching codes that is probably preferable.

Steven

stevenj@alum.mit.edu wrote:
> abramovs wrote:
>> the problem is that i need the frequency resolution generated by the 2*n
>> FFT but i don't need all the information of the spectrum (only the first n
>> bins). cutting doun the FFT order will harm my frequency resolution. the
>> sampling frequency is fixed and cant be changed.
> 
> No, don't take the first half of your data.  Take every other data
> point.  This halves the sampling rate, and gives you the same frequency
> "resolution" (i.e. the same size bins) as the full DFT.  Of course, it
> discards half of your data, too, so if you can make the full FFT fast
> enough by switching codes that is probably preferable.
> 

Keep in mind the basics of sampling theory.

If there is energy above fs/4, you need to filter before decimating by
two, or there will be aliasing

--
Mark Borgerding

Mark Borgerding wrote:
> Keep in mind the basics of sampling theory.
>
> If there is energy above fs/4, you need to filter before decimating by
> two, or there will be aliasing

Sure.  I was assuming that it was just noise above fs/4, in which case
decimating by 2 will decrease the SNR (which is what generally happens
when you use a subset of your data).  If this is true and he can accept
a lower SNR, okay; otherwise he is probably better off doing the full
FFT.  (I doubt that the cost of filtering will be low enough to be
smaller than the difference between a size N and a size N/2 FFT.)

Steven