Can DFT algorithm be faster than FFT ?

[Zaja]

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 – more CPUs instead of one fast CPU)

Is it possible to create such a system that execute plain DFT algorithm faster then FFT algorithm?

Of course I have sufficient number of FPU. Input data and
hardware are the same for both cases.

DFT has to be evaluated for N values which if done in the obvious way, clearly takes N² multiplications.
FFT takes only N*log2 N operations.

 

[MrAl]

Hi,

What do you mean by "the obvious way"?

 

[Zaja]

Hi,
What do you mean by "the obvious way"?

The way of calculating dictated by definition.
**broken link removed**

Where N is number of samples.

So we create matrix with N-1 rows and N-1 columns.
Row index is "n", column index is "k".

Then we sum all columns in one row.
And then do the same with rest of rows.
easy peasy


Question still remain unanswered
Is it possible to create such a system that execute plain DFT algorithm faster then FFT algorithm?

 

[MrAl]

Hello again,

Ok, then i guess i dont understand your question, perhaps i am missing something here. If we build a car B to go faster than car A in a race, then by definition and simple comparison we've already got the fastest car. Since an FFT is already a fast DFT, if we make a faster DFT it would have to be a FFT, just a better algorithm perhaps. The FFT uses symmetries which almost always simplifies the calculations, and in terms of speed the number of calculations is the whole ball game.
Sorry if i dont understand your question correctly.

In terms of the operations required though if we look at it from a purely theoretical standpoint, for comparison we might perform the limit:
z=limit [x approaches +infiity] of (x*(log(x)/log(2))/x^2)
and we get:
z=0

which shows that x^2 increases faster than x*log2(x). Therefore x*log2(x)<x^2 for x getting very large.

 

[Zaja]

Thanks MrAl for taking a shot, you was only one who dared to try

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
**broken link removed**


-----------------------------------------------------------------
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.