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

Auto Correlation Function Octave In my version, the graph is at the beginning and the end.

Auto Correlation Function Java 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 ?


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);
    Complex[] c1 = f1.getOutputData();

    // FFT x2
    FFT f2 = new FFT(x2, blockSize, 44100);
    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);
    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).


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.

Auto Correlation in Java flipped

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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – jojeck
    Commented May 13, 2014 at 15:21
  • $\begingroup$ I added some code in my originally post. $\endgroup$
    – christopo
    Commented May 13, 2014 at 15:30
  • $\begingroup$ I added another picture with the flipped output array. $\endgroup$
    – christopo
    Commented May 13, 2014 at 15:56
  • $\begingroup$ 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. $\endgroup$
    – jojeck
    Commented May 13, 2014 at 16:01
  • $\begingroup$ I believe that error might be in your class FFT - presume that's not the original one coming from apache-commons-math3. $\endgroup$
    – jojeck
    Commented May 13, 2014 at 18:40

2 Answers 2


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.

  • $\begingroup$ Sorry, why the downvote? The graphs look centred except for extra whitespace at the end. $\endgroup$
    – Andrew G
    Commented Feb 27, 2015 at 14:53

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.