Maker Pro
Maker Pro

FFT algorithm

P

pgw

Jan 1, 1970
0
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?
 
E

Eeyore

Jan 1, 1970
0
pgw said:
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?

Have you tried comp.dsp ?

Graham
 
R

Richard Henry

Jan 1, 1970
0
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?

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".
 
P

pgw

Jan 1, 1970
0
Dnia Sat, 24 Mar 2007 17:28:14 +0000, Eeyore napisa³(a):
Have you tried comp.dsp ?

I have no idea that such a group exist. Thanx.
 
P

pgw

Jan 1, 1970
0
Dnia 24 Mar 2007 11:44:36 -0700, Richard Henry napisa³(a):
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".

FFT algorithm in place will by very helpful. I have almost 8MB input date
to compute.
 
R

Robert Baer

Jan 1, 1970
0
pgw said:
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?
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.
 
P

pgw

Jan 1, 1970
0
Dnia Sat, 24 Mar 2007 19:24:49 -0500, Jamie napisa³(a):
You don't want to compute 8Megs in a single pass. you need to
break it in small little chucks ..

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?
 
J

Jamie

Jan 1, 1970
0
pgw said:
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?
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.
 
J

Jamie

Jan 1, 1970
0
pgw said:
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.
You don't want to compute 8Megs in a single pass. you need to
break it in small little chucks ..
 
J

Jamie

Jan 1, 1970
0
pgw said:
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?
for 100Khz, you need 0.2K/s rate.
 
M

MooseFET

Jan 1, 1970
0
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)

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.
 
R

Robert Baer

Jan 1, 1970
0
Jamie said:
You don't want to compute 8Megs in a single pass. you need to
break it in small little chucks ..
Eight megs is nothing; i have done FFTs with millions of digits for
input sample, to do multi-million digit myltiply, divide, etc.
 
P

pgw

Jan 1, 1970
0
Dnia 24 Mar 2007 20:06:35 -0700, MooseFET napisa³(a):
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.

I will make a computation on 32bits and save results on 32bits.
 
P

pgw

Jan 1, 1970
0
Dnia Sat, 24 Mar 2007 20:49:25 -0500, Jamie napisa³(a):
for 100Khz, you need 0.2K/s rate.

Yes, that is true, it prevents aliasing. But i think i need more than 2
samples/period.
 
J

joseph2k

Jan 1, 1970
0
Jamie said:
for 100Khz, you need 0.2K/s rate.
Jamie, what are you babbling about?

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

pgw

Jan 1, 1970
0
joseph2k said:
pgw, what time interval were the samples accumulated over?
400ns

That will determine the resolution of the result.

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

joseph2k

Jan 1, 1970
0
Jamie said:
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.

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.
 
J

Jamie

Jan 1, 1970
0
Robert said:
Eight megs is nothing; i have done FFTs with millions of digits for
input sample, to do multi-million digit myltiply, divide, etc.

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
 
J

Jamie

Jan 1, 1970
0
joseph2k said:
Jamie wrote:




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.
for streaming, i do sample overlapping.
i use 25% of the last block as part of the current block etc..
 
On Mar 24, 8:22 pm, Jamie
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.

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
 
Top