Connect with us

FFT algorithm

Discussion in 'Electronic Design' started by pgw, Mar 24, 2007.

Scroll to continue with content
  1. pgw

    pgw Guest

    I have a question about FFT. I want to implement Cooley-Tukey FFT algorihtm
    but i must know how much RAM i need. I have N samples (24bit) so i need 3xN
    bytes for input and 3xN bytes for output and how much more?
     
  2. Eeyore

    Eeyore Guest

    Have you tried comp.dsp ?

    Graham
     
  3. There are FFT algortihms that allow the computation to occur "in
    place", so a separate output memory is not required unless you are
    then going to process the results further. Google "FFT in place".
     
  4. pgw

    pgw Guest

    Dnia Sat, 24 Mar 2007 17:28:14 +0000, Eeyore napisa³(a):
    I have no idea that such a group exist. Thanx.
     
  5. pgw

    pgw Guest

    Dnia 24 Mar 2007 11:44:36 -0700, Richard Henry napisa³(a):
    FFT algorithm in place will by very helpful. I have almost 8MB input date
    to compute.
     
  6. Robert Baer

    Robert Baer Guest

    3xN for input, 3xN for the infamous but necessary pre-zeroed
    "buffer"; that space can also be used during the transform (there are a
    few in-place versions), and maybe a few dozen or so for intermediate
    calcs (Real, Imaginary, Sine, Cosine; butterfly, etc).
    Else double for 6xN on seperate output.
     
  7. pgw

    pgw Guest

    Dnia Sat, 24 Mar 2007 19:24:49 -0500, Jamie napisa³(a):
    I have 2.5M samples for each 24bit because I need high frequency
    resolution. That what i want to do is a kind of THD meter. I think 2.5M/s
    samples is enough for band 20-100kHz. (maybe I'm wrong)

    But I don't understand what You mean "little chucks"?
    You mean that I should divide all 2.5M samples to smaller parts and make on
    each FFT?
     
  8. Jamie

    Jamie Guest

    now that depends. if you convert that to floats, you would need the
    Sizeof(Float)*N*2; the reason for the 2 is that you need the Real
    and imaginary readings.
    if you are attempting a full integer level FFT which i have done,
    you would need to allocate 4*N*2; 4 bytes for each 32 bit.
    place the 24 bit sample in upper order, and use the lower byte
    for your fraction.
    That is just my opinion of course.
     
  9. Jamie

    Jamie Guest

    You don't want to compute 8Megs in a single pass. you need to
    break it in small little chucks ..
     
  10. Jamie

    Jamie Guest

    for 100Khz, you need 0.2K/s rate.
     
  11. MooseFET

    MooseFET Guest

    By time you get through an FFT, you lose bits. You should usually
    figure on dropping one bit for every power of two in the length. This
    means that at 24bits, your results will be poor. You may want to add
    some LSB space to the values to help prevent this.
     
  12. Robert Baer

    Robert Baer Guest

    Eight megs is nothing; i have done FFTs with millions of digits for
    input sample, to do multi-million digit myltiply, divide, etc.
     
  13. pgw

    pgw Guest

    Dnia 24 Mar 2007 20:06:35 -0700, MooseFET napisa³(a):
    I will make a computation on 32bits and save results on 32bits.
     
  14. pgw

    pgw Guest

    Dnia Sat, 24 Mar 2007 20:49:25 -0500, Jamie napisa³(a):
    Yes, that is true, it prevents aliasing. But i think i need more than 2
    samples/period.
     
  15. joseph2k

    joseph2k Guest

    Jamie, what are you babbling about?

    pgw, what time interval were the samples accumulated over? That will
    determine the resolution of the result.
     
  16. pgw

    pgw Guest

    I think that a number of samples determine the resolution, and a time
    interval (sampling frequency) determine a band.
     
  17. joseph2k

    joseph2k Guest

    Now this one i gan agree mostly with. Proper FFT does require imaginary
    input and does produce imaginary output (sine-cosine). In most real cases
    the imaginary input is all zero, but it does double the input buffer space
    needed to compute the FFT and doubles the output size as well.

    There are various tradeoffs in setting up any particular implementation, you
    can have in place computation (where the input buffer, the output buffer,
    and the computation all take place in a single buffer space), the input
    buffer can be in-order or "decimated" (the ordering mixed up in a
    particular way), the output may be the in-order or decimated. Also the
    coefficients may be read from a table or computed "on-the-fly" (a memory
    space versus time tradeoff, usually with options in between the limit
    cases). Reordering algorithms take only a little time and can easily be
    in-place, and normally take little time.

    If you need to support streaming instead of computing on a single sample you
    may need to double the input buffer space yet again.

    If you are using integer math for the FFT you need to consider how to
    prevent or handle overflow and underflow cases which will occur, this often
    becomes the requirement for additional bits/bytes for the buffer.
     
  18. Jamie

    Jamie Guest

    I'll take your word for it, I have only done up to 500 khz sampling
    in code writing for it.
    The last project was for a vibration monitor system and we kind of
    went over board with the project but we wanted good resolution.
    The transducers were a bit hard to find
     
  19. Jamie

    Jamie Guest

    for streaming, i do sample overlapping.
    i use 25% of the last block as part of the current block etc..
     
  20. Guest

    On Mar 24, 8:22 pm, Jamie
    No, if you have purely real inputs (and hence half of the outputs are
    redundant by conjugate symmetry), there are numerous methods to save a
    factor of two in memory (and time) over the complex transform. These
    methods can also operate in-place.

    So, the answer to the original poster is that he/she needs storage for
    the N samples (overwritten by the N outputs), plus O(1) additional
    memory, at minimum. Of course, various algorithms may require more
    memory in exchange for better speed, accuracy, and/or simplicity.

    Regards,
    Steven G. Johnson
     
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.
Electronics Point Logo
Continue to site
Quote of the day

-