Basic question about fast Fourier transforms.

103 Views Asked by At

If I consider the function $\sin(t)$ evaluated between 0 and 60 (seconds) with $\Delta t = 0.01$.

When I take the fast Fourier transform, the frequency of oscillations can be obtained directly of

$$f = \frac{(\text{Position of the first peak} - 1 )}{60}$$

What happens when the time range changes? For example, obtain the frequency of $\sin(t)$ evaluated between 50 and 60 with $\Delta t = 0.01$. How I can calculate the frequency?

1

There are 1 best solutions below

1
On BEST ANSWER

Short answer: The general formula is given by $$ f = \frac{2\pi k_1}{N\Delta t} $$ where $k_1$ is the position of your first peak (starting with index 0 -- subtract 1 if you are using index 1), $N$ is the number of sample points you are using, and $\Delta t$ is the space between sample points. To see why, we need to look into how the Discrete Fourier Transform actually works.

Long answer: To actually approximate your continuous function $\sin(t)$ in a computer, we take some number of discrete sample points. If we want to do this in some interval $[t_0, t_f]$ (in your case $t_0 = 0$ and $t_f = 60$), we would break up the interval into some evenly spaced grid-points so that $t_n = t_0 + n\Delta t$ where $n = 0, 1, ..., N - 1$ with $N$ as the number of points, and $\Delta t = (t_f - t_0)/N$ the space between your grid-points. Now, call your function $x(t) = \sin(t)$ and we can find some discrete number of outputs corresponding to each $t_n$ input: $x_n = \sin(ft_n)$. Here $f$ is your frequency. Now we may actually use the DFT: $$ X_k = \sum_{n = 0}^{N - 1} x_n e^{-i 2\pi kn/N} $$ where $X_k$ will be the output points of your DFT. In order to make analytic progress plugging in $x_n$, we need to use $\sin$'s relationship to complex exponentials: $$ \sin(ft_n) = \frac{e^{ift_n} - e^{-ift_n}}{2i} $$ Plugging this into the DFT formula yields: \begin{equation} \begin{split} X_k &= \sum_{n = 0}^{N - 1} \left(\frac{e^{ift_n} - e^{-ift_n}}{2i}\right) e^{-i 2\pi kn/N} \\ &= \sum_{n = 0}^{N - 1} \frac{e^{ift_0}}{2i} e^{in(f\Delta t - 2\pi k/N)} - \sum_{n = 0}^{N - 1} \frac{e^{-ift_0}}{2i} e^{in(f\Delta t + 2\pi k/N)} \end{split} \end{equation} where in the second step I have used the definition that $t_n = t_0 + n\Delta t$, as well as some properties of exponentials. Now, it can be shown using a finite geometric series formula that $\sum_{n = 0}^{N - 1} e^{inx}$ will basically vanish unless $x$ is some integer multiple of $2\pi$. This gives us two peak conditions: \begin{equation} \begin{split} f\Delta t - 2\pi k/N = 0 \\ f\Delta t + 2\pi k/N = 2\pi \end{split} \end{equation} These are the only two restrictions because $k$ can only go between $0$ and $N - 1$. Thus, the frequency will be found with the formula \begin{equation} \begin{split} f = \frac{2\pi k_1}{N\Delta t} \\ f = \frac{2\pi}{\Delta t}\left(1 - \frac{k_2}{N}\right) \end{split} \end{equation} where $k_1$ is the first peak, and $k_2$ is the second peak.

An implementation in python can be found here. Note that there is a certain amount of error in the frequency, given that we have discretized the domain. However, you might convince yourself that this error doesn't get too big by messing with the value of $t_0$. Note that I used the function np.abs() whenever I do anything with $X_k$ -- this is just because $X_k$ is complex. This has the effect of just taking the magnitude of $X_k$.