3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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