Discrete Fourier Transform

Posted on In Views: Word count in article: 533 Reading time ≈ 2 mins.
Discrete Fourier Transform (DFT) is a linear transform that converts a finite sequence of equally-spaced samples of a function in the time domain into a same-length sequence of equally-spaced samples in the frequency domain, which is a complex-valued function of frequency.

Continuous Fourier Transform

See Fourier Transform.

In brief:

$$f(t)=\sum\limits_{n=-\infty} ^{+\infty}C_ne^{in\omega_0 t}
=\sum\limits_{n=-\infty} ^{+\infty}e^{in\omega_0 t}\frac{1}{T}\int_{0}^T f(t)e^{-in\omega_0 t}dt$$

where $F(\omega)= C _n=\frac{1}{T}\int _{0} ^T f(t)e ^{-in\omega _0 t}dt$ is Fourier Transform.

Discrete Fourier Transform

For $N$ discrete signals sampled at equal intervals in a continuous signal, denoted as $\mathbf{X}=\{x _0, x _1,\cdots, x _{N-1}\}$, assume the sampling interval is $\Delta t=0$ and consider the original sequence has a period $T$. Then, the continuous fourier transform could be converted to DFT as :

$$
\begin{align*}
F _k &= \frac{1}{N\Delta t}\sum\limits _{n=0} ^{N-1}x _{n\Delta t}\cdot e ^{-i(n\omega _0)k\Delta t}\\
&=\frac{1}{N}\sum\limits _{n=0} ^{N-1}x _n\cdot e ^{-i(n2\pi / T)k}\\
&=\frac{1}{N}\sum\limits _{n=0} ^{N-1}x _n\cdot e ^{-i(n2\pi / (N\Delta t))k}\\
&=\frac{1}{N}\sum\limits _{n=0} ^{N-1}x _n\cdot e ^{-i2\pi \frac{k}{N}n}
\end{align*}
$$
However, $\frac{1}{N}$ will make the value too small, so we always remove this term (actually it is moved to the inverse transform):

$$
\begin{align*}
F _k =\sum\limits _{n=0} ^{N-1}x _n\cdot e ^{-i2\pi \frac{k}{N}n}
\end{align*}
$$

Given a certain $k$, $ e ^{-i2\pi \frac{k}{N}n}$ could be treated as a signal in a certain frequency ($k/N$). Then, $\sum\limits _{n=0} ^{N-1}x _n\cdot e ^{-i2\pi \frac{k}{N}n}$ could be treated as calculating the similarity of a signal sequence $\{x _0, x _1,\cdots, x _{N-1}\}$ and $\{e ^{-i2\pi \frac{k}{N}\cdot0}, e ^{-i2\pi \frac{k}{N}\cdot1},\cdots, e ^{-i2\pi \frac{k}{N}\cdot(N-1)}\}$. Hence, DFT could also be represented in a matrix form:

$$
[F _0, F _1, \cdots, F _{N-1}]=[x _0, x _1,\cdots, x _{N-1}]\cdot\begin{bmatrix}
k=0,& k=1,& \cdots,& k=N-1&\\
 \vdots,& \vdots,& \ddots,& \vdots&
\end{bmatrix}
$$

Fast Fourier Transform (FFT), a method to calculate DFT efficiently,  is based on the above formula.

If $k$ is expressed in Hz, each $k$ represents $\frac{kf _s}{N}$Hz. $\frac{f _s}{N}$ is the Frequency Resolution.

One-sided and Two-sided FFT

One-sided FFT (torch.fft.rfft) only considers positive frequency while two-sided FFT (torch.fft.fft) considers both positive and negative frequency. If $x$ is real numbers and $N$ is even, then $|F _k|$ is symmetric about $|F _{N/2}|$.

Hence:

  • if $N$ is even, one-sided FFT contain $N/2+1$ elements ($k=0,\cdots,N/2$) where $k=N/2$ is called Nyquist Frequency.
  • if $N$ is odd, one-sided FFT contain $\lfloor N/2\rfloor$ elements ($k=0,\cdots,\lfloor N/2 \rfloor$-1) because Nyquist Frequency is skipped.

Reference