VF_FFTVD_FFTVE_FFT
VFb_FFTVDb_FFTVEb_FFT
VF_FFTtoCVD_FFTtoCVE_FFTtoC
VFb_FFTtoCVDb_FFTtoCVEb_FFTtoC
VCF_FFTVCD_FFTVCE_FFT
VCFb_FFTVCDb_FFTVCEb_FFT
FunktionSchnelle Fourier-Transformation (engl. Fast Fourier Transform, FFT)
Syntax C/C++#include <VFstd.h>
void VF_FFT( fVector Y, fVector X, ui size, int dir );
void VCF_FFT( cfVector Y, cfVector X, ui size, int dir );
void VF_FFTtoC( cfVector Y, fVector X, ui size );
void VFb_FFT( fVector Y, fVector X, ui size, int dir; fVector Buf );
void VCFb_FFT( cfVector Y, cfVector X, ui size, int dir; cfVector Buf );
void VFb_FFTtoC( cfVector Y, fVector X, ui size; cfVector Buf );
C++ VecObj#include <OptiVec.h>
void vector<T>::FFT( const vector<T>& X, int dir=1 );
void vector<complex<T>>::FFT( const vector<complex<T>>& X, int dir=1 );
void vector<complex<T>>::FFTtoC( const vector<T>& X );
void vector<T>::b_FFT( const vector<T>& X, int dir, vector<T>& Buf );
void vector<complex<T>>::b_FFT( const vector<complex<T>>& X, int dir, vector<complex<T>>& Buf );
void vector<complex<T>>::b_FFTtoC( const vector<T>& X, vector<complex<T>>& Buf );
Pascal/Delphiuses VFstd;
procedure VF_FFT( Y, X:fVector; size:UIntSize; dir:Integer );
procedure VCF_FFT( Y, X:cfVector; size:UIntSize; dir:Integer );
procedure VF_FFTtoC( Y:cfVector; X:fVector; size:UIntSize );
procedure VFb_FFT( Y, X:fVector; size:UIntSize; dir:Integer; Buf: fVector );
procedure VCFb_FFT( Y, X:cfVector; size:UIntSize; dir:Integer; Buf: fVector );
procedure VFb_FFTtoC( Y:cfVector; X:fVector; size:UIntSize; Buf: cfVector );
CUDA-Funktion C/C++#include <cudaVFstd.h>
int cudaVF_FFT( fVector d_Y, fVector d_X, ui size, int dir );
int cudaVCF_FFT( cfVector d_Y, cfVector d_X, ui size, int dir );
int cudaVF_FFTtoC( cfVector d_Y, fVector d_X, ui size );
void VFcu_FFT( fVector h_Y, fVector h_X, ui size, int dir );
void VCFcu_FFT( cfVector h_Y, cfVector h_X, ui size, int dir );
void VFcu_FFTtoC( cfVector h_Y, fVector h_X, ui size );
CUDA-Funktion Pascal/Delphiuses VFstd, VCFstd;
function cudaVF_FFT( d_Y, d_X:fVector; size:UIntSize; dir:Integer ): IntBool;
function cudaVCF_FFT( d_Y, d_X:cfVector; size:UIntSize; dir:Integer ): IntBool;
function cudaVF_FFTtoC( d_Y:cfVector; d_X:fVector; size:UIntSize ): IntBool;
procedure VFcu_FFT( h_Y, h_X:fVector; size:UIntSize; dir:Integer );
procedure VCFcu_FFT( h_Y, h_X:cfVector; size:UIntSize; dir:Integer );
procedure VFcu_FFTtoC( h_Y:cfVector; h_X:fVector; size:UIntSize );
BeschreibungDie Fourier-Transformation von X wird berechnet und in Y gespeichert. Dabei dürfen X und Y auch identisch sein (also X durch Y überschrieben werden). Die Vorwärts-Transformation erhält man für dir = 1, die Rückwärts-Transformation für dir = -1. Gemäß Konvention enthält die Rückwärts-Transformation eine Skalierung des Ergebnisses mit dem Faktor 1.0/size (wodurch das Ergebnis von einmal Vorwärts- und einmal Rückwärts-Transformation wieder – von Rundungsfehlern abgesehen – den Ursprungsvektor ergibt). Für Situationen, in denen man diese implizite Skalierung umgehen möchte, spezifiziere man dir = -2.
Es wird ein FFT-Algorithmus angewandt, der es erfordert, daß size eine Potenz von 2 sein muss.
Komplexe Version: Sowohl X als auch Y enthalten komplexe Zahlen.
Reell-komplexe Version: Der Eingabevektor X ist reell. Der Ausgabevektor Y ist komplex. Da diese Funktion nur eine Vorwärts-Transformation durchführen kann, wird ein Argument "dir" hier nicht benötigt.
Rein reelle Version: Für die Vorwärts-Transformation ist X ein reeller Vektor. Das Ergebnis Y ist zwar als fVector definiert (also als reeller Vektor), besteht aber aus komplexen Zahlen. Diese sind auf spezielle Weise so gepackt, dass sie in den für einen gleich großen reellen Vektor zur Verfügung stehenden Speicherplatz passen (N=size, U ist die unkomprimierte Fourier-Transformierte von X):
 
Y0Y1Y2Y3  .....  YN-2YN-1
U0.ReUN/2.ReU1.ReU1.Im  .....  UN/2-1.ReUN/2-1.Im

Die Begründung für diese Art des Speicherns ist die folgende: Wenn die size Datenpunkte von X eine reelle Funktion der Zeit darstellen, X = g(t), dann liefert die Vorwärts-Transformation von X eine Funktion U=G(f) in der Frequenz-Domäne. Im Prinzip besteht U aus size+1 komplexen Datenpunkten: size/2 Punkte für positive Frequenzen, noch einmal size/2 Punkte für negative Frequenzen sowie einen Punkt für die Frequenz 0.
Nun gilt für die Fourier-Transformierte einer reellen Funktion die Symmetriebedingung G(-f) = |G(f)|* (der Stern bezeichnet die komplex-konjugierte Form). Daher brauchen die Punkte für negative Frequenzen nicht gespeichert zu werden. Die gesamte Information ist bereits in der positiven Hälfte enthalten. Außerdem sind noch das nullte und das Element mit dem Index size/2 der Transformierten reell, ihre Imaginärteile also 0. Diese beiden nehmen demnach nur je einen reellen Speicherplatz in Anspruch, während die noch verbliebenen size/2-1 komplexen Datenpunkte genau in die übrigen size-2 reellen Speicherplätze passen. So ist sichergestellt, dass X von seiner Transformierten überschrieben werden darf, wenn dies gewünscht wird.

Für die Fourier-Transformation mehrerer gleich-großer Vektoren empfehlen wir, die einzelnen Vektoren in die Zeilen (C/C++) oder Spalten (Pascal/Delphi) einer Matrix zu kopieren und MF_Rows_FFT bzw. MF_Cols_FFT aufzurufen. Je nach Größe der einzelnen Vektoren ist dieses Verfahren ab ca. 4 Vektoren effizienter als die Einzel-Verarbeitung.

Für die reelle Version der Rückwärts-Transformation muss X ein gepackt-komplexer Vektor sein, und man erhält einen reellen Vektor Y.

VFb_FFT, VFb_FFTtoC und VCFb_FFT verwenden den als Argument Buf übergebenen Puffer-Speicher, anstatt ihn selbst zu reservieren. Dadurch sind sie etwas effizienter als die ungepufferten Versionen. Buf muss (mindestens) so groß sein wie X und Y.

Die aus historischen Gründen noch vorhandenen Versionen mit den Präfixen VFp_,  VFs_ und VFl_ werden zukünftig entfallen.

FehlerbehandlungWenn size nicht eine Potenz von 2 ist, wird eine Fehlermeldung "Size must be integer power of 2." ausgegeben und das Programm abgebrochen.
Rückgabewertkeiner
QuerverweisVF_filter,   VF_convolve,   VF_autocorr,   VF_xcorr,   VF_spectrum

VectorLib Inhaltsverzeichnis  OptiVec Home