1. If x[n] or y[n] are not power-of-two lengths, make them power-of-two lengths by extending the array(s) to the appropriate length (this is called zero-padding) 2. Choose one of the inputs to time-reverse (for example, given x[l] form x[-l]) 3. Apply FFT to both sequences: a. X[f] = FFT( x[n] ) b. Y[f] = FFT( y[n] ) 4. cross-correlation = IFFT[ (X[f])(Y[f]) ]
Example 3: Cross-correlation pseudocode. Inputs are finite sequences x[n] and y[n].