The Fourier Transform is one of deepest insights ever made. Unfortunately, the meaning is buried within dense equations:

Yikes. Rather than jumping into the symbols, let's experience the key idea firsthand. Here's a plain-English metaphor:

**What does the Fourier Transform do?**Given a smoothie, it finds the recipe.**How?**Run the smoothie through filters to extract each ingredient.**Why?**Recipes are easier to analyze, compare, and modify than the smoothie itself.**How do we get the smoothie back?**Blend the ingredients.

Here's the "math English" version of the above:

- The Fourier Transform takes a time-based pattern, measures every possible cycle, and returns the overall "cycle recipe" (the strength, offset, & rotation speed for every cycle that was found).

Time for the equations? No! Let's get our hands dirty and *experience* how any pattern can be built with cycles, with live simulations.

If all goes well, we'll have an aha! moment and intuitively realize why the Fourier Transform is possible. We'll save the detailed math analysis for the follow-up.

This isn't a force-march through the equations, it's the casual stroll I wish I had. Onward!

## From Smoothie to Recipe

A math transformation is a change of perspective. We change our notion of quantity from "single items" (lines in the sand, tally system) to "groups of 10" (decimal) depending on what we're counting. Scoring a game? Tally it up. Multiplying? Decimals, please.

The Fourier Transform changes our perspective from consumer to producer, turning *What did I see?* into *How was it made?*

In other words: given a smoothie, let's find the recipe.

Why? Well, recipes are great descriptions of drinks. You wouldn't share a drop-by-drop analysis, you'd say "I had an orange/banana smoothie". A recipe is more easily categorized, compared, and modified than the object itself.

So... given a smoothie, how do we find the recipe?

Well, imagine you had a few filters lying around:

- Pour through the "banana" filter. 1 oz of bananas are extracted.
- Pour through the "orange" filter. 2 oz of oranges.
- Pour through the "milk" filter. 3 oz of milk.
- Pour through the "water" filter. 3 oz of water.

We can reverse-engineer the recipe by filtering each ingredient. The catch?

**Filters must be independent**. The banana filter needs to capture bananas, and nothing else. Adding more oranges should never affect the banana reading.**Filters must be complete**. We won't get the real recipe if we leave out a filter ("There were mangoes too!"). Our collection of filters must catch every last ingredient.**Ingredients must be combine-able**. Smoothies can be separated and re-combined without issue (A cookie? Not so much. Who wants crumbs?). The ingredients, when separated and combined in any order, must make the same result.

## Seeing The World As Cycles

The Fourier Transform takes a specific viewpoint: **What if any signal could be filtered into a bunch of circular paths?**

Whoa. This concept is mind-blowing, and poor Joseph Fourier had his idea rejected at first. (*Really Joe, even a staircase pattern can be made from circles?*)

And despite decades of debate in the math community, we expect students to internalize the idea without issue. Ugh. Let's walk through the intuition.

The Fourier Transform finds the recipe for a signal, like our smoothie process:

- Start with a time-based signal
- Apply filters to measure each possible "circular ingredient"
- Collect the full recipe, listing the amount of each "circular ingredient"

Stop. Here's where most tutorials excitedly throw engineering applications at your face. Don't get scared; think of the examples as "Wow, we're finally seeing the source code (DNA) behind previously confusing ideas".

If earthquake vibrations can be separated into "ingredients" (vibrations of different speeds & strengths), buildings can be designed to avoid interacting with the strongest ones.

If sound waves can be separated into ingredients (bass and treble frequencies), we can boost the parts we care about, and hide the ones we don't. The crackle of random noise can be removed. Maybe similar "sound recipes" can be compared (music recognition services compare recipes, not the raw audio clips).

If computer data can be represented with oscillating patterns, perhaps the least-important ones can be ignored. This "lossy compression" can drastically shrink file sizes (and why JPEG and MP3 files are much smaller than raw .bmp or .wav files).

If a radio wave is our signal, we can use filters to listen to a particular channel. In the smoothie world, imagine each person paid attention to a different ingredient: Adam looks for apples, Bob looks for bananas, and Charlie gets cauliflower (sorry bud).

The Fourier Transform is useful in engineering, sure, but it's a metaphor about finding the root causes behind an observed effect.

## Think With Circles, Not Just Sinusoids

One of my giant confusions was separating the definitions of "sinusoid" and "circle".

- A "sinusoid" is a specific back-and-forth pattern (a sine or cosine wave), and 99% of the time, it refers to motion in one dimension.
- A "circle" is a round, 2d pattern you probably know. If you enjoy using 10-dollar words to describe 10-cent ideas, you might call a circular path a "complex sinusoid".

Labeling a circular path as a "complex sinusoid" is like describing a word as a "multi-letter". You zoomed into the wrong level of detail. Words are about concepts, not the letters they can be split into!

The Fourier Transform is about circular paths (not 1-d sinusoids) and Euler's formula is a clever way to generate one:

Must we use imaginary exponents to move in a circle? Nope. But it's convenient and compact. We *can* separate the path into real and imaginary parts, but don't forget the big picture: we move in circles.

## Following Circular Paths

Let's say we're chatting on the phone and, like usual, I want us to draw the same circular path simultaneously. (*You promised!*) What should I say?

- How big is the circle? (Amplitude, i.e. size of radius)
- How fast do we draw it? (Frequency. 1 circle/second is a frequency of 1 Hertz (Hz) or 2*pi radians/sec)
- Where do we start? (Phase angle, where 0 degrees is the x-axis)

I could say "2-inch radius, start at 45 degrees, 1 circle per second, go!". After half a second, we should each be pointing to: starting point + amount traveled = 45 + 180 = 225 degrees (on a 2-inch circle).

Every circular path needs a size, speed, and starting angle (amplitude/frequency/phase). We can even combine paths: imagine tiny motorcars, driving in circles at different speeds.

The combined position of *all the cycles* is our signal, just like the combined flavor of *all the ingredients* is our smoothie.

Here's a simulation of a basic circular path:

(Based on this animation, here's the source code. Modern browser required. Click the graph to pause/unpause.)

The magnitude of each cycle is listed in order, starting at 0Hz. Cycles `[0 1]`

means

- 0 strength for the 0Hz cycle (0Hz = a constant cycle, stuck on the x-axis at zero degrees)
- 1 strength for the 1Hz cycle (completes 1 cycle per time interval)

Now the tricky part:

**The blue graph measures the**. Another lovely math confusion: the real axis of the circle, which is usually horizontal, has its magnitude shown on the vertical axis. You can mentally rotate the circle 90 degrees if you like.*real part*of the cycle**The time points are spaced at the fastest frequency**. A 1Hz signal needs 2 time points for a start and stop (a single data point doesn't have a frequency). The time values`[1 -1]`

shows the amplitude at these equally-spaced intervals.

With me? `[0 1]`

is a pure 1Hz cycle.

Now let's add a 2Hz cycle to the mix. `[0 1 1]`

means "Nothing at 0Hz, 1Hz of strength 1, 2Hz of strength 1":

Whoa. The little motorcars are getting wild: the green lines are the 1Hz and 2Hz cycles, and the blue line is the combined result. Try toggling the green checkbox to see the final result clearly. The combined "flavor" is a sway that starts at the max and dips low for the rest of the interval.

The yellow dots are when we actually measure the signal. With 3 cycles defined (0Hz, 1Hz, 2Hz), each dot is 1/3 of the way through the signal. In this case, cycles `[0 1 1]`

generate the time values `[2 -1 -1]`

, which starts at the max (2) and dips low (-1).

Oh! We can't forget phase, the starting angle! Use `magnitude:angle`

to set the phase. So `[0 1:45]`

is a 1Hz cycle that starts at 45 degrees:

This is a shifted version of `[0 1]`

. On the time side we get `[.7 -.7]`

instead of `[1 -1]`

, because our cycle isn't exactly lined up with our measuring intervals, which are still at the halfway point (this could be desired!).

**The Fourier Transform finds the set of cycle speeds, strengths and phases to match any time signal.**

Our signal becomes an abstract notion that we consider as "observations in the time domain" or "ingredients in the frequency domain".

Enough talk: try it out! In the simulator, type any time or cycle pattern you'd like to see. If it's time points, you'll get a collection of cycles (that combine into a "wave") that matches your desired points.

But… doesn't the combined wave have strange values between the yellow time intervals? Sure. But who's to say whether a signal travels in straight lines, or curves, or zips into other dimensions when we aren't measuring it? It behaves exactly as we need at the equally-spaced moments we asked for.

## Making A Spike In Time

Can we make a spike in time, like `(4 0 0 0)`

, using cycles? I'll use parentheses `()`

for a sequence of time points, and brackets `[]`

for a sequence of cycles.

Although the spike seems boring to us time-dwellers (*that's it?*), think about the complexity in the cycle world. Our cycle ingredients must start aligned (at the max value, 4) and then "explode outwards", each cycle with partners that cancel it in the future. Every remaining point is zero, which is a tricky balance with multiple cycles running around (we can't just "turn them off").

Let's walk through each time point:

At time 0, the first instant, every cycle ingredient is at its max. Ignoring the other time points,

`(4 ? ? ?)`

can be made from 4 cycles (0Hz 1Hz 2Hz 3Hz), each with a magnitude of 1 and phase of 0 (i.e., 1 + 1 + 1 + 1 = 4).At every future point (t = 1, 2, 3), the sum of all cycles must cancel.

Here's the trick: when two cycles are on opposites sides of the circle (North & South, East & West, etc.) their combined position is zero (3 cycles can cancel if they're spread evenly at 0, 120, and 240 degrees).

Imagine a constellation of points moving around the circle. Here's the position of each cycle at every instant:

Time 0 1 2 3 ------------ 0Hz: 0 0 0 0 1Hz: 0 1 2 3 2Hz: 0 2 0 2 3Hz: 0 3 2 1

Notice how the the 3Hz cycle starts at 0, gets to position 3, then position "6" (with only 4 positions, 6 modulo 4 = 2), then position "9" (9 modulo 4 = 1).

When our cycle is 4 units long, cycle speeds a half-cycle apart (2 units) will either be lined up (difference of 0, 4, 8…) or on opposite sides (difference of 2, 6, 10…).

OK. Let's drill into each time point:

- Time 0: All cycles at their max (total of 4)
- Time 1: 1Hz and 3Hz cancel (positions 1 & 3 are opposites), 0Hz and 2Hz cancel as well. The net is 0.
- Time 2: 0Hz and 2Hz line up at position 0, while 1Hz and 3Hz line up at position 2 (the opposite side). The total is still 0.
- Time 3: 0Hz and 2Hz cancel. 1Hz and 3Hz cancel.
- Time 4 (repeat of t=0): All cycles line up.

The trick is having individual speeds cancel (0Hz vs 2Hz, 1Hz vs 3Hz), or having the lined-up pairs cancel (0Hz + 2Hz vs 1Hz + 3Hz).

When every cycle has equal power and 0 phase, we start aligned and cancel afterwards. (I don't have a nice proof yet -- any takers? -- but you can see it yourself. Try `[1 1]`

, `[1 1 1]`

, `[1 1 1 1]`

and notice the time spikes: `(2 0)`

, `(3 0 0)`

, `(4 0 0 0)`

).

Here's how I visualize the initial alignment, followed by a net cancellation:

## Moving The Time Spike

Not everything happens at t=0. Can we change our spike to `(0 4 0 0)`

?

It seems the cycle ingredients should be similar to `(4 0 0 0)`

, but the cycles must align at t=1 (one second in the future). Here's where phase comes in.

Imagine a race with 4 runners. Normal races have everyone lined up at the starting line, the `(4 0 0 0)`

time pattern. Boring.

What if we want everyone to *finish* at the same time? Easy. Just move people forward or backwards by the appropriate distance. Maybe granny can start 2 feet in front of the finish line, Usain Bolt can start 100m back, and they can cross the tape holding hands.

Phase shifts, the starting angle, are delays in the cycle universe. Here's how we adjust the starting position to delay every cycle 1 second:

- A 0Hz cycle doesn't move, so it's already aligned
- A 1Hz cycle goes 1 revolution in the entire 4 seconds, so a 1-second delay is a quarter-turn. Phase shift it 90 degrees backwards (-90) and it gets to phase=0, the max value, at t=1.
- A 2Hz cycle is twice as fast, so give it twice the angle to cover (-180 or 180 phase shift -- it's across the circle, either way).
- A 3Hz cycle is 3x as fast, so give it 3x the distance to move (-270 or +90 phase shift)

If time points `(4 0 0 0)`

are made from cycles `[1 1 1 1]`

, then time points `(0 4 0 0)`

are made from `[1 1:-90 1:180 1:90]`

. (Note: I'm using "1Hz", but I mean "1 cycle over the entire time period").

Whoa -- we're working out the cycles in our head!

The interference visualization is similar, except the alignment is at t=1.

Test your intuition: Can you make `(0 0 4 0)`

, i.e. a 2-second delay? 0Hz has no phase. 1Hz has 180 degrees, 2Hz has 360 (aka 0), and 3Hz has 540 (aka 180), so it's `[1 1:180 1 1:180]`

.

## Discovering The Full Transform

The big insight: our signal is just a bunch of time spikes! If we merge the recipes for each time spike, we should get the recipe for the full signal.

The Fourier Transform builds the recipe frequency-by-frequency:

- Separate the full signal (a b c d) into "time spikes": (a 0 0 0) (0 b 0 0) (0 0 c 0) (0 0 0 d)
- For any frequency (like 2Hz), the
*tentative*recipe is "a/4 + b/4 + c/4 + d/4" (the strength of each spike is split among all frequencies) - Wait! We need to offset each spike with a phase delay (the angle for a "1 second delay" depends on the frequency).
- Actual recipe for a frequency = a/4 (no offset) + b/4 (1 second offset) + c/4 (2 second offset) + d/4 (3 second offset).

We can then loop through every frequency to get the full transform.

Here's the conversion from "math English" to full math:

A few notes:

- N = number of time samples we have
- n = current sample we're considering (0 .. N-1)
- x
_{n}= value of the signal at time n - k = current frequency we're considering (0 Hertz up to N-1 Hertz)
- X
_{k}= amount of frequency k in the signal (amplitude and phase, a complex number) - The 1/N factor is usually moved to the
*reverse transform*(going from frequencies back to time). This is allowed, though I prefer 1/N in the forward transform since it gives the*actual*sizes for the time spikes. You can get wild and even use 1/sqrt(N) on both transforms (going forward and back still has the 1/N factor). - n/N is the percent of the time we've gone through. 2 * pi * k is our speed in radians / sec. e^-ix is our backwards-moving circular path. The combination is how far we've moved, for this speed and time.
- The raw equations for the Fourier Transform just say "add the complex numbers". Many programming languages cannot handle complex numbers directly, so you convert everything to rectangular coordinates and add those.

## Onward

This was my most challenging article yet. The Fourier Transform has several flavors (discrete/continuous/finite/infinite), covers deep math (Dirac delta functions), and it's easy to get lost in details. I was constantly bumping into the edge of my knowledge.

But there's always simple analogies out there -- I refuse to think otherwise. Whether it's a smoothie or Usain Bolt & Granny crossing the finish line, take a simple understanding and refine it. The analogy is flawed, and that's ok: it's a raft to use, and leave behind once we cross the river.

I realized how feeble my own understanding was when I couldn't work out the transform of `(1 0 0 0)`

in my head. For me, it was like saying I "knew" addition but, gee whiz, I'm not sure what "1 + 1 + 1 + 1" would be. Why not? Shouldn't we have an intuition for the simplest of operations?

That discomfort led me around the web to build my intuition. In addition to the references in the article, I'd like to thank:

- Scott Young, for the initial impetus for this post
- Shaheen Gandhi, Roger Cheng, and Brit Cruise for kicking around ideas & refining the analogy
- Steve Lehar for great examples of the Fourier Transform on images
- Charan Langton for her detailed walkthrough
- Julius Smith for a fantastic walkthrough of the Discrete Fourier Transform (what we covered today)
- Bret Victor for his techniques on visualizing learning

Today's goal was to *experience* the Fourier Transform. We'll save the advanced analysis for next time.

Happy math.

## Appendix: Projecting Onto Cycles

Stuart Riffle has a great interpretation of the Fourier Transform:

Imagine spinning your signal in a centrifuge and checking for a bias. I have a correction: we must spin *backwards* (the exponent in the equation above needs a negative sign). You already know why: we need a phase *delay* so spikes appear in the *future*.

## Appendix: Another Awesome Visualization

Lucas Vieira, author of excellent Wikipedia animations, was inspired to make this interactive animation:

(Detailed list of control options)

The Fourier Transform is about cycles added to cycles added to cycles. Try making a "time spike" by setting a strength of 1 for every component (press Enter after inputting each number). Fun fact: with enough terms, you can draw any shape, even Homer Simpson.

## Appendix: Using the code

All the code and examples are open source (MIT licensed, do what you like).

- Interactive example (view source)
- Github gist
- Reddit discussion on details of the computation, I'm pb_zeppelin

## Other Posts In This Series

- A Visual, Intuitive Guide to Imaginary Numbers
- Intuitive Guide to Angles, Degrees and Radians
- Intuitive Arithmetic With Complex Numbers
- Understanding Why Complex Multiplication Works
- Intuitive Understanding Of Euler's Formula
- An Interactive Guide To The Fourier Transform
- Intuitive Understanding of Sine Waves

Hey, great use of animations to explain and edify..

and I much appreciate your crediting and linking to my HTML5 sine animation.. Kudos!

Nice article!

gord.

awesome! if the world does come to an end today, i can at least die having understood the basics of DFT

This is really, really awesome. Thank you for sharing!

Absolutely fantastic article, thanks for this!

Spectacular article – I’ve always wanted to see it explained in an intuitive way and you’ve finally done it. Congrats on all the hard work.

I think you should make a similar post for explaining fourier transforms as a change of basis from time to frequency.

@gord: Thanks for the note — the pleasure was all mine, your original sine animation was incredible! So concise and effective.

@sean: Hah, I feel the same!

@Mike, @matt, @Bo: Thanks, I appreciate it

@josh: Great point. I’d like to do a follow-up going into some of the more advanced math & interpretations. There’s some good overlaps with linear algebra here too.

Great explanation! Thanks.

Is there somewhere that explains convolution this well?

The recipe analogy is really horrible and confusing.

@Steve: Glad you enjoyed it! I don’t have an article on convolution yet, but it’d be a great follow-up.

@Marnee: Looks like it didn’t work for you! The key is realizing whether you’re looking at “ingredients” (inputs) or the “cooked meal” (output). The transform lets you switch between the two. Smoothies are nice because there’s just blending/separating, no “cooking” that is difficult to undo.

I really like your presentation!

I recently wrote a tutorial on the DFT as well, though I came at it from a different point of view. My understanding of it is based on correlation between the time domain signal and a series of sinusoids of increasing frequency: http://practicalcryptography.com/miscellaneous/machine-learning/intuitive-guide-discrete-fourier-transform/

Hey, man, this is really great. I like to use DFTs for stochastic processes and look at their underlying trend (this is similar to harmonic regression, which is kinda’ cool). Thanks for this!

Nicely done!

Rarely seen such a complicated and confusing presentation of the Fourier transform. Sorry, I didn’t like it.

I learned it as a way to approximate the solution to conductive heat transfer integral math. The length of the series that substitutes for the equation has diminishing changes after only a few members of the series are calculated. when the material constants are only measureable to within 10%, the answer would be good. the integral math would normally be very hard to solve- the series is easy comparatively speaking (accurate to how many places….).

It was at that time taught for computerized solutions as finite difference method (rather than finite element method). letting the computer grind out the solution to ‘complicated’ math. Not quite Rayleigh’s ‘shooting’ method (superposition methods solved with a first guess on computer-ie natural frequencies of rotating shafts) but at least as effective. Bessel functions ultimately similar- just more obtuse (3rd order nonlinear partial diff eq….) approximations.

Sorry, Fourier transform’s rotted my brain an University, and I accepted a career in Computing and not Electrical and Electronic Engineering

I know my place.

What a great article – I’ve been playing on and off with Fourier transforms for years… I don’t think I’ve ever seen anyone elucidate on the subject quite as well as this…

I got stuck at the first formula, where there is an x missing in the exponent.

Loved this! I’m going to reread it about four more times until I’ve memorized it.

@James: Glad you liked it! Thanks for the link, I’ll check it out (I’m planning on doing a more math-focused follow-up, so that’ll come in handy).

@Francisco: More than welcome, glad you enjoyed it.

@Rene: Thanks!

@Yves: No problem :). Beauty (a clear explanation?) is in the eye of the beholder.

@Kwazai: Neat stuff! I believe heat transfer was the original use case for the transform. I’m a physics newbie but would like to get into more applications.

@NeilPost: The Fourier Transform was a brutal mistress for most of us ;).

@Dan: Thanks, really glad it’s helping!

@Peter: D’oh! Of course there’d be a typo in the first line. Fixed now.

@Zaine: Awesome. If there are any parts that are confusing after the 2nd reading, I probably need to reword them :).

do not share those secrets.

if you know the shortcut maths – hide it. use it for your own profit.

it’s the only power you have. if you share it to everyine – you will lose your advantage. they won’t pay you back, won’t share their secrets.

does bankeers share the shortcut maths for integral sums? no. they just convert it into caviar and gold. leaving others complex as hell ineffective school methods.

@Glukk-

the only way I know to ‘abort’ the system as we know it (prostitutes like bankers…) is to give it away. Best things in life are not free-they just make you happy to think they are.

Engineering is the art(science?) of fudge factors…

Mother Earth News solved the global energy crisis in the 70’s- nobody listened….

Kalid, your article appeared in my mailbox and I had no intention of reading it at that moment, but read the first bit and I was totally, totally hooked! I was flat out excellent and we all certainly appreciate the seriously hard work and thought that you obviously put into this. It was riveting, and helped me understand in a much different and wholly more satisfying way, than my college math days, The Fourier Transform. Full marks, Kalid! Full marks!

A nice description! You might enjoy the “full”

mathematical story at

http://www.civilized.com/files/newfourier.pdf

@Glukk: The Fourier Transform cannot stay in the hands of the math elite!

@Garth: Awesome, I love it when math gets addictive! Thanks for the kind words

@Gary: Thanks! I’ll have to check that out. I’m looking to do a more math-focused follow-up.

You ask how to easily prove “When every cycle has equal power and 0 phase, we start aligned and cancel afterwards.”

This is because the roots of x^n = 1 sum to 0 (Vieta’s formulas):

x^n – 1 = (x-r1)(x-r2)…(x-rn) = x^n – (r1 + r2 + … + rn)x^(n-1) + …

so r1 + r2 + … + rn = 0.

I think the best way to intuit why a spike can be built in the way you describe is by going back to the circle. I am going to speak extremely loosely in the spirit of your blog.

Instead of thinking of a sum of sines, let’s go back to your circle analogy. Imagine N evenly spaced “slots” around the circle, in which we can place some number of “dots” which represent the presence of a frequency. As you said, at time 1, the dots will be all evently spaced out throughout the circle, spaced by 1 unit representing each frequency increment. Then at time 2 they will be spaced out by 2, at time 3, 3, etc. However, very often the dots will “wrap around”. In fact, this will always happen unless the dots are placed with a one unit spacing (N slots, N dots, so either you go in steps of one or you have to loop around). What I want to convince you of now is that whether or not there is looping, the resulting occupied slots form a regular polygon on the unit circle, and further, every occupied slot is occupied equally with dots. If the “step size” is not “divisible” into N, then you will hit every slot exactly once. This is an N-sided regular polygon, each slot gets hit the same number of times. (Good!) When there is “divisibility”, this means that you will eventually hit a space you already occupied, and therefore will begin repeating. We are left with a regular polygon, and it also must have each vertex occupied evenly, since repetition happens after a number of times divisible into N. So the result is always expressible as the sum of the vertices of a regular polygon (times some integer to account for some integer number of layers). But it is visually obvious that the sum of vertices of a regular polygon sum to the center of the polygon (zero).

There is one exception to this rule: a “one-gon” is the only shape with a “bias”. This is what will be responsible for our “spike”. Actually, it’s not surprising that there is a weird exception somewhere, after all, if there were destructive interference everythere, then we woud have found a nontrivial sum of sines that add to zero, proving they are not linearly independent!

Everything I’ve said above is very loose, but I think the purpose of this blog is not to prove things rigorously, but to get a really good intuition for them. And I hope this is what I have done.

I love the smoothie metaphor!

Keep it coming! Thanks!

It must have been hard work. And fun in putting in a lot of imagination to get this done. Great work.

Worth the wait – only 22 years for me!

Great explanation for something that is so seemingly complicated!

“One of my giant confusions was separating circles from sinusoids.”

This was one of my most notable Aha!-moments during the Analysis class as well. Glad to see it explained clearly here. You might find the website below very interesting, especially ‘phasor phactory’ (in case you haven’t encountered it yet).

http://www.jhu.edu/signals/index.html

Keep up this useful work,

M.

This is all very interesting and I do rather like the use of the unit circle definition of the sine wave as an illustrative tool. However, the exposition still lacks something that has always bothered me about discussions of Fourier’s ideas: Specifically, it doesn’t actually explain why the transform works at all. A few years back, when working on a software algorithm for synchronous signal detection, I once again became intrigued by the FFT and why it actually works. At that time, I set upon the task of figuring it out. The result of this effort was an essay, with graphs and mathematics, which I originally called “Fourier for Dummies” – apeing the interminable string of “XXXYouNameIt for Dummies” books.While I left this original title in the link on my web page, I actually named the piece more descriptively as “A look at Fourier from a High School Math Perspective: Fourier and AC Signal Processing”. You can read the essay and/or download a PDF from my web server at:

http://linuxbio.med.buffalo.edu/Fourier/AC_Signal_Processing.html

You may hate it or you may love it but it may be worth a look.

A couple examples of using the Fourier integrals and series on a known signal (e.g. a simple one like 1+sin(t)) and showing how the ‘parts’ are extracted would be helpful.

I tried and failed to get what I expected (e.g. 1 for the DC component for this litle signal above at w=0) when I attempted to evaluate the integral form, which probably just means I forgot how to integrate properly (but Maxima blew up on it too).

Kalid – As always, thanks *so much* for your efforts! I look forward to you tackling the Laplace transform one of these days:)

1+sin(t) can be evaluated very easily at w=0 if you remember that e raised to the zero power is always exactly equal to 1. On the otherhand, if you write the integral in expanded form (i.e. as integral of x(t)Cos(wt)-jx(t)Sin(wt)) and integrate piecewise.Then you are only ingtegrating Cos(wt), iSin(wt), Sin(t)Cos(wt) and iSin(t)Sin(wt) and combining the results. Since you have no phase shift and only a single frequency, the integrals of iSin(wt) and Sin(t)Cos(wt) evaluate to exactly zero. The integral of Cos(wt) also evaluates to exactly zero everywhere except at w=0. This is easily seen since Cos(0)=1, so at w=0, you are taking the integral of 1. The integral of iSin(t)Sin(wt) is non-zero when w=1 and zero everywhere else.

When you actually do the integral, at least for the value of the integral of Cos(0) dt, there is this irritating problem that the integral actually evaluates to “t”, not “1” and this is probably why Maxima blew up calculating the definite integral: t would have been replaced by infinity in the calculations! This is exactly the problem that Lipot Fejer resolved by proving that the series converged only when cast in terms of the means. So whenever you are attempting to recover amplitudes, you need to take the mean, which essentially means dividing by “t”. When you do this, you get the expected result. You may still need to massage the equations in Maxima to prevent the possibility of dividing Infinity by infinity. Intuitively you (a human) may think that this should be equal to 1, however, in reality it is mathematically undefined This is because infinity+x is still infinity so the ratio of 2 infinities must be indeterminate since, by definition, you can never say that 2 infinities have the same value and there is no way to find out if they do.

More complex periodic functions can be analyzed in a similar fashion by first applying trigonometric transforms to the functions and then integrating the components. Not always easy, but it works.

Somehow my attribution got bombed from the last post

Thanks, Great article

Stephen,

Thanks for replying. I actually did recognize that e^0 is one. The integral becomes integral(1+sin(t)dt), which evaluates to t-cos(t). But, evaluating that from -inf to +inf blows up, which is no big surprise.

Dividing by ‘t’, as you mentioned, doesn’t quite get me there either.

The formula in the first bullet of section 2.4 in http://www.civilized.com/files/newfourier.pdf (see Gary Knott’s post above – thanks Gary) does work (divide by 1/p (the fundmental frequency) and adjust the limits of integration to be one cycle), but I don’t follow (yet, anyway, but I’m not giving up) how we can just replace the +/-infinities in the formal definition of the integral.

At least I finally got the answer I was looking for, but needless to say I would have failed the exam (which is why I like this blog in the first place ).

Glenn

The reason the Fourier transform of 1+sin(t) seems to be blowing up is because it does… The Fourier transform of a pure Fourier mode will always just be a delta function centered around the appropriate frequency. In the case of the zero frequency component, we expect zero anywhere away from zero, but an infinitely thin spike around zero.

Glenn,

I should have mentioned the 1 cycle issue. Here’s the explanation you are looking for (I hope). Since Sin and Cos are periodic, the integral over one cycle is exactly the same as the integral over an infinite number of cycles. Also, since the integral 1+sin(t)dt evaluates to t-cos(t), then divide by t to get 1-cos(t)/t. In the limit of infinity, this clearly becomes exactly equal to 1 – not to mention that cos(t) can never exceed one anyway, so this integral can never blow up – at least not with real valued t. If t is complex, I’m not sure what may happen. Why Maxima can’t cope with this probably has something to do with how it deals with the definition of infinity. Also, if I remember the deatils, the 1/p issue has to do with changing the limits of the integration to cover exactly one cycle. It is essentially the same as integrating from -2Pi to +2Pi. You might also consider forgetting about the negative frequency part of the spectrum. For all real valued data (that is, all real data!) it is exacly the mirror image of the positive spectrum anyway,

Daniel,

Are you sure about this? I’ve done a lot of fourier analysis on single frequency sine waves with and without a DC offset and indeed, the result is always a spike at the fundamental frequency of the sine wave and if there is a DC offset, another at the origin.However, these are not of infinite amplitude – quite the contrary, the heights are always exactly equal to the amplitude of the sine wave and it’s DC component. If this were not to be the case, the Fourier transform would not really be very useful for AC signal analysis. I suspect that you are thinking about some other interesting property of the transform and I would like to have you clarify what you are thinking about – perhaps the transform of the delta function?

I’d be happy to explain myself. I say the Fourier Transform of has three spikes, one at and one at both and respectively. Namely, for

If you don’t buy this, well, let’s just check it. According to the definition given at the beginning of the post of the Inverse Fourier Transform, we have

Then when we perform the integration, the delta functions yield the integrand evaluated at the value of s that makes the argument of that delta function zero. This gives

as desired.

Daniel,

Don’t get me wrong. It is not at all that I disagreed with your assertions, especially since they are formally correct in every way. They are also really cool and insightful and your clarification is very adequate,.The confusion centers arount the traditional use of the delta function in the time domain as an infinitely high pulse of zero duration whose integral =1. Also, invoking this interpretation involves understanding a lot of really difficult math involving distributions. etc. I am also a little preplexed by the use of “s”, usually reserved for the complex variable of integration of the LaPlace transform. My only intent is to help clarify the workings of the Fourier concept using simple, approachable math.

I think I can answer that question also. When the frequency domain is discrete, it makes sense to talk about non-infinite amounts of each component, as you describe. The trouble is, when the frequency domain is continuous, it makes less sense to talk about the amount at each frequency, and a “amount density” is more applicable. After all, in the real world there is not really such thing as a pure sine tone; everything has some width in frequency space. But if a finite width has noninfinitesimal “amounts” at every frequency, then the total amount is infinite, which makes no sense. This is the same principle why discussing the mass of an object in detail requires a notion of a local mass density, because if every POINT in the object had its own noninfinitesimal mass, the whole thing would have infinite mass. The Dirac delta is a formal way to revive the concept of a pure sine frequency even after we have evolved to the notion of densities. The Dirac delta is the representation of a “point mass” in the “density” way of thinking about things.

I think what you said about the height of the transform being equal to the amplitude is correct in the discrete frequency interpretation, because there densities DON’T make sense, while “amounts” do.

“But if a finite width has noninfinitesimal “amounts” at every frequency, then the total amount is infinite, which makes no sense”. The problem with this statement is that the width is finite and therefore there are only a finite number of finite amounts and the sum is therefore finite! If I recall my history,this is precisely the polemic that raged for years regarging whether in the limit, the differential becomes vanishingly small on the one hand or 0 on the other.. The point was that as the slice becomes smaller and smaller it’s contribution also becomes smaller, and in the limit, the sum converges on the integral. The argument is whether an infinite number of infintely small pieces totals up to a finite value. Certainly we know that when we integrate a simple function that the answer almost always gives us the area bounded by the curve, not an infinite value, and in this regard, for all practical considerations it does not seem to matter if we consider that the differential truly reaches 0 in the limit or not.I suppose that we could argue about this for years, just as mathematicians did in the 19th century, However, it appears that Paul Dirac must have finally resolved this debate with the invention of the Delta Function. In the interest of all the other readers of this posting, I think we should put the whole matter to rest. At least that’s what I am going to do!

Yes, what you are saying is correct, but the “amounts” have to tend toward zero as the “pieces” become smaller to give a finite result. I am just explaining why setting the amount at each piece to a constant (non infinitesimal) would give trouble.

Goodness me, what a splendid article!

@Yves: It would be great if you could post a link which explains better (no sarcastic tone in this line). It would genuinely benefit the many other people who also feel this explanation is not so good. Kalid may include few points from that link to make this article better.

Seriously, can we have you education minister, for the whole world? okthnx

a) I love you.

b) I basically hate practically all my math teachers, for the destruction they have spread in mine, and everybody else’s mind.

Math is as easy as pie! but needs someone to bake it as good as you did!

Great!!

Congra!

I had asked Kalid about the Fourier Transform a while back and he had emailed a great brief explanation. I just returned to this site to see whether there were any updates and I’m happy to see that the Fourier Transform is on here. This is a fantastic website!

Thanks Claude!

Hi Genius,

Thanks for the article ,It was awesome like always but i have a doubt.What does negative values in time mean like -1 the graph is always positive in x and y value is just projection of point in x so i can’t get negative meaning of time

I just figured out how the transform works on my own. I think its “better explained” by showing how multiplying f(t) by e^iwt is really rotating in the complex plane with frequency w/2pi, and the larger the value you get integrating this over all time, the better f(t) “matched the rythm of w”. Further more, depending on where in e^iwt’s phase f(t) keeps getting bigger at periodically, that will be contributing the most to the fourier transform’s complex value. So the final value, the sum over all time of f(t)’s complex position when rotated by multiplication with e^iwt, tells you about the phase and magnitude of the match-up between w, the rotation speed, and f(t), the function being rotated. Its wierd, its very much a sort of circular integral, where depending on w, you get really far from where the value of the integral starts, or depending on how f(t) matches up with the phase of e^iwt, gives the integral’s angle in the complex plane. Its a little mathematical machine, and it is an extremely intuitive one. For instance, why divide by 2*pi? Because that is how much further a rotation in the complex plane moves a value of f(t), it moves it more by a factor of 2*pi.

Hah, just a curious learner here. Negative values in time, for the signal you mean? In this case, if it’s an infinitely-repeating signal (that’s what the Fourier Transform assumes), then -1 means “1 second before the current cycle started, i.e. near the end of of the previous cycle”. Sort of like “-1AM” might mean 11PM of the night before.

Hi Jose, thanks — that’s a really neat interpretation. Yep, it’s almost like a “dot product” where you are seeing how big and overlap you can get (and different phases will have different overlaps).

Wonderful!

Thanks for the explanation.

may be this be silly but can you just brief out the terms in the formula like n,N,k sorry to ask this.

@RR: Thanks

@Satheesh: No problem, just updated the post (the Discovering the Full Transform section)

Hi,

Thanks a lot.Best wishes to reach heights.

The old Yamaha DX synthesizers series used frequency modulation to create, from 4 to 6 sine waveforms, quite complex sounds.

@Angel: Cool background — it seems to only take a few components before the shapes get really intricate.

Is there anyway to visualize orthogonal signals?Or understand it intuitively instead of just saying that their dot product is zero. I’m studying trigonometric fourier series and having a hard time grasping how each multiple of fundamental frequency component acts the same way like orthogonal vectors that when adding them together they doesn’t interfere and you can add frequency components with right amplitudes to the sum and you don’t need to correct already calculated amplitudes when adding a new term.

Is there anyway to visualize orthogonal signals?Or understand it intuitively instead of just saying that their dot product is zero. I’m studying trigonometric fourier series and having a hard time grasping how each multiple of fundamental frequency component acts the same way like orthogonal vectors that when adding them together they doesn’t interfere and you can add frequency components with right amplitudes to the sum and you don’t need to correct already calculated amplitudes when adding a new term.

I just wanted to learn digital signal processing… After a couple of chapters in my dsp book i noticed that i have to study signals and systems first in order to understand fully dsp. It became clear very soon that i need to learn more math especially fourier analysis to make sense of everything in my signals and systems book. I’m on chapter three now in my signals and systems book (fourier series) and it will probably take my whole life to get to a fourth.

This could not get better. I have been trying to understand this concept on my own and it has been a long difficult task. But with this post of yours, my life is easy now. Keep up the good work man!

The part I missed on the first 2 animations– the values listed beside “time” are amplitude values, while the timing is implied as divisions of the 1hz cycle.

Further down I was able to use context clues. overall, EXTREMELY HELPFUL

Also: The amplitude of the waveform corresponds to the X value on the circle, as opposed to the Y value like every other example i’ve seen.

I realized it doesn’t matter which you choose, it is just a 90 degree phase shift. Because its a damn circle and X and Y are perpendicular.

This is probably really

obvious to you, but it gave me some trouble. Now i have a broader understanding.

Sorry for the 3 separate comments

Where were you when I got my BSEE!! Great explanation.

@Hamppi: I see orthogonal signals as ones whose net “overlap” or contribution to the other is entirely wiped out when you multiply them piece-by-piece.

Imagine two signals driving a car. One controls the speed, the other controls the direction. When the speed is at max, the direction might be null (no direction, the brakes). And when the direction is north, the speed might be null (no speed, the brakes). Sometimes they are both on (North at 10mph, or South at 10mph). Over all time though, the car does not move, because the sum of all contributions cancels.

@Akshar: Thank you!

@Ben: Great feedback, I really like knowing which parts can be clarified. I’ll update the article to make your feedback more clear. Thanks!

@Vic: Glad you enjoyed it

thank you very much for your help!. I want some solved problems

I was struggling with Fourier for quite some time.

Wikipedia and other web based explanations are way too complicated for my rudimentary knowledge – and thus, useless.

Thanks for explaining a difficult concept so elegantly.

The metaphors /analogies were excellent while the animations are superb !

Would you please be kind enough and consider doing the same magic and explain the concept of (Claude) Shannon Entropy ? That’s another painful concept to grasp.

Thanks

A. Scarlat MD

@A. Scarlat MD: Really glad it clicked, thanks for the note! Yes, often times people jump into extremely technical discussions of math without laying an intuitive foundation. I’d like to do more signal processing posts later on :).

Very complicated explanation.

Is this presentation targeted for persons already familiar with Fourier Series?

Think With Circles, Not Just Sinusoids:

What is a circle? Just a circle itself? A sinusoid?, a Complex exponential? or vice versa. Why not considering a circle the son of a cone? Or maybe a circle is just a straight line for bug living in an infinite radius circle.

Thank you very much for this work sharing your insights, there has been very practice for my math career, keep going!

I wonder why most books about periodic phenomena most of the time instead of using circles, use a trigonometric description or even more , a complex exponential description?

How we multiply a circle (representing AC electrical current) by another circle (representing a AC alternating “voltage”) for finding for example the instantaneus AC power. So in other words what is the geometric picture of this two circles multiplied together?

I wonder what the circle based description would be for a two dimensional Fourier transform?

If we have sinusoidal AC voltages and currents, how do we multiply the corresponding two circles for finding the instantaneus AC power? What is the geometric picture?,

I wonder why most books use a trigonometric description or even more a complex exponential for playing with the associated math for both theoretical and practical use?

What would be the “circle” for a two or more dimensionsonal Fourier Transform?

@Anon: Glad it was helpful

@Anonymous: Not sure why most books jump to the most technical definition first :). Intuitively, I imagine a circular path, and on that circular path, another circle is traveling [a bit like how the Earth moves around the sun, and the moon moves around the Earth]. The combined effect of the two positions is the net power seen.

FINALLY THIS MAKES SENSE

What is the practical use of this circle view approach in solving practical problems?

For example what is the “circle” output of a linear system for any periodic “circle” input? How we represent the “circle” amplitude response and the “circle” phase response?

What is the “circle” transfer function of a linear system?

Thanks! Really good!

“Click graph the graph to pause/unpause.” –> “Click the graph to pause/unpause.”

Thanks Waldir, just fixed.

After years of trawling the net..;this is one place where I truly understood fourier transform

@Purushottam: Awesome, glad it helped!

Kudos! This is the best ever intuitive presentation of Fourier! And the animations…gr8 work…Thanks for the effort…Similar insights on Wavelets might be of gr8 help too…pls consider it….Thanks again…keep it going!!!

This is a work of a an extremely talented and gifted person!!!

Question – i am trying to understand what probability density functions have to do with “cyclicality”?? Because characteristic function of a probability density is Fourier Transform, so it needs to be time and cycle driven, but I just not sure what does cyclicality have to do with probability..

Thank you!!!!!!!!!!!!!!!

@Murugesh: Thanks for the note! Wavelets would be a good follow-up. I need to learn more about them.

@Roman: Really appreciate the kind words. Interesting, I don’t know much about probability distribution functions and their relationship to the Fourier Transform, but something to study!

Hello Khalid,

All I have to say is that you have put together a wonderful article. Your style of writing immensely helps in removing the apprehension in the mind of the reader of having to deal with a complex topic.

I am an Image Processing/Computer Vision enthusiast. I plan to write articles in this domain the help students and professionals maneuver complex topics in these subjects by presenting them in a easy to grasp manner

My article on Fourier Transforms @ http://jasexplains.blogspot.in/ is the first write-up. Would be very thankful if you can provide your feedback.

JAS

Hi Kalid,

I am myself writing my own website with math/signal processing/electronics content and, although I am probably not doing it as well as you are, I do believe these complex subjects can be explained in a simple way. This explanation of the Fourier Transform is an excellent example of it. Thanks.

This is golden. Thank you.

I can’t comment on the rigor or accuracy, but in my view this article is absolutely brilliant.

Please write some textbooks.

Wonderful and revelatory stuff – you make learning it a delightful experience with all the visual metaphors and animations gradually building to the abstract formulas. what a rarity – maths taught in a human way! I’ve been trying to grok the fourier transform for months with little success outside of the basic concept that it decomposes a signal into frequencies. The formulas themselves just confused me. Now i really feel I have a handle on it.

Thank you for the effort in making this .

Hope everybody who gets swamped in this domain comes here.

I like your site. This is the way teaching math should be done, in order for anybody to “get” it.

Simple thanks.

@JAS: Glad you’re enjoying it! Yep, part of writing is getting in the head of the reader and gently going down the path, vs. blasting people with all the details up front :). I’ll check out your article later today.

@Hugo: Thanks for the note! I love hearing about other people doing their explanations. Everyone has a different style, so looking forward to checking out yours.

@zenbowman: More than welcome.

@Burke: Thanks! Hoping to do some more material on Calculus, Trig, etc. organized into a book. Stay tuned…

@Tim: Thanks so much — exactly, why can’t we be *human beings* when talking about math? Sure, math can be written down in a way that can be used by machines, but it doesn’t mean we have to think and talk like them. Let’s use metaphors/visualizations to make the rigorous proofs more palatable.

@andeww, Erti-Chris: Thanks!

This is awesome! Nicely intuitive.

Better explained is great service to all “scratch heads” who badly wanno feel the concepts behind these great scientific discoveries but unfortunately are somewhere caught tangled.. ………….. It takes gr8 effort and flair to be consistent and maintain this network of better explained!! Thank you…. I have a question to this article…the first cosine wave we simulate from a circular motion and the sine wave in the referral link provided, vary in explaining the amplitude….the link has an extra perpendicular line dropping from the revolving “radius head” taken to be the amplitude…i clearly understand the amplitude concept there…. but the cos signal in this article gives a different explanation for the amplitude…( u had mentioned to turn the circle by 90 degree mentally which i fail to comprehend…) i am probably not in the right perspective…

sthyusr

I didn’t enjoy this article as much as the others. This is because the recipe analogy didn’t feel intuitive. If anyone is having difficulties processing this, I highly recommend reading James’ http://practicalcryptography.com/miscellaneous/machine-learning/intuitive-guide-discrete-fourier-transform/. It’s way more verbose and more intuitive (if you understand simple statistic concepts like correlation and variance).

The analogy is rather out-of-place, confusing and seems like an unnecessary detour. Most important of all, the author seems to lack primary insight on the subject himself. Smoothie is a whole and its ingredients are parts. It is not the same with signals at all. They are all whole in their own domain. The analogy is totally misplaced and the information provided only partly correct. The key idea of FT – change of variable – is not emphasized at all. Only well informed people should be allowed to author such articles.

That said, there are a couple of good insights for new learners – 1. decomposition of a signal into other signals, though that hardly warrants such a confusing and misplaced analogy and 2. representation of complex numbers on the z-plane, though this may not be the best place for such a long discussion on that.

@Amit,

What a shame that some feel the need to squelch the brilliance of others, presumably to bolster their own inadequacies.

The ability to recognize an analogy like this does not demonstrate a lack of insight, it proves the author’s ability to understand the concept at an intuitive level– a task which is much more challenging and profound than merely memorizing equations.

To this end, I am confounded by your own statement that the smoothie is not an apt analogy. We can both agree that a smoothie is a ‘whole’ while the ingredients are ‘parts’. But that does not preclude the ingredients themselves from being whole on their own. Before berries are thrown in the blender, they are just that: berries, which are themselves a whole. Regardless, this distinction is primarily one of taste– the important observation is that a signal can be represented as a sum of Fourier modes in the same way that smoothies can be represented as a union of ingredients. The features of this analogy carry through quite naturally, and the aspects that do not are clearly addressed by the author.

My next concern is that you object that the author does not address the concept of ‘change of variable': “The key idea of FT – change of variable – is not emphasized at all.” However, the author very clearly mentions this in the very first section after the introduction “From Smoothie to Recipe”:

“A math transformation is a change of perspective. We change our notion of quantity from single items”

In the very next sentence of your comment you mention that “Only well informed people should be allowed to author such articles.” Judging by the fact that you clearly didn’t read (or worse, didn’t understand) the author’s mention of change of variables, I think I will modify your assertion: “Only people who read (and are capable of understanding) the article should be allowed to post incindiary remarks regarding the article’s validity”.

I applaud the author’s work in compiling this article, as I think it does a very good job at laying down the key ideas to newcomers of Fourier Analysis, and manages to motivate the equations intuitively instead of simply asserting them.

On that note, I am saddened that this article did not meet its mark for you.

Kalid, I love this, it’s brilliant. I’ve forwarded it to my nephew who is a non-verbal autistic 10-year-old with an IQ of 138, the ability to give you the day of the week for any date, and the ability to read a page of text if you just wave it at him. I feel we might hear more of him in the future.

I love this: “Wow, we’re finally seeing the source code (DNA) behind previously confusing ideas”. I’m applying your clear nuts-and-bolts approach to the atheist morality problem. I hope you will hear more of me in the future. I will keep this article as an example of how intellectual work should be done.

Hi Simon, thanks for the note — hope your nephew enjoys it :). Really appreciate the kind words, I hope the strategy of finding specific examples to illuminate abstract concepts gets more traction. It’s a spiral of theory, practice, theory, practice…

Those animations are AMAZING. Mad mad props. But I don’t really get how the time points are spaced…

“The time points are spaced at the fastest frequency. A 1Hz signal needs 2 time points for a start and stop (a single data point doesn’t have a frequency). The time values [1 -1] shows the amplitude at these equally-spaced intervals.”

Like for a 1 Hz signal why are you measuring at 2 points, for a 2 Hz signal at 3 points, for a 3 Hz signal at 4 points and so on? Does this have something to do with the Nyquist-Shannon sampling theorem?

Hi Niko, great question. Each animation is over the course of 1 second. If you are specifying a 0Hz (constant) component, then a single value is fine, since it’ll be the same throughout.

If you are analyzing a 1Hz signal inside that interval, you just need a measurement at the beginning and halfway (at 0.0 and 0.5 seconds) to make a determination of its strength. If you only had the measurement at the beginning (0.0 seconds) you wouldn’t know how strong the 1Hz signal was halfway, when it was completing its cycle.

If you are trying to measure a 2Hz cycle (which goes up and down twice during the period), then you need at least 2 measurements beyond the starting one (so at 0.0, 0.333, and 0.666 seconds) to specify its behavior. Yep, this is related to the sampling theorems, I’ll need a follow-up on that and build up my own deeper intuition :).

Kalid, could you possibly tell us what software you use to create these animations? How do you accomplish these?

@Pi: Sure thing. I’m using Javascript and the HTML5 Canvas tag to make the animations. You can open http://betterexplained.com/examples/fourier/?cycles=0,1 and do View Source to see the code. The details of how to do web programming will probably need a few more articles though!

Question from a reader:

I was looking through your material on fourier transform and its by far the best explanation I have found anywhere. I spent a few days reading this and I understand everything except for one hiccup. Could u explain why there is the 1/N factor in the second equation? If you take a simple example, at t = 0, the formula should spit out the sum of strengths, but instead it spits out the average. Can you please lead me on the right track?

Thanks!

Abhi

—–

Awesome, glad you enjoyed it! Great question about the 1/N term. There are several versions of the Fourier Transform, they key is realizing you need to average the strengths somewhere along the way when you apply the forward transform and then the reverse. If f(x) is the forward transform and F(x) is the reverse, then you can have:

f(x) = find the components

F(x) = average them, and recombine

or

f(x) = find the components, and average them

F(x) = recombine

or

f(x) = find the components, and apply a 1/sqrt(N) factor

F(x) = recombine, and apply a 1/sqrt(N) factor

Either way, after doing f(F(x)) or F(f(x)), i.e. apply the forward and reverse transforms, you need a 1/N term. Lots of books don’t explain this part!

Ah, reading again, your question is *why* is the average needed? Good question. If you have a single instant (a spike in time like (1 0 0 0 0 0 …)), then its magnitude should be shared among every possible frequency (which can claim it?). In other words, the frequency strengths would be (1/n 1/n 1/n 1/n 1/n…). A complete signal is just a series of instants, and its strength is averaged among every possbile frequency (however, each frequency has a phase shift, which increases for each instant, and may result in no “net” strength at a given frequency; still, having 0 because you had 1 and -1 constructively interfere is intuitively different from having 0 because there was no activity at all!).

Hey Kalid great work on this one. I started learning about EEG signal analysis and the Fourier tranformation comes up constantly. I never heard of it before and for such a beginner this is a great, very helpful, article.

However to better understand everything about what you said I have a couple questions which I hope you can answer:

1) Why is the strenght (amplitude) in every example 1? In reality, is the signal not comprised of waves of varying amplitude?

2) In the interactive graphs, why does the time slot change its value when the amplitude (strenght) of the wave is changed from 1 to a bigger number? As I can tell the values “time” slot is giving us are saying at which point in time we do the measurement, but why does it change?

3)Does the Fourier transformation get the number of frequencies that is equal to the number of samples taken in a given time period that is being analyised?

4)Can we get a frequency from a Fourier Transformation that is a decimal number for example a frequency of 4.5 Hz?

Thanks, and I hope you keep making these!!

Hi Matija, glad it helped

1) Actually, the amplitudes don’t need to be 1.0 (for example: http://imgur.com/11VKmdJ)

2) The time slot values is the strength of the signal. For example, seeing [1 2 3 4] on the time side means “The signal starts with strength 1. At the next intervals it has strength 2, then 3, then 4″. So if you double the amplitude of all the components, you’ll double the amplitudes of all the time slots.

3) Yep :). Think of it like this: N frequencies and N time samples convey the same information about the signal (it’s like changing coordinates from the time-domain to the frequency-domain… but either way, you need the same amount of data to represent the signal).

4) If you want fractional frequencies (4.5Hz) and therefore fractional time measurements (1.5 intervals), you need the continuous version of the Fourier transform [not the discrete one]. In math class, when working with analytic functions, you’ll learn the continuous one. But for engineering applications (with quantized time measurements) you’ll use the discrete one, since computers are storing individual data points, not an analytic function.

@Daniel

“What a shame” that the internet allows mediocre people to post any garbage as knowledge and pull it off! I repeat, this article is basically flawed because the analogy does not capture the true essence of the Fourier transform. I understand this article will provide some starting thought for beginners, but that’s pretty much all it should be used for. No doubt, the animations are nice and the article is well-written, but I have problem with the content, and anyone who understands Fourier transform well would have the same problem. It is unfortunate that some people are unable to accept healthy criticism without descending to provocative language.

Amit, your feedback would carry more weight if 1) I claimed this were a math-first encyclopedic article (re-read the intro) and 2) you didn’t purport to be the arbiter of what could or could not be written on the matter.

I don’t know of any factual errors, but am happy to correct them. Stylistically, it’s your opinion that the ideal introduction to the transform lies in the mechanics (changing variables) not the “ingredient-first” viewpoint it enables. Let’s agree to differ here.

Well explanation is very good but i m stuck at some points. I don’t understand how the Yellow points are placed and what is meant by 0 Hz at strength 0/1? plz reply asap. Thank u!

Hi Rick, for the yellow intervals, see my reply to Niko on July 7 2013.

0Hz is the speed of the cycle ingredient we’re considering, and the strength is how large it is. A strength of 0 means that cycle ingredient is not present in the signal.

Wow, Thanks a lot, that was very informative and entertaining as well.

I am a retired mathematics teacher and I have to say that one of the most inspired pieces of teaching that I have seen.

Fantastic article. I have a basic maths understanding but am not a mathematician, and have found most descriptions of Fourier transform to be utterly impenetrable. However this article presented exactly what I needed, for my purposes, and the interactive animations helped greatly too. A huge thanks!

I’ve just been finding some other great articles on this site too. Great work!

@Matija: re Q4, I’m not sure if this helps, but the above examples/annotations are all based on an overall time interval of 1 second, and 1Hz, 2Hz, etc. Probably in a real application the overall time interval would not be 1 second, and therefore the frequencies would change accordingly. For example (as I understand it), if the time interval was 1/10th second then the waves would have frequencies of 0Hz, 10Hz, 20Hz, etc, for as many samples as you have in that interval. If the time interval were 2 seconds then you would actually have 0Hz, 0.5Hz, 1Hz, 1.5Hz, etc, which might be of some use in your case. Also bear in mind the article uses the unit “Hz” (and “seconds”) a little loosely in places, which it explains. Hope this helps.

@Whippy: Thanks for the comments! Glad you’re enjoying the site :).

I think there is a mistake where you introduce the formulas in the end. The formula for timepoint and frequency are swapped. The frequency one should contain the 1/N factor, like in the appendix.

Anyhow, thank you so much for this!

Sorry, I didn’t read the part where you said you preferred to move the factor to the inverse. I was just trying to produce the same results as in the article

Hi Thomas, no problem! I should probably clarify that point. In the article, correct, I do the averaging (1/N) in the forward step.

Simply, Brilliant

Thanks Stephen, there’s been a lot of spammers lately (and getting through the anti-spam plugins on the site). They use “compliment spam” which sounds a lot like regular people, I’ll be updating the anti-spam plugins today.

The section where you introduce the animations needs to be clarified. The way it is written confuses me. I don’t understand what is happening to the animation when you change the values in the Cycles and Time box. When you change one it automatically changes the other, why? Why is there always a 0? What does a sentence like “Nothing at 0Hz, 1Hz of strength 1, 2Hz of strength 1″ even mean?

Confused.

Not good at all. I was confused and you added spices into it.

The animation controller are the worst. I didn’t get what the those number were.

sorry.

Great article Kalid. Thanks!

However, while it explains how the signal components are put together, it doesn’t really seem to explain how they can be extracted. I don’t understand the process of isolating the individual frequencies from the mix.

I’m amazed at the number of bored and boring people who think it’s ok to criticise your explanation. They clearly all think they’re very clever, but none of them mention where we can find their superior explanation. This is the internet people, if you don’t like what you see, move on – don’t bore the rest of us with your smug whining!

Thanks Will! Isolating the individual frequencies is tricky. Let me expand on the analogy in the post.

Imagine you have a bunch of toy cars, racing around a circular track. Some are going fast, some are going slow, and our “function” is the total position of all these cars. (Just add up the coordinates for all the cars — that’s our function. We could have an East-West position and North-South position over time.)

Now, how can we find out how many cars are going at, say, 10mph exactly?

We can put a conveyer belt around the track, and run it like a treadmill (against the car’s direction). If this treadmill is going 10mph, then cars going exactly that speed will stay still. The other cars are going either faster or slower, and will continue to circle around the track (over time, their average contribution will be nothing).

Only cars matching the speed of 10mph will stick around, and can be measured. Maybe we see 3 cars going that speed. We might write “The strength of the 10mph speed is 3 cars”.

The Fourier Transform takes the notion that any signal really has a bunch of spinning circular paths inside. If we can take our signal and “run it on a treadmill”, then we can extract the contribution, if any, at every speed (frequency).

The fancy equation e^{i*2*pi*x} is a way to create a circular path of frequency “x”, and we put in a negative sign because it is running backwards, getting e^{-i*2*pi*x}. That is just the treadmill: we multiply in our signal, and the overall result (if anything) is how many cars were at that speed, so to speak.

Hope that helps!

(Btw, appreciate the support. Writing online, you quickly realize you’ll get feedback from all types. I feel no strong obligation to help people who can’t enjoy a freely-provided resource, especially with feedback is as inactionable as “I didn’t get it”).

@Stephen: I’d like to do a video to help walk through the animations. Basically, we have two ways to describe a signal: as a series of points (here’s where the signal was at time 0, 1, 2, 3, 4…) or as a series of ingredients (the signal is made from a 0Hz cycle, a 1Hz cycle, a 2 Hz cycle, etc.).

The cycles have various strengths (how much of each ingredient to use). When you change either side, the widget converts the new values to the other. So, if you add a different set of time points (from 1 1 1 1 to 2 2 2 2, for example) then the corresponding cycle ingredients are adjusted. If you change the cycle ingredients, the time points they lead to are similarly adjusted.

It’s a little tricky, but the upcoming video will help clarify.

Thanks Kalid!

So any circuit / algorithm that wanted to do a Fourier transform effectively has to generate its own set of frequencies and test the signal against those? Or do something equivalent, but probably a bit more efficient maybe.

Perhaps you should offer the whining bores their money back!

Heh — can’t please everyone, and you’ll go crazy trying.

You got it: if you’re trying to compute the Fourier Transform for *every* frequency (i.e., to get the strength of every ingredient) then you need to generate every possible candidate and loop through (if on a computer, for example).

In the real world, there are tricks to avoid this manual iteration. For example:

—–

From http://www.math.hmc.edu/funfacts/ffiles/20003.3.shtml

In fact, your ears do Fourier series automatically! There are little hairs (cilia) in you ears which vibrate at specific (and different) frequencies. When a wave enters your ear, the cilia will vibrate if the wavefunction “contains” any component of the correponding frequency! Because of this, you can distinguish sounds of various pitches!

—-

So, our ear is setup in a way that each hair is tuned to react at different frequencies. As sound comes in, different hairs vibrate (extracting the strength of the pitch it’s detecting). Nature usually has ways to do everything in parallel, while our computers manually crunch through.

Cool! Thanks!

I’m nodding a paragraph in, this is already very exciting and well written.

I have read almost all ur posts and love it!

I dint know what Fourier transform is, one hour ago so this may be stupid question..

Fourier transform has all positive values then how can it give back a signal with negative values?? Similar question shateesh had asked about but ur answer dint satisfy me

Can you add at least one graph of sample Fourier transform for people like me :p

Also do you know about best algorithms to compare Fourier transform in order to compare two sound signal??

Your answer will really be appreciated.

Hi

Great article, especially for somebody like me with no previous Fourier experience.

I have one question that is still confusing for me and it would be great if you could help:

on your animation for basic [0, 1] circles I get time points [1, -1]

When i calculate DFT(1,-1) (using the formula above or use calculator like this:http://calculator-fx.com/calculator/fast-fourier-transform-calculator-fft/1d-discrete-fourier-transform) I get amplitude of 2 for the 1Hz circle. I am expecting this value to be 1 (and not 2). What am I missing?

Thanks for your help!

@Pradip: Great question. The Fourier Transform is based on circular paths, which start at an angle of 0 [neutral], go positive [90 degrees], back to zero [180 degrees], negative [270 degrees], and back to neutral [360].

By aligning and delaying various circular paths, you can reach the negative numbers. In general, you can modify a positive signal by starting each cycle at the opposite side to make it negative. So, if a cycle would have started at 45 degrees, start it at 180 + 45 = 225 degrees instead.

Down the road I’d like to do a follow-up with more sample transforms and graphs, thanks for the suggestion.

@stmag: Great question. There are several variations of the FT and DFT equations, and one decision is where the “1/N” scaling factor is applied.

In the calculator linked, try entering [1 0 0 0 ]. The result is [1 1 1 1], which appears to have magnitude 4, even though the input signal had magnitude 1. It’s fine to list the frequency magnitudes as [1 1 1 1], if you remember you need to apply the 1/4 scaling factor when going back from frequency to time.

In my examples, I apply the scaling factor immediately, so [1 0 0 0] becomes [1/4 1/4 1/4 1/4]. For me, this makes it easier to see that the max magnitude of the [1/4 1/4 1/4 1/4] pattern will be 1, which is the time spike we have. Since the two sequences are shown side by side in the simulation, I think it’d be confusing to have the time segment [1 0 0 0] transform into the cycles [1 1 1 1].

Thanks for the question, it’s something to clarify in the post.

Thanks Kalid. In a case like below where a DTFT pair exists for p_N[n] but you also have another term (constant a raised to power n) included, is there a simple method for finding the DTFT without doing crazy convolution integrals?

h[n] = a^n * p_N[n] where p_N[n] = u[n] – u[n-N] and 0 < a < 1

I am a junior in DFT, actually i just heard of fourier transformation for the first time (shame on me, i know), and tried the wikipedia explanation. and i was like ‘holy cow, am i dumb or is this thing too much for anyone’. Then i found your site… I <3ed it. I cant say i understand everything just yet, ill need to work a lot harder for that. But i did have a very clear theoretical and practical idea of what im about to study now.

Dnx a million, you make science sound like less science.

Nice job with the graphs, and good idea the challenge to try (0, 0, 4, 0). That was the point when i finally really understood

Ohh Thanks for your enlightening. Got the insight and felt happy. Love u man !

Very helpful.. Thank you.

Thanks Pradip, glad it helped!

@eta: Awesome, glad it clicked for you. Wikipedia is a good reference to *remember* something you’ve forgotten, but it’s tough going to learn something new (in Math, anyway). I have to make sure I’m not fooling myself by trying simple examples and checking the intuitive result meets the actual one. Thanks for letting me know the examples helped.

Hi, thanks for this, it helps a lot. But there is a peculiarity:

“A 1Hz cycle goes 1 revolution in the entire 4 seconds, so a 1-second delay is a quarter-turn. Phase shift it 90 degrees backwards (-90) and it gets to phase=0, the max value, at t=1″

Surely a 0.25Hz cycle goes one revolution in 4 seconds?

@gparley: Thanks, you are correct. I was very loose with my terminology, to avoid the need for decimals.

If a signal had 4 data points (a b c d), I wanted to imagine scaling it up so it took 4 seconds of time to complete. A cycle that would have complete 1/4 of the entire signal each step (.25Hz) could be seen as a “1Hz” signal that went through a data point per second (a, b, c, d).

Similarly, something which completed half the cycle each step (.50) would be a “2Hz” signal which ran through 2 positions per second (a, c, a, c). This is a mental conversion I was running in my head, and I need to clarify this part, thanks!

you misspelled “intution”

Thanks, just fixed up.

Suddenly I discovered the meaning of your site

to make money isnt it?

there you go

you do give some insights Im’ not saying the opposite

but alot of it is hogwash you can find it in many other books

but for pure robots as you say its useful it dazzles

maybe you are the Conway of explanations

@aristogeit: I guarantee you, there’s more effective ways to make money online than through a math blog :). My goal is to help people grok the ideas I struggled with.

@aristogeit: go read those books why to visit this blog and help him make more money if you think that way. Don’t waste your precious time in commenting here. Next time we would take permission from you whether to write blog or not.

Hi,

I just made a 2D fft filtering tool on my website, you can mask off regions of the spectrum as a filter and see the effects by performing an iFFT on the spectrum

http://www.ejectamenta.com/Imaging-Experiments/fourierimagefiltering.html

Thank You.

From what i have seen so far(not too much) this is the best possible way to explain “Fourier transform”. And i must say you did the best.

Thank you again to explain it so clearly.

@Dave: Cool demo, thanks!

@Saif: glad it helped!

Hi

Trying to understand your animation – the first one (http://treeblurb.com/dev_math/sin_canv00.html)

On r.h.s. you have a cosine wave which is 1 period long and goes from 1 to -1. And I assume on the l.h.s. you are plotting the values from it on the circle. But how do you get the circle. If you just have a cosine wave, you will oscillate along the x-axis. Don’t you need the sum of cosine+sine to go into a circle ?

Thanks

Asif

Hi Asif, actually that’s not my animation, but the one that inspired my own.

The plot is actually of the height on the circle as we traverse it at a constant speed, so it’s a sine wave. Sine and cosine can be defined on the unit circle, see http://betterexplained.com/articles/intuitive-trigonometry for more. Hope that helps!

A very good explanation, but I wonder if it might be a bit too oversimplified in places? Simplification is good but i think calling them position (0 1 2 3) and then recycling arabic numerals for many other purposes just gets confusing after a while.

Great explanation!

Just a smaalll request….it would be really helpful if you can do a blog on different distributions…poisson, exponential, etc…intution to these would be great.

Hi Shweta, glad you liked it. Thanks for the suggestion — I’d like to do more on probability down the road.

very very appetising

” The yellow dots are when we actually measure the signal. With 3 cycles defined (0Hz, 1Hz, 2Hz), each dot is 1/3 of the way through the signal. ” — Why is the signal measured only 1/3 of the way ? Why not at any other points ?

Hi Ravi, good question. We need to make measurements quickly enough to capture the fastest-moving signal. Start off with a 0Hz signal, which is constant.

How many measurements do you need? Just 1. Measuring at the beginning will give enough information since it’s a constant value.

Now, how about a cycle which repeats once during the signal? (The 1Hz component). We need to measure at the beginning (t=0) and halfway through (t=1/2). Why halfway?

First, we want our samples to be evenly spaced, but also, we need two measurements to describe the behavior of that 1Hz cycle. Having a single data point at t=0 doesn’t let us fit a curve to it, we need two points to “lock in” the cycle (many different 1Hz cycles can have the same value at t=0, but have different phase offsets).

A 2Hz cycle is similar: it repeats twice during the interval. We get the starting point (t=0) and two other data points (t=1/3 and t=2/3) to lock in the phase cycle of this 2Hz signal. Eventualy I’d like to do a follow-up to explain this more, but the main idea is if you have a fast-moving signal, you need more data points to catch (and describe) its behavior.

Thanks a lot ! I never understood the fourier before. You really made this topic easy and fun.

Wonderful site! I will be spending more time here.

I appreciate both your use of simple analogies and your disclaimer as to their limitations; I like your raft and river comparison for how far an analogy can take you.

I recently came across a curious discussion of how Fourier transforms may be used in quantum physics to explain how a particle like an electron can appear to be both particle and wave together. I had some trouble visualizing some of the descriptions but this site with the interactive animations pulled it all together quite well for me. Visually seeing how a ‘time pulse’ can be generated from the summation of all possible wave functions helped me visualize there are two equivalent ways to describe the electron:

a) summation of all applicable quantum waveforms derived from an infinite series of Feynman diagrams

b) a ‘chunk’ of probability that appears localized in time and space (particle) but tapers off to nill at greater distances (wave)

To those who doubt the usefulness and need for analogy, I leave you with the words of Erwin Schrodinger:

“If you can not, in the long run, explain what you have been doing, your doing has been worthless.”

Thanks Eric, really appreciate the comment.

Wow, that’s a great analogy with with electron, it’s a way to see how both a probability waveform (Fourier cycle components) and a particle (time spike) can describe the same phenomena — awesome!

Great Schrodinger quote too, if our understanding dies with us, what’s the point?

Really wonderful site!! I recently bumped into the site and read few articles. Each one gave me Aha moment. Thank you for that.

Fourier transform is well explained , but I have question about -ve sign in front of ‘i’ in forward transform. From your article on imaginary number I learned that negative ‘i’ is clock wise rotation . In animation we see all circles going CCW which is natural for increasing degrees , but ‘i’ is negative. Why?

Also why ‘i’ is positive for reverse transform

This is great explanation for those who struggle with math and want to click without being a math guru. The part I struggle the most with is seeing a sound as a whole in the time domain, sampling it and applying the ft. Let’s say the word “hello” is sent over the air and each letter corresponds to specific frequency , amplitude and phase: (made up example)

H – 5hz

E – 28hz

L – 100hz

L – 100hz

O – 330hz

Assumption is that the word hello lasts exactly 1second.

How does this word looks in the time domain graph? Would we have to divide whole 1second into every hz value and spread out accordingly? For example 1/5 , 1/28 , etc.

If above is true the next step would be to sample the time domain?

Let’s say we sample at 600hz?

What does the sample contain? Does it contain every amplitude from every frequency at sampling time or it’s value is the result of then FT? What is the sensor device that can sense all those different frequency to allow sampling, ft and so on. How this device knows the difference between 10hz and let’s say 13000hz?

I understand that ft converts all signals into one but above drives my brain crazy.

Just to add up to my question.

Is the signal coming to microphone (the magic devices I though about in my question) already a sum of all signals within the frequency range of the microphone? In other words is the sound coming to mic the total of all frequencies that could be constructed via FT if we would know every frequency value?

Hi Kaild,

Firstly, congratulations on a well written article. I love the idea behind the site. If I understand you correctly any signal is a series of time spikes, whose frequencies are phase shifted to produce constructive interference at each spike.

However, I tried computing the signal (4,4,0,0) using the method you describe in the full analysis section and my 1hz term gave me an amplitude of 2 (and not 1.41 as given by the graph) ie, 1hz=4/4:0 4/4:-90 0/4:180 0/4:90 = 2:180.

I’m obviously missing something here (and godamit I thought I had it!)

Kind regards. B

@Pradeep Maskeri

Good observation and question. You’re putting some concepts together well to notice the negative power of i and think it should be a CW rotation.

Let me see of I can fill in some of the details.

The Fourier Transform (FT) is not exactly a rotational transform in the way you are thinking. Instead the FT takes one thing that can have an associated idea of rotation, and transforms it to another thing that can also have an associated idea of rotation. The FT does not take one complex number and transform it to give one complex number that has been rotated, instead it takes one method of representing a complicated bunch of stuff and transforms it to give a different description of the same stuff. The forward and reverse transform then are not forward and reverse rotations of a complex number, but rather the following:

– forward, start with a bunch of basic things (sin and cos) turn them into one complicated thing (composite waveform of arbitrary shape)

– reverse, start with one complicated thing and turn it into a bunch of simple things.

Hope this helps.

Eric V

@Bart

Your second question points toward the answer to some of the missteps in the first question.

Please don’t be offended by use use of the word ‘missteps’. I’ve made them a plenty and will make more. In the physical sciences it is a beautiful thing to make missteps and wrong guesses, greater still to voice them and ask questions. It demonstrates growth.

I can answer your question by telling you a thing that I claim is true. I only warn you ahead of time that it’s kind of a lie. Imagine the chagrin of the poor souls who came up with the corpuscular theory of light (http://en.wikipedia.org/wiki/Corpuscular_theory_of_light)

only to learn it’s all wrong, light is a wave not a particle. Then along comes quantum physics and tells us it is a particle, absolutely it’s a particle. We know this because the equations that govern it are, well, wave equations… but I digress.

Here is the great lie I have to tell you that, for now, is “true”.

You are right, the sound arriving at the microphone is already the sum of all frequencies. What arrives at the microphone is just a single pressure wave with a complicated shape, not a whole bunch of sin and cos waves. The Fourier Transform (FT) just lets us look at it as if it were a bunch of sin and cos waves. Then we can perform some tricky math with it. We can send it through a computer and do all sorts of jazzy things like take an old Parlophone mono recording of a concert with a rude telephone ringing in the background and remove just that sound. I saw a recording engineer at Abbey Roads studio do this with some pretty fancy software, blew my mind!

You also start asking, “What is the sensor device that can sense all those different frequency to allow sampling”? For a lovely game of chasing rabbits down holes, go ahead and see what Wikipedia has to say about the Nyquist Sampling Theorem. It’s good fun and a lovely headache. Let me see if I can shorten it. Lets say you have the setup you’ve provided, a human voice saying the word hello, and that sound hits a microphone. We want to record it to play back later, but we want to record it digitally! Start with what the mic gives us, an electric voltage wave that has the same complicated shape as the pressure wave that hit the mic. Take a ‘sample’ to see how strong the voltage is every so often. The strength will just get converted to a number (this is a binary number that can be stored digitally). As the voltage varies from -100% to +100% the digital number that comes out of our ADC (analog to digital converter) is a number between 0 and 256 (for 8 bit encoding). But how often is ‘every so often’? By the Nyquist Theorem, twice for each cycle of the highest frequency we want to represent. Humans have a tough time hearing any sound at a frequency higher than 20K Hz (repeats every 0.05ms). So you take 2 samples every 0.05ms. Each sample is an 8 bit number. Store it as a file. To play it back; read the first 8 bits, convert it in a DAC (3 guesses what DAC stands for) to a voltage between -2V and +2V, send it to an amp then speakers, repeat for each subsequent group of 8 bits. I left out a detail or two. This lets you faithfully record a sound up to 20kHz. If a higher frequency sound hit the mic our sampling would have missed it.

As for my ‘true’ lie… the Fourier Transform isn’t just about sound. It can be about anything that is represented as a wave (like a quantum wave function for an electron, or an atom, or a cat, or the universe). It lets us take a ‘thing’ that we want to look at and express it in one of 2 ways:

-single waveform complicated shape

-many waveforms simple shape

From the standpoint of sound wave we like to think the ‘real’ thing is the single complicated waveform. The other mess of an infinite number of basic shaped sin and cos waves are not really ‘real’ they are just a convenient mathematic way to treat the object. If the wave is the quantum waveform of a photon we may like to view it the same way. The photon is a ‘real’ object. The ‘real’ part is the single quantum waveform, or is it? However, the single waveform can have a position operator applied to it, to ask the question “where are you, oh little photon?”. Likewise it can have a momentum operator performed on it to ask the question “how fast are you going?” Werner Heisenberg discovered an interesting relationship between those two tasks. Yes it was math alone that caused him to propose his Uncertainty Principle. In this case the sum of all the ‘little’ equations (where, when, how fast, how much charge, how much mass, etc.) may seem to be more real than just the composite wave function, which really is just a probability cloud of nothingness.

The Fourier Transform just gives us a way to go back and forth between the parts, and the composite. Its up to us to decide which version we want to work with.

Thanks Eric for the thoughtful comments (as always!)

@Billy: Great question. When combining the spikes for (4, 0, 0, 0) and (0, 4, 0, 0) we need to take the phase shifts into account.

The first spike is at t=0 and has components without any phase: 1, 1, 1, 1.

The second spike occurs at t=1 and needs to adjust its components to: 1, 1:-90, 1:-180, 1:-270

What happens when we combine the ingredients?

The terms that are perfectly in phase (aligned) can just be added, so the 0Hz component becomes 2:

2 x x x

But how about the 1Hz component? In the first spike it has phase of 0, in the second spike it has a phase of -90. This is like going 1 mile East (0 degrees) then 1 mile South (-90). The result is going sqrt(1^2 + 1^2) = sqrt(2) = 1.41 at a SouthEast direction (-45 degrees).

So, we get

2 1.41:-45 x x

The other terms can be worked out similarly. Great question and something I’d like to clarify: the cycle ingredients can be “out of sync” (due to their phase) and may not combine simply. They can even cancel when fully out of phase (1:-90 and 1:+90 will cancel out and give nothing, like going 1 mile North then 1 mile South).

Stumbled on to better explained last night. Really enjoying it.

My ah ha moment with Fourier is when I looked at the trig identities and realised that two sinusoids multiplied together resulted in another sinusoid centered on the x axis, unless they were the same frequency, in which case the result would be all above the x-axis, (basic orthogonality). This meant that if I summed the product I would always get zero, unless I had the ‘key’ frequency then I would get a value. So Fourier decomposition was just repeatedly multiplying a signal by different sinusoids, ‘secret keys’, to ‘extract’ out its contribution.

Hello everyone,i am doing my project in image processing.. i have done video segmentation using the Fourier transform . I applied 3-D fft on video (gray image(2D)+no of video frames(1D)=3D) and Obtained magnitude and phase spectrum and reconstructed video frames back from the phase spectrum only . i am doing coding part using Matlab software

I have found that moving part pixel intensity values becomes dominant (means its intensity values are increased so much) compared to stationary part intensities in reconstructed frames of original frames .(e.g.in waterfall and traffic on road, water part and moving car’s intensity values are increased respectively compared to the stationary background). i want to know how did this happen?

You didn’t emphasize the basic idea that the Fourier transform is a special case of a phenomenon that takes place in any real vector space with an inner product. Once you get that it’s just not that fancy and it’s only scary because we write it in a scary fashion, life becomes easier.

As a mathematician, I find it much easier to think of L^2 as being orthogonally spanned by the e(nx) functions and taking the Fourier transform is the analog of writing out an unknown vector in coordinates. What’s so hard about that?

This abstract perspective helps you practically too. You become less reliant on formulas since you have a good global understanding of the notion of a Fourier transform. In some sense, you’re rephrasing this when you talk about smoothies but I don’t know how effective the metaphor is.

Huge caveat: I am a mathematician and “math that anyone can understand” is often math that I have a hard time understanding because of the way it’s presented.

Hi AR, thanks for the comment!

My primary learning philosophy is “blurry to sharp” (successive refinement) instead of “full detail, top-to-bottom” (walk through the formal definition, even slowly). My blurry version of the Fourier Transform is that it uses filters to break a whole into parts, much like a smoothie can be separated into constituent ingredients (there’s likely many analogies, but I like smoothies).

To get technical, sure, we’ve projected a function onto an infinite set of orthogonal basis functions defined by e^ix — but to me that’s the *mechanism*, not the goal. The goal was to filter a signal into parts for easy analysis, which can be done via an integral, or perhaps mechanically (our ear essentially runs a mechanical Fourier Transform on the incoming sound waves, and as a result we can hear several sounds simultaneously), and so on. It’s a bit like describing a car as a “horseless carriage” (what it looks like) or an “auto-mobile” (how it behaves — it moves itself) or a “vehicle driven by an internal combustion engine”. The latter is the most specific, but not likely to be the most approachable or helpful to a newcomer.

When learning a topic, I need to understand what it does / why it does it, before the how. From there, I can appreciate both the abstractions and subsequent implementation details. When writing, I basically write for myself — what do I wish I had heard up front? One of the trickiest things when explaining is avoiding the Curse of Knowledge and remembering what it’s like before the concept clicked. After it clicked, hearing “project onto orthogonal basis” is a nice reminder, but before it clicks, it would (for me) have been dutifully accepted but not really internalized. (“Sure, ok, we can hypothetically project a function onto other functions. But do I feel what’s going on? Not really.”) That said, everyone’s goals are different. Appreciate the feedback!

is there anybody to answer my question given in post no.176????????????

Fantastic!

I found this article incredibly helpful as a high school student in need of college-level mathematics concepts. This article helped me understand the basic concept of what the Fourier transform does, and for anyone who needs to know why it works with more math (but still only high school level), I would recommend Stephen’s link to his essay: http://linuxbio.med.buffalo.edu/Fourier/AC_Signal_Processing.html I found it incredibly easy to understand as well as very helpful. One thing about it, though: make sure you keep reading if you don’t understand something, because it is probably fully explained in the next paragraph or two.

Fourier Transform cannot get anymore explicit… And… you made it free… You’ve got a very large heart – never forget that. God bless you!!

Signal,

I suspect that there are several reasons you’ve not received any replies. First thing is that as soon as you move the FFT into 2-dimensional space it moves very quickly away from the core ideas of this thread. Secondly, I think that it is not clear exactly what you are asking. As far as I can tell, what you are doing is 1) taking a time series of images and running a 2D FFT on each. Then 2) throwing away the amplitude data and 3)Inverse transforming the images back into the spatial domain.

The real problem is in the statement of the next part of the problem – to wit: “I have found that moving part pixel intensity values becomes dominant”. I suspect that you are referring to the reverse transformed images. What’s more I suspect that you are also referring to an image by image comparison when specifying increase or decrease.

Anyway, keep in mind that the FFT tells you about periodicity. In 2 dimensions, this means how bits of the image are spaced (and oriented). Think about a picket fence – this would have a very strong “DOT” at a point corresponding to the picket fence’s spacing (i.e., distance from the center in the frequency domain) and orientation (i.e., angle of the radial line connecting the “DOT” to the center) in the original image. Incidentally, there should also be a “DOT” corresponding to the width of each individual picket as well as “DOT”s representing pixel spacing and size.

Now, in the next step you throw away all the data about fixed spacings in the image (the stuff that’s not moving) and keep only the data about stuff whose periodic relationship to the scene has changed (that is, the phase has changed) from image to image (The “moving” stuff), and the wonder why moving abjects are enhanced.

Does this help

In this section on Fourier transforms:

“I could say “2-inch radius, start at 45 degrees, 1 circle per second, go!”. After half a second we should be at the same spot: starting point + amount traveled = 45 + 180 = 225 degrees (on a 2-inch circle

I might be missing something basic, or there is a mistake.

If it is 1 circle per second, then I would say after 1 second we would have completed a circle and be back to the same place or starting point. How, on a circle, would you be back at the same spot after 225 degrees? In half a second at one circle per second I would think we would be 1/2 way around a circle, at a spot opposite where we started.

Thanks for writing this- hope it’s part of a future book. This link might be helpful for those who want to understand it from the frequency perspective:

http://www.dspguru.com/sites/dspguru/files/conv-dsp-tutorial.pdf

@Bob: Ah, that phrase wasn’t clear. I meant that by following the instructions, we’d each be at 225 degrees on our own circles (we’re at the corresponding positions on our own circle).

I’ve clarified the wording, thanks!

@Carl: Thanks!

Hey!

Very nice material. Thank you.

I have noticed a small typo in the Appendix: Projecting Onto Cycles section. You have mixed up the Fourier transform with the inverse Fourier transform

Hey!

Super helpful.

So how would you create a linear trajectory with a sum of sine and cosine graphs, any amplitude?

you might enjoy this website

http://1ucasvb.tumblr.com/page/2

Too good! Fourier transform is more clear to me now than it was ever before QQ

aha!

Jenn Ng

Sorry it took so long to reply but here is how I would answer your question. First, you are proposing to transform a non-periodic function of the form f(t)=At. By definition you can’t do this with the Fourier series being discussed here. You need to use the full integral definition instead. That is, multiply your function by the complex exponential e^-(jwt) and integrate. (That is, integrate Ate^(-jwt) dt). You should get some function of w that is a complex exponential. (w is the radial frequency 2*pi*f). Once you get this, use euler’s formula to re-write the complex exponential as an infinite sum of sines and cosines. This will give you the indefinate integral. Depending on what you want, you will probably need to handle infinities in the integral limits when finding the definate integral – a real pain but doable. Admittedly this is all very tedious but it can be made to work.

Jenn,

As a follow-on, you might be interested to know about the old Maxim that a Square Wave is made up of an infinite number of even harmonics while a Triangle wave is made up of an even number of Odd harmonics. In either case the amplitude of each term decreases as a function of frequency. If you don’t believe it, try graphing the first 10 (even or odd) harmonics. If you get the phase and amplitudes right, you will see a really good approximation of a square wave or a triangle wave emerge as you add harmonics. Even Sin(t)+0.5Sin(2t) will already have a square wave character.

OOPS – That was supposed to be an infinite number of Odd harmonics.

Hello everyone,i have a doubt….

I know that for a given signal, the sampling frequency Fs must be twice or more than maximum frequency of the signal Fm. It is easy to understand the concept for a 1D signal. But I don’t know how to calculate sampling frequency or Nyquist rate for a multidimensional signal like 2D image.So can anyone help me regarding it.???

Fantastic guide, one of the best I’ve read! Thanks much for sharing this.

Ugh how is everyone else understanding this? I got so confused after the applet was introduced..What do the the different paths of the different “motor cars” mean? Are you saying that every wave is a sum of infinitely smaller waves?

someone help

@Jake

“Are you saying that every wave is a sum of infinitely smaller waves?”

Instead of worrying about what one analogy or another means, look to the fundamental nature of a periodic signal and the ideas embodied in Fourier’s conjecture – i.e., that any periodic waveform can be represented as a sum of sine and or cosine waves. So, take some complex periodic waveform. By definition, it must have a period and it must repeat identically in each of these periods. This period is the fundamental frequency. Well if we remove the fundamental what are we left with? The answer is simply all the other frequencies that make up the waveform. Fourier’s methods allow us to pick any one of those frequencies and remove it. Each time we do this the waveform becomes simpler until at last there is only one frequency left. Fourier does not constrain the sizes of those frequency components – only their frequencies.

@Signal

The 2D FFT is admittedly more confusing, but to answer your question about nyquist and sample rate for a 2D fft, in particular with regard to images, you have to think in terms of “spatial frequencies”. For example, how often does some feature repeat and what is the smallest feature that you need to resolve. In an image, sample rate corresponds to the number of pixels in a given spatial unit. So, for example, if you have a mosquito in a picture, and the mosquito fills a space smaller than 2 pixels, it will fall below the Nyquist sampling limit. Indeed, you may see a speck in the image, but there will be no information about the size of that speck – only that it is there. Further, you would need at least 2 pixels covering the smallest feature of the mosquito – say a small stripe on its back or it’s antennae – to resolve these either. So, to summarize, for an image, sampling frequency is pixels per unit length and nyquist defines the resolution limit.

Great article – really helpful and empowering

very nice work!

but if you could provide intuitive explanations about forward FFT that will be great!

The demonstrations here seem to be inverse FFT to me.

Thank you very much!! fallen in love with your brain..

Nice introduction!

Why did you end your tutorial just when you started explaining the math part of the math?

All you’ve done is teach the why. What about the how? That’s the part that’s difficult.

EXCELLENT site! My mind has opened.

I recall my days at secondary school in Wales being taught, parrot-fashion: “The square on the hypotenuse is the sum of the squares on the opposite two sides. Now, get on with it!” – Cue blank looks from us all.

Where were you dude?!!!

I think I will use these lessons for my kids, that is how valuable I think your site is. Well done Sir and thank you for taking the time to make this available.

BTW, I would love to see your insights into Z-Transforms and how to APPLY the damn things! :0)

Andy

You rock!

Bamm!! Your explanation rocks!

Excellent explanation, really really useful. Cheers!

It helps me very much! Up to now, I hardly recognize anyone even my professors as a real teacher. Today, you are the real one. Thank you!

Thanks An!

Awesome!

This is probably the most useful thing I’ve seen on the internet so far. I don’t know I would have been able to understand this sh*t without you. Thanks a lot.

This is really useful. I studied Fourier Transformations thirty years ago as an undergraduate and longed to understand what I was doing!

We used them for Crystallography: a FT of a crystal structure shows you what its x-ray picture will look like… but I still don’t understand why? Can you explain?