0
$\begingroup$

I'm reading through Digital Signal Processing, Proakis and Manolakis, third edition. I've reached section 3.2: Properties of $\mathcal Z$-transform.

One property is the convolution:

$$x(n) = x_1(n)\star x_2(n) \longleftrightarrow X(z) = X_1(z)X_2(z)$$

Other property is correlation:

$$r_{x_1,\ x_2}(l) = \sum_{n=-\infty}^{\infty}x_1(n)x_2(n-l) \longleftrightarrow R_{x_1,\ x_2}(z)=X_1(z)X_2\left(z^{-1}\right)$$

I'm confused by the time reversal (folding) which appears in the correlation property at $X_2\left(z^{-1}\right)$. I know that the folding step occurs on convolution but not on cross/auto/correlation. Why is this and what am I missing?

To clarify the "time reversal" expression I'm referring to another property of $\mathcal Z$-transform taken from the same source:

If $$x(n) \longleftrightarrow X(z)$$ Then $$x(-n) \longleftrightarrow X(z^{-1})$$

For the two answers: Matt's one clarifies the matter using a mathematical perspective while Peter's one shows in an intuitive way how the folding occures in polynomial multiplication. So thanks, I wish SE had a way to mark two answers as accepted.

$\endgroup$
4
$\begingroup$

Note that (discrete-time) convolution is defined as

$$x_1[n]\star x_2[n]=\sum_kx_1[k]x_2[n-k]\tag{1}$$

and correlation is defined as

$$r_{x_1,x_2}[n]=\sum_kx_1[k]x_2[k-n]\tag{2}$$

Comparing $(1)$ and $(2)$ we see that correlation can be written as the following convolution:

$$r_{x_1,x_2}[n]=x_1[n]\star x_2[-n]\tag{3}$$

The $\mathcal{Z}$-transform of $x_2[-n]$ is given by

$$\sum_nx_2[-n]z^{-n}=\sum_nx_2[n]z^n=X_2\left(\frac{1}{z}\right)\tag{4}$$

Consequently, from $(3)$ the $\mathcal{Z}$-transform of $r_{x_1,x_2}[n]$ must be

$$R_{x_1,x_2}(z)= X_1(z)X_2\left(\frac{1}{z}\right)\tag{5}$$

$\endgroup$
  • $\begingroup$ I understand, from a pure mathematical perspective, that the folding step is somehow "inherent" to the $\mathcal Z$-transform and correlation must cancel this "inherent" folding hence the term $X_2(z^{-1})$. Is this correct? $\endgroup$ – tomab Aug 17 '16 at 6:23
  • 1
    $\begingroup$ @tomab: I think your understanding is correct. Time-reversal is inherent in convolution (just look at its definition), and, consequently, in polynomial multiplication, but not in correlation. So for correlation we indeed need to "undo" it, and this is reflected in the Z-transform domain by $X_2(z^{-1})$. $\endgroup$ – Matt L. Aug 17 '16 at 7:35
3
$\begingroup$

Let's look at convolving: $$ x_1 = [1, 2, 3];\\ x_2 = [3, 2, 2]; $$ So: $$ Y(z) = X_1(z) X_2(z) = (1 + 2 z^{-1} + 3z^{-2})(3 + 2z^{-1} + 2 z^{-2})\\ = 3 + 2z^{-1} + 2 z^{-2} + 6z^{-1} + 4z^{-2} + 4 z^{-3} + 9z^{-2} + + 6z^{-3} + 6 z^{-4}\\ = 3 + 8 z^{-1} + 15 z^{-2} + 10 z^{-3} + 6 z^{-4} $$ and then via the reverse-and-multiply:

$$ \begin{array}{ccccccc} n=0 :& 0 & 0 & 0 & 1&2&3& & & = 3\\ & 0 & 2 & 2 & 3\\ n=1 :& 0 & 0 & 0 & 1&2&3& & & = 8\\ & 0 & 0 & 2 & 2 & 3\\ n=2 :& 0 & 0 & 0 & 1&2&3& & & = 15\\ & 0& 0 & 0 & 2 & 2 & 3\\ n=3 :& 0 & 0 & 0 & 1&2&3& & & = 10\\ & 0& 0& 0 & 0 & 2 & 2 & 3\\ n=4 :& 0 & 0 & 0 & 1&2&3& & & = 6\\ & 0& 0& 0& 0 & 0 & 2 & 2 & 3\\ \end{array} $$

So really polynomial multiplication and the "reverse and multiply" convolution procedure produce the same result.

$\endgroup$
  • $\begingroup$ This is a nice example showing that polynomial multiplication and convolution lead to the same result. But why "time-reversed" convolution? It's just plain old convolution! Anyway, I think the OP's actual question was why we have $X_2(z^{-1})$ (which corresponds to time-reversing $x_2[n]$) in the Z-transform of the correlation of $x_1[n]$ and $x_2[n]$. $\endgroup$ – Matt L. Aug 16 '16 at 21:02
  • $\begingroup$ @MattL. Yes,"time-reversed" was inaccurate; I'm not quite sure what the right wording should be: I've gone with "reverse and multiply" instead. $\endgroup$ – Peter K. Aug 16 '16 at 21:04
  • 1
    $\begingroup$ @MattL. I got a different sense of what the OP was asking. My understanding (the question is a little vague) is that "I know that to convolve you time-reverse one of the signals, but the formula for correlation has the time reversal explicitly in it... why is that?" $\endgroup$ – Peter K. Aug 16 '16 at 21:08
  • 1
    $\begingroup$ OK, I see. My reading of the question was prompted by the OP mentioning $X_2(z^{-1})$ in the Z-transform of the correlation. We'll have to wait and see :) $\endgroup$ – Matt L. Aug 16 '16 at 21:12
  • $\begingroup$ This example is great as I can see how polynomial multiplication has the "reverse" in it, which I wasn't aware of until now. $\endgroup$ – tomab Aug 17 '16 at 6:27

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.