Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

need help on 2048 point FFT algo

Status
Not open for further replies.

helios

Full Member level 2
Joined
Jun 3, 2005
Messages
147
Helped
22
Reputation
44
Reaction score
10
Trophy points
1,298
Activity points
2,800
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...

:cry: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

Advanced Member level 4
Joined
Jul 12, 2005
Messages
109
Helped
15
Reputation
30
Reaction score
4
Trophy points
1,298
Activity points
2,236
You can see

R. Blahut. "Fast algorithms of DSP"

or

CORDIC algorithm
 

helios

Full Member level 2
Joined
Jun 3, 2005
Messages
147
Helped
22
Reputation
44
Reaction score
10
Trophy points
1,298
Activity points
2,800
vadkudr said:
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

Member level 4
Joined
Jan 25, 2006
Messages
77
Helped
22
Reputation
44
Reaction score
7
Trophy points
1,288
Activity points
2,351
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
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top