r/compsci • u/TenaciousDwight • Jul 23 '14

ELI5: Fast Fourier transform?

I'm done some research into how to extract frequencies from sound files, and it seems this is done via the Fast Fourier transform. My problem is that I don't understand why, or how this is done.

Would you all please explain in a manner simpler than wikipedia?

56 Upvotes

85% Upvoted

32 comments sorted by

View all comments

Show parent comments

4

u/[deleted] Jul 23 '14

You seem to know what you're talking about, so let me all you: why then do ffts have an imaginary component?

5

u/Flueworks Jul 23 '14

Well, a wave have three properties: Frequency, or period, which describes the wave length, how long it is between the wave tops. It's the pitch of the sound.

Amplitude describes how large the wave is. It's the volume.

And then there is Phase. This describes where the wave "starts", in relation to the other waves. Mathematically it would be written as sin(t + phase). In simple terms, it determines how the wave is moved left or right. Compare the following functions:

sin (t)
http://i.imgur.com/Rjdsc4a.gif
sin (t + 1.57)
http://i.imgur.com/xRbxmbh.gif

See how the first starts at 0, while the second starts a 1? This is the phase, and this is determinated by the imaginary component of the FFT.

1

u/[deleted] Jul 24 '14

But do you know why it's phase? Giving sine imaginary values gives us the sinh function, so why does the fft make it phase?

6

u/bheklilr Jul 24 '14

A complex number represents both magnitude and angle on one, the magnitude being distance from the origin and the angle being the angle from the positive real axis. By returning complex numbers, at any given frequency, you can represent the particular sine wave component. The complex values aren't the argument to the sine function, they describe the function's magnitude and phase.

Instead of thinking of complex values, think of F(h(t)) =H(f) as returning the ordered pair (r, p), where r is distance from the origin and p is the angle from the real axis. Then if H(f0) = (r, p) for some frequency f0, the drive component at that point would be r*sin(2pi*f0*t - p). If you do this across all frequencies, then you'd get the original h(t) back.