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

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?

• Any code maybe? It's hard to debug it without seeing it. One guess is that maybe java is automatically doing some kind of fftshift operation. – jojek May 13 '14 at 15:21
• I added some code in my originally post. – christopo May 13 '14 at 15:30
• I added another picture with the flipped output array. – christopo May 13 '14 at 15:56
• Like I said above, most probably this function is automatically shifting FFT. Can you post the magnitude spectrum of some known signal for both octave and your program? Simple abs of FFT. If it is shifted then you have your answer. – jojek May 13 '14 at 16:01
• I believe that error might be in your class FFT - presume that's not the original one coming from apache-commons-math3. – jojek May 13 '14 at 18:40