Placeholder Image

Subtitles section Play video

  • (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,