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$

2 Answers 2

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$
2
  • $\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, 2016 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, 2016 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$
5
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.