How can we quantify that?

The easiest way would be to record a bunch of points as we rotate, and average them to find their midpoint:

It makes sense that the distance of this midpoint from the origin is proportional to the strength of the signal, because as the high points in our signal get higher, they will move the scribble farther away. But what if the signal contains no energy at 3 Hz? Let’s remove the 3 Hz wave and see:

Now there is nothing to pull the scribble off center, and all of the other oscillations tend to (approximately) balance each other out.

This looks promising as a way to detect energy at a given frequency. Time to translate it into math!

For a looping signal of N samples:

Raising e to an imaginary power produces rotation around a unit circle in the complex plane, according to Euler’s formula.

How?

Magic, as far as I can tell. But apparently it’s true.

So this equation is a little different from what we started with. I’ve added a normalization factor of 1/N, and changed the sign of the exponent. I also rearranged the terms slightly for clarity.

This form is normally called the inverse DFT, which is confusing, but apparently the difference between the DFT and IDFT is a matter of convention, and can depend on the application.

So, let’s call that close enough.

Anyway, once you can “see” what’s going on in your head, a lot of the quirks of working with the DFT become much less mysterious.

If you’ve had to work with DFT output before, you may have wondered:

• Why does the first element in the result (k=0) contain the DC offset? Because in that case, our samples don’t spin at all, so all we’re doing is averaging them.
• Why doesn’t the DC offset affect the frequency information? Because adding a constant value to all the samples just makes the whole scribble bigger, which doesn’t affect the midpoint.
• Why does the second half of the output array contain a mirror image of the first half? It’s just our old friend aliasing. When calculating the last element (k=N-1), we’re rotating by (N-1)/N at each step, which is almost all of the way around. This is the same as taking small steps (1/N) in the wrong direction. That’s why the result at (k=N-1) has the same magnitude as (k=1). It’s equivalent to processing a negative frequency of (k=-1).
• Why does a sine wave with amplitude 1.0 come out of the DFT as 0.5? When we spin the sine wave, we get a circle of diameter 1.0, but it’s midpoint is only half that distance away from the origin.
• Where is the other half of the energy then? It’s hiding in the negative frequency part!

Hopefully this was more helpful than confusing.

This article first appeared on #AltDevBlogADay and is used here with kind permission of the author.

• Stuart Riffle is a graphics/systems programmer with 14 years in the industry, whose credits include Madden, Bond, and Need for Speed. His specialties are optimization, rendering, concurrency, and compilers.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.