Re: Very large FFT

Hi again,

I looked at http://www.jjj.de/fxt/fxtbook.pdf on page 329 where the guy
explains a method for a 1D FFT of arbitary large size and started to
implement it with Matlab around an hour before going home. That is then
work to be continued tomorrow.

He seems to follow the general thing that was also mentioned here of
splitting it in a row * column and then doing FFTs row wise, then
transpose and repeat the rows again (in effect on the columns) and then
transposing it again. New question is: Why is the extra twiddle factor
multiplication needed halfway through the algorithm?

Some quick answers to comments from previous posting authors:
-Yes phase will have to be taken into account but I can handle that
easily.
-I am not worried about speed since my application does a 256 - 8k point
FFT(depending on config for that channel) every 6.25ms as part of a larger
signal chain (integrations, averaging band extraction etc.) and the VERY
large FFT is done when the timeslot has some extra free time available.
Obviously the small FFT channels have more free time available. Since the
very large one is done in the background, it is finished when it is
finished. The background FFT is anyway processed in SDRAM which means it
is slow.

R






Rune Allnor wrote:
A 1M FFT is *formally* equivalent to multiplying a 1M x 1M matrix
with
a 1M vector.

That't mathematically true. But it is not the way how FFT works. FFT
uses symmetries in this matrix introduced by the prime factors of it's
size. Only if the size is a prime number, there is no redundency.

The matrix is known, though, so all the coefficients are
computed on the fly, and you don't actually use more than 2M or maybe
3M elements in memory.

That's true anyway.


Marcel




_____________________________________
Do you know a company who employs DSP engineers?
Is it already listed at http://dsprelated.com/employers.php ?
.