Convolution

Table of Contents

THERE IS NO PHYSICAL MEANING FOR THIS, FYI!

Just thought you woud like to know. It's used because it gives a nice way of describing the output of a linear, time-invariant system.

Linear systems

Requirements

homogeneity
change in input signal's amplitude results in a corresponding change in output signal's amplitude. A system is said to be homogenous if it has this property.
additivity
adding two inputs is equivalent to the corresponding outputs being added to each other. I.e. convolution_fc4ea4b74bd597497d2beafded3ed1a5a8488c94.png

For DSP, we also have:

shift invariance
shift in input implies identical shift in output

Impulse Function Decomposition

  • Input signal is decomposed into simple additive components
  • System response of the input signal results in by adding the output of these components passed through the system
  • A signal be decomposed as a weighted sum of basis signals
    • E.g. Fourier Series

The impulse function is simply a convolution_734ace1ca706cad07392531389b813068bc44391.png function, and so we have the decomposition to be:

convolution_cfc80d0a1e8d1155a294b4b785dcff14e543730e.png

Matrix

For a matrix we simply do the same thing, but now consider some convolution_49fd3b25474425ce0e536633b89ac031379e90fb.png matrix with all entries being zero except the middle, which is 1, to be the definition of our convolution_734ace1ca706cad07392531389b813068bc44391.png.

(Not sure how you do it if convolution_094b02afce734f4ce51933d0093ef3d2da9f8123.png is even..)

Checkout this. Scroll a bit down and you got the section about "2D Convolution".

My view on things

  1. Decompose our input signal into a set of impulses

convolution_cfc80d0a1e8d1155a294b4b785dcff14e543730e.png

  1. Compute output by adding the scaled and shifted impulse responses, convolution_93192fe3e2dc4f68bbc7d0420e7a25e5c4dad63c.png

    convolution_d7a2571c5ff8be3f3eccadd9c2c11ffb63301412.png

    where convolution_bc116374d314269201772040a5eb58683d1559c7.png is a linear time-invariant system which takes input convolution_1acf443977313267da30d56c0216cbdcfc58525e.png.

  2. If we only consider a smaller region by letting all entries for convolution_bc116374d314269201772040a5eb58683d1559c7.png be zero outside of this region:

    convolution_9ae1ab1d9c21a15a49f04f181f23f9b733f765ea.png

    For some finite number of convolution_094b02afce734f4ce51933d0093ef3d2da9f8123.png. Note the differences in the summation terms.

Why the flipping?!

The impulse response describes how each point in the input signal affects the output signal. This results in each point in the output signal being affected by points in the input signal weighted by a flipped impulse response.

That is; it's because of the maths, yo.