Aufteilungsschritt beim FFT-Verfahren
- Mit der Abkürzung
- kann man für gerades N die Summe in gerade und ungerade
Indizes aufspalten
- Für halb so viele Werte ist der Faktor bei der Fouriertransformation
gerade
- also gilt für k = 0, ... N/2 - 1
- mit den Fouriertransformationen Ygn
der Werte x2n mit geradem Index bzw. Yun
der Werte x2n+1 mit ungeradem Index.
- Für k > N/2 - 1 schreiben wir
- Nun ist aber
- also folgt sofort
- Man hat nun als Operationen für die Fouriertransformation
von N Punkten 2 Fouriertransformationen für N/2 Punkte sowie je eine
Multiplikation und Addition pro Index k, zusammen