FFT discussion, anyone?

I have really been struggling with the concepts involved with the Fourier analysis technique for the past few days. Has anyone got a more laymens explanation to the transformation process? Eventually, I would like to understand the more advanced Fast Fourier Transform, too, but I'm trying to grasp one level at a time! So far, all I get is that the Fourier approach is a specialized wavelet analysis technique which allows one to store time-domain data in more compact structures, as well as revealing more precise information about the wave, it's frequencies, phases, etc.

I also understand that it is based on a complex number algorithm, and those numbers in some way relate to the sin and cosines of the packet.

All I can get from the FFT is that it is hundreds of times more efficient than calculating each number linearly, and is implemented by somehow feeding previous calculations into current calculations, and that it is often described with "butterfly" graphs (which are a complete mystery to me).

My goal, using the different FFT transformations, is to project sound waves that I have captured from my sound card onto graphs on screen.

This tut should help.

my advice is to pick an fft library and use it, and spend your time concentrating on the output, not the algorithm.

Ok, I have made a *little* progress here. Basically I now have a DIF (decimation in frequency) algorithm that is almost complete:

Code:

---

void dif_transform( int samples[], int length )
{
 int i, j, k;
 int even_base, odd_base, even, odd;
 int block_count, points_per_block, butterflies;

 block_count = 1;
 points_per_block = 1 << length;

  for( i = 0; i < length ; ++i )
  {
  butterflies = points_per_block >> 1;
  even_base = 0;

      for( j = 0 ; j < block_count; ++j )
      {
      odd_base = even_base + butterflies;

            for( k = 0; k < butterflies; ++k )
          {
            even =
            samples[ even_base + k ] + samples[ odd_base + k ];

            odd =
            ( samples[ even_base + k ]
            - samples[ odd_base + k ] )
            * twiddle( points_per_block, k );

            samples[ even_base + k ] = even;

            samples[ odd_base + k ] = odd;
          }

      even_base += points_per_block;
      }

  block_count <<= 1;        // twice as many blocks
  points_per_block >>= 1;    // half as many points in each block
  }

 return;
}

---

I don't take any credit for it, it was taken from the example:

Code:

---

PROCEDURE DIF(p,VAR f);
LOCAL Bp,Np,Np',P,b,n,BaseE,BaseO,e,o;
BEGIN {DIF}
{initialise pass parameters}
Bp:=1;    {No. of blocks}
Np:=1<<p; {No. of points in each block}               
{perform p passes}
FOR P:=0 TO (p-1) DO
  BEGIN {pass loop}
  Np':=Np>>1; {No. of butterflies}
  BaseE:=0;  {Reset even base index}
  FOR b:=0 TO (Bp-1) DO
    BEGIN {block loop}
    BaseO:=BaseE+Np'; {calc odd base index}
    FOR n:=0 TO (Np'-1) DO
      BEGIN {butterfly loop}
      e:= f[BaseE+n]+f[BaseO+n];
      o:=(f[BaseE+n]-f[BaseO+n])*T(Np,n);
      f[BaseE+n]:=e;
      f[BaseO+n]:=o;
      END; {butterfly loop}
    BaseE:=BaseE+Np; {start of next block}
    END; {block loop}
  {calc parameters for next pass}
  Bp:=Bp<<1; {twice as many blocks}
  Np:=Np>>1; {half as many points in each block}
  END; {pass loop}
END; {DIF}

---

My primary problem now is with the "twiddle-factor" function. How to implement it? It was mentioned that a table lookup would be most efficient. Does anyone know about this? Also, since the output is bit-reversed, is there an easy way to reorder the bits efficiently?

The purpose of the Fourier transform is to get the frequency-domain representation of a given presentation of a signal in time-domain.

Such analysis of the frequency domain can be used for example for audio compression by removing frequencies and coding less dominant frequencies with less bits than the more dominant frequencies, see for example: psycho accoustic model.

An important mathematical concept in signal analysis is the complex number, which consists of a real part and a imaginary part.

It can be written as

c = a + b j

Here c is the complex number, a is the real part and bj is the imaginary part. Note that electrical engineers use j, mathematicians would use i. In literature you will find both, depending on the kind of literature.

An important aspect of complex numbers is the Euler formula, which states

e^(j*t) = cos (t) + j * sin (t)

This relationship is used a lot in signal analysis, mainly because complex e-powers are far more easier to use in calculations than cosines and sines. They also lead to more compact descriptions of signals. You'll need it for example to perform Fourier transforms.

This is a link to an introduction in complex numbers, it is a mathematical text, the authors use i.

http://www.ping.be/~ping1339/complget.htm

Periodical signals are build of a finite number of sines and cosines, determining which sines and cosines these are is part of the Fourier analysis called Fourier series. Adding the determined sines and cosines results in a signal equal to the periodical signal.

Non-periodical signals are also build of sines and cosines, but the number of sines and cosines here is infinite. The Fourier transform is the tool to find all those sines and cosines.

http://www.rpi.edu/~boucha/fourier.pdf
http://mathstat.carleton.ca/~elenad/.../Fseries_1.pdf
http://www.spd.eee.strath.ac.uk/~int...urier/dft.html

The butterfly-concept is a visualisation of the calculations made when using the FFT.

http://www.spd.eee.strath.ac.uk/~int.../fftbutfy.html

Signals like the voltage of an electric circuit are continue signals, sampled signals are called discrete signals. What you want to do is analyse a discrete signal, the soundcard samples a provided continue signal. So you need to know about digital signal processing.

A very good tutorial is the DSP guide, which can be read online or downloaded in PDF-format.

http://www.dspguide.com/

Quote:

---

All I can get from the FFT is that it is hundreds of times more efficient than calculating each number linearly, and is implemented by somehow feeding previous calculations into current calculations, and that it is often described with "butterfly" graphs (which are a complete mystery to me).

---

The FFT is the fast version of the normal discrete Fourier transform (DFT), it uses a far more efficient calculation scheme.

A good FFT library can be found at www.fftw.org. But there are a lot more FFT implementations in a lot of languages. I suggest you take a look first at the more simple implementations of the FFT, they provide a better understanding of the algorithm.