W01_L01_P02 - Representation of signals as frequencies

Okay, by the way there's something
fundamental we're doing here that's going

to be important for what we want to think
about. We talked about we're going to talk

about time frequency analysis right. And
here's the big idea that we're going to

think about with Fourier. Fourier says we
can represent things with sines and

cosines. Well, a big deal? Why does that
help us, right? When we think about this

we're going to think about this F of X as
being a time signal. And what this Fourier

transform allows us to do i.e. Fourier
expansion allows us to do is say, well

actually what am I to do I'm going to
place, representing this function in the X

domain by representing it in terms of
collections of cosines and sines. And in

fact what I care about are the C of N, the
coefficients, okay, here. So for instance,

C1 corresponds to N being one here. Maybe
I'll illustrate it actually over here,

this is a little simpler. Think about what
these mean right here, if I think about

what the A1 represents. A1 represents
cosine X, right? So cosine X has a certain

frequency. So what I'm doing is replacing
my X dependents by a bunch of frequency

content so I have cosine 1X, cosine 2X,
cosine 3X, cosine 4X every, and it gets

higher, higher and higher frequencies. So
what I want to do is take a signal in time

and simply replace it by a representation
of the signal, as a, as a collection of

frequency components, okay? So by the way,
when you hear a bird chirp, if you have a

detector for bird chirpers, right? You
would see its frequency content. You're

seeing it's fourier transform. You're not
seeing the pressure wave and how the

signal is changing in time. What you see
is, what is the spectral content of that

bird chirping, okay? That's what you look
at when you typically do audio

engineering. Frequency content, you always
take the signal and you always represent

it in terms of frequency content. And how
do you do that? Fourier transform it,

okay? That's the role this is going to
play. It's a different representation of

the signal, okay? W e're going to work
with that a lot. Part of what we want to

do is start thinking about if I represent
this is frequency domain, what does that

buy me? And it turns out like for instance
in radar problems it buys you a ton, so

that's what we're going to talk about
Friday. Okay, questions on that, so far.

Yeah? Function's not periodic on my .
What's the relation? Yeah. So typically

this is defined, when you. The way we
think about this is you say look. Suppose

this is defined on. Negative l to l and
let's just say this is some function like

this. That's my function, F of X, but the
Fourier transform, where the Fourier

representation, Fourier series does to do
this, it says, well, actually, this is a

periodic function. Is it not? It just then
takes this thing here, and it. I should

have drawn an easier function. [LAUGH] And
it makes a periodic extension of it. Now

typically we're only interested in this
domain here but technically what it does

is it create, it's valid from negative
infinity, to infinity and what it does is

creates periodic extension and at
discontinuities, you see one right there,

it takes a value halfway between. As you
sum to infinity. By the way, nobody in

this class is going to sum to infinity. I
know, you'd be here for a long time, okay?

All right, we're not summing to infinity.
You always say, yeah. Infinity's big,

right? So lets just take something big and
call it good, okay? So that's going to be

the idea of the Fourier Transform, okay?
Now, by the way, what else are Fourier

Transforms good for? Let me show you.
Actually, I'm going to skip that cause' we

want to get to the. There's some nice
properties it has, that we'll address

later. But for right now, I want to make a
couple comments about this here. This is

exists in MATLAB. You want to take a
signal or a function, and turn it into

frequencies. Okay? You would define it sum
f. Suppose you have a vector F in MATLAB

Actually, let's not call it F. Let's call
it, suppose I have U. I have some function

you define and if I want it in the tran
sform domain all I got to do in MATLAB is

say the following let's call it UT for U
transform is, see how easy that is, nice.

FFT stands for fast fourier transform. Now
why not just call it the FT, right? Seems

a little bit bragging to call it the FFT.
Like, oh, I'm super-fast. Well, it turns

out they can brag cause this operation
here, one of a couple comments I want to

make about this. We're not going to go
into too much detail about it. But when

you do the FFT. FFT was kind of invented
in the late 60s by Tookie and Cooley. Now

picture yourself in the late 60s. Long
hair, tie dye, ladies show up to class,

having a drum circle afterwards. Okay, but
at that time, computers were, slow. My

iPhone over there, would be like, the mega
computer of the world. 1968. Okay, so

given that, these guys are trying to
actually compute pretty important things.

I mean, I mean it depends on what you
think is important. But for instance one

of the big, one of the big pushes in
computational science came from Los

Alamos, when they were actually trying to
compute, pressure waves to create, bombs,

okay? that's a slow computation. It's a
3D, PD comp, computation. And, extremely

slow. Anything you can do to speed up your
code would be greatly appreciated, 'kay?

And generically, when you would compute
this, this would be something like,

whatever the size of your vector you're
working with here, costs you order N

squared to do this. Well, Cooley and
Tookie came up with an algorithm that said

well actually I can do that. N log n. By
the way, if you can beat n log n, you'll

be famous. Okay?You will. Guarantee it.
Promise you. I'll give you more than 25

cents if you can do it. Okay? I'll give
you $one, and buy you lunch. Okay. So

there you go, so what they came up with is
this very, this algorithm that's pretty

much the standard. That's, that's about
as, unless you have a very specific

problem with very specific setup maybe you
can beat this, but for the most part

that's kind of almost like a speed limit.
And if you can beat that, you're, yo u're

rocking it, so that's why they added the
extra F, okay? Fast forward transform and

we're about to use it. Couple things that
they came up with, a couple of

observations, the key to this algorithm is
that what it does, here's, it was actually

a very simple observation they made. What
they found out is because of the

relationship among these four A
coefficients or these, these, these

frequency components. What they found out
is, hey you know what? I could take a

problem of size N and I could break it up
into two sizes of N/2. Well, that problem

size van over two. I can break that up
into two problems sizes of n over four.

Right, so you take this problem of size N.
Two problems of size n over two. Four

problems of size n over four. Eight
problems of size N over eight, blah, blah,

blah, all the way down to. End problems of
one by one. Do you know how easy to solve

one by one, pretty easy. Remember each
problem that you solve what ever size it

is . Computational speed. So if you're
solving the big problem of, order ends,

of, size N, it's very expensive, but if I
can solve, a bunch one by ones, then I

have to just group my answers back
together, and that's what cost, log N,

cost me N, solve, the N equation decides
one, and log N to glue it all back

together, k. So that's the big
contribution to the world, Okay. So that's

what they did, late'60s. Fast Fourier
transform. And at that point, the

algorithm really relied on the fact that
when you take this vector, U, is that. 2N

number of points disquaritazation, right,
so you disquarize it into, sixteen points,

32 points, 64 points, 128 points, however
many points, right, that you, power of

two, so you can always break it down to
smaller and smaller problems. Nowadays,

that's not so important, you can almost
get N log N, there's, really fancy ways to

do this, like if I use a hundred points,
right, which is. Two problems the size 50,

and four problems the size 25. Right,
then, all of a sudden. 25. Okay what do I

got to do to that. So then, right, so you
ran into a prob lem.

But now they pad 0's in there and they can
pretty much get an n login speedout. Okay

and there was a hand, yes. Fidelity, when
gluing the, gluing the solutions back

together. Yup, exactly, sweet right? I
know