Jump to content
Electronics-Lab.com Community

Can DFT algorithm be faster than FFT in some case


Zaja

Recommended Posts

Hello, Im student of 2 year of electronics from Poland. Once I was sitting and waiting on a corridor, and my tutor come to me and chat a while. Finally he gave me a task to think through. After few hours of intense thinking I started to bang my head over the wall.
Friend of mine recomended me that forum. Maybe you have some idea?
--------------------------------------------------------------------------------------

Heres the task:
Contemporary CPU consists of many FPU units (Floating Pointing Unit) allowing parallel calculation.
What is more, it is possible to equip a system with many CPU consisting of hundreds of FPU
(current trends is a horizontal scaling instead of vertical scaling

Link to comment
Share on other sites


I was quite suprised that none of you tried to tackle the problem. Propably you dont find it interesting enough.


Looking at the number of needed operations FFT is always faster

FFT
Needs N/2*log2(N/2) multiplications
N*log2 N additions

DFT
N(N-1) multiplications
N*N additions
So in the best way DFT is as fast as FFT.


So the only drawback of FFT lies in the execusion of algoritm itself.
In DFT we may use paralell operations more efficiently, because result of next step does not depend on previous one. Superskalarity and floating point libraries can also be taken into account :)

In FFT it looks like that
support-ex-fft32k-thumb.gif


-----------------------------------------------------------------
Today I had discussion as heated as I could have with the lecturer. And conclusions was that there have to be 2 conditions fulfilled to calculate DFT faster than FFT:

1) all summing operations have to be done on one clock circle (sic!)
2) CATCHE memory have to be multiport and make all operations during one clock cycle. The same memory cell cannot be written and read at the same time, so for one separate operation we need unused, new cell because all operations have to be done during one clock cycle. Theoretically we may create as big memory as we wish, so propability of overlapping is really small.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
  • Create New...