Definition 1 (DFT)
Die diskrete Fourier-Transformation (DFT) der Länge N
ist gegeben durch
(1) |
(2) |
In der Definition läßt sich direkt ablesen, daß jeder Ergebniswert von allen Eingangswerten abhängt. Ein naiver iterativer Algorithmus zur Berechnung der DFT hat also eine Zeitkomplexität von .
Definition 2 (2D-DFT)
Die 2D-DFT ist gegeben durch
(3) |
Die 2D-DFT läßt sich auf die 1D-DFT zurückführen
(4) |
(5) |