Index of Fast Fourier Transformation


1. Introduction

The fourier transformation is generally needed to transform a signal from the spacial dimension into the frequency dimension. Using the inverse fourier transformation the converted signal can be restored from frequency dimension.

A very good general description about the mathematics and formula is given at Wikipedia-Fourier Transformation.

This paper will show you how to use the Fast Fourier Fransformation (FFT), witch is a special implementation of the generous Fourier Transformation.


2. How to use FFT

This chapter shows you how to use the FFT of the Zeus-Framework. Further informations about the implementation of the FFT is given in the next chapter "Implementation". Lets start with some really easy transformations. Following examples are using the Butterfly implementation, witch is a very fast and performat way to transform the signals into the frequency space. Not that all examples need an array of length by 2 power to n (2^n).

All the code described below, comes from the FFT example Source code witch is included by the Zeus-Framework. To download please click here.

2.1 Demo application

First we create a simple demo application, witch is able to manage following functions:

  • Produce a signal (for instance a sin(x).
  • Stores the signal to a file
  • Loads a signal from a file
  • Transforms the signal with fft or ifft

2.1.1 Generating a signal

In our main routine we create a signal with 256 entries. Then we pass the signal to a routine to fill it up with some values. In our case we simply but in a sinus based signal.


#define SAMPLE_MAX  256

/**********************************/
/*! Generates a sin(x) signal
*/
/**********************************/
void generateSin(TComplex* axIn, Int iN)
{
  for(Int i = 0; i < iN; i++)
  {
    axIn[i].setReal( sin(10*TConstants::Pi / iN * i) );
  }
}

/**********************************/
/*! Main entry of the application
*/
/**********************************/
int main(int argc, char* argv[])
{
  TAutoPtr<TArgumentParser> ptrParser
    = new TArgumentParser(argc, argv);

  TComplex axComplex[SAMPLE_MAX];
  Int iMax = SAMPLE_MAX;
  if (ptrParser-<hasArgumentWithValue(L"-gen"))
  {
    TString strFunct = ptrParser->getArgumentValue(L"-gen");
    if (strFunct.equals(L"sin"))
    {
      generateSin(axComplex, iMax);
    }
  }
...
}

You can use any signal you want. Try with cosinus, gaussian curve or just set random values.

2.1.2 Transforming the signal

To transform the signal, we simply pass it to the fast fourier transformation object. The signal variable is used as inout parameter. In our example we measure the time passed to transform the signal. This is somehow interesting if you want to implement your own FFT and compare it with the provided classes.


int main(int argc, char* argv[])
{
...
  if (ptrParser->hasArgument(L"-fft"))
  {
    Float fTime = TTime::getTimeStamp();
    TButterflyFFT FFT;
    FFT.fft(axComplex, iMax);
    printf("Time for fft[%d]: %f [secs]\n", 
      iMax, TTime::getTimeStamp() - fTime );
  }


  if (ptrParser->hasArgument(L"-ifft"))
  {
    Float fTime = TTime::getTimeStamp();
    TButterflyFFT FFT;
    FFT.ifft(axComplex, iMax);
    printf("Time for ifft[%d]: %f [secs]\n", 
      iMax, TTime::getTimeStamp() - fTime );
  }

...
}

This returns you the transformed signal eigher in frequency dimension (fft) or in spacial dimension (ifft).

FFT of sin(x)

IFFT of fft(sin(x))

2.1.3 Storing and Loading signals

To store and load signals we use a tab seperated format. This allows us to import the file into tools like spreadsheet from OpenOffice and analyse it.

Following values are stored:

  • Real component
  • Imaginary component
  • Absolute value (only information)
  • Argument value (only information)

3. Implementation

This chapter will show two implementations of the FFT provided by the Zeus-Framework.

3.1 Symetric FFT

The first FFT algorithm we will interduce within the Zeus-Framework is the symetric FFT. This is a very tiny and simple algorthim. It provides two simple methods fft() and ifft() to transform the data.

3.1.1 The algorithm

The algorithm was interduced to me in the image processing class at the University of Fribourg. I modified some to be able to run it in C++.

The implementation has been done in the class TSymetricFFT. This class needs a sample count, to create itself. Using this we precalculate the coefficients of the FFT and store them into an array:


/*static*/ Float TSymetricFFT::m_f2Pi = TConstants::Pi * 2;
/*static*/ Float TSymetricFFT::m_fSqrt2 = sqrt(2);

/*******************************************/
/*! Creates a symetric fourier transformater
*/
/*******************************************/
TSymetricFFT::TSymetricFFT(Int iN)
{
  m_iN = iN;
  m_ppW = new TComplex*[m_iN + 1];
  for (Int i = 0; i <= m_iN; i++)
  {
    m_ppW[i] = new TComplex[m_iN + 1];
    for (int j = 0; i > 0 && j <= m_iN; j++)
    {
      Float fPs = (m_f2Pi/i) * j;
      m_ppW[i][j].setReal( cos(fPs) );
      m_ppW[i][j].setIm( -sin(fPs) );
    }
  }
}

Doing this the FFT object might be used to transform various signals with the same length [iN]. Note that we need a 2 dimensional array of complex numbers.

The transforming for FFT and IFFT can be done in the same routine. Since this is a symetric FFT, we need not to concern about any factors for IFFT. The IFFT simply inverts the argument on line 29.


01 /*******************************************/
02 /*! fast fourier transformation using a 
03     divide and conquer method
04 */
05 /*******************************************/
06 void TSymetricFFT::fft_DivideAndConquer(TComplex* F, 
                                           TComplex* f, 
                                           Int iN, 
                                           Int iFact)
07 {
08   Int iM = iN / 2;
09   if (iM == 1)
10   {
11     F[0] = (f[0] + f[1]) / m_fSqrt2;
12     F[1] = (f[0] - f[1]) / m_fSqrt2;
13   }
14   else
15   {
16     TComplex* g = new TComplex[iM];
17     TComplex* h = new TComplex[iM];
18     TComplex* G = new TComplex[iM];
19     TComplex* H = new TComplex[iM];
20     for (int x = 0; x < iM; x++)
21     {
22       g[x] = f[2*x];
23       h[x] = f[2*x+1];
24     }
25     fft_DivideAndConquer(G, g, iM, iFact);
26     fft_DivideAndConquer(H, h, iM, iFact);
27     for (int u = 0; u < iM; u++)
28     {
29       TComplex xW(m_ppW[iN][u].getAbsValue(), 
                     iFact * m_ppW[iN][u].getArgument(), 
                     true);
30 
31       TComplex xAux = H[u] * xW;
32       F[u]   = (G[u] + xAux) / m_fSqrt2;
33       F[iM+u] = (G[u] - xAux) / m_fSqrt2;
34     }
35 
36     delete [] g;
37     delete [] h;
38     delete [] G;
39     delete [] H;
40 
41   }
42 }

So basically the call of fft() will lead to the call fft_DivideAndConquer(aFrequency, aSpacial, iN, 1) and the ifft() to the call fft_DivideAndConquer(aFrequency, aSpacial, iN, -1).

Its very obvious that this algorithm uses the divide and conquer scheme to solve the problem. The time complexity is somewhat O(nlogn). Since we have to allocate the arrays during the computation, I concider this algorithm as not very afficient for C++. Java for instance does not need the deletion (lines 36 to 39), since the garbage collection will do that later on. Therefore this algorithm can be efficient on those platforms. However we could rewrite the algorithme not using differnt array but operating on one array only. This will lead me to the next algorithm used for FFT in Zeus-Framework, the butterfly.

3.2 Butterfly FFT

The butterfly FFT is a well known algorithm. The Zeus-Framework implements a Radix-4 algorithm within the class TButterflyFFT. Since we have no recursion like the symertic FFT does, and we don't need to allocate memory all the time, we are a lot faster. It provides two simple methods fft() and ifft() to transform the data. One the less I will not explain all the internals here, since there are very good webpages about it, more complete that I could do :-)

Further informations on Butterfly you will find at:
Communication and Multimedia Laboratory
Wikipedia-Butterfly diagram.

I recommend to use this class to process large data.

3.3 2D Transformation

Both classes (TSymetricFFT and TButterflyFFT) implement also the 2D FFT feature. The 2 dimensional transformation is mainly used for images. The procedure how to do that by your own is very simple. First you transform all rows of the 2D array. Then you transform all columns of the result again.

The Zeus-Framework classes contain two methods, fft2D() and ifft2D().


4. Links

Here some links to other webpages contains lots of information about FFT: