Thread: FFT discussion, anyone?

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    This tut should help.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    my advice is to pick an fft library and use it, and spend your time concentrating on the output, not the algorithm.
    hello, internet!

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    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/

    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. FFT and convolution
    By DavidP in forum General Discussions
    Replies: 7
    Last Post: 07-03-2009, 09:31 AM
  2. Working up to an FFT
    By lordbubonicus in forum C Programming
    Replies: 14
    Last Post: 12-06-2007, 09:59 PM
  3. FFT returning values in wrong order
    By DavidP in forum C# Programming
    Replies: 3
    Last Post: 10-25-2007, 01:15 PM
  4. Terrain Screenshot and Discussion
    By Epo in forum Game Programming
    Replies: 28
    Last Post: 01-20-2006, 08:26 PM
  5. Slogan for a discussion board for Programmers of Bangladesh
    By zahid_isback in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 04-20-2004, 01:38 AM