Re: Very large FFT

AdriaanB wrote:
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?

(snip)


The 'row' FFTs have phases which each take their 't=0' point to be the time of the first time-domain sample in the batch of samples used for that individual FFT.

When combining the FFTs, the phases of each of the successive FFTs have to be adjusted to compensate for the fact that each of their 't=0' points is getting later and later relative to the first time-domain sample in the first row. The extra twiddle factor multiplication does this.

Regards,
John
.