Prečo a ako sa FFT rýchlejší ako DFT?

[muralicrl]

Dobrý deň, prečo FFT je rýchlejšia ako DFT? S pozdravom, N. Muralidhara

 

[A.Anand Srinivasan]

je vzhľadom k počtu zúčastnených operácií ....

 

[barry14]

FFT je len matematicky efektívna metóda výpočtu DFT. V podstate sa spolieha na lámanie požadovaných výpočtov do menších, ktoré možno vykonať veľmi rýchlo. Najmenšia jednotka je 2 písm výpočtu. To je dôvod, prečo väčšina FFT implementácie vyžaduje, aby počet bodov analyzovaných sa rovná sile 2 (256, 512, 1024, a i.). Počet výpočtov vykonávať rovnice DFT priamo úmerná N * N, kde N je počet dátových bodov. Algoritmus FFT znižuje toto množstvo úmerné NlogN, kde je log 2 na základňu. Vzhľadom k tomu, LOGN increasea za oveľa nižšiu cenu, než N, ušetrený čas pri použití FFT môže byť značný. Napríklad pre N = 1024, pomer N / LOGN je asi 100. Ak teda 1024 miesto DFT trvá 100 sekúnd, FFT na rovnakých dátach trvať len 1 sekundu.

 

[ddkrishna]

FFT ia rýchly algoritmus pre výpočet DFT. Skôr než výpočet DFT N miesto, kde N je zložené číslo, FFT počíta niekoľko menších DFT a spája výsledok v elegantnej spôsobom. To je spôsobené tým, že N je možné rozložiť ako N = N1 N2 ... Nm

 

[raghuram_msc]

Vážení priateľov, okrem toho, čo bolo povedané vyššie, "pevnosť" z FFT spočíva v efektívnom využití, čo sa nazýva "FFT koša". Sai

 

[avi_e-]

Ahoj priateľovi, v FFT sme ísť na Butterfly Štruktúra a používame tiež trochu opačné poradie, takže je rýchlejší ako DFT, v ktorom ideme pre analytické výpočty. S pozdravom, Avinash.S.