2
$\begingroup$

Ok, this is leaving me increasingly frustrated. This builds on a previous question here but I am still not getting the indexing, although I learned from that question all the same.

Case 1: First convolution equation example:

$$ h[k] * h^*[-k] = \sum_{n=-\infty}^{\infty} h[n] \ h^*[n+k] $$

The way I got the right hand side, was:

1) Make the $h$'s have dummy variables, so $h[n]$ and $h^*[-n]$.

2) Flip one of them around, so now I get $h[n]$ and $h^*[n]$

3) Add the delay $k$ into the one that way flipped, so finally I have $\sum_{n=-\infty}^{\infty} h[n] \ h^*[n+k]$.

Great, I have a convolution.

Case 2: Second convolution example: (Unrelated to first)

We have:

$$ \sum_{i=-\infty}^{\infty} h[i-m] \ R_{xx}[i]. $$

Here we want to try and find out what convolution this corresponds to. The way to solve this, (apparently), is to make the assumption that another variable $g[n]=h[-n]$, and call it a day. Then we get:

$$ \sum_{i=-\infty}^{\infty} h[i-m] \ R_{xx}[i] = \sum_{i=-\infty}^{\infty} g[-(i-m)] \ R_{xx}[i] = \sum_{i=-\infty}^{\infty} g[m-i] \ R_{xx}[i] = g[m] * R_{xx}[m] = h[-m] * R_{xx}[m] $$

This works great.

Case3: The problem:

This is my problem. Case 1 showed the steps for how to do a normal convolution. Case 2 showed how the method of substitution works. However, if I try to solve Case 1 using this substitution method, I get the wrong answer, even though it worked on case 2. Why is that?

To wit - where am I going wrong here?

$$ h[k] * h^*[-k] = h[k] * g^*[k] = \sum_{n=-\infty}^{\infty} h[n] \ g^*[k-n] = \sum_{n=-\infty}^{\infty} h[n] \ h^*[-(k-n)] = \sum_{n=-\infty}^{\infty} h[n] \ h^*[n-k] $$

However, this is **clearly* the wrong answer! What am I doing wrong here?

$\endgroup$
  • 1
    $\begingroup$ This question is very closely related to this one of yours on math.SE where the comments and answers have already pointed out that you are using very bad notation such as $h[k]*h^*[-k]$ etc from the getgo which is getting you into trouble. Perhaps trying to understand what you have been told there, instead of asking further questions here with the same bad notations, will go farther in aiding your understanding of how your bad notation only serves to confuse you. $\endgroup$ – Dilip Sarwate Sep 3 '13 at 19:07
  • 1
    $\begingroup$ @DilipSarwate This question is based off of that one, with new information. Case-3 is the new information I learned from that question. Also, I have been trying to understand it, but to no avail. math.stack has said bad notation but I cannot change my books' notation, and do not know where to go off from here. I spend labor day weekend trying to solve this with no avail, so I am not just willy nilly posting. Thanks for your consideration. Please consider removing the downvote given this. $\endgroup$ – TheGrapeBeyond Sep 3 '13 at 19:13
3
$\begingroup$

This question is plagued by bad notation that the OP is unwilling to abandon because, unfortunately, his book uses it. This greatly impedes his understanding of the concepts.

Case 1: First convolution equation example: $$ h[k] * h^*[-k] = \sum_{n=-\infty}^{\infty} h[n] \ h^*[n+k] $$

The way I got the right hand side, was:

1) Make the $h$'s have dummy variables, so $h[n]$ and $h^*[-n]$.

2) Flip one of them around, so now I get $h[n]$ and $h^*[n]$

3) Add the delay $k$ into the one that way flipped, so finally I have $\sum_{n=-\infty}^{\infty} h[n] \ h^*[n+k]$.

${}{}{}{}{}$

No. 3) is not correct. When convolving, you flip one signal and then move it to the right by $k$ which will give you $h^*[n-k]$, not $h^*[n+k]$. Thus you end up with $\sum_n h[n]h^*[n-k]$ as in the leftmost sum in $(2)$ below.

Great, I have a convolution. (emphasis added)

The right side of the last equation is not generally called a convolution; it is called the autocorrelation function of $h$. If $h$ and $g$ are two finite-energy sequences (meaning $\sum_n |g[n]|^2$ and $\sum_n |h[n]|^2$ are finite), then the $k$-th term of their convolution is $$\sum_{n=-\infty}^\infty h[n]g[k-n] = \sum_{n=-\infty}^\infty h[k-n]g[n]. \tag{1}$$ It is not a good idea to use $h[k]\star g[k]$ to denote the convolution in general or its $k$-th term in particular -- far better to write $h\star g$ in general and $(h\star g)[k]$ in particular -- as the OP has already been told repeatedly on math.SE. Be that as it may,

for the case when $g[n] = h^*[-n]$ for all $n$, we can write $(1)$ as $$\sum_{n=-\infty}^\infty h[n]h^*[n-k] = \sum_{n=-\infty}^\infty h[k-n]h^*[-n] = \sum_{m=-\infty}^\infty h[m+k]h^*[m] \tag{2}$$ where the last equality was obtained by replacing $n$ by $-m$. Notice the difference from the OP's result. For complex-valued sequences, there are two different ways of defining the autocorrelation function $R_{hh}[\cdot]$ depending on which sequence we choose to conjugate, but both ways give the same conjugate symmetry property $R_{hh}[-n] = (R_{hh}[n])^*$.

${}{}{}$

Case3: The problem:

This is my problem. Case 1 showed the steps for how to do a normal convolution. (emphasis added) Case 2 showed how the method of substitution works. However, if I try to solve Case 1 using this substitution method, I get the wrong answer, even though it worked on case 2. Why is that?

To wit - where am I going wrong here?

Where you are going wrong is that your analysis of Case 1 is not quite correct as explained above, while your Case 2 is not a convolution at all, and is not an autocorrelation or cross-correlation of complex-valued sequences either, because these require conjugation of one of the terms. So you are really mixing up things and then complaining that the answers are not the same.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, to remove any doubt that my book says all I claim it says, here is what my book says. In the meantime I will study your post. $\endgroup$ – TheGrapeBeyond Sep 4 '13 at 3:17
  • 1
    $\begingroup$ This is from page 100 of Monson's H. Hayes' "Statistical Digital Signal Processing And Modelling", and he is from Georgia Tech. I am not 'unwilling to abandon' the notation, I am just trying to follow the man's book. You say: "as the OP has already been told repeatedly on math.SE, though he will have none of it". Thats not nice. I am trying to learn from the book. There is no need for such wording. $\endgroup$ – TheGrapeBeyond Sep 4 '13 at 3:20
  • 1
    $\begingroup$ Bad notation is bad notation, no matter how authoritative the writer might be or how prestigious the writer or the institution might be, and in this instance, what is written is wrong on the face of it. $\endgroup$ – Dilip Sarwate Sep 4 '13 at 3:47
  • 1
    $\begingroup$ I can appreciate that it is bad notation on an author's part, but please do not ascribe a motive to me as "unwilling to abandon" something. Thank you. $\endgroup$ – TheGrapeBeyond Sep 4 '13 at 4:01
  • $\begingroup$ Back to the problem at hand: This bad notation would then seem to be endemic. Even my classical Oppenheim and Shaffer book uses it. (Page 67, new Edition, 2009). My original question came from notes of Professor Buckley at Villanova U, here. Full PDF here. Everywhere I turn this notation seems to be used in my EE books. I am not defending it. I would just like to learn the proper notation. $\endgroup$ – TheGrapeBeyond Sep 4 '13 at 4:02
2
$\begingroup$

Case 1 is an autocorrelation (in this case of the impulse response of your systems), which your book clearly states. It measures the similarity between two sequences, whereas the convolution measures the overlap of two sequences. A convolution would have a negative delay.

The second case, I'm not sure is a convolution at all. You're trying to convolve the impulse response of a channel with the autocorrelation matrix - but you only give a single index for the matrix. I think you've missed out an implicit sum over one of the indices here. Either way, I'm not sure what it would represent in a statistical signal processing context.

In the third case, when you flip the 'g' function you need the delay should go the other way i.e. g[-k-n], to be consistent with the substitution you've made. This will end up with an autocorrelation. However, as has been noted, this isn't a convolution - but what you've written above is.

Remember that convolutions and correlations are not quite the same thing just with different signs. For instance, blur on an image is a convolution with a blurring operator and the un-blurred image. The correlation of those two sequences will be different.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Tom - thanks for the answer. Let me just clarify what I am after. I know what a convolution and correlation are. What I am specifically trying to ascertain, is -how exactly- we go from "blah convolved with foo" to writing in in summation form. In case one, I apply the rule set from the wiki on convolution, (dummy variable, flip one, add delay, done), and it works. $\endgroup$ – TheGrapeBeyond Sep 4 '13 at 15:43
  • $\begingroup$ In the second case, I am trying to go backwards, from the sum shown, to the statement "blah convolved with foo". This is what I am having problems with. BTW, this is from here, with full document here. (Page 22). If you can elucidate this, possibly with the general rule, I would highly, highly appreciate it. $\endgroup$ – TheGrapeBeyond Sep 4 '13 at 15:44
  • $\begingroup$ Well, 'foo convolved with bar' is the same as case 1 with the sign of the delay reversed. The second one is copied incorrectly - you're missing and extra channel impulse, which you need for the statement to make sense. For case 3, I've explained that you make a sign error - correct that and you get what you wanted (like case 1). Note that this isn't a convolution, it's a correlation (to be consistent with case 1). You're merely confusing signs. $\endgroup$ – Tom Kealy Sep 5 '13 at 8:59
  • $\begingroup$ From reading you're other comments: the convolution is defined the way it is as the product of two functions (one time reversed). If you see something like that, it's a convolution. $\endgroup$ – Tom Kealy Sep 5 '13 at 9:03
  • $\begingroup$ In random process theory, if $x$ is the input and $y$ the output of a LTI system with pulse response $h$, then, $h\star R_{xx}$ gives the cross-correlation of $x$ and $y$, $R_{yx}$ or $R_{xy}$ depending on the definition. Since $R_{xx}$ is even, "flipping it" gives $R_{xx}$ again and so this convolution could be expressed as a correlation too. But in any case, we can think of a signal $R_{xx}$ passing through $h$ and then through $\hat{h}$ (where $\hat{h}[n]=h^*[-n]$) to give the signal $R_{yy}$, i.e, $$R_{yy}=\hat{h}\star(h\star R{xx})=(\hat{h}\star h)\star R_{xx}=R_{hh}\star R_{xx}.$$ $\endgroup$ – Dilip Sarwate Sep 6 '13 at 3:12

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.