Discrete Fourier Transform 📂Fourier Analysis

Discrete Fourier Transform

Buildup¹

Let’s assume that $f$ is some physical signal measured at specific intervals. Considering realistic conditions, there will be a moment when the measurement of the signal starts, $t=0$ , and a moment when the measurement ends, $t=\Omega$ . Thus, it can be assumed that the function value of $f$ is $0$ everywhere except for $[0, \Omega]$ .

Sampling Theorem
Let’s assume that $\hat{f} \in L^{2}$ and $f (t) = 0\ \text{for } t \in [0, 2\Omega]$ . Then, $\hat{f}(\omega)$ is determined by the values at $m\pi / \Omega (m=0, \pm 1, \pm 2, \dots)$ . That is, the following holds:
$\hat{f}(\omega) = \sum \limits_{m = -\infty}^{\infty} \hat{f} \left( \dfrac{m\pi}{\Omega}\right) \dfrac{\sin (\Omega \omega -m\pi )}{\Omega \omega - m\pi}$

Therefore, since the value of $f$ exists only in the interval $[0,\Omega]$ , which has a length of $\Omega$ , according to the sampling theorem, the value of $\hat{f}$ is determined by the discrete intervals of $\hat{f} \left( \dfrac{\pi m}{\Omega/2} \right) = \hat{f} \left( \dfrac{2\pi m}{\Omega} \right)$ . By calculating this value, according to the definition of Fourier Transform, it is as follows.

$\hat{f} \left( \dfrac{2\pi m}{\Omega} \right) = \int_{-\infty}^{\infty} f(x)e^{-i(2\pi m/ \Omega)x}dx = \int_{0}^{\Omega} f(x)e^{-i(2\pi m/ \Omega)x}dx$

Now, let’s think about dividing $[0, \Omega]$ into $N$ intervals. Then, the left endpoints of the divided intervals are as follows.

$0, \dfrac{1\Omega}{N}, \dfrac{2\Omega}{N}, \dots, \dfrac{n\Omega}{N}, \dots, \dfrac{(N-1)\Omega}{N}$

Considering the method of trapezoids, multiplying the function value at the points above by the length of each interval $\dfrac{\Omega}{N}$ and summing it all together, it can be understood that it will be similar to the integral value.

$\hat{f} \left( \dfrac{2\pi m}{\Omega} \right) = \int_{0}^{\Omega} f(x)e^{-i(2\pi m/ \Omega)x}dx \approx \sum_{n=0}^{N-1}e^{-i2\pi mn /N}f \left( \dfrac{n\Omega}{N} \right)\dfrac{\Omega}{N}$

If we say that $a_{n} = f(n\Omega/N)$ ,

$\dfrac{N}{\Omega}\hat{f} \left( \dfrac{2\pi m}{\Omega} \right) \approx \sum_{n=0}^{N-1}e^{-i2\pi mn /N} a_{n}$

Now, if we say that $\hat{a}_{m}=\sum_{n=0}^{N-1}e^{-i2\pi mn /N} a_{n}$ ,

$\dfrac{N}{\Omega}\hat{f} \left( \dfrac{2\pi m}{\Omega} \right) \approx \hat{a}_{m}$

Here, since $e^{-2\pi i n}=1$ ,

$e^{-2\pi i (m+N)n / N}=e^{-2\pi imn / N}e^{-2\pi in}=e^{-2\pi imn / N}$

It holds, and $\hat{a}_{m}$ has a period of $N$ .

$\hat{a}_{m+N}=\hat{a}_{m}$

Now, naturally, we can think about mapping from a $N$ -dimensional vector $\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1}) \in \mathbb{C}^{N}$ to a $N$ -dimensional vector $\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N}$ . Let’s define the $N$ -point discrete Fourier transform as follows.

Definition

The linear transformation $\mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N}$ defined as follows is called the discrete Fourier transform.

$\mathcal{F}_{N}(\mathbf{a}) = \hat{\mathbf{a}},\quad \hat{a}_{m}=\sum_{n=0}^{N-1}e^{-i2\pi mn /N} a_{n}\quad (0\le m < N)$

In this case, $\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1})$ and $\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N}$ .

Explanation

In signal processing, which often deals with discrete signals, time domain signals are commonly denoted by $x$ , and frequency domain signals by $X$ .

$x[n] = x_{n} = \sum \limits_{k=0}^{N-1}X[k]$