0
$\begingroup$

I had an exam one of these days and one of the questions was:

"Knowing that an auto-correlation estimator of a sinal x[n] could be defined by:

$$ R_{xx}[k] = \sum_{n=-\infty}^{+\infty}h[n].x[n+k] , k=0,1,...,n-1 $$ and that the non-periodic convolution: $$ y[n]=x[n]*h[n] = \sum_{k=-\infty}^{+\infty}h[k].x[n-k] $$ show how to calculate the autocorrelation with a convolution operation"


And here is my reasoning:

let's say that: $$ h[n] = x[-n] $$ Therefore, we would have some $y[n]$ for the following convolution: $$ y[n] = x[n]*h[n]=x[n]*x[-n] = \sum_{k=-\infty}^{+\infty}x[k].x[k-n] $$ So it would be nice to invert the signal $y[n]$, finding then a $y[-n]$. However, we will get the same result as before since convolution is a commutative operation: $$ y[-n]=x[-n]*h[-n]=x[-n]*x[n]=x[n]*x[-n]=\sum_{k=-\infty}^{+\infty}x[-k].x[-k+n] $$ Therefore, $R_{xx}[n]=y[n]=y[-n]$, since the convolution sum is symmetric with respect to zero.

Question:

Is my reasoning correct by formal mathematics? The professor gave me a zero in this answer because he says that my assumption $R_{xx}[n]=y[n]=y[-n]$ is wrong because the correct calculation of the autocorrelation has a complex conjugate in one of the terms (so it might not be symmetric with respect to zero). I agree with it even though he has not placed this formalism in the autocorrelation definition. So, following the exam's definitions, is my reasoning correct?

Also, can I say that this will always be true whenever the signal is purely real? And by consequence of the question above: can some of these be demonstrated for complex signals?

$\endgroup$
  • $\begingroup$ i think your reasoning is correct, given the definitions you have. sometimes the autocorrelation is defined as something a little different. then it isn't as easy and your equating convolution with something turned around to autocorrelation is not longer valid. but it's correct in this case, given your definitions. $\endgroup$ – robert bristow-johnson May 7 '14 at 3:09
  • $\begingroup$ Thanks for the comment. But it is possible tu use a convolution to calculate a autocorrelation when we have complex signals? $\endgroup$ – FELIPE_RIBAS May 7 '14 at 3:20
  • $\begingroup$ i think so. can you express the autocorrelation of a complex signal? the autocorrelation of $x[n]$ is the cross-correlation of $x[n]$ with itself. i think, in keeping with the notion of an inner product in a Hilbert space, the cross-correlation will complex-conjugate the latter argument. $\endgroup$ – robert bristow-johnson May 7 '14 at 4:05
  • $\begingroup$ If we will complex-conjugate the latter argument, how can a convolution be used to represent this operation since the convolution is a commutative operation? $\endgroup$ – FELIPE_RIBAS May 7 '14 at 4:17
  • $\begingroup$ so cross-correlation not just the convolution of the two sequences with one time-reversed. it is the convolution of the two sequences with one time-reversed and complex-conjugated. $\endgroup$ – robert bristow-johnson May 7 '14 at 5:17
0
$\begingroup$

There are two things to consider. First, looking only at the exam question you can say that the convolution of $h[n]$ with a sequence $y[n]$ is given by

$$(h*y)[k]=\sum_nh[n]y[k-n]$$

Now define $y[n]=x[-n]$:

$$(h*y)[k]=\sum_nh[n]x[n-k]$$

Consequently, we have

$$\sum_nh[n]x[n+k]=(h*y)[-k],\quad y[n]=x[-n]$$

So you need to flip the signal $x[n]$, compute the convolution, and flip the result. This is true, given the sum in your exam question. No need to worry about complex conjugates because we just used the definition of the autocorrelation sum in the question.

The other issue is the definition of the autocorrelation for complex sequences, and how it can be implemented by convolution. The usual definition is

$$R_{xx}[k]=\sum_nx^{*}[n]x[n+k]$$

The convolution of $x^*[n]$ with a sequence $h[n]$ is

$$(x^**h)[k]=\sum_nx^*[n]h[k-n]$$

For $h[n]=x[-n]$ we have

$$(x^**h)[k]=\sum_nx^*[n]x[n-k]=R_{xx}[-k]$$

So for complex signals, you need to compute the convolution sum of $x^*[n]$ with $x[-n]$, and flip the result to arrive at the autocorrelation.

Note that $R_{xx}[k]=R_{xx}^*[-k]$, so instead of flipping the result, you can also use its complex conjugate.

$\endgroup$
  • $\begingroup$ Nice answer. Just correct me if I'm wrong: we can only say all of these because the summation is always symmetric with respect do zero. Is that correct? I'm asking that because of situations like your third line of your demonstration, in the first equality (sum = conv). The correct notation would be a negative 'n' inside both terms of the summation, no? And thus for every positive 'n' we have a negative one, so we could change its signal. $\endgroup$ – FELIPE_RIBAS May 7 '14 at 19:34
  • $\begingroup$ @FELIPE_RIBAS: I'm not sure if I understand what you mean, but I don't think you're right. Imagine $h[n]=0$ for $n<0$, then we could write all sums from $n=0$ to $n=\infty$, and all equalities would remain valid. $\endgroup$ – Matt L. May 7 '14 at 19:54
  • $\begingroup$ I mean this: $(h*x)[-k]=h[-k]*x[-k]=\sum h[-n]x[-n+k]$ following the convolution definition, no? And because 'n' varies from $-\infty$ to $+\infty$ then we can invert its signal and make $\sum h[-n]x[-n+k]=\sum h[n]x[n+k]$ $\endgroup$ – FELIPE_RIBAS May 7 '14 at 19:57
  • $\begingroup$ @FELIPE_RIBAS: Well, you can also simply compute $(h*x)[k]$ and then flip the result. But in principle the sum always goes from $-\infty$ to $\infty$. $\endgroup$ – Matt L. May 7 '14 at 20:13

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.