How not to fall victim to the star notation of the convolution?

The Convolution Series

  1. Definition of convolution and intuition behind it
  2. Mathematical properties of convolution
  3. Convolution property of Fourier, Laplace, and z-transforms
  4. Identity element of the convolution
  5. Star notation of the convolution
  6. Circular vs. linear convolution
  7. Fast convolution
  8. Convolution vs. correlation
  9. Convolution in MATLAB, NumPy, and SciPy
  10. Deconvolution: Inverse convolution
  11. Convolution in probability: Sum of independent random variables

Introduction

Taking advantage of the introduction of delays in the previous article, I wanted to warn you against a common pitfall when talking about the convolution [1].

The star notation x[n]h[n]x[n] \ast h[n] is very convenient. It must, however, be used with caution.

The following notation should be clear to you by now

y[n]=x[n]h[n],nZ.(1)y[n] = x[n] \ast h[n], n \in \mathbb{Z}. \quad (1)

What if we wanted to obtain a delayed version of y[n]y[n], i. e., y[nn0]y[n-n_0]? A natural move would be to substitute nnn0n \leftarrow n-n_0

y[nn0]=?x[nn0]h[nn0],(2)y[n-n_0] \stackrel{?}{=} x[n-n_0] \ast h[n-n_0], \quad (2)

but…

Let’s evaluate the right hand side of “Equation” 2

x[nn0]h[nn0]=k=x[kn0]h[nn0k]=k=x[k]h[n2n0k]=y[n2n0].(3)x[n-n_0] \ast h[n-n_0] = \sum_{k=-\infty}^{\infty} x[k-n_0] h[n-n_0 - k] = \newline \sum_{k=-\infty}^{\infty} x[k] h[n-2n_0 - k] = y[n-2n_0]. \quad (3)

By blindly substituting nnn0n \leftarrow n-n_0, we overshot the desired delay by a factor of two.

The correct way to write this is [1, Eq. 2.52]

y[nn0]=x[n]h[nn0]=k=x[k]h[nn0k].(4)y[n-n_0] = x[n] \ast h[n-n_0] = \sum_{k=-\infty}^{\infty} x[k] h[n-n_0 - k]. \quad (4)

This is just one of many problems that arise when using the star notation.

Useful notational tip

When the convolution looks any way different from the typical x[n]h[n]x[n] \ast h[n], I try to bring it back to that basic form by defining “helper functions”. Then I use the definition of the convolution and substitute the original functions again, inserting the correct argument.

How this works is best explained through an example.

Example 1: Both convolved signals delayed

Let’s say the operands of the convolution we need to perform are both delayed by different amounts, i. e., we want to calculate

x[nnx]h[nnh]=n,nx,nhZ.(5)x[n-n_x] \ast h[n-n_h] = \dots \quad n,n_x,n_h \in \mathbb{Z}. \quad (5)

Let’s define two “helper functions” x1[n],h1[n]x_1[n], h_1[n]

x1[n]=x[nnx],(6)x_1[n] = x[n-n_x], \quad (6)
h1[n]=h[nnh].(7)h_1[n] = h[n-n_h]. \quad (7)

Now we can insert these functions into Equation 5

x[nnx]h[nnh]=x1[n]h1[n],(8)x[n-n_x] \ast h[n-n_h] = x_1[n] \ast h_1[n], \quad (8)

use the definition of the convolution

x1[n]h1[n]=k=x1[k]h1[nk],(9) x_1[n] \ast h_1[n] = \sum_{k=-\infty}^{\infty} x_1[k] h_1[n-k], \quad (9)

and finally substitute the original functions x[n]x[n] and h[n]h[n] according to Equations 6 and 7 respectively

k=x1[k]h1[nk]=k=x[knx]h[nknh].(10)\sum_{k=-\infty}^{\infty} x_1[k] h_1[n-k] = \sum_{k=-\infty}^{\infty} x[k-n_x] h[n - k - n_h]. \quad (10)

This approach always works for me. At the same time, any shortcuts in an attempt not to use it inevitably led me to an error in calculations.

Example 2: One of the convolved signal is time-reversed

This final example should make clear why “helper functions” ensure us that we correctly evaluate the star notation. In this example, one of the operands is time-reversed.

x[n]h[n]=h2[n]=h[n]x[n]h2[n]=k=x[k]h2[nk]=h2[nk]=h[(nk)]k=x[k]h[kn].(11)x[n] \ast h[-n] \stackrel{h_2[n]=h[-n]}{=} x[n] \ast h_2[n] = \sum_{k=-\infty}^{\infty} x[k] h_2[n-k]\newline \stackrel{h_2[n-k]=h[-(n-k)]}{=} \sum_{k=-\infty}^{\infty} x[k] h[k-n]. \quad (11)

Is it possible to guess the correct answer right away? Yes, definitely. But it is not easy, especially if the arguments get even more complicated and the convolution is a part of a much larger body of derivations.

Summary

In this article, we discussed notational issues concerning the discrete convolution and how to avoid common pitfalls when using the star notation. It all boils down to the idea of using “helper functions”.

Bibliography

[1] A. V. Oppenheim, R. W. Schafer Discrete-Time Signal Processing, 3rd Edition, Pearson 2010.