Correlation Using FFT / IFFT (Convolution in Frequency Domain) in Java

Question

I try to find about the delay between two audio files using Cross Correlation in Java. I've already done this algorithm so far that i get a idea about how many samples is the delay.

• FFT x1 -> Zero Padding to length: x1.length() + x2.length()
• FFT x2 -> Zero Padding to length: x1.length() + x2.length()
• X3 = FFT{x1} multiply FFT{2}*
• x3 = IFFT{X3}

To validate my results, i use octave. So i can see that my result is in generally correct, but the position of my graph isn't correct.

For testing i use the same files, so that this represent auto correlation function. In octave graph the maximum correlation is in the center of output vector, which seems to be right. -> so the delay is 0, because same files

In my version, the graph is at the beginning and the end.

So if i use two different signals, in octave the maximum correlation moves left/right from center. In my algorithm its going from beginning to middle or end to middle.

So it seems my graph is calculated correct, because the peak moves the amount of samples that is the difference between the files. But the position isnt correct.

It looks like i have to modify my output vector: left half <-> right half

Any ideas whats my problem ?

Edit:

public void execFastCrossCorrelation() throws FFTException
{
    // the used block size is N(x1) + N(x2)
    int blockSize = (x1.length+x2.length-1);

    // create & calc FFT with zero padding & get result

    // FFT x1
    FFT f1 = new FFT(x1, blockSize, 44100);
    f1.execFFT();
    Complex[] c1 = f1.getOutputData();

    // FFT x2
    FFT f2 = new FFT(x2, blockSize, 44100);
    f2.execFFT();
    Complex[] c2 = f2.getOutputData();

    // create output for cross correlation by using fast convolution : c3 = c1 multiply c2*
    Complex[] c3 = new Complex[c1.length];
    for(int i=0; i<c1.length;i++)
    {
        c3[i] = c1[i].multiply(c2[i].conjugate());
    }

    // create & calc IFFT  & get result
    IFFT f3 = new IFFT(c3, c3.length, 44100);
    f3.execIFFT();
    Complex[] corrResult = f3.getOutputData();

// search the maximum corrleation coefficient and his index
    double maxVal = 0;
    int maxIndex = 0;

    for(int i=0; i<corrResult.length;i++)
    {
        if(corrResult[i].abs() > maxVal)
        {
            maxVal = corrResult[i].abs();
            maxIndex = i;
        }
    }

So FFT class is done by using apache-commons-math3. Simply use the input vecotr and create a FFT for the given blockSize (rounded up/down to power of two and zero padded if necessary).

Edit:

So now i tried to flip the output (means left halft -> right half and right half -> left half)

The result matches the version of octave.

If i try this with different files, its also working like in octave, means the maximum is moving from the center to left/right. That means that my idea that the output vector has to be "mirrored" seems to be right. Do you have any idea why?

Answer 1

A real (non-complex) time-domain input will always give a FFT that is duplicated (mirrored)

Some implementations will perform a shift to put the DC (frequency=0Hz) term at index 0. Otherwise you will find the DC term halfway through the array.

Answer 2

FFT by default puts negative frequncies after positive frequencies. It happens due to properties of FFT. You may google Cooley-Tukye algorithm and learn about butterfly operation for more details. Seems, one of your library performs automatic shift of output samples, while the other does not. Check library documentation for this information.