Thursday, January 22, 2015

Cooley–Tukey FFT algorithm


In this article I will show you, how you can compute the Cooley–Tukey FFT algorithm using the pure JAVA language.

If you are trying to work with some kind of signal analysis, you have probably learned that the FFT is the most widely used technique to extract the frequency spectrum from a signal.

You have of course many options to get some working FFT library. But some of them are licensed, and some of them are not easy to use nor well documented. If you want only to do some simple experiments with the FFT, you can freely use the code which I share On code.google.com. Once you add the FFTCooleyTukey class to your project, you can use it as follows:

    ...
    int SAMPLE_SIZE=1024;
    double[][] sample = new double[2][SAMPLE_SIZE];
    double[][]fftValues = new double[2][SAMPLE_SIZE];
    double[][]ifftValues = new double[2][SAMPLE_SIZE];
    //Read values and zero the imaginary part
    for(int i=0;i<SAMPLE_SIZE;i++){
      sample[0][i]=source[i];
      sample[1][i]=0;
    }
    System.out.println("\nOrig: "+Arrays.toString(sample[0]));
    try {
      fft.fft(sample, fftValues);
      System.out.println("FFT amplitudes: "+Arrays.toString(fftValues[0]));
      //Ask for aprticular frequency components
      System.out.println("200Hz component: "+fftValues[0][(int)Math.round(fft.getIndexOf(200))]);
      System.out.println("500Hz component: "+fftValues[0][(int)Math.round(fft.getIndexOf(500))]);
      fft.ifft(fftValues,ifftValues);
      System.out.println("IFFT amplitudes: "+Arrays.toString(ifftValues[0]));
    } catch (Exception ex) {
      Logger.getLogger(TunerPitchAnalyzer.class.getName()).log(Level.SEVERE, null, ex);
    }
    ...



Usage examples:
You can for example simply find the fftValues[0] for an index which holds the highest value and directly take the signal's base frequency like this:
    nFreq = fft.getFreq(maxIndex);

Or you can build a simple equalizer. Just multiply correspondent values in the fftValues[0] with a gain coefficient. The signal restored with the ifft() will then reflect the changes in the frequency spectrum.

Fill free to download the source on href="https://code.google.com/p/fft-processor/source/browse/trunk/FFTCooleyTukey.java

Hope this will help you.