FFT

Fast Fourier Transform – rychlá Fourierova transformace. Efektivní algoritmus pro výpočet diskrétní Fourierovy transformace (DFT). Významně snižuje počet operací z řádu \(\mathcal{O}(N^2)\) na \(\mathcal{O}(N \log N)\), což umožňuje praktické využití Fourierovy analýzy ve zpracování signálů, kompresi obrazu, řešení diferenciálních rovnic a dalších oblastech vědy a techniky.

Diskrétní Fourierova transformace (DFT) přepočítává \( N \) vzorků signálu \( x_n \) do frekvenční domény podle vzorce:

\[ X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i k n / N}, \quad k = 0, 1, \dots, N-1. \]

FFT využívá symetrie a redundance výpočtů DFT a typicky se implementuje přes algoritmus Cooley-Tukey, který rozkládá DFT na menší podproblémy a rekurzivně je řeší.

Využití FFT:

• Digitální zpracování signálů: spektrální analýza, filtrace, rozpoznávání řeči.
• Obrazová analýza: JPEG a MPEG komprese využívají diskrétní kosinovou transformaci (DCT), příbuznou FFT.
• Numerické simulace: řešení parciálních diferenciálních rovnic metodou spektrálních metod.
• Vědecké výpočty: rozklad signálů v astronomii, fyzice či biologii.

FFT je jedním z nejdůležitějších algoritmů v moderní informatice a vědě, protože umožňuje efektivní zpracování velkých množství dat v reálném čase.