# remove zero padding effect crosscorrealation

I am trying to make the cross correlation on the frequency domain and I use the fft function which takes power of 2 input data so I must pad with zero my incoming sample signal and localy generated special code to take fft of this signals.

I compare the first maximum and second maximum peak ratio and then I decide if the code was found or not found. When I use zero padding version this ratio and phase change.

How can I remove zero padding unwanted effect from this correlation?

Thanks for helps.

so let's say the length of your FFT is $N$. let's say that you fill half of the buffer with your signal and fill the other half with zeros.

$$x[n] = 0 \quad \text{ for } \tfrac{N}2 \le n < N$$

the DFT of $x[n]$ is $X[k]$. then magnitude-square and inverse DFT:

$$R_x[n] = \mathcal{iDFT}\bigg\{ \bigg|X[k]\bigg|^2 \bigg\}$$

in the time domain, this comes out as

$$R_x[\ell] = \sum\limits_{n=0}^{\tfrac{N}2 - 1 - \ell} x[n] x[n+\ell]$$

we call $\ell$ the "lag" of the autocorrelation.

now suppose $x[n]$ is periodic with some period $P$ which is much smaller than $\frac{N}2$.

$$x[n+P] = x[n] \quad \text{for } 0 \le n < n+P < \tfrac{N}2$$

with a lag of zero

$$R_x = \sum\limits_{n=0}^{\tfrac{N}2 - 1} (x[n])^2$$

which, if we apply a little bit of statistical sleight-of-hand, we might expect is $\tfrac{N}2$ times the expected power $\overline{x^2}$. in the limit with $P \ll \tfrac{N}2$we can sorta do this with periodic $x[n]$.

\begin{align} R_x &= \sum\limits_{n=0}^{\tfrac{N}2 - 1} (x[n])^2 \\ &\approx \sum\limits_{n=0}^{\tfrac{N}2 - 1} \overline{x^2} \\ &= \frac{N}2 \overline{x^2} \end{align}

now with a lag of $mP$ where $m>0$ is an integer:

\begin{align} R_x[mP] &= \sum\limits_{n=0}^{\tfrac{N}2 - 1 - mP} x[n] x[n+mP] \\ &= \sum\limits_{n=0}^{\tfrac{N}2 - 1 - mP} x[n] x[n] \\ &= \sum\limits_{n=0}^{\tfrac{N}2 - 1 - mP} (x[n])^2 \\ &\approx \sum\limits_{n=0}^{\tfrac{N}2-1 - mP} \overline{x^2} \\ &= \left( \frac{N}2 - mP \right) \overline{x^2} \\ \end{align}

eliminating $\overline{x^2}$ we have

$$R_x[mP] \approx \left( 1 - \frac{2mP}N \right) R_x$$

for $P \ll \tfrac{N}2$.

this suggests an envelope on the autocorrelation of

$$\big| R_x[\ell] \big| \le \left( 1 - \frac{2 |\ell|}N \right) R_x$$

this is for the rectangular window. it can be generalized for other windows. the envelope results from the two windows having less area in common as the lag $\ell$ increases.

• yeah, i know the question is about cross-correlation and my answer is about auto-correlation. – robert bristow-johnson Dec 29 '16 at 6:51