[This content was created with ML, available from the App Store.]

Convolution

If a system is both linear and time invariant, we can compute its response to an input signal through the operation of convolution, the result of which is nothing more than a linear combination of the system's time-shifted impulse responses by the values of the input signal.

In discrete time domain, a system that is both linear and time invariant transforms a finite-length input signal sn to output yn=snhn , where hn is the impulse response of the system and is the convolution operator.

      yn=snhn

      yn=k=0k=N1skhnk

      yn=s0hn+s1hn1++sN1hn(N1)

But what does all this mean?

We will use the following story as a device to demonstrate the meaning of convolution in a simple way.

The Outback Weather Station

You are running a weather station at a remote location in the outback in the sun-burnt country called Australia. From the station you can see a long stretch of road that runs north-south, along which cars and trucks travel occasionally. Ever since you have been at the station, you have noticed that there is something special about the hours the trucks travel on that road: if they pass, they pass only on the hour, never between the hours.

One Sunday morning in summer you get up early to watch the glorious rise of Orion. After an early breakfast, you realize that you have nothing to do the whole day. To prevent yourself from being overcome by boredem, you decide to find out whether more trucks will travel north on the road that day. It is nearly six o'clock. You pick up a pen and a notebook and go outside and sit in a comfortable chair facing the road. You look at your your watch; it's six o'clock. You check the road: no trucks travelling in either direction. You immediately write the number zero in the middle of a blank page in the notebook. Then you check the road every hour until midnight.

When you see a truck travelling north on the hour, you update the number in the notebook by adding a one to it; when you see a truck travelling south on the hour, you subtract one. Similarly you update the number accordingly for multiple trucks travelling in the same direction. When you see multiple of them travelling north, you update the number by adding the number of trucks travelling in that direction; when you see multiple of them travelling south, you update the number in the notebook by subtracting the number of trucks travelling in that direction.

You are acting as a system recording the net flow of trucks bound north.

The System

What is the system in the above story?

You and your notebook and your pen is the system: you are recording the net flow of trucks bound north; that is, you are keeping track of the difference between the number of trucks travelling north and number of trucks travelling south. The output yn of the system is the number in the note book.

What is the input signal sn?

The input signal sn to the system is the flow of trucks at each hour. You interpret the north-bound trucks as a positive flow, and the south-bound trucks as a negative flow: For north-bound trucks you increment the number in the notebook by the number of trucks going north; for south-bound trucks you decrement the number in the notebook by the number of trucks going south. If you see no trucks going in either direction, then you update the number by zero; but this is the same as not updating it.

For example, if you see one north-bound truck at 9 AM, then two south-bound trucks at 3 PM, and no trucks afterwards, then the input signal sn will have two non-zero numbers: A 1 at 9 AM and a -2 at 3 PM.

     sn= {0,0,0,1,0,0,0,0,0,2,0,0,0,0,}

The above signal conveys the information that you saw no trucks at 6 AM, 7 AM, and 8 AM; then you saw one truck going north at 9 AM. After that you did not see any trucks until 3 PM. At 3 PM you saw two trucks going south, and no trucks afterwards.

The system has three important properties, but only two of them are required for convolution.

The system is both linear and time invariant. These two properties enable us to use convolution to compute the response of the system to an input signal. The system is also causal, but we don't need this property to be able to use convolution.

It is causal: You don't update the count in the notebook before you see a truck pass by; you update the count only when a truck passes by. The count remains the same until you update it.

It is time invariant: Your recording behaviour does not change with time: you faithfully update the number in the notebook at every hour when trucks pass by and you don't change it for any other reason.

It is linear: If you update the count in the notebook by one N times, the result will be the same as if you update it by N just once.

As a system, you are recording the difference between the number of trucks travelling north and number of trucks travelling south. To demonstrate this, let's start with the number zero ( 0) which you wrote in the notebook at 6 AM on that day.

If you don't see any trucks on the road that day, then you don't update the number in the notebook.

     sn= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,}

If you see only two north-bound trucks at 11 AM, then you increment the number by two ( 2) at 11 AM.

     sn= {0,0,0,0,0,2,0,0,0,0,0,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn= {0,0,0,0,0,2,2,2,2,2,2,2,2,2,}

If see only one south-bound truck at 1 PM, then no trucks afterwards, then you decrement the number by one at 1 PM.

     sn= {0,0,0,0,0,0,0,1,0,0,0,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn= {0,0,0,0,0,0,0,1,1,1,1,1,1,1,}

If you see a north-bound truck at 9 AM, then another one going south at 4 PM, then no trucks afterwards, then you update the number twice as follows.

     sn= {0,0,0,1,0,0,0,0,0,0,1,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn= {0,0,0,1,1,1,1,1,1,1,0,0,0,0,}

Finally if you see a one north-bound truck at 9 AM, then another one going north at 11 AM, then another three going north at 4 PM, then no trucks afterwards, then you update the number three times as follows.

     sn= {0,0,0,1,0,1,0,0,0,0,3,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn= {0,0,0,1,1,2,2,2,2,2,5,5,5,5,}

Its Impulse Response

The convolution requires that we know the impulse response of the system.

Determining the impulse response of this system (you and your notebook and your pen) is very easy.

Let's imagine for a moment that when you checked the road at six AM that day, you saw only one truck going north and no trucks afterwards, and that therefore you wrote a one in the notebook at six AM:

     sn=δn= {1,0,0,0,0,0,0,0,0,0,0,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn=hn= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

This sequence of values represents the response of the system: the system remembers that initial value of one indefinitely until one or more trucks pass by.

We call this sequence of values the impulse response of the system. The impulse input sn is that single truck you saw going north at six AM. We denote the impulse response by hn.

     sn=δn= {1,0,0,0,0,0,0,0,0,0,0,0,0,0,}      yn=hn= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

Thus, the impulse response of the system is just a sequence of endless ones.

That is, someone looking at the number in the notebook every hour would see the endless sequence of ones if no other trucks passed after 6 AM.

Let's instead imagine that you saw a single truck, the first one, going north at 11 AM (5 hours after 6 AM) and no trucks afterwards, and that therefore you wrote a one in the notebook at 11 AM:

     sn=δn5= {0,0,0,0,0,1,0,0,0,0,0,0,0,0,}

Then someone looking at the number in the notebook every hour would see the following sequence of values.

     yn=hn5= {0,0,0,0,0,1,1,1,1,1,1,1,1,1,}

This time if no other trucks passed after 11 AM, then someone looking at the number in the notebook every hour would see an endless sequence of ones which start at 11 AM (5 hours after 6 AM). This response is the same as the previous response but it is shifted in time by 5 hours because the input signal is shifted in time by 5 hours (that is, the first and only truck passed 5 hours after 6 AM).

Because the input signal is a 5-hour delayed impulse and because the system is time invariant the response of the system is also shifted in time by 5 hours.

     hn5= {0,0,0,0,0,1,1,1,1,1,1,1,1,1,}

Some Examples

Example 1

You see 5 trucks that day, all travelling north: 1 truck at 6 AM, another at 7 AM, then 3 more at 8 AM; and no trucks afterwards.

What is the response yn of the system to the input signal sn?

     sn= {1,1,3}
     hn= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     sn=δn+δn1+3δn2
     yn=hn+hn1+3hn2

     δn= {1}
     δnhn= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     δn1= {0,1}
     δn1hn1= {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     δn2= {0,0,1}
     δn2hn2= {0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     yn=hn+hn1+3hn2
     yn= {1,2,5,5,5,5,5,5,5,5,5,5,5,5,5,5,}

The output yn is just a linear combination of the system's time-shifted impulse response hnk by the values of the input signal sn: For each impulse δnk in the input signal, we compute the response hnk of the system, then we linearly combine all the responses by multiplying each one by the number sk and adding them.

What we have just described can be written formally as follows.

      yn=snhn

      yn=k=0k=N1skhnk

      yn=s0hn+s1hn1++sN1hn(N1)

Therefore for a linear and time invariant system, convolution is nothing more than a linear combination of the system's time-shifted impulse responses by the values of the input signal.

Example 2

You see 7 trucks that day: a single truck going north at 6 AM, 2 trucks going north at 8 AM, 1 truck going north at 10 AM, then two trucks going south at 12 PM, and a single truck going south at 2 PM, and no trucks afterwards.

What is the response yn of the system to the input signal sn?

     sn= {1,0,2,0,1,0,2,0,1}
     hn= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     sn=δn+2δn2+δn42δn6δn8
     yn=hn+2hn2+hn42hn6hn8

     δn= {1}
     δnhn= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     δn2= {0,0,1}
     δn2hn2= {0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     δn4= {0,0,0,0,1}
     δn4hn4= {0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     δn6= {0,0,0,0,0,0,1}
     δn6hn6= {0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     δn8= {0,0,0,0,0,0,0,0,1}
     δn8hn8= {0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

     yn=hn+2hn2+hn42hn6hn8
     yn= {1,1,3,3,4,4,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

The output yn is just a linear combination of the system's time-shifted impulse response hnk by the values of the input signal sn: For each impulse δnk in the input signal, we compute the response hnk of the system, then we linearly combine all the responses by multiplying each one by the number sk and adding them.

What we have just described can be written formally as follows.

      yn=snhn

      yn=k=0k=N1skhnk

      yn=s0hn+s1hn1++sN1hn(N1)

Therefore for a linear and time invariant system, convolution is nothing more than a linear combination of the system's time-shifted impulse responses by the values of the input signal.

[This content was created with ML, available from the App Store.]