Impulsive autocorrelation sequence

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.