11
$\begingroup$

I know that zero shifting in the autocorrelation function is equal to its energy, yet, I would like to understand why the peak is at zero.

$\endgroup$
10
$\begingroup$

Are you looking for a formal proof or the intuition behind this? In the later case: "Nothing can be more similar to a function than itself". Autocorrelation at lag $\tau$ measures the similarity between a function $f$ and the same function shifted by $\tau$. Note that if $f$ is periodic, $f$ shifted by any integer multiple of $\tau$ and $f$ coincide, so the autocorrelation has a comb shape - with peaks at the integer multiples of the period with the same height as the central peak.

$\endgroup$
  • 2
    $\begingroup$ @JasonR A finite-energy signal (which is what the OP is asking about since he says that the autocorrelation function at zero lag is the energy) cannot be periodic, and so the latter half of this answer is not applicable to the OP's question, but does apply to the periodic autocorrelation function that one defines for periodic signals. In my answer, I have tried to distinguish between these two cases, and also pointed out that autocorrelation functions of periodic signals might have periodic valleys as deep as the periodic peaks. $\endgroup$ – Dilip Sarwate Nov 29 '12 at 15:28
  • $\begingroup$ @Dilip: As always, good points. $\endgroup$ – Jason R Nov 29 '12 at 16:04
  • $\begingroup$ it is not a proof, not even close to a proof. just words which work only because you know the answer. $\endgroup$ – John Smith Feb 5 at 10:36
7
$\begingroup$

The autocorrelation function of an aperiodic discrete-time finite-energy signal is given by $$R_x[n] = \sum_{m=-\infty}^{\infty}x[m]x[m-n]~~~~ \text{or}~~~ R_x[m] = \sum_{m=-\infty}^{\infty}x[m](x[m-n])^*$$ for real signals and complex signals respectively. Restricting ourselves to real signals for ease of exposition, let us consider the summand $x[m]x[m-n]$. For fixed delay $n$ and a given $m$, $x[m]x[m-n]$ typically will have positive or negative value. If it so happens that for a particular delay $n$, $x[m]x[m-n]$ is nonnegative for all $m$, then all the terms in the sum will add up (no cancellation) and so $R_x[n]$ is guaranteed to have positive value. In fact, the sum will be largest if all the peaks in $x[m-n]$ line up with peaks in $x[m]$ and the valleys in $x[m-n]$ line up with the valleys in $x[m]$. For example, if $x$ is an over-sampled sinc function, say, $$x[m] = \begin{cases} \frac{\sin(0.1 \pi m)}{0.1 \pi m}, & m \neq 0,\\ 1, & m = 0\end{cases}$$ with peaks at $m = 0, \pm 25, \pm 45, \ldots$ and valleys at $\pm 15, \pm 35, \pm 55, \ldots$ $x(t)$, then $R_x[n]$ will have maxima at $n = 0, \pm 25, \pm 45, \ldots$ (and by the same token, will have minima at $n = \pm 15, \pm 35, \pm 55, \ldots$ when the peaks line up with valleys). The global maximum of $R_x[n]$ is obviously at delay $n = 0$ when the tallest peak in $x[m]$ and $x[m-n]$ coincide. Indeed, this conclusion applies not just to this sinc signal but to any signal. At lag $n = 0$, we have $$R_x[0] = \sum_{m=-\infty}^\infty (x[m])^2$$ and we are guaranteed that not only are all the peaks and valleys lined up with each other (no matter where these occur in $x[m]$) but also that the highest peaks and deepest valleys are lined up appropriately.

More formally, for pedants like @JohnSmith who demand formal proofs, the Cauchy Inequality says that for complex-valued sequences $u$ and $v$, $$\left|\sum_m u[m](v[m])^*\right|^2 \leq \sum_m |u[m]|^2 \sum_n |v[m]|^2.$$ Restricting ourselves to real-valued sequences only for ease of exposition, a more detailed version says that $$-\sqrt{\sum_m \left(u[m]\right)^2 \sum_m \left(v[m]\right)^2} \leq \sum_m u[m]v[m] \leq \sqrt{\sum_m \left(u[m]\right)^2 \sum_m \left(v[m]\right)^2}$$ where equality holds in the upper (lower) bound if there is a positive (negative) number $\lambda$ such that $u = \lambda v$, (that is, $u[m]=\lambda v[m] ~ \forall m$ where $\lambda > 0$ ($\lambda < 0$)). Recognizing that the sums inside the square roots are the energies $\mathcal E_u$ and $\mathcal E_v$ of the sequences, we can write that $$-\sqrt{\mathcal E_u \mathcal E_v} \leq \sum_m u[m]v[m] \leq \sqrt{\mathcal E_u \mathcal E_v}$$ Setting $u[m] = x[m]$ and $v[m] = x[m-n]$ where $n$ is some integer, we have that $$-\sqrt{\sum_m \left(x[m]\right)^2 \sum_m \left(x[m-n]\right)^2} \leq R_x[n] \leq \sqrt{\sum_m \left(x[m]\right)^2 \sum_m \left(x[m-n]\right)^2}$$ and recognizing that now $\mathcal E_u = \mathcal E_v = \mathcal E_x$, we have that $$-\mathcal E_x \leq R_x[n] \leq \mathcal E_x$$ with equality holding in one of the bounds if $x[m] = \lambda x[m-n]$ for all $m$. Finally, noting that $$\mathcal E_x = \sum_m (x[m])^2 = R_x[0]$$ and that when $n=0$, the sequence $u[m] = x[m]$ is identical to the sequence $v[m] = x[m-n] = x[m-0] = x[m]$ (that is, $\lambda = 1$ is the positive real number such that $u[m] = \lambda v[m]$ for all $m$), we have that $$-R_x[0] \leq R_x[n] \leq R_x[0]$$ showing that $R_x[n]$ has a peak value at $n=0$, all other autocorrelation values are smaller than this peak.


When $x[m]$ is a periodic finite-power signal, the sums given above for $R_x[n]$diverge. In such cases, one uses the periodic autocorrelation function $$R_x[n] = \sum_{m=0}^{N-1} x[m](x[m-n])$$ where $N$ is the period of $x[m]$, that is, $x[m] = x[m-N]$ for all integers $m$. Note that $R_x[n]$ is a periodic function of $n$. Now, while it is true that $R_x[0] \geq |R_x[n]|$ for $1 < n < N$, the maximum value $R_x[0]$ also repeats periodically: $R_x[kN] = R_x[0]$ for all integers $k$. Note also that it is possible that $R_x[n] = -R_x[0]$ for some $n \in \{1, 2, \ldots, N-1\}$, typically at $n = N/2$ if $N$ is even, and so we can have valleys that are as deep as the tallest peaks in the periodic autocorrelation function. The simplest example of such a sequence is when $N=2$ and one period of the sequence is $[1 ~ -1]$ whose periodic autocorrelation is just the periodic sequence $[2 ~ -2]$, that is, alternating peaks and valleys with the autocorrelation $R_x[n]$ having peak value $2$ when $n$ is an even integer (don't forget that $0$ is an even integer!) and having "anti peak" value $-2$ at odd values of $n$. More generally, we have this phenomenon whenever $N$ is even and one period $\vec{x}$ can be decomposed into $[\vec{x^\prime}, -\vec{x^\prime}]$.

$\endgroup$
3
$\begingroup$

using

$$ \left(x[n] - x[n+m] \right)^2 = x^2[n] + x^2[n+m] - 2x[n]x[n+m] $$

one can easily show that

$$\begin{align} R_x[m] & = \sum_{n=-\infty}^{\infty}x[n]x[n+m] \\ & = \sum_{n=-\infty}^{\infty}x^2[n] - \frac{1}{2} \sum_{n=-\infty}^{\infty}\left(x[n] - x[n+m] \right)^2 \\ & = \ R_x[0] \quad \quad - \frac{1}{2} \sum_{n=-\infty}^{\infty}\left(x[n] - x[n+m] \right)^2 \\ \end{align}$$

the first term is simply $R_x[0]$ and the second term is a non-negative number being subtracted from the first. that means $R_x[m]$ cannot exceed $R_x[0]$ for any $m$.

$\endgroup$
  • 1
    $\begingroup$ the only correct answer here. thanks a lot, I had trouble deriving it myself. $\endgroup$ – John Smith Feb 5 at 10:38

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.