0
$\begingroup$

I am looking for a proof that a finite length sequence can only have an impulsive autocorrelation sequence if the sequence is a single impulse itself, ie.:

assume $s[n]$ is nonzero for $n=0,1,2,3$ only and compute $$r_s[k]=\sum_{n=0}^{3-|k|}s[n]s[n+|k|]$$ for $k=0,1,2,3$.

What are all the solutions for $s[n]$ that make $r_s[k]=1$ for $k=0$ and $r_s[k]=0$ otherwise?

$\endgroup$
  • 1
    $\begingroup$ Hi: you're not going to be able to prove that $s[0] = 1$ unless you normalize what you've defined there because, in statistics, what you've defined there is referred to as the autocovariance. There are some relevant links that discuss difference between autocorrelation and autocovariance. It's quite confusing because DSP seems to sometimes differently than statistics defines it. I'm still not clear on the definitions in DSP and I don't want to go into this here but you can go to my user name and look at relevant discussions there. It might help you to some extent. $\endgroup$ – mark leeds Oct 27 at 20:01
  • 2
    $\begingroup$ I don't see why this should be closed as off-topic. $\endgroup$ – Matt L. Oct 27 at 20:30
  • $\begingroup$ @MattL. Because it reads like a homework problem... but isn't! $\endgroup$ – Peter K. Oct 27 at 21:37
2
$\begingroup$

Here is a detour over the frequency domain. We'll use index $k$ for frequency and index $n$ for time. Capital letters for Frequency Domain variables

  1. The Fourier Transform (FT) of an impulse is $R(k)=1$
  2. FT of the autocorrelation is the magnitude squared of the FT of the original signal, i.e $R(k) = |S(k)|^2$
  3. Combining 1 and 2 we get $|S(k)| = 1 $,i.e. $S(k)$ must be an allpass filter
  4. An allpass filter has zeros that are inverse of the poles
  5. Any finite length sequence can be viewed as the impulse response of an FIR filter
  6. An FIR filter has all the poles at $z=0$
  7. An FIR allpass filter can therefore have only zeros at $z = \infty$
  8. Zeros at infinity correspond to pure integer delays.
  9. Pure delays have only one non-zero sample

And that's basically it. This says if $s[n]$ is a finite length sequence, the only way to get a unit impulse as auto correlation is to have only one non-zero sample. Any sample will work though, it doesn't have to be at $n=0$. For a length of 3 you get 4 solutions: $[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]$

$\endgroup$
2
$\begingroup$

The autocorrelation function $r_s[k]$ of a sequence $\{s[n]\}$ is just the inner product (dot product) of $\{s[n]\}$ with a shifted version of itself: $$r_s[k] = \sum_n s[n]\cdot s[n+k].$$ Two important properties of finite-energy signals is that $r_s[0] \geq 0$ (indeed $r_s[0]$ equals $0$ only for the zero signal $s[n]=0$ for all $n$) and $|r_s[n]| \leq r_s[0]$.

Now suppose that the sequence is of finite length meaning that there are two finite numbers $n_\min$ and $n_\max$ (with $n_\max > n_\min$) such that

  • $s[n] = 0$ for all $n < n_\min$ and for all $n > n_\max$.
  • $s[n_\min] \neq 0$, $s[n_\max] \neq 0,$

that is, $s$ is a finite length sequence "lasting" from $n=n_\min$ to $n = n_\max$ where the "endpoints" are nonzero (but we make no claim about intermediate elements which may or may not be $0$; we don't really care). Its "length" is thus $n_\max-n_\min+1$. Note that $\{s[n]\}$ is guaranteed to have at least two nonzero elements in it, namely $s[n_\min]$ and $s[n_\max]$. Note also that $r_s[n_\max-n_\min] = s[n_\min]\cdot s[n_\max] \neq 0$ and so $r_s[k]$ cannot be an impulse function; it has at least two nonzero elements $r_s[0]$ and $r_s[n_\max-n_\min]$.

All that remains is to put all these notions together to cobble up a proof of the proposition

The autocorrelation function of a finite-length sequence is an impulse if and only if the sequence itself is an impulse.

The if part is straightforward and is left as an exercise for the OP and interested diligent readers. For the only if part, recall that in order to prove $A \iff B$, it suffices to prove that $A \implies B$ (which is the exercise mentioned in the previous sentence) and also that $A^c \implies B^c$ (which is logically equivalent to $B\implies A$). We have shown above that a non-impulsive sequence such as the $\{s[n]\}$ discussed above (it has at least two nonzero elements) has a non-impulsive autocorrelation function (which we showed above also has at least two nonzero elements) and so we are done.

Note that in contrast to @PeterK's answer, there is no need for decision tree enumeration etc.

$\endgroup$
  • $\begingroup$ Nice, Dilip! Thanks for the contribution. Yes, mine was focusing on the limited version presented, not the general case like yours. $\endgroup$ – Peter K. Oct 29 at 12:21
1
$\begingroup$

Okay, I'll bite: $$ \begin{alignat}{5} r_s[0] =& 1 &\rightarrow &s[0]s[0]+ s[1]s[1] + s[2]s[2] + s[3]s[3] &=& 1\tag{L1}\\ r_s[1] =& 0 &\rightarrow &s[0]s[1] + s[1]s[2] + s[2]s[3] &=& 0\tag{L2}\\ r_s[2] =& 0 &\rightarrow &s[0]s[2] + s[1]s[3] &=& 0\tag{L3}\\ r_s[3] =& 0 &\rightarrow &s[0]s[3] &=& 0 \tag{L4}\\ \end{alignat} $$ The last line means either $s[0] = 0$ or $s[3] = 0$.

Rather than try to write out the logic, I thought a decision tree might be better. See below.

Each node is labeled for the line that causes the decision.

I believe it shows that you can only have an impulse autocorrelation if the sequence itself is just a (possibly delayed) impulse...at least for a sequence of length 4.

Enumeration of decisions.

$\endgroup$
  • 1
    $\begingroup$ that was neat peter. I was el-wrongo for sure. But, what about if the $s[i]$ are not restricted to be 0 or 1. Then, you won't get r(0) = 1. Or does the question imply that they are restricted to be 0 or 1 ? $\endgroup$ – mark leeds Oct 28 at 1:30
  • $\begingroup$ @Hilmar: Thanks. I see how one can get one 1.0 for the autocorrelation using your argument. Note though that, atleast in statistics, if $s[k]$ represents the data, then the expression written down by the OP is the formula for the empirical auto-covariance. $\endgroup$ – mark leeds Oct 28 at 7:19
  • $\begingroup$ Thanks Peter. I had a similar proof to yours but it seems like there should be a more elegant and simpler one. For example. for arbitrary $N$, an enumeration such as a tree enumeration would be cumbersome. Any other ideas? $\endgroup$ – Steven Kay Oct 29 at 2:18
  • $\begingroup$ @StevenKay See Dilip's answer,I think it gets you closer to what you need. $\endgroup$ – Peter K. Oct 29 at 12:21
  • $\begingroup$ Peter, Thanks for the help and also to Dilip! Yes, this is what I needed and also provides insight into the problem. This property is well known but couldn't find a proof. $\endgroup$ – Steven Kay Oct 30 at 12:21

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.