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 Y^g_n der Werte x_2n mit geradem Index bzw. Y^u_n der Werte x_2n+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
  •