Transcript

After delving into a bit of pure mathematics over the last few lectures, I now want to look at what all this has to do with the Fourier Transform.

So what tools do we have in our arsenal? We have Sine waves, Cosine waves, we’ve learned about how we can shift a signal’s phase by adding Sine and Cosine waves together and we’ve found a new shorthand way of doing mathematical operations with Sines and Cosines by using the 3 forms of a complex number.

We’re now going to use all of these tools as we look at the secret of how the Fourier Transform actually works. This secret is called Convolution.

But before we start to talk about convolution, let’s first remind ourselves of what Fourier said about signals, or as he called them, functions.

“Any function of a variable, whether continuous or discontinuous, can be expanded in a series of sines of multiples of the variable.”

So, in other words, Fourier saw any signal as a lot of sine waves, each with its own frequency phase and amplitude, all added together.

This is what a transform is: a way of building up a signal out of simpler building blocks. In Fourier’s case, he built his signals out of Sine waves, but Fourier was by no means the only person to invent a transform. There are other types of transforms.

The Laplace Transform, for example, overcomes a big disadvantage of the Fourier Transform.

One problem with the Fourier Transform which we shall explore later is that it assumes that signals repeat themselves forever, which clearly many of them don’t. This is where a Laplace Transform has a distinct advantage.

Whereas Fourier assumes that signals are made up of a collection of sine waves with constant amplitude, Laplace constructs his signals from a collection of decaying sine waves which decay to nothing, or near enough, long before “forever” is reached.

Another type of transform is the Wavelet Transform. A wavelet is a little burst of sine wave that starts at zero amplitude, grows to some value then decays back to zero.

By adding lots of wavelets together, changing the point in time at which each wavelet starts, the shape of its envelope and its frequency, you can make up any signal you like just as you can with Fourier’s Sine Waves.

So Fourier, building his signals, as he did, out of Sine waves, claimed that he could take any signal, break it down into its constituent waves and tell us what the properties of each wave were. We discovered back at the beginning of the course that a sine wave has 3 properties: Frequency, Amplitude and Phase, so we expect, at the end of Fourier’s transform, to end up with list of waves containing 3 columns for each wave: One for Frequency, one for Amplitude and one for Phase.

So what is convolution?

Convolution is the mathematical equivalent of looking for your slippers.

I have no idea where I put my slippers, so I have to search in every room.

I know what they look like so I’ll recognize them when I see them.

Now what happens if I find my wife’s slippers first? Well, that’s fine. I know they aren’t mine as my wife’s slippers are grey and mine are purple.

Here are my slippers! Now how did they get here?

Applying this analogy to the world of signals, my slippers are like the Sine wave that we’re looking for within our signal. I’ll know it when I find it as I know what frequency I’m looking for, but I don’t know, where, or rather when it occurs in the signal. In other words, I have no idea what its phase is.

So, just as I have to search every room in my house for my slippers, I have to search every phase in my signal for the sine wave that I’m looking for. To demonstrate how convolution works, let’s look at a more visual example.

By this point in the course, you probably know what I look like.

Here I am!

Now imagine that I was in the middle of a crowd of people. How would you find me?

Well one way you could do it would be to compare each person in the crowd with the image of me that you have in your memory. Let’s call this the test image.

If we slide the test image over all the people in the crowd, the moment the test image and the real me converge, you’ll know that you have found me.

To find the phase of the Sine wave with the frequency we are looking for in our signal, we do exactly the same thing. We slide, or convolve, a Cosine wave of the same frequency over the signal. Let’s call this Cosine wave the Test Wave.

Why am I using a cosine wave and not a sine wave? Well it is simply a matter of convention. As far as the maths is concerned, I could use either; after all sine waves and cosine waves are the same wave, just with a 90º phase difference between them. However, very soon, you’re going to understand the Fourier Transform formula and that formula is written in the language of complex numbers. Therefore I want to keep things consistent. When writing a complex number, we always start with the real part, which corresponds to the cosine component. So, just as complex numbers begin with the, cosine component, so will I.

So here is our Test wave, a cosine wave, and I’m slowly going to slide it over my signal by increasing its phase. The moment the test wave converges with the sine wave we are looking for, we know that we have found the phase of the sine wave within our signal.

Convolving the two waves in this manner is all very well for us humans, we can easily identify by sight when the two waves converge, but how could we detect the point of convergence mathematically? How would a computer do it?

What we need is to somehow generate a number, a score that indicates how well the 2 signals match. When they don’t match at all, then the score needs to be low. When they match completely, the score needs to be high.

Well, one way we could do this would be as follows:

Let’s reset our test signal to its initial position. Now I’m going to multiply each point on our test wave with each point on the signal and plot the multiplied signal on a new graph.

At an angle of 0 degrees, our test wave has a value of 1 and our signal has a value of 0.17. So we multiply these 2 points together which gives us 1 times 0.17 which equals 0.17.  Let’s plot this point here.

At an angle of 2 degrees, our test wave has a value of 0.98 and our signal has a value of 0.34. So we multiply these 2 points together which gives is 0.98 times 0.34 which equals 0.34 and plot this point here.

At an angle of 4 degrees, our test wave has a value of 0.94 and our signal has a value of 0.5. So we multiply these 2 points together which gives is 0.94 times 0.5 which equals 0.47 and plot this value here.

We do this for all the points which gives us a new “multiplied signal” shown here in green. We then measure the area enclosed by the “multiplied graph”. This gives us a single value which is the score of how well matched the test wave and the sine wave which I’m looking for within my signal are.

The score for this initial position of the test wave is 31.

Now let’s increase the phase of the test wave a little and do the whole operation again. Each point on the test wave is multiplied by each point on the signal, and the resulting area enclosed by the graph gives us the score of how well matched the signal and test wave are.                 

If I animate this process, look what happens to the score, as my test wave moves closer and closer to being in phase with the signal, the area enclosed by the graph increases meaning that the “score” increases too. When the 2 waves are in phase, the score reaches its highest value, 180 in this case, then begins to fall off again as the 2 waves slip out of phase. When the 2 waves are at their most out of phase, the score is at its lowest value, -180 in the case of these 2 waves.

So when my test wave reaches a phase of 80º, the 2 signals match perfectly and the score is at its highest value. I have found the phase of the sine wave in my signal.

That’s all very well for a simple signal like this, but what about a more complicated signal? What about a signal made up of more than 1 sine wave?

Which sine waves are present in this signal? What are their frequencies? What are their phases and what are their amplitudes? Well, just like the slippers, we have to look for them.

Let’s start by convolving a test wave with a frequency of 1 and amplitude of 1 over our signal. When we multiply all the points on our test wave by all the points on our signal and plot them on the multiplied graph, it doesn’t matter what the phase is, there is always as much area enclosed by the graph above x-axis as there is below it. This means that when we calculate the total area enclosed by the graph, we’ll always get a score of 0. This indicates that our signal does not contain a sine wave with a frequency of 1.

Let’s try convolving a test wave with a frequency of 2 over our signal. This time, as we increase the phase, we can see how the multiplied signal shifts up and down over the x-axis. When we measure the area enclosed by the multiplied graph, we see that the score is not zero so our signal does contain a sine wave with a frequency of 2 in it. Finding the point at which the score is greatest, tells us that the phase of this sine wave is 30º.

Let’s try convolving a test wave with a frequency of 3 over our signal. Again, the multiplied signal shifts up and down over the line and the score is not zero so our signal does contain a sine wave with a frequency of 3 in it. The score is highest at a phase of 60º, so the phase of this sine wave is 60º …and so on.

If I were to try a test frequency of 4 on this wave, I would get zero again as this signal does not contain a sine wave with a frequency of 4.

So whenever we try a frequency that does not exist in the signal, we get a value of 0 in the score, no matter what phase we try, and when a frequency does exist in the signal. We get a score that is non-zero. If that frequency does exist in the signal the moment we find the point at which the score is at its maximum, we have found the phase of the sine wave we are looking for.

While we’ve been searching our signal for sine waves, we’ve found their frequencies and phases, but we haven’t said anything about their amplitude. Well that’s just what the score is. The maximum score we found for each frequency is proportional to the amplitude of the sine wave we are looking for. It doesn’t actually tell us what the original amplitude was, but it does tell us what its relative contribution is to the overall signal.

Just for curiosity’s sake, what would we have to do to make the score equal to the actual contribution of this particular sine wave in the original signal?

Well, we’d have to divide the score by half of the period of the signal. The period of this signal is 360°, so half of the period will be 180°. For this test wave, with a frequency of 3, the maximum score was 72, so if we divide 72 by 180, we get 0.4 which is the actual amplitude of this frequency within the signal.

However, as we’re only concerned with splitting the signal apart into its constituent sine waves   , the relative contribution, or, as I called it, the score, is good enough for now.

So our signal is made up of 2 waves. The first has a frequency of 2  at a phase of 30º and relative amplitude of 90. The second has a frequency of 3 at a phase of 60º and relative amplitude of 72.

When these 2 sine waves are added together, we get a result which looks like our signal. So, using convolution, we have managed to deconstruct our signal into its constituent sine waves. We have just found our first Fourier series.

Now Fourier was a wily old mathematician. Although he knew he could get his answer using convolution, he could see how hard he had had to work to get there. Fourier noticed that there was a slightly quicker way to do it.

What I am about to show you is not the “Fast Fourier Transform”, we’ll take a look at that in a later lecture. What I want to demonstrate here is how we don’t actually need to do the whole convolution operation, i.e. slide our test wave all the way over our signal, to get our result.

We just saw how the score increases to a maximum the nearer the test wave and the sine wave we are looking for in our signal, get to being in phase with each other.

If I trace the line which the score value describes as we convolve the 2 waves; just look at which function that line makes. It’s a phase shifted sine wave with the same phase as the sine wave we are looking for within our signal.

But we know that any phase shifted sine wave can be described by adding a non-phase shifted cosine wave and a non-phase shifted sine wave at the same frequency but different amplitudes. So instead of having to perform the entire convolution, all we need to do is multiply our signal firstly by a cosine wave and then by a sine wave, then use Phythagoras and the inverse tangent rule to calculate the amplitude and phase shift from 2 scores for each wave.

So let’s do just that for our signal.

The first frequency that was present in the signal was 2 so let’s start with that frequency.

If I calculate the score using a non-phase shifted cosine wave as my test wave, I get 78.

If I calculate the score using a non-phase shifted sine wave as my test wave, I get 45.

Using Pythagoras, the square root of 78² plus 45² equals 90.

Using the inverse tangent rule, inverse tan of 45 divided by 78 equals 30º, the same answer as before.

The second frequency that was present in my signal was 3 so let’s calculate for that frequency.

If I calculate the score using a non-phase shifted cosine wave as my test wave, I get 36.

If I calculate the score using a non-phase shifted sine wave as my test wave, I get 62.

Using Pythagoras, the square root  of 36² plus 62² equals 72.

Using the inverse tangent rule, inverse tan of 62 divided by 36 equals 60º, again, the same answer as before.

So let’s review what we just did:

Firstly we multiplied every point of our signal by every point of a Cosine wave at a known frequency to get a multiplied cosine signal which we plotted on a new graph

We then found the area enclosed by that graph which we used as a score, or relative amplitude for the cosine component at that frequency.

We then multiplied every point of our signal by every point of a Sine wave at the same frequency as the Cosine wave to get a multiplied sine signal which we plotted on a new graph.

We then found the area under that graph which we used as a score, or relative amplitude for the sine component at that frequency

We then repeated the whole process again and again at many different frequencies until we had found all the frequencies in our signal.

So how can we express what we’ve just done in a mathematical language?

Well we start with a signal. I said, at the beginning of the course that I would demonstrate how Fourier worked using sound signals. Sound is a signal whose amplitude changes over time so let’s call our signal x of t, the “t” denoting that the variable in our signal is time.

First of all, in stage 1, we multiply the signal by a cosine wave. But the x-axis of a cosine wave is usually an angle. Back in the lecture on phase, we saw how we could scale our x-axis to fit the 360º of a circle by multiplying our time value by the frequency we are looking for then multiplying the result by 360º. Well that’s all very well if we were working in degrees like we have been until now. However, remember that when your calculator calculates the cosine or sine of a value using the infinite series we saw in the lecture on Euler’s identity, it is actually working in radians. So we have to convert the time value, not into degrees but into radians. Instead of there being 360º in a circle, we say that there are 2π radians in a circle. So we multiply our time value, “t”, by the frequency, “f”, we are looking for and then by 2π radians. So for stage 1, we multiply our signal x of t by the cosine of 2πft.

Here is what I get when I multiply the sound signal coming from the violin we passed on the way with the cosine wave.

Now, we need to find the area under the graph of our multiplied signal to obtain the score which represents the amplitude of the contribution of this cosine wave to the overall signal. But how do we do that?

If we wanted to calculate the area of a rectangle, we would take the height of the rectangle and multiply it by its width. But our signal is not a rectangle! Is there any way we could make it into one? Well, we could make it into lots of rectangles, or rather we could break it down into lots of slices and treat each slice as if it was a rectangle and then add the areas of all the rectangles together. You can see how the blocky rectangles do approximate the shape of the multiplied signal. If we reduce the width of each rectangle, and increase the number of rectangles, then we get a better approximation. The thinner the rectangles and the more of them there are, the closer we get to the actual value of the area under the graph. If we were to make each rectangle infinitely thin and increase the number of rectangles to infinity, we could calculate the area exactly.

This is known as integration which we represent mathematically by an integration sign.

So to find the area under the multiplied cosine graph, we take the integral of our multiplied signal x of t times cos 2πft with respect to t, i.e. each slice is t seconds thick where the difference between one t and the next is infinitely small. We write this mathematically as the integral of x of t times the cosine of 2πft dt.

But an integral has to have limits. “t” has to start somewhere and end somewhere. Well in a repeating signal such as the one we have here, it is enough to look at one cycle of the signal as after that cycle is complete, the signal will just repeat itself.

In our signal here, you can see that everything repeats itself every 3.5ms so we say that the period of our signal is 3.5ms and we integrate it between time equals zero and time equals 3.5ms.

Now as this is a repeating signal, it doesn’t actually matter where we set our limits so long as we integrate over exactly 1 cycle. Imagine this signal went on forever. Imagine it didn’t have a beginning or an end. Just as the signal will repeat itself again and again into the future, so it has already repeated itself again and again since the ancient past. So just as our graph here looks from now, when time equals zero, into the future, we could also look back into the past, when time was less than zero, and the signal would still look the same.

Instead of integrating from 0 to 3.5ms, we could integrate from minus 1.75ms till 1.75ms and the result of the integral would still come out the same, so long as the period over which we integrated remained exactly 3.5ms which is the period of this particular signal.

Now not all signals have a period of 3.5ms. How to we write the limits of the integration for an arbitrary signal with a period of “p” seconds?

Well, if we always ensure that our time equals zero point is exactly in the centre of the graph, then we need to integrate from a point in time that is minus a half of the period until a point which is plus half of the period. So our integration limits become minus p over 2 and plus p over 2.

But why is that important? Why not just integrate from zero to the period “p”  like we did before? What’s all this dividing the period by 2 business? We’ll answer that question towards the end of the lecture.

So now we have the score for how much the Cosine wave at this first frequency contributes to our overall signal. The next stage is to repeat all the steps we just took, only now using a Sine Wave at the same frequency.

We take our signal, multiply it by a sine wave and then integrate, to find the area under the graph giving the score which represents the amplitude of the contribution of this sine wave to the overall signal.

So we now have 2 separate integrals which I’m going to call the Cosine Integral and the Sine Integral; but having to deal with 2 separate equations is a little messy. Is there any way we could combine it into 1 equation? Could we, for example, add the 2 integrals together?

Well, unfortunately, no.

That would simply give us a result which is the sum of the areas under both graphs which would give us the wrong answer. Remember, in order to work out the phase of the particular sine wave we are looking for, or in other words, when exactly it occurs in our signal, we need to keep the scores of the Cosine and Sine components separate. But how can we do that and still combine our 2 integrals into 1 equation?

Well in the last few lectures, we’ve been talking about a special number that does just that: The imaginary number “i”!

If we multiply one of the integrals by “i” we could have our cake and eat it, so to speak; but which integral? Well the integral with the Sine in it of course, just like Euler’s formula multiplies the Sine term by “i”.

So now, if we multiply the Sine integral by “i”, we could add the two integrals or even take one away from the other and it wouldn’t make any difference to the result as the “i” keeps them separate.

So what should we do? Add or take away? The answer is actually more political than mathematical. Political, in the sense that whereas mathematically, it doesn’t really matter which sign we write, everyone has to agree to do the same thing to avoid confusion.

In this course, we are learning about the Fourier Transform, which is a method of breaking down signals into their constituent Sine Waves. It stands to reason therefore that if Fourier knows how to break signals down, he can also take those Sine Waves and put them back together again to recover the signal, and indeed he can using the Inverse Fourier Transform.

We don’t have time in this course to look in any detail at the Inverse Fourier Transform, but I will just say that the equations for the Fourier and Inverse Fourier Transforms look quite similar so to differentiate between them, the convention has grown up that we denote the Fourier Transform with a minus sign between the integrals and the Inverse Fourier Transform with a plus sign between the integrals. So, not wanting to flout convention, let’s combine these 2 integrals into 1 equation by putting a minus sign between them.

Mathematicians like to be tidy. If they can, they like to reduce their equations to be as short as possible. For example, do we really need the 2 integration signs? After all, as we saw, integration is simply adding an infinite number of rectangular areas together.

Each of these integrals simply gives us a number. So, for the sake of the following example, let’s do away with all the Cosines and Sines and trying to keep the separate for a second and deal with some simple numbers.

Imagine I wanted to do the following calculation:

9 plus 11 minus two plus 3.

9 plus 11 equals 20

and

2 plus 3 equals 5.

20 minus 5 equals 15.

However, we could remove the brackets, making sure, of course, to change the sign in the second set of brackets as this is a minus operation, and do the whole calculation at once, without having to calculate each bracket separately.

9 plus 11 equals 20 minus 2 equals 18 minus 3 equals 15.

This would appear to indicate that just as I can combine the calculation of 2 brackets into one calculation, so I can combine the 2 integrations into one and we would get the same answer.

If this is true of 2 integrals we actually do want to add together, how much more so is it true, of 2 integrals that we’re not really adding together at all, because of the “i” will keep the result of the second integration separate anyway. So we can combine the cosine and sine integrals into one, big operation.

But we can go further. Our signal x of t is multiplied both by the cosine wave and the sine wave, so we could take it out as a common factor and put everything else in brackets.

But hey! Look at this: Inside the brackets: It’s Euler’s Formula with a few minor differences. The theta in our case is 2ᴨft and instead of adding sine and cosine terms we are subtracting them instead. So we can replace the entire brackets with e to the minus i2ᴨft. The minus is there because we have cosine term minus the sine term.

So this gives us a neat equation which describes how we calculate the contribution of the cosine and sine terms at our first test frequency.

Now we need to run this equation again and again for lots of different frequencies, or in other words we need to keep changing the value of “f”. We write this like this.

n is an index. When n equals 1, we are testing the signal with our first frequency f₁, and we get a result c₁.

c₁ is a complex number whose real part tells us the score for the contribution of the Cosine wave at frequency 1 and whose Imaginary part tells us the score for the contribution of the Sine wave at frequency 1.

When n equals 2 we test the signal with our next frequency: f₂ and we get a result c₂.

c₂ is also a complex number whose real part tells us the score for the contribution of the Cosine wave at frequency 2 and whose Imaginary part tells us the score for the contribution of the Sine wave at frequency 2.

And so it is true for c₂, c₃, c₄ and so on. We generalize this by calling the terms by the collective name cₙ.

So that’s it! There you have it. This is how the Fourier Transform works and what the equation means. Job done, end of course.

Well, not quite.  What we have just calculated here is not the Fourier transform. It’s a Fourier series! What’s the difference?

Remember Fourier’s claim that any function could be expanded in a series of Sines of multiples of the variable”?

Well, this claim was a hotly debated subject at the time. As we learned in the introduction to the course, eminent mathematicians like Lagrange and Laplace both challenged Fourier’s paper on the subject, and, it seems with good reason.

It took the further work of Peter Gustav Lejeune Dirichlet to give a satisfactory demonstration of Fourier’s claim. However, there were certain restrictive conditions that had to exist for Fourier’s idea, as he proposed it in his paper, to work.

The problem with Fourier’s claim is indicated by the limits of the integral. Remember that we found the area under the graph of the multiplied signal over 1 cycle of the signal; from time equals zero to the period of the signal, or as we wrote it before, from minus half of the period of the signal to plus half of the period. Only repeating signals have a cycle. The whole meaning of the word “cycle” is something that goes round and round again and again, or in other words, a signal that keeps repeating itself.

The problem is: repeating signals are not the only signals out there. In fact, most of the useful signals we encounter from day to day don’t repeat themselves. The words that I am saying to you are a kind of signal; a sound signal. If I was to repeat same sentence to you over and over again in this lecture, you’d very quickly get bored, and most likely switch off as no new information can be imparted in a repeating signal.

Hence Fourier’s claim that any signal can be expanded in a series of Sines cannot be true. Only repeating signals can be expanded in a Series of Sines. But here we are spending all this time learning about a mathematical idea that is so revolutionary it underpins most of the electronic communications we have nowadays not to mention many other applications that Fourier couldn’t have even dreamed of. If the Fourier series only allows us to model a small proportion of signals, how comes it’s so useful?

Well that was thanks to Derichlet who made some small but significant changes to Fourier’s equation.

“What happens”, he asked, “if the signal doesn’t repeat itself?” If a signal doesn’t repeat itself, then it cannot have a period… or can it? The word “never” suggests: “infinity”. Maybe we could say that the signal actually does repeat itself, but it will only repeat itself after an infinite amount of time. Therefore the limits of the integral must expand to encompass the whole of time, from minus infinity to plus infinity, or to put it another way, the signal has never repeated itself, and the signal will never repeat itself again.

This is why I changed the limits of the Fourier series equation before from looking at the signal from time equals zero to the period, to looking at the signal from minus half the period to plus half the period. I wanted the integral to remain consistent with the way we write the Fourier Transform equation looking in both directions, into the past and into the future of the signal.

But now we have a problem and that problem is called “Infinity”. How can we calculate the infinite? As we’ll see, it’s not only the period of the non-repeating signal that is going to become infinite, but also the length of the list of Sine waves that we need to describe it.

Come with me as we journey, “Into the Infinite”; and we see how Derichlet turned “Fourier Series” into the “Fourier Transform”.