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] $$