DFT algorithm faster then FFT algorithm?

HTD DFT algorithm faster then FFT algorithm

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.

Try find solution of that equation :

N*log2 N < N²
( time account DFT < time account FFT )

+++

andre_teprom said:

Try find solution of that equation :

N*log2 N < N²
( time account DFT < time account FFT )

Click to expand...

You see...
N*log2N <N²
Is fulfilled for all natural numbers.
---------------------------------------------------------------------------

The way of calculating DFT dictated by definition.
Where N is number of samples.



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

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


The trick here is that: It is difficult to rearange CPU and FPU in such a way that time of calculating plain DFT is faster than FFT algorithm !

Im stuck, so any insides or thoughts are especially welcome

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.

hi Zaja,

If you consider the possibility to implement a dedicated structure ( such as in FPGA ) performing an combitational operation - instead uC sequential - may be your purpose be an excelent idea.

+++