need help on 2048 point FFT algo

[helios]

Hi

I Need to code a 2048 point FFT in a low power DSP processor...all i have is 2x4k Memory + 1X1k Memory banks. Lets name this as X Y Z memory

:!:X mem and Y mem will be used for the FFT process and the Input and output of each stage can be swapped between these memories...

But For the twiddle factor I must use the Z memory which is only 1K . so there is no space to save the 2048 complex twiddle factors in the memory..:?:

So all i need is some twiddle factor generation Algorithm which can use a 512 point twiddles and generate the 2048 twiddles for each stage.:idea:

Or any algo which can generate 2048 twiddles with very less complexity.:?:


_ Helios
:?:

 

[vadkudr]

You can see

R. Blahut. "Fast algorithms of DSP"

or

CORDIC algorithm

 

[helios]

You can see

R. Blahut. "Fast algorithms of DSP"

or

CORDIC algorithm

I know all these books... M question was.. how to generate twiddle factors with a limited number of i.e 512 twiddle...

_helios

 

[mimomod]

Hi helios,

i'm a novice in FFT. In fact I am taking a DSP course which discusses the FFT algorithms. I haven't implemented the FFT alg. in any processor like you are doing now. But theoretically, when you use FFT alg. then won't use the same number of multiplications as the original DFT formula, i.e. the twiddle factors should be much less than 2048, because this is what FFT alg. does to reduce the computational burden.

Take for example radix-4 FFT algorithm. In this case you just need 4 twiddle factors (numbers) for all FFT butterlies in all stages, plus some additional factors. In this way 1K memory space is more than enough.

best