Subtitles section Play video Print subtitles (bell dings) - Hello, welcome to a coding challenge. I actually just finished this coding challenge, and I'm coming back to re-record a little intro to it. And what I made in this coding challenge is a drawing machine. Maybe let's call this a Fourier transform drawing machine. There's a few more things we want to do with it. There's going to be some followup videos. But this very, very long video, if you can stand to watch it, has, as part of it, at the end, this. This is the end result. I am using an algorithm called Fourier Transform to take an arbitrary signal, in this case, a sequence of X's and a sequence of Y's, the path of the Coding Train logo, thank you to Tom Fevrier. I will link to Tom Fevrier's Twitter, who provided the path for this particular logo, to trace the path of the logo through this sort of sequence of rotating circles, sometimes referred to as epicycles. Okay, so what's going on here? So, first thing I should mention is this is a continuation of my coding challenge Fourier Series. And so, what I did in that particular coding challenge, which was inspired by a Smarter Everyday video on the same topic, was create the Fourier series for a square wave. I don't know why I just had to write that. But in this video, I'm going to do something different, which is I'm going to use the Fourier transform algorithm. And these are different concepts. I somewhat conflated these in my previous video. The idea of the Fourier transform. Now, where I know this algorithm from, where I learned about this algorithm first in like, learning about coding and creative coding and new media and sound and video is with the terminology FFT, and actually, if you go into the p5 sound library, you'll see there is a class or function called p5.FFT. I don't remember exactly what it's called, but something like that. The F here stands for fast, Fast Fourier Transform. The algorithm I'm going to implement, by the way, is discrete Fourier transform. Why is this FFT thing, where is it typically used? Well, it's typically used in, it's in signal processing, but a familiar place where you might find that is in audio signal processing. So let's say you have some arbitrary sound wave that maybe looks like this, and it has a really high-pitched, awful, screeching sound in it. How would you filter that out? Well, if you could take this sound wave pattern and break it into a bunch of smaller sound waves, a bunch of sound waves that have varying amplitudes and frequencies, then you could take, you could sort of remove the one that has the high-pitched sound in it and then add them all back together and get a new sound wave. So the idea of a Fourier transform, I think I said this in the Fourier Series, but it's unsmoothie-ing a smoothie. If we could take a smoothie that's made with blueberry, mango, and strawberries, and like, separate it out and then put it back together without the strawberries, this is essentially what happens in signal processing. But in this video, what I'm going to do is instead of the signal being an audio, it's going to be a series of X values or a series of Y values, and eventually, there actually a way to do that with the X, Y values together that I will get to. So, I am not going to go too deep into the math in this particular video. I'm not going to derive the Fourier Transform algorithm. I'm not going to talk about Fast Fourier Transform. I'm just going to use a very crude, discrete Fourier Transform implementation just to get the thing working. If you want to know more about the math, though, let me reference a few really key references. The 3blue1brown video, But what is the Fourier Transform? will give you an infinitely better understanding of what the Fourier Transform algorithm is and what it does, and even how it works, way better than my trying to ramble through that over on the whiteboard. I would also highly recommend this GoldPlatedGoof video, Fourier Analysis for the Rest of Us, which goes through the details of the math in a much deeper way, and then there's this wonderful video from Mathologer, Epicycles, complex Fourier series and Homer Simpson's orbit, which will give you the full story of everything that I'm trying to do. But hopefully, what's useful to you that's different in my video than from these is I'm just going to sit here and attempt to code the thing. And I know that it's going to work, because I already did it, and here is the result. So enjoy. This is a very long video. I hope that if you watch it, you get the code, you make your own variation of it, please share it with me. You can go to thecodingtrain.com, to the particular coding challenge page, and then there's instructions on how to submit a user community variation thingy there. Okay, goodbye, enjoy, or not, or whatever. I am ready to start coding, finally. Now, this is where I left off before in my Fourier Series coding challenge, and the difference now is what I want to do is be able to have an arbitrary signal and then compute what all of these amplitudes and frequencies and phases should be. So, the way that I'm going to do that is, so let's think about this. This is really a bunch of Y values that I'm calculating. So let's make an array called something like Y, and this is going to be the signal, this is my signal. This could be audio, it could be Y positions, any arbitrary digital signal/array of numbers. Then what I want to do is I want to have like, the Fourier transform of that particular signal. So I want to say, fourierY = fourierTransform, or maybe like dft, discrete Fourier Transform, of the Y value. So this is the idea. The first thing that I need to do is compute the discrete Fourier transform of an arbitrary signal. Now I need some kind of signal. So I think what I'm going to absurdly do is hardcode the signal. Let's actually make it the square wave, and then we'll know if it kind of worked. So what is the square wave? Square wave would be something like 100, 100, 100, - 100, -100, -100, and then like, do that a few times. So this is going to be my arbitrary signal, which I'm just hardcoding the square wave. And we'll do some interesting things that we might, maybe I'll try a Perlin noise signal or just a sine wave signal. We'll try different things, random numbers, and see what that does. So then, this actual code here can largely stay the same, 'cause in theory, the difference is now, instead of following the specific Fourier Series for the square wave, I just need to take the results of my discrete Fourier transform. So this would be a loop that's going to go through the length of that transform, how many different wave patterns are there that I'm adding together, and then this ultimately, I'm going to have to figure out. So let's comment this out right now, and there's a little bit of an issue where I have this x and y as like, local variables here. But let's, I think this will be okay. So let's refresh this, and DFT is not fine. Okay, step one, let's write the discrete Fourier Transform algorithm. So, I'm going to start by making a function called dft. It's going to have some array of values, and now, I need to, at the end, I need to return something. (laughs) The idea is that I will return the discrete Fourier transform of those values. So, a couple things. One is I highly recommend, if you want to pause this video right now and read this particular article on the Algorithm Archive by James Schloss or the LeIOS YouTube channel. This is a really nice article about Fourier transforms and the discrete Fourier Transform algorithm, and this particular algorithm for FFT. But what I'm going to do is I'm just going to follow exactly what's here on the Wikipedia page. So, my signal is x sub n, lowercase xn. So what I need to do is basically,