1
$\begingroup$

How can the linear convolution be defined rigorously for two discrete signals $x = [x(0), …, x(N_x-1)]$ and $h = [h(0), …, h(N_h-1)]$ of different finite lengths $N_x$ and $N_h$ respectively?

Let's assume for simplicity that $N_x = 3$ and $N_h = 2$, i.e. $x = [x(0), x(1), x(2)]$ and $h = [h(0), h(1)]$. Does the sum go from $0$ to $N_x - 1$ or to $N_h - 1$? However, $$\sum_{i = 0}^{N_x-1} x(i) h(n - i) \neq \sum_{i = 0}^{N_h-1} h(i) x(n - i)$$ i.e. the commutativity cannot hold, and also both sums will have "illegal" terms containing $h(-2)$, $h(-1)$, $h(2)$, $h(3)$, $h(4)$ and $x(-1)$, $x(3)$, $x(4)$ (which I guess can be set to zero, but that somehow seems not right since that redefines my initial signals).

$\endgroup$
3
  • $\begingroup$ your summation limits should be variable $\endgroup$
    – Fat32
    Nov 19 '20 at 20:37
  • $\begingroup$ @Fat32, from $0$ to $n$ seems like the right choice, i.e. $y(n) = \sum_{i=0}^{n}x(i)h(n-i) = \sum_{i=0}^{n}h(i)x(n-i)$. $\endgroup$
    – orbit
    Nov 19 '20 at 20:44
  • $\begingroup$ not actually... $\endgroup$
    – Fat32
    Nov 19 '20 at 20:46
2
$\begingroup$

This is a deep topic, which is a typical boundary problem: how to deal with data when it is unknown?

The simplest way: finite sequences are often regarded as if they were infinite, padded with zeros to the left and the right. Then the summation because well-defined, and zero values are canceled. Mathematics even has a name for the space of such "almost zero" sequences: $c_{00} $ (space of eventually zero sequences), stable under finite addition, product and convolution.

In your case, you can use the largest upper limit in the summation, and consider the signal (or the filter) to be zero outside its support.

For practical reasons, other extensions are used: periodic continuation, symmetry or anti-symmetry, constant or polynomial extrapolation, sometimes combined with windowing.

To help you understand the simplest way: convolution seems complicated, yet it could help to visualize that it as a multiplication of polynomials (they are really related). If polynomials are too complicated, think of numbers (and let us forget the carry for a moment). Each digit (or monomial for polynomials) corresponds to a sample of the signal or a tap of the filter. Suppose that you multiply $12.3$ by $4,567$. The first digit before the dot will result from products of units, product of tens and first decimals, etc.: $2\times 7$, $3\times 6$ and... $1\times 0$, because even if $4567$ has no decimal, it can be seen as having a first decimal of $0$ ($4567.0$). So a number can be naturally extended for multiplication with as many zeros as necessary behind the dot, and also "before" the top digit: $12.3$ is like $\ldots00012.3000\ldots$. In practice for the multiplication, you don't need to append an infinite number of zeroes. It suffices to stick to the number with most digits (plus one for the carry, but that's another story).

As you can see, a digit to the left of one number is combined to a digit to the right for the other number. If there is not digit, implicitly you put a zero.

$\endgroup$
2
  • 2
    $\begingroup$ Profound but I am having difficulty understanding what your point is. Please elucidate for simple-minded folks like myself. Thanks $\endgroup$ Nov 20 '20 at 5:03
  • $\begingroup$ It is not a point, it is a dot.. $\endgroup$ Nov 20 '20 at 11:17
5
$\begingroup$

The OP says that sequences

$x = [x(0), …, x(N_x-1)]$ and $h = [h(0), …, h(N_h-1)]$ (are) of different finite lengths $N_x$ and $N_h$ respectively

He does not claim that $x$ and $h$ are finite-length segments of possibly longer (maybe even infinitely longer) sequences, and so the standard assumption is that finite length means what it says. In particular, $x[n]$ has value $0$ whenever $n < 0$ or whenever $n \geq N_x$, and similarly, $h[n]$ has value $0$ whenever $n < 0$ or whenever $n \geq N_h$.

The general definition of the convolution of sequences $p$ and $q$ is that result of the convolution is another sequence, which we denote as $\big(p\star q\big)$ whose $n$-th term is given by $$\big(p\star q\big)[n] = \sum_{k=-\infty}^\infty p[k]q[n-k] = \sum_{k=-\infty}^\infty p[n-k]q[k]\tag{1}$$ subject to the usual shibboleths about convergence of the sums and the like. So, applying this to the case at hand, we have that \begin{align} \big(x\star h\big)[n] &= \sum_{k=-\infty}^\infty x[k]h[n-k]\\ &= \sum_{k=0}^{N_x-1} x[k]h[n-k] & \scriptstyle{\text{because $x[k]=0$ for $k<0$ or $k\geq N_x$}} \tag{2} \end{align} Using the alternative formula for $\big(p\star q\big)[n]$, we have \begin{align} \big(x\star h\big)[n] &= \sum_{k=-\infty}^\infty x[n-k]h[k]\\ &= \sum_{k=0}^{N_h-1} x[n-k]h[k] & \scriptstyle{\text{because $h[k]=0$ for $k<0$ or $k\geq N_x$}} \tag{3} \end{align}

Both $(2)$ and $(3)$ are valid expressions for $\big(x\star h\big)[n]$ and for each integer $n$, both give the same value for $\big(x\star h\big)[n]$ even though the expressions are seemingly quite different.. The OP claims that $$\sum_{i = 0}^{N_x-1} x(i) h(n - i) \neq \sum_{i = 0}^{N_h-1} h(i) x(n - i)$$ but this claim is false; for every choice of integer $n$, the two sums result in the same expression (except for a trivial re-arrangement of the terms). Don't believe it? Let's try a few special cases keeping firmly in mind that $x[n]$ and $h[n]=0$ if $n < 0$.

For $n = 0$, \begin{align}\require{cancel} \sum_{k=0}^{N_x-1} x[k]h[0-k] &= x[0]h[0] + x[1]\cancelto0{h[-1]} + x[2]\cancelto0{h[-2]} + \cdots\\ &= x[0]h[0]\\ \sum_{k=0}^{N_h-1} x[0-k]h[k] &= x[0]h[0] + \cancelto0{x[-1]}h[1] + \cancelto0{x[-2]}h[2] + \cdots \\&= x[0]h[0] \end{align}

For $n = 1$, \begin{align} \sum_{k=0}^{N_x-1} x[k]h[1-k] &= x[0]h[1] + x[1]h[0] + x[2]\cancelto0{h[-1]} + \cdots \\&= x[0]h[1]+x[1]h[0]\\ \sum_{k=0}^{N_h-1} x[1-k]h[k] &= x[1]h[0] + x[0]h[1] + \cancelto0{x[-1]}h[2] + \cdots \\&= x[1]h[0] + x[0]h[1] \end{align} More generally, assuming that $N_h < N_x$, for each $n$, $0 \leq n \leq N_h -1$, $$\sum_{k=0}^{N_x-1} x[k]h[n-k] = x[0]h[n] + x[1]h[n-1] + \cdots + x[n]h[0]\tag{4}$$ while $$\sum_{k=0}^{N_h-1} x[n-k]h[k] = x[n]h[n]0] + x[n-1]h[1] + \cdots + x[0]h[n]\tag{5}$$ which is the same sum as in $(4)$ except for being in reverse order! Fortunately, addition is commutative.....

That the sums in $(2)$ and $(3)$ are equal (except for being written in reverse order) is true not just for $0 \leq n \leq N_h -1$ but for all $n$. I won't bother typing out the gory details, but each sum in $(2)$ and $(3)$ contains at most $\min(N_x,N_h)$ nonzero terms and they occur in reverse order one from the other. $(2)$ and $(3)$ are the same sum even though the expressions look different at first glance, regardless of the OP's claims, and convolution is indeed commutative: for every integer $n$,

$$\big(p\star q\big)[n] = \big(q\star p\big)[n].$$

$\endgroup$
3
$\begingroup$

It's quite straightforward to give an exact formulation for the convolution of two finite-length sequences, such that the indices never exceed the allowed index range for both sequences. If $N_x$ and $N_h$ are the lengths of the two sequences $x[n]$ and $h[n]$, respectively, and both sequences start at index $0$, the index $k$ in the convolution sum

$$(x\star h)[n]=\sum_{k=-\infty}^{\infty}x[k]h[n-k]\tag{1}$$

must satisfy

$$0\le k \le N_x-1\tag{2}$$

and

$$0\le n-k \le N_h-1\tag{3}$$

$(3)$ is equivalent to

$$k\le n\quad \textrm{and}\quad n-N_h+1\le k\tag{4}$$

Plugging $(2)$ and $(4)$ into $(1)$ results in

$$(x\star h)[n]=\sum_{k=\max\{0,n-N_h+1\}}^{\min\{N_x-1,n\}}x[k]h[n-k]\tag{5}$$

And since we can exchange the roles of $x[n]$ and $h[n]$ in $(1)$, Eq. $(5)$ is equivalent to

$$(x\star h)[n]=\sum_{k=\max\{0,n-N_x+1\}}^{\min\{N_h-1,n\}}h[k]x[n-k]\tag{6}$$

$\endgroup$
1
$\begingroup$

Convolution of two sequences is defined like:

$$ y[n] = x[n] \star h[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k] = \sum_{k=-\infty}^{\infty} h[k]x[n-k] = h[n] \star x[n] \tag{1}$$

And the commutativity does hold according to Eq.1; i.e. for any value $n$, you will have the same output $y[n]$ from either of the summations.

When the sequences have finite support (finite length), then you should adjust the limits of the summation properly to get the correct range of dummy index $k$.

In your example, The limits of the summation will depend on the output index $n$. This way you will prevent illegal terms such as $h[-2]$ etc.

$\endgroup$
1
  • $\begingroup$ "The limits of the summation will depend on the output index n". How exactly? $\endgroup$
    – orbit
    Nov 19 '20 at 20:52

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.