4 ms·

k is the output index (the "bin" in the frequency domain), or the notch in the rotated space in that graphic. Every output frequency coefficient contains a full

by 0x09 13y ago

k is the output index (the "bin" in the frequency domain), or the notch in the rotated space in that graphic. Every output frequency coefficient contains a full sum of the input function, hence a direct translation of that formula is O(n^2) -- which is why the FFT, with O(nlogn) complexity is so important. The graphic doesn't really help show how the analysis itself happens, it just presents the result, which is a series of waves that add up to f. The actual process of obtaining a frequency coefficient from a time-domain function is easy to describe: multiply the function by a (co)sine wave with a particular frequency and sum together the result. But it's not very intuitive why that works until you consider that one period of a sine wave sums to zero. By multiplying the sine with the function, you perturb the shape of the sine with just the amount of energy that the function contains at that given frequency. So that instead of summing to zero, the sum measures "how much" of that particular wave is present. That's Fourier analysis. Fourier synthesis is more easily visualized (I think anyway). Simply multiply a sine wave at each frequency by the corresponding coefficient derived above, and sum those weighted waveforms together elementwise to recover your function.

zokier 13y ago
> But it's not very intuitive why that works until you consider that one period of a sine wave sums to zero. By multiplying the sine with the function, you perturb the shape of the sine with just the amount of energy that the function contains at that given frequency. So that instead of summing to zero, the sum measures "how much" of that particular wave is present. That's Fourier analysis Thank you. This really helped. Based on that explanation, wouldn't the formula be more like: http://www.texpaste.com/n/nphm1fgp http://www.texpaste.com/n/nphm1fgp ? I suppose there is some further magic which allows for phase differences or something.
- 0x09 13y ago
  Right, you need both sine and cosine parts, hence e^ix, in order to fully describe the function. Unless the function is completely odd (or even), in which case the transform really is equivalent to `x[n] * sin(2pik*x/N)` (or cos). To see why imagine analyzing a function W that is just a plain cosine wave (any frequency and amplitude). If we only use the sine part of the Fourier transform, F(W) is indistinguishable from F(-W). In fact both are zero everywhere. Transforms that use only sines or cosines (like the DCT) provide a complete basis by increasing in frequency by only a half cycle (pi) rather than by integer cycles (2pi). Essentially trading half a transform of sines and half a transform of cosines for one transform of half-cosines (or sines).

by 0x09 13y ago

zokier 13y ago

> But it's not very intuitive why that works until you consider that one period of a sine wave sums to zero. By multiplying the sine with the function, you perturb the shape of the sine with just the amount of energy that the function contains at that given frequency. So that instead of summing to zero, the sum measures "how much" of that particular wave is present. That's Fourier analysis Thank you. This really helped. Based on that explanation, wouldn't the formula be more like: http://www.texpaste.com/n/nphm1fgp http://www.texpaste.com/n/nphm1fgp ? I suppose there is some further magic which allows for phase differences or something.

0x09 13y ago
Right, you need both sine and cosine parts, hence e^ix, in order to fully describe the function. Unless the function is completely odd (or even), in which case the transform really is equivalent to `x[n] * sin(2pik*x/N)` (or cos). To see why imagine analyzing a function W that is just a plain cosine wave (any frequency and amplitude). If we only use the sine part of the Fourier transform, F(W) is indistinguishable from F(-W). In fact both are zero everywhere. Transforms that use only sines or cosines (like the DCT) provide a complete basis by increasing in frequency by only a half cycle (pi) rather than by integer cycles (2pi). Essentially trading half a transform of sines and half a transform of cosines for one transform of half-cosines (or sines).