1. This forum section is a read-only archive which contains old newsgroup posts. If you wish to post a query, please do so in one of our main forum sections (here). This way you will get a faster, better response from the members on Motherboard Point.

How to make FFT when having small amount of RAM?

Discussion in 'Embedded' started by Gelber, Oct 17, 2006.

  1. Gelber

    Gelber Guest

    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, Oct 17, 2006
    #1
    1. Advertisements

  2. Gelber

    linnix Guest

    Are you doing high-pass or low-pass? Low sampling rates will be
    low-pass anyway.
    Be more specific. Frequency spec, sampling rate, ram size and cycle
    time.
     
    linnix, Oct 17, 2006
    #2
    1. Advertisements

  3. Bandwidth
    Whats the upper and lower limit of the frequency... IE Bandwidth?

    Frequency Capture range
    What sort of accuracy do you require?..... IE you can "bin" each frequency
    segment.

    Do you need applitude and phase Or just amplitude?


    You can start limiting your memory szie when you know the answers to these
    questions.... as the size is a dependant on them.

    Joe
     
    Joe G \(Home\), Oct 17, 2006
    #3
  4. Gelber

    rickman Guest

    The FFT is a shortcut calculation method for doing the DFT on all
    frequency bins of a time sampled input stream. If you don't need all
    frequency bins the optimizations you can do on the FFT are very
    limited. You don't have to worry about FFT "on the fly" since by
    definition, an FFT is done in batches.

    If you only need specific frequency bins, you can perform the DFT on
    each bin separately. This requires N steps, IIRC. An FFT takes N/2 *
    log_2(N). So if you need more than a small part of the frequency
    spectrum, the FFT will be easier anyway.

    Perhaps if you told us more about the overall problem we could help you
    understand if this is the right way to approach the problem.
     
    rickman, Oct 17, 2006
    #4
  5. Gelber

    Bill Davy Guest

    In addition to all the other comments, and if the samples are coming in and
    you have time as they arrive, and the number of bands is small, you could
    set up a digital filter for each frequency band you are interested in. I am
    sure Google would find something for "band pass FIR finite impulse response
    filter"
     
    Bill Davy, Oct 18, 2006
    #5
  6. Gelber

    stevenj Guest

    For N inputs K outputs, applying the DFT formula directly takes O(N K)
    time and O(K) memory (since you do a single pass through the inputs,
    you don't need to store them...you can process each input as it is read
    and then discard it). You can also use Goertzel, which has the same
    complexity but a better constant factor for the time (at the expense of
    some floating-point accuracy). Using this kind of method that doesn't
    require you to store the input is the only way to save memory over an
    FFT.

    An FFT takes O(N log N) time (putting a particular constant factor like
    1/2 in front of this is a fantasy) and O(N) memory. There are things
    called "pruned" FFTs to compute a few (K) outputs, which take O(N log
    K) time and O(N) memory. I've found pruned (1d) FFTs to be beneficial
    in practice only for the case where you want contiguous bins and 1 << K
    << N (see fftw.org/pruned.html). In any case, a pruned FFT does not
    save memory.

    Regards,
    Steven G. Johnson

    PS. Note that the original poster also queried comp.dsp, leading to
    duplicate threads. Sigh.
     
    stevenj, Oct 18, 2006
    #6
  7. Gelber

    Gelber Guest

    Thank you all for your answers. Now I have more informatin about different
    methods.

    I think the zoom-FFT sounds like the most apropriate for my project if it
    manages to run the low pass filter at the sampel rate.

    Or else I must add a RAM memory to the microcontroller to buffer my sampels.

    Thank you all.
     
    Gelber, Oct 19, 2006
    #7
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.