이산 푸리에 변환

이산 푸리에 변환

discrete fourier transform

빌드업1

$f$가 특정한 간격마다 측정되는 어떤 물리적인 신호라고 하자. 그러면 현실적인 조건을 생각해봤을 때, 신호가 측정되기 시작하는 순간 $t=0$와 측정이 끝나는 순간 $t=\Omega$가 존재할테니 $f$의 함숫값은 $[0, \Omega]$를 제외한 곳에서 모두 $0$이라 가정할 수 있다.

주파수 샘플링 정리

$\hat{f} \in L^{2}$이고 $f (t) = 0\ \text{for } t \in [0, 2\Omega]$라고 가정하자. 그러면 $\hat{f}(\omega)$는 $m\pi / \Omega(m=0, \pm 1, \pm 2, \dots)$에서의 값들로 결정된다. 즉 다음이 성립한다.

$$ \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} $$

그러면 $f$의 값이 길이가 $\Omega$인 구간 $[0,\Omega]$에만 존재하므로, 샘플링 정리에 의해서 $\hat{f}$의 값은 이산 간격의 $\hat{f} \left( \dfrac{\pi m}{\Omega/2} \right) = \hat{f} \left( \dfrac{2\pi m}{\Omega} \right)$들에 의해 결정된다는 것을 알 수 있다. 따라서 이를 계산해보면, 푸리에 변환의 정의에 의해서 다음과 같다.

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

여기서 $[0, \Omega]$를 $N$개의 구간들로 쪼갠다고 생각해보자. 그러면 쪼갠 구간의 왼쪽 끝점들은 다음과 같다.

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

구분구적법을 생각해보면 위의 점들에서의 함숫값과 각 구간의 길이 $\dfrac{\Omega}{N}$를 곱해서 모두 더하면 적분값과 비슷할거라는 것을 알 수 있다.

$$ \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} $$

여기서 $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} $$

이제 $\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} $$

여기서 $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} $$

가 성립하고 $\hat{a}_{m}$은 $N$의 주기를 갖는다.

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

따라서 $N$차원 벡터 $\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1}) \in \mathbb{C}^{N}$으로부터 $N$차원 벡터 $\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N}$가 매핑된다는 것을 알 수 있다. 이를 바탕으로 $N$-포인트 이산 푸리에 변환discrete Fourier transform, DFT을 다음과 같이 정의하자.

정의

다음과 같이 정의되는 선형변환 $\mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N}$을 이산 푸리에 변환이라 한다.

$$ \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) $$

이때 $\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1})$, $\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1})$이다.

같이보기


  1. Gerald B. Folland, Fourier Analysis and Its Applications (1992), p249-251 ↩︎

댓글