How to make FFT when having small amount of RAM?

Let's say I have an embedded system with a small amount of RAM and I want to 
make an FFT of sampled data. But I don't need to make the FFT of the whole 
frequency range. Is there some kind of shortcut one can make to achieve this 
and save RAM?



And let's say that the system isn't fast enough to make the FFT on the fly 
on the samples.

Gelber wrote:
> Let's say I have an embedded system with a small amount of RAM and I want to 
> make an FFT of sampled data. But I don't need to make the FFT of the whole 
> frequency range. Is there some kind of shortcut one can make to achieve this 
> and save RAM?
>  
> 
> And let's say that the system isn't fast enough to make the FFT on the fly 
> on the samples.
> 

1. What exactly are you trying to accomplish? Perhaps there are some 
better ways then the FFT.

2. The FFT of the size N takes 2N of memory at least. If you insist on 
the use of the FFT, the only way to reduce the memory load is to 
decimate your signal.

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

Gelber wrote:
> Let's say I have an embedded system with a small amount of RAM and I want to
> make an FFT of sampled data. But I don't need to make the FFT of the whole
> frequency range. Is there some kind of shortcut one can make to achieve this
> and save RAM?

Just use the DFT (or DTFT) formula directly for the output bins that
you want.  For K outputs and N inputs, this has O(N K) complexity,
which isn't too bad for small K.  Moreover, if you are reading your
inputs on the fly, you don't actually need to store all N inputs at
once; the storage is only O(K).

(There is also Goertzel's algorithm, which has similar complexity but
saves a few operations over the straightforward DTFT formula, at the
price of worse accuracy.  In general these O(N K) formulas are less
accurate than an FFT, unless you do something fancy like Kahan
summation.  But the rms errors aren't too bad, growing as O(N^0.5) for
the DTFT and O(N^1.5) for Goertzel if I remember correctly.)

Steven

Gelber wrote:
> Let's say I have an embedded system with a small amount of RAM and I want to 
> make an FFT of sampled data. But I don't need to make the FFT of the whole 
> frequency range. Is there some kind of shortcut one can make to achieve this 
> and save RAM?
> 
> 
> 
> And let's say that the system isn't fast enough to make the FFT on the fly 
> on the samples.
> 

If the frequencies of interest are continuous, you may want to use what 
is sometimes known as a "zoom fft".  Basically, tune to the center of 
the band of interest, low pass filter, decimate, and then perform the 
FFT at the decimated rate.

By using multirate filtering, you can get very good space and cpu 
efficiency.



-- 
Mark Borgerding
3dB Labs, Inc
Innovate.  Develop.  Deliver.

Yes I concur. ZOOM FFT can analyze a narrow frequency band while still
taking the advantage of fast transform.

Step 1: select your center frequency f0
Step 2: multiply the data by sin(f0) and cos(f0)
Step 3: Apply decimation filter so the data is reduced
Step 4: Apply FFT with small size, say N = 64

On Tue, 17 Oct 2006 15:58:25 +0200, "Gelber" <gelb@nospam.com> wrote:

>Let's say I have an embedded system with a small amount of RAM and I want to 
>make an FFT of sampled data. But I don't need to make the FFT of the whole 
>frequency range. Is there some kind of shortcut one can make to achieve this 
>and save RAM?
>
>
>
>And let's say that the system isn't fast enough to make the FFT on the fly 
>on the samples.

Depending on how many output samples (bins) you want, you could
compute the DFT for just the bins of interest.   You'll need an input
buffer of length N, and an output buffer of only the length needed.

Of course, you could prune an FFT to do the same thing, but I think
the memory saving may not be as big.

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

I have an idea.



Could I do it like this? If I sample 100 samples at say 10 kHz, multiply
them with a window function and then zero pad them with 900 zeros. Then I
make an FFT of the band in interest. I repeat this 10 times and accumulate
the bins (100 bins). Would I get a frequenzy resolution of 10 Hz with this
method?



If not I maybe try the zoom FFT procedure.



I want to be able to make a sound analyzer tool with an ATMEL Atmega16
microcontroller connected with a graphical display presenting the frequency
components.

"Eric Jacobsen" <eric.jacobsen@ieee.org> skrev i meddelandet
news:7e9aj29vtkgaf3ltb5to06minrful1pmdn@4ax.com...
> On Tue, 17 Oct 2006 15:58:25 +0200, "Gelber" <gelb@nospam.com> wrote:
>
> >Let's say I have an embedded system with a small amount of RAM and I want
to
> >make an FFT of sampled data. But I don't need to make the FFT of the
whole
> >frequency range. Is there some kind of shortcut one can make to achieve
this
> >and save RAM?
> >
> >
> >
> >And let's say that the system isn't fast enough to make the FFT on the
fly
> >on the samples.
>
> Depending on how many output samples (bins) you want, you could
> compute the DFT for just the bins of interest.   You'll need an input
> buffer of length N, and an output buffer of only the length needed.
>
> Of course, you could prune an FFT to do the same thing, but I think
> the memory saving may not be as big.
>
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

Gelber wrote:
> Let's say I have an embedded system with a small amount of RAM and I want to
> make an FFT of sampled data. But I don't need to make the FFT of the whole
> frequency range. Is there some kind of shortcut one can make to achieve this
> and save RAM?

Another technique, called the Chirp Z transform, may be of use. The
technique can compute the z transform of N points on the unit circle.
Unlilke the FFT, the N points can be any number and can reside at any
interval in the band.

-V

Gery wrote:
> I have an idea.
>
>
>
> Could I do it like this? If I sample 100 samples at say 10 kHz, multiply
> them with a window function and then zero pad them with 900 zeros. Then I
> make an FFT of the band in interest. I repeat this 10 times and accumulate
> the bins (100 bins). Would I get a frequenzy resolution of 10 Hz with this
> method?
>
>
>
> If not I maybe try the zoom FFT procedure.
>

Nope. The zero padding merely interpolates between the 10 Hz points; it
doesn't reveal any input frequency content between them. Averaging
improves the SNR but does not change the resolution.

FWIW, I was confronted with a very similar problem about a year ago.
After poking around a bit and asking the group I wound up doing a zoom
FFT with a mixer, two stage decimating LPF, and a small complex FFT.

John

Vladimir Vassilevsky wrote:
> 

> 2. The FFT of the size N takes 2N of memory at least. If you insist on 
> the use of the FFT, the only way to reduce the memory load is to 
> decimate your signal.
> 

You can reorder the computations in an FFT so that a size N FFT only 
uses the amount of memory required to hold the complex input or complex 
output (ie. number of samples times the number of bits to represent a 
complex sample).  Look for "in-place FFT algorithm".