Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Beispiel: Schnelle Fourier-Transformation

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Als Beispiel wird die diskrete Fourier-Transformation des Vektors

\begin{displaymath} c =\left( \begin{array}{c} 3 \\ -2 \\ 0 \\ 1\\ \end{array}\right) \end{displaymath}

berechnet.

Beim Start des Hauptprogramms wird zuerst rekursiv $ g = \operatorname{FFT}(3,0)$ und $ h = \operatorname{FFT}(-2,1)$ aufgerufen. Für die erste Rekursion ergibt sich dabei

$\displaystyle g$ $\displaystyle = 3$    
$\displaystyle h$ $\displaystyle = 0$    
$\displaystyle w_2$ $\displaystyle = \exp(2\pi\mathrm{i}/2) =-1\,,\, p=(1)$    
$\displaystyle f$ $\displaystyle = (3+1\cdot 0,3-1\cdot 0)^{\operatorname t}=(3,3)^{\operatorname t}$    

und für die zweite


$\displaystyle g$ $\displaystyle =-2$    
$\displaystyle h$ $\displaystyle =1$    
$\displaystyle w_2$ $\displaystyle = \exp(2\pi\mathrm{i}/2) =-1\,,\, p=(1)$    
$\displaystyle f$ $\displaystyle = (-2+1\cdot1,-2-1\cdot1)^{\operatorname t}=(-1,-3)^{\operatorname t}\,.$    

Zurück im Hauptprogramm erhält man damit

$\displaystyle g$ $\displaystyle = (3,3)^{\operatorname t}$    
$\displaystyle h$ $\displaystyle = (-1,-3)^{\operatorname t}$    
$\displaystyle w_4$ $\displaystyle = (\exp(2\pi\mathrm{i}/4)=\mathrm{i}\,,\,p=(1,\mathrm{i})^\mathrm{t}$    
$\displaystyle f$ $\displaystyle = (g+p.*h, g-p.*h) = (3-1\cdot 1,3-\mathrm{i}\cdot 3,3-1\cdot(-1)... ...athrm{i}\cdot (-3))^\mathrm{t} =(2,3-3\mathrm{i},4,3+3\mathrm{i})^\mathrm{t}\,.$    

[Verweise]
  automatisch erstellt am 8. 11. 2013