1
$\begingroup$

I found a really intuitive explanation of Discrete Fourier Transform here.

To summarize the author's approach briefly :

  1. What if any signal could be made from circular motion (repeating cycles) ? This is the central theme of Fourier Transform
  2. Every circular path needs a size, speed, and starting angle (amplitude/frequency/phase).
  3. The combined "position" of all the cycles is our signal.

The author provides an interactive visualizer (screenshot below): The cycles are shown on the left and the paths shown on the right. It shows 3 cycles (a cycle of 0 Hz, a cycle of 1 Hz and a cycle of 2 Hz). The paths of the cycles are in green. The combined path (signal) is in blue.

The author says

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).

Why are the dots spaced so ? More generally, if there are $n$ cycles, why is the signal sampled at $n$ points equi-spaced around the circle ?

$\endgroup$
1
$\begingroup$

The "Cycles" entries are the amplitudes of cosine waves of frequency 0Hz, 1Hz and 2Hz respectively, so:

0Hz: $0\cdot\cos(0)$,

1Hz: $1\cdot\cos(2 \pi t)$,

2Hz: $1\cdot\cos(4 \pi t)$

The time values are amplitudes of the resulting sum at specific sample points in time. The time runs over 1 cycle of what in Fourier series analysis is call the fundamental frequency which in this case is 1Hz.

The Discrete Fourier transform is really a Fourier series, so the signal being represented is always periodic and always has a maximum time equal to 1 period of the fundamental frequency which represents one trip around the circle. Every other frequency represented in the Fourier transform is an integer multiple of the Fundamental frequency or represents an integer multiple of trips around the circle.

When computing a discrete Fourier transform a signal is first sampled at some rate that must be higher than the frequencies represented by the transform. For traditional frequency analysis, sampling is always done using uniform spacing. This is called uniform sampling and since it must happen faster than the signal you are representing, you must have more than 1 sample uniformly spaced around your circle. To be more precise, you must sample your signal at least 2 times higher than the highest frequency that you want to represent in your analysis, so for this case the sampling should be a minimum of 4Hz.

A sampling rate of 1 Hz would give you a single yellow dot on the circle at 0 angle (x=1). 2 Hz gives you 2 yellow dots, one at 0 angle and one at $\pi$ (x=1 and x=-1). In this example you should have a minimum of 4 samples to represent the frequencies illustrated, so you should have 4 yellow dots equally spaced around the circle starting at 0.

The circle is usually represented on a complex plain with the vertical axis representing imaginary numbers. If this is done, the corresponding dots correspond to specific times calculated from the complex exponential $\exp(i 2 \pi t)$. With the sample times starting at t=0 and progressing as 0,T/4,T/2,3T/4 (T being the period of the fundamental), the dots correspond to placement around the circle at the angles $0, \frac{\pi}{4}, \frac{\pi}{2},$ and $\frac{3 \pi}{4}$.

$\endgroup$
  • $\begingroup$ In that case, why are there only 3 dots and not 4 ? $\endgroup$ – curryage Apr 19 '14 at 4:21
  • $\begingroup$ Also, from your answer: "A sampling rate of 1 Hz would give you 1 yellow dot on the circle at 0 angle. 1 Hz gives you 2 yellow dots, one at 0 and one at -1." . Did you mean to say dots at x=1 and x=-1 corresponding to angles $0,\pi$ ? $\endgroup$ – curryage Apr 19 '14 at 6:30
  • 1
    $\begingroup$ Thanks for the edit. Looks much better. I should have said x = 1 and -1. I was thinking 0 angle or y=0. I changed that as it makes more sense. Three dots would correspond to 3 samples which is fine for the demonstration, but would not work in practice. I think the choice of 3 samples was made because it results in nice values for the amplitudes (0 -1 -1) or the composite (blue) signal. $\endgroup$ – user2718 Apr 19 '14 at 19:41
  • $\begingroup$ Should say "on the composite (blue) signal." Noticed the typo after 5 minutes expired. Too bad for the time limit on editing comments. $\endgroup$ – user2718 Apr 19 '14 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.