remove zero padding effect crosscorrealation

Question

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.

Answer 1

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[0] = \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[0] &= \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[0] $$

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[0] $$

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.