1 Frage zu Fouriertransformation

Die 2-D-Diskrete Fouriertransformation (DFT) einer Bild von \(N \times N\) erfordert eine bestimmte Anzahl von Additionen und Multiplikationen. Für ein Bild der Größe \(1024 \times 1024\) (also \(N = 1024\)) kann die Anzahl der Operationen wie folgt berechnet werden: 1. **Direkte Berechnung der 2-D DFT:** - Die direkte Berechnung der 2-D DFT erfordert \(N^2\) 1-D DFTs, und jede 1-D DFT eines Vektors der Länge \(N\) erfordert \(N^2\) komplexe Multiplikationen und \(N(N-1)\) komplexe Additionen. - Für ein \(N \times N\) Bild ergibt dies insgesamt \(N^2 \times N^2 = N^4\) komplexe Multiplikationen und \(N^2 \times N(N-1) = N^3(N-1)\) komplexe Additionen. Für \(N = 1024\): - Komplexe Multiplikationen: \(1024^4 = 1.099.511.627.776\) - Komplexe Additionen: \(1024^3 \times 1023 = 1.073.741.824 \times 1023 = 1.098.135.040.512\) 2. **Berechnung mit der Fast Fourier Transformation (FFT):** - Die FFT reduziert die Anzahl der Operationen erheblich. Die 2-D FFT kann als zwei aufeinanderfolgende 1-D FFTs berechnet werden. - Eine 1-D FFT eines Vektors der Länge \(N\) erfordert etwa \(\frac{N}{2} \log_2 N\) komplexe Multiplikationen und \(N \log_2 N\) komplexe Additionen. - Für ein \(N \times N\) Bild ergibt dies insgesamt \(N \times N \log_2 N\) 1-D FFTs. Für \(N = 1024\): - Komplexe Multiplikationen: \(1024 \times \frac{1024}{2} \log_2 1024 = 1024 \times 512 \times 10 = 5.242.880\) - Komplexe Additionen: \(1024 \times 1024 \log_2 1024 = 1024 \times 1024 \times 10 = 10.485.760\) Zusammengefasst: - **Direkte Berechnung:** - Komplexe Multiplikationen: \(1.099.511.627.776\) - Komplexe Additionen: \(1.098.135.040.512\) - **FFT Berechnung:** - Komplexe Multiplikationen: \(5.242.880\) - Komplexe Additionen: \(10.485.760\) Die FFT ist also wesentlich effizienter als die direkte Berechnung.