# Autocorrelation and FFT : avoid zero-padding

Some posts evocate the computation of convolution or cross-correlation using FFT and zero-padding the temporal signal.

I want to compute the autocorrelation of a 3D array using FFTW (2 dimensions are periodic). The file is very large (dimension 256*256*49995, double precision, 25GB).

1 : Is padding necessary for periodic dimensions?

2 : Is it possible to avoid zero-padding to limit memory usage? (fftw++ seems to answer yes)

3 : From the 3d FFT of the non-padded signal, is it possible to compute the cross-correlation using a Discrete Cosine Transform?

Cross-correlation = DCT[ FFT(signal)*Conjugate(FFT(signal)) ]


EDIT - 4 : Is it mandatory to use a mask?

Thanks

• It would be helpful if you give a little more information about what it is you wish to compute. It would appear that you have 49995 images of size 256x256. Each image would have a 2D autocorrelation function which might be an aperiodic autocorrelation if you zero-pad, or a periodic autocorrelation if you don't want to zero-pad. What do you want to do with these 49995 autocorrelation functions of size 256x256 or 512x512? Treat the numbers in each bin as a different time series of length 49995 and calculate the autocorrelation function (periodic or aperiodic) of each series? If not, what? Aug 29, 2014 at 16:14
• @DilipSarwate : From a CFD simulation, I have extracted some planes at a given y position during time. I want to compute the spatio-temporal correlation which is the average of f(x,z,t)*f(x+dx,z+dz,t+dt). The field is periodic in x and z so I need periodic autocorrelation in x and z (256*256). However, it is not periodic in time. Aug 29, 2014 at 16:39