OptiVec: MF

MF_FFT

MD_FFT

ME_FFT

MF_FFTtoC

MD_FFTtoC

ME_FFTtoC

MCF_FFT

MCD_FFT

MCE_FFT

Function

two-dimensional Fast Fourier Transform

Syntax C/C++	#include <MFstd.h> void MF_FFT( fMatrix Y, fMatrix X, unsigned ht, unsigned len, int dir ); void MCF_FFT( cfMatrix Y, cfMatrix X, unsigned ht, unsigned len, int dir ); void MF_FFTtoC( cfMatrix Y, fMatrix X, unsigned ht, unsigned len );
C++ MatObj	#include <OptiVec.h> void matrix<T>::FFT( const matrix<T>& MX, int dir ); void matrix<complex<T> >::FFT( const matrix<complex<T> >& MX, int dir ); void matrix<complex<T> >::FFTtoC( const matrix<T>& MX );
Pascal/Delphi	uses MFstd; procedure MF_FFT( MY, MX:fMatrix; ht, len:UInt; dir:Integer ); procedure MCF_FFT( MY, MX:cfMatrix; ht, len:UInt; dir:Integer ); procedure MF_FFTtoC( MY:cfMatrix; MX:fMatrix; ht, len:UInt );

Description

The Fourier transform of MX is calculated and stored in MY. The forward transform is obtained by setting dir = 1, the inverse (or backward) transform by setting dir = -1. A Fast Fourier Transform algorithm is used that requires both ht and len to be powers of 2.
Complex version: Both MX and the output MY are complex matrices.
Real-to-complex version: The input matrix MX is real. The output matrix MY is complex. As this function can only perform a forward transform, no argument "dir" is needed.
Purely real version: For the forward transform, MX is a real matrix. The output MY is also defined as fMatrix, although it consists of complex numbers. The reason is that, just as in the one-dimensional case, the symmetry properties of two-dimensional FFT allow to store the result in a packed format, fitting into the same memory space as the input matrix. The order of storage in MY is derived from the ordering in the one-dimensional case, with the packing applied first to all rows, then to the columns. The resulting order is indicated in the following table. U means the uncompressed result.

U_0,0.Re	U_0,len/2.Re	U_0,1.Re	U_0,1.Im	···	U_0,len/2-1.Re	U_0,len/2-1.Im
U_ht/2,0.Re	U_ht/2,len/2.Re	U_1,1.Re	U_1,1.Im	···	U_1,len/2-1.Re	U_1,len/2-1.Im
U_1,0.Re	U_1,len/2.Re	U_2,1.Re	U_2,1.Im	···	U_2,len/2-1.Re	U_2,len/2-1.Im
U_1,0.Im	U_1,len/2.Im	U_3,1.Re	U_3,1.Im	···	U_3,len/2-1.Re	U_3,len/2-1.Im
···	···	···	···	···	···	···
U_ht/2-1,0.Re	U_ht/2-1,len/2.Re	···	···	···	···	···
U_ht/2-1,0.Im	U_ht/2-1,len/2.Im	U_ht-1,1.Re	U_ht-1,1.Im	···	U_ht-1,len/2-1.Re	U_ht-1,len/2-1.Im

For inverse real-matrix FFT, the input matrix has to be of this packed-complex format, and you get a real matrix. If you prefer to get the result of forward FFT as a true complex matrix, use MF_FFTtoC.

About special versions with the prefixes VFs_ and VFl_, consult chapter 4.8.

Error handling

If either ht or len is not a power of 2, VF_FFT (on which MF_FFT is based) complains "Size must be an integer power of 2" and the program is aborted.