AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

1D und 2D FFT DFT rekursiv

Ein Thema von alleinherrscher · begonnen am 24. Mai 2013 · letzter Beitrag vom 25. Mai 2013
Antwort Antwort
Benutzerbild von alleinherrscher
alleinherrscher

Registriert seit: 8. Jul 2004
Ort: Aachen
797 Beiträge
 
Delphi XE2 Professional
 
#1

1D und 2D FFT DFT rekursiv

  Alt 24. Mai 2013, 12:13
Im Gegensatz zu den hier im Forum bereits bekannten (diskreten) FFT Algorithmen, präsentiere ich hier einen rekursiven Algorithmus mit der Delphi nativen Unterstützung für komplexe Zahlen. Der Code wird dadurch sehr kurz und übersichtlich. Der Pseudocode kann dem Wikipedia Artikel zum Thema FFT entnommen werden.

Hinweis: Die Anzahl an Komponenten (n) des Eingangsvektors f mit einer Zahl 2^n entsprechen.

uses System.VarCmplx;
Delphi-Quellcode:
type
  TComplexVector = array of Variant;
  TFourierMatrix = array of array of Variant;
Delphi-Quellcode:
function FFT(n:integer;f:TComplexVector):TComplexVector;
var g,u,v,f1,f2:TComplexVector;
    k:integer;
begin
 if n=1 then
    result:=f
 else
   begin
     setlength(f1, n div 2);
     setlength(f2, n div 2);
     for k := 0 to (n div 2)-1 do
       begin
         f1[k]:=f[2*k+1];
         f2[k]:=f[2*k];
       end;

     g:=FFT(n div 2,f2);
     u:=FFT(n div 2,f1);

     setlength(result,n);

     for k := 0 to (n div 2)-1 do
       begin
         v := VarComplexExp(VarComplexCreate(0,-2*Pi*k/n));
         result[k]:=g[k]+u[k]*v;
         result[k+(n div 2)]:= g[k] - u[k]*v;
       end;
   end;
end;
Für die inverse FFT (iFFT) sind lediglich die Minuszeichen in der Exponentialfunktion zu entfernen:

Delphi-Quellcode:
function iFFT(n:integer;f:TComplexVector):TComplexVector;
var g,u,v,f1,f2:TComplexVector;
    k:integer;
begin
 if n=1 then
    result:=f
 else
   begin
     setlength(f1, n div 2);
     setlength(f2, n div 2);
     for k := 0 to (n div 2)-1 do
       begin
         f1[k]:=f[2*k+1];
         f2[k]:=f[2*k];
       end;

     g:=FFT(n div 2,f2);
     u:=FFT(n div 2,f1);

     setlength(result,n);

     for k := 0 to (n div 2)-1 do
       begin
         v := VarComplexExp(VarComplexCreate(0,2*Pi*k/n));
         result[k]:=g[k]+u[k]*v;
         result[k+(n div 2)]:= g[k] - u[k]*v;
       end;
   end;
end;
Beide Funktionen können auch zweidimensional verwendet werden. Hierfür werden erst alle Zeilen einer Matrix und dann alle Spalten Fouriertransformiert:

Hinweis: Auch hier gilt, dass die Dimension der Matrix (w,h) in beiden Komponenten w=2^n bzw h=2^m geschrieben werden kann.

Delphi-Quellcode:
function FFT2D(Input:TFourierMatrix;w,h:integer):TFourierMatrix;
var F,R:TComplexVector;
  j: Integer;
  i: Integer;
begin

setlength(F,w);
setlength(result,w,h);

for j := 0 to h-1 do
   begin
      for i := 0 to w-1 do
          F[i]:=Input[i,j];
      R:=FFT(w,F);
      for i := 0 to w-1 do
        result[i,j]:=R[i];
   end;

setlength(F,h);
for i := 0 to w-1 do
   begin
      for j := 0 to h-1 do
          F[j]:=result[i,j];
      R:=FFT(h,F);
      for j := 0 to h-1 do
        result[i,j]:=R[j];
   end;

end;
iFFT2D folgt analog durch ersetzen der procedure FFT durch iFFT in die procedure FFT2D.
„Software wird schneller langsamer als Hardware schneller wird. “ (Niklaus Wirth, 1995)

Mein Netzwerktool: Lan.FS

Geändert von alleinherrscher (25. Mai 2013 um 16:49 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#2

AW: Vorschlag für CodeLib: 1D und 2D FFT DFT rekursiv

  Alt 24. Mai 2013, 13:29
Kann das sein, dass 2 mal der gleiche Ausdruck VarComplexExp(VarComplexCreate(0,-2*Pi*k/n)) berechnet wird?
Den Faktor bräuchte man doch nur einmal in der Schleife zu berechnen:
Delphi-Quellcode:
for k := 0 to (n div 2)-1 do
begin
   v := VarComplexExp(VarComplexCreate(0,-2*Pi*k/n));
   result[k]:=g[k]+u[k]*v;
   result[k+(n div 2)]:= g[k] - u[k]*v;
end;
fork me on Github
  Mit Zitat antworten Zitat
24. Mai 2013, 20:17
Dieses Thema wurde am "24. May 2013, 20:17 Uhr" von "TBx" aus dem Forum "Algorithmen, Datenstrukturen und Klassendesign" in das Forum "Neuen Beitrag zur Code-Library hinzufügen" verschoben.
Benutzerbild von alleinherrscher
alleinherrscher

Registriert seit: 8. Jul 2004
Ort: Aachen
797 Beiträge
 
Delphi XE2 Professional
 
#4

AW: 1D und 2D FFT DFT rekursiv

  Alt 25. Mai 2013, 16:48
Korrekt Ich werde es oben einbauen.
„Software wird schneller langsamer als Hardware schneller wird. “ (Niklaus Wirth, 1995)

Mein Netzwerktool: Lan.FS
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +2. Es ist jetzt 17:03 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf